Tipo: Conjunto de valores que uma variável pode assumir. Tipo de dados abstrato (ADT): Modelo matemático com operações. Estrutura de dados: Coleção de variáveis, implementação de um ADT. Lista linear: é uma sequência de n >= 0 nós, a1, a2, ..., an, todos de um mesmo tipo. O número de elementos da lista (n) é o comprimento da lista. Observe que existe uma ordenação implícita: se n > 0 temos que: a1 é o primeiro nó da lista. an é o último nó da lista. se 1 < k < n ak é precedido por a(k-1) e seguido por a(k+1). se n = 0 dizemos que a lista é vazia. Existem duas formas de se representar uma lista no computador - Alocação Sequencial: Os nós de uma lista ocupam posições contíguas ou igualmente distanciadas. (Vetor). - Alocação Ligada: A contiguidade dos nós é lógica. Ex.: __________________________ |a1|a2|_____..._________|an| Alocação Sequencial _____ _____ _____ |a1|__|--->|a2|__|---> ... --->|an|__|--->(Nada) Alocação Ligada Operações básicas sobre listas lineares: - Insere(x, p, L): insere x na posição p da lista L, movendo os elementos nas posições a partir de p, para a próxima posição. Isto é, se L := a1, a2, ... , an , após a inserção temos L := a1, a2, ... , a(p-1), x, ap, ... , an. Se na lista L não existe a posição p o resultado é indefinido; - Localiza(x, L): retorna a posição da primeira ocorrência do elemento x na lista L. Se x não pertence a L então retorna -1; - Acessa(p, L): retorna o elemento na posição p da lista L. Caso L não contenha o elemento p, o resultado é indefinido. - Proximo(p, L): Devolve a posição seguinte a p na lista. Se p é a última posição da lista, devolve FIM. Caso L não contenha o elemento p, o resultado é indefinido. - Remove(p, L): remove o elemento p da lista. Isto é, se L := a1, a2, ... , an , após a remoção temos L := a1, a2, ... , a(p-1), a(p+1), ... , an; - Vazia(L): retorna 1 (equivalente a true, em C) se a lista L está vazia, 0 caso contrário. - Conta(L): retorna o número de elementos de L. - Primeiro(L): retorna o primeiro elemento da lista L. - Imprime(L): imprime em ordem os elementos de L. - Limpa(L): faz com que a lista L seja uma lista vazia (n = 0) Outras operações possíveis: - Combinar duas ou mais listas, segundo algum critério; - Quebrar uma lista em duas ou mais listas, também usando algum critério; - Ordenar os nós de uma lista, de acordo com os conteúdos de alguns de seus campos. Exemplo: eliminar duplicatas de uma lista com as operações acima. p = Primeiro(L); Enquanto p != FIM q = Proximo(p, L); Enquanto q != FIM Se Acessa(p, L) == Acessa(q, L) Remove(q, L); senão q = Proximo(q, L); p = Proximo(p, L); Implementação em vetor: Fácil de percorrer e acessar, mas difícil de inserir e remover. #define MAX ... // valor inteiro que corresponde ao tamanho // maximo do vetor typedef ... TipoDoElemento; typedef struct _Lista { int fim; /* fim = -1, quando a lista está vazia*/ TipoDoElemento elementos[MAX]; } Lista; int vazia(Lista *L) { return(L->fim == -1); } TipoDoElemento Acessa(p, *L) { if (p < L->fim) return(L->elementos[p]); } Listas Lineares com disciplina de acesso. Listas Lineares em que as inserções, as remoções e os acessos em geral são feitos no primeiro e/ou no último nó. (1) Pilha (Stack): É uma lista linear em que todas as inserções, as remoções e os acessos em geral são feitos numa só extremidade chamada topo. remoções | V |_| <- fim (topo) <- inserções Inserir = Empilhar ("Push Down") |_| Remover = Desempilhar ("Pop Up") |_| |_| <- inicio (base) A pilha é uma estrutura do tipo LIFO (Last In First Out), ou último que foi inserido será o primeiro a ser removido. Exemplos da vida real: (a) Pilha de livros, pratos, etc....; (b) Estacionamento de trens. (2) Fila (Queue): É uma lista linear em que todas as inserções são feitas numa extremidade ("REAR") e todas as remoções e qualquer acesso em geral são feitos na outra extremidade ("FRONT"). ____________________ remoções -> |_|_|____________|_|_| <- inserções î î início (FRONT) fim (REAR) A fila é uma estrutura do tipo FIFO (First In First Out). Ex.: (a) Estacionamento de trens; (b) Sistemas de multiprogramação; (c) Fila de Banco. Pilhas: O tipo abstrato de dados pilha, normalmente possui as seguintes operações: - Empilha(p, S): insere o elemento p na pilha S. - Desempilha(p, S): remove o elemento do topo da pilha S e o devolve em p. - Vazia(S): retorna 1 se a pilha S está vazia, 0 caso contrário. - Limpa(S): faz com que a pilha S seja uma pilha vazia (topo = -1). Exemplo: Editor de texto. Processar uma linha, sendo que '#' indica que o caractere anterior deve ser apagado, e '@' que a linha toda deve ser apagada. Pilha linha, imprime; Leia ch; Enquanto ch != '\n' Se ch == '#' Desempilha(lixo,linha); senão se ch == '@' Limpa(linha); senão Empilha(ch, linha); Leia ch; Enquanto !Vazia(linha) Desempilha(ch, linha); Empilha(ch, imprime); Enquanto !Vazia(imprime) Desempilha(ch, imprime); Imprime ch; Representação da Pilha em C: #define MAX ... typedef ... TipoDoElemento; typedef struct _Pilha{ int topo; /* topo = -1, quando a pilha está vazia */ TipoDoElemento elementos[MAX]; } Pilha; /* Procedimento para inserir um elemento x na pilha S */ void Empilha(TipoDoElemento x, Pilha *S) { S->topo++; if( S->topo == MAX ) OVERFLOW(); /* a pilha já está cheia*/ else S->elementos[S->topo] = x; } /* Procedimento para remover um elemento na pilha S */ void Desempilha(TipoDoElemento *x, Pilha *S) { if( S->topo == -1 ) Underflow(); /* a pilha está vazia*/ else *x = S->elementos[S->topo--]; } O Underflow ocorre quando queremos remover um elemento inexistente. Em geral, não é uma condição de erro em um programa (pode até ser desejável). O Overflow ocorre quando queremos inserir um elemento em uma lista que já está completa.