Tonlisboa

Estrutura de Dados, Pesquisa e Ordenação (EPO)
Listas Lineares

Pablo Dalbem

Lista
Lista é um TAD que contém uma sequência de zero ou mais elementos. Em uma lista, a inserção e remoção de elementos podem ocorrer em qualquer posição. Importante: Não pode haver espaços entre os elementos da lista!

Lista
Operações em listas:

Inserir -> insere um elemento em qualquer posição da lista; Remover -> remove um elemento em qualquer posição da lista. Mostrar -> mostra todos os elementos que estão na lista.

Implementação
Existem 2 principais estruturas de dados para implementar o TAD Lista.

1) Estrutura estática, por meio de vetores. 2) Estrutura dinâmica, por meio de ponteiros.

Veremos, primeiramente, a implementação por meio de vetores.

Implementação
A estrutura da nossa Lista é composta por:

-Um vetor de caracteres, chamado item; -Uma variável chamada ini, para indicar o início da lista; -Uma variável chamada fim, para indicar o final da lista.

A variável fim aponta sempre para a próxima posição livre da lista, onde poderá ser inserido um elemento!!

Implementação
A estrutura utilizada:

Item: ini: fim: 0 0

0

1

2

3

4

Quando as variáveis ini e fim apontam para a mesma posição (zero), significa que a lista está vazia.

Implementação
Inserção de um item:
A Item: ini: fim: 0 1
0 1 2 3 4

O elemento ‘A’ foi inserido na lista. Como a lista estava vazia, ‘A’ é o primeiro elemento. A variável fim precisa ser incrementada para indicar onde é o final da lista agora.

Implementação
Inserção de mais um item: em qual posição inserir?
A Item: ini: fim: 0 2
0

B
1 2 3 4

Ao querer inserir o elemento ‘B’, o programa deve perguntar em qual posição o usuário deseja inserí-lo. No exemplo, foi escolhida a posição 1.

Implementação
Inserção de mais um item: em qual posição inserir?
C Item: ini: fim: 0 3
0

A
1

B
2 3 4

Ao inserir o elemento ‘C’, o usuário escolheu a posição 0 (zero).