implementacaoestseq 4

4. Implementação de Listas Lineares usando Alocação Estática e Acesso Sequencial

Como tratado anteriormente, a implementação de uma lista linear requer que seja feita uma escolha quanto ao tipo de alocação de memória e quanto ao tipo de acesso aos dados. Das quatro possibilidades apresentadas na Figura 2.2, apenas três serão abordadas neste curso: estática sequencial; estática encadeada; dinâmica encadeada.

Nesta seção trataremos da implementação de listas lineares usando alocação estática/sequencial, nas seções 4 e 5 trataremos das outra formas de alocação de memória e tipos de acesso. Aqui faremos a especificação do TDA para listas lineares não ordenadas e ordenadas. Estas mesmas especificações deverão ser utilizadas nas seções 4 e 5.

Uma lista estática sequencial pode ser implementada através de um vetor. Exemplos de listas estáticas/sequenciais: lista telefônica, lista de alunos, entre outras.

Características de Lista Estática/Sequencial: os elementos da lista estão armazenados fisicamente em posições consecutivas; a inserção de um elemento na posição a(i) causa o deslocamento a direita do elemento de a(i) ao último; eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último; Vantagens: acesso direto indexado a qualquer elemento da lista tempo constante para acessar o elemento i - dependerá somente do índice.

Desvantagem: movimentação quando eliminado/inserido elemento tamanho máximo pré-estimado

Quando usar: listas pequenas inserção/remoção no fim da lista tamanho máximo bem definido

4.1. Implementação do TDA lista_não_ordenada

a) estrutura da lista - cada elemento da lista chamaremos de nó

0 1 2 3 4 (MAX-1)

inicio da lista fim da lista fim do vetor (implícito) (explícito) (implícito)

define estrutura Lista como