Algoritmos e Estruturas de Dados IIIEC013

Revisão: Listas Revisão: Listas EncadeadasEncadeadas

Prof. César Melo

Todos os créditos reservados ao professor Leandro Galvão

Listas EncadeadasListas Encadeadas

Listas encadeadasListas encadeadas ou listas ligadas ou listas ligadas representam uma seqüência de objetos representam uma seqüência de objetos na memória do computador.na memória do computador.

Exemplo: Exemplo: Lista de afazeresLista de afazeres1.1. Comprar uma lâmpadaComprar uma lâmpada

2.2. Trocar uma lâmpada queimadaTrocar uma lâmpada queimada

3.3. Procurar uma conta no quartoProcurar uma conta no quarto

4.4. Pagar uma conta na internetPagar uma conta na internet

5.5. Desligar o computadorDesligar o computador

6.6. DormirDormir

Listas EncadeadasListas Encadeadas

PróximaaçãoAção atualAção atual

Na lista de afazeres anterior, uma tarefa Na lista de afazeres anterior, uma tarefa dependia da execução da tarefa anteriordependia da execução da tarefa anterior

Listas EncadeadasListas Encadeadas

21. 1. ComprarComprar lâmpadalâmpada

32. Trocar 2. Trocar lâmpadalâmpada

43. 3. ProcurarProcurar contaconta

54. Pagar 4. Pagar contaconta

65. 5. DesligarDesligar micromicro

fim6. Dormir6. Dormir

DormirDormirDesligar Desligar

micromicroPagar Pagar contaconta

Procurar Procurar contaconta

Trocar Trocar lâmpadalâmpada

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por vetoresvetores

Como representar a lista anterior em um Como representar a lista anterior em um programa escrito na Linguagem C?programa escrito na Linguagem C?

Primeira opção: vetores ou matrizesPrimeira opção: vetores ou matrizes

Comprar Comprar lâmpadalâmpada

Tarefa:

Índice: 1 2 3 4 5 6

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por vetoresvetores

Primeira opção: vetores ou matrizesPrimeira opção: vetores ou matrizes

Como acrescentar Como acrescentar “Ligar micro”“Ligar micro”??

DormirDormirDesligar Desligar

micromicroPagar Pagar contacontaLigar Ligar micromicro

Procurar Procurar contaconta

Trocar Trocar lâmpadalâmpada

Comprar Comprar lâmpadalâmpada

Tarefa:

Índice: 1 2 3 4 5 6 7

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por vetoresvetores

Primeira opção: vetores ou matrizesPrimeira opção: vetores ou matrizes Os itens da lista são armazenados em posições Os itens da lista são armazenados em posições

adjacentesadjacentes na memória. na memória.

A lista pode ser percorrida em qualquer direção.A lista pode ser percorrida em qualquer direção.

A inserção de um novo item pode ser realizada A inserção de um novo item pode ser realizada após o último item com custo constante.após o último item com custo constante.

A inserção de um novo item no A inserção de um novo item no meio da listameio da lista requer um requer um deslocamento de todos os itens deslocamento de todos os itens localizados após o ponto de inserção.localizados após o ponto de inserção.

Retirar um item do início da lista requer um Retirar um item do início da lista requer um deslocamento de itens para preencher o espaço deslocamento de itens para preencher o espaço deixado vazio.deixado vazio.

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por ponteirosponteiros

Segunda opção: ponteirosSegunda opção: ponteiros

Estruturas de dados dinâmicasEstruturas de dados dinâmicas: estruturas de : estruturas de dados que contém ponteiros para si próprias.dados que contém ponteiros para si próprias.

struct lista { char nome_tarefa[30];float duracao;char responsavel[30];...struct lista *prox;

};

struct lista { char nome_tarefa[30];float duracao;char responsavel[30];...struct lista *prox;

};

ponteiro para a própria estrutura lista

campos de informação

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por ponteirosponteiros

Representação gráfica de um elemento da lista:Representação gráfica de um elemento da lista:

Cada item é encadeado com o seguinte, mediante uma Cada item é encadeado com o seguinte, mediante uma variável do tipo variável do tipo ponteiroponteiro..

Permite utilizar Permite utilizar posições não adjacentes posições não adjacentes de memória.de memória.

É possível inserir e retirar elementos É possível inserir e retirar elementos sem necessidade sem necessidade de deslocar de deslocar os itens seguintes da lista.os itens seguintes da lista.

próximo nó

Listas EncadeadasListas Encadeadas:: Representação por :: Representação por ponteirosponteiros

Cada item em particular de uma lista pode ser Cada item em particular de uma lista pode ser chamado de chamado de elementoelemento, , nónó, , célulacélula, ou , ou itemitem..

O apontador para o início da lista também é O apontador para o início da lista também é tratado como se fosse uma célula (tratado como se fosse uma célula (cabeçacabeça), para ), para simplificar as operações sobre a lista.simplificar as operações sobre a lista.

O símbolo O símbolo // representa o ponteiro nulo ( representa o ponteiro nulo (NULLNULL), ), indicando o fim da lista.indicando o fim da lista.

3 5p

2 /4

162

Operações sobre lista encadeadaOperações sobre lista encadeada

Podemos realizar algumas operações Podemos realizar algumas operações sobre uma lista encadeadas, tais como:sobre uma lista encadeadas, tais como: InserirInserir itens; itens;RetirarRetirar itens; itens;Buscar Buscar itens.itens.

Para manter a lista ordenada, após Para manter a lista ordenada, após realizar alguma dessas operações, será realizar alguma dessas operações, será necessário apenas necessário apenas movimentar alguns movimentar alguns ponteiros ponteiros (de um a três elementos).(de um a três elementos).

Operações sobre lista encadeadaOperações sobre lista encadeada

Outras operações possíveis:Outras operações possíveis:CriarCriar uma lista uma listaDestruirDestruir uma lista uma listaOrdenarOrdenar uma lista uma listaIntercalarIntercalar duas listas duas listasConcatenarConcatenar duas listas duas listasDividirDividir uma lista em duas uma lista em duasCopiarCopiar uma lista em outra uma lista em outra

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: InserçãoInserção de itens de itens

Podemos inserir itens:Podemos inserir itens:NoNo começo começo de uma listade uma listaNo No final final de uma listade uma listaNoNo meio meio de uma listade uma lista

p 5 2 /4

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: InserçãoInserção de itens no de itens no inícioinício

O endereço armazenado no ponteiro O endereço armazenado no ponteiro p p deve ser alterado para o endereço do item deve ser alterado para o endereço do item a ser acrescido à lista.a ser acrescido à lista.

163

3

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: InserçãoInserção de itens no de itens no finalfinal

O endereço armazenado em O endereço armazenado em pp será será alterado caso a lista esteja vazia oualterado caso a lista esteja vazia ou

O campo O campo proxprox do último item será do último item será alterado.alterado.

/3p

/

3 /5p

164

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: InserçãoInserção de itens no de itens no meiomeio

Campo Campo proxprox do item a ser inserido recebe do item a ser inserido recebe o campo o campo proxprox do item posterior do item posterior

Campo Campo proxprox do item antecessor recebe o do item antecessor recebe o endereço do item a ser inseridoendereço do item a ser inserido

165

2 /4

5

3p

lista[5].prox ← lista[2]

lista[3].prox ← 5

lista[5].prox ← lista[2]

lista[3].prox ← 5

p 5 2 /4

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: RemoçãoRemoção de itens no de itens no inícioinício

O endereço armazenado no ponteiro O endereço armazenado no ponteiro p p deve ser alterado para o endereço do item deve ser alterado para o endereço do item que segue o primeiro item da lista.que segue o primeiro item da lista.

166

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: RemoçãoRemoção de itens no de itens no finalfinal

O campo O campo proxprox do último item será do último item será alterado caso a lista contenha mais de um alterado caso a lista contenha mais de um item ouitem ou

O endereço armazenado em O endereço armazenado em pp será será alterado para alterado para NULLNULL..

/3p

/

3 /5p

167

Operações sobre lista encadeadaOperações sobre lista encadeada:: :: RemoçãoRemoção de itens no de itens no meiomeio

Item antecessor recebe o campo Item antecessor recebe o campo proxprox do do item a ser removidoitem a ser removido

168

5 2 /43p

lista[3].prox ← lista[5].prox

lista[3].prox ← lista[5].prox

Outros tipos de Listas EncadeadasOutros tipos de Listas Encadeadas

Existem ainda outras variações de lista Existem ainda outras variações de lista encadeada, dentre elas:encadeada, dentre elas:

Listas Listas Duplamente EncadeadasDuplamente Encadeadas

Listas Listas CircularesCirculares

Listas Duplamente EncadeadasListas Duplamente Encadeadas

Cada elemento da lista é ligado a seu Cada elemento da lista é ligado a seu sucessor e a seu predecessor.sucessor e a seu predecessor.

Possibilita um trajeto em ambos os Possibilita um trajeto em ambos os sentidos, simplificando o gerenciamento sentidos, simplificando o gerenciamento da lista.da lista.

Listas Duplamente EncadeadasListas Duplamente Encadeadas

typedef struct elemento TElemento;struct elemento {

int nro;TElemento *ant;TElemento *prox;

};

typedef struct elemento TElemento;struct elemento {

int nro;TElemento *ant;TElemento *prox;

};

A estrutura de dados de um nó de uma A estrutura de dados de um nó de uma lista duplamente encadeada recebe um lista duplamente encadeada recebe um novo campo: um novo campo: um ponteiro para o nó ponteiro para o nó antecessorantecessor..

170

Listas Duplamente EncadeadasListas Duplamente Encadeadas

Vantagens:

Facilitar as operações de manuseio dos Facilitar as operações de manuseio dos elementos da lista;elementos da lista;

Caminhar em ambas as direçõesCaminhar em ambas as direções

Desvantagem:Desvantagem:

Espaço a mais para armazenar um outro Espaço a mais para armazenar um outro ponteiro;ponteiro;

Considere as operações de inserção, Considere as operações de inserção, inserção ordenada, e remoção;inserção ordenada, e remoção;

170

Listas CircularesListas Circulares

São listas encadeadas cujo fim aponta São listas encadeadas cujo fim aponta para o seu início, formando um círculo que para o seu início, formando um círculo que permite uma trajetória contínua na lista. permite uma trajetória contínua na lista. Podem ser:Podem ser:

Singularmente encadeadasSingularmente encadeadas

Duplamente encadeadasDuplamente encadeadas

Listas CircularesListas Circulares

A estrutura de um nó de uma lista circular A estrutura de um nó de uma lista circular permanece a mesma. Dependerá apenas permanece a mesma. Dependerá apenas se o encadeamento da lista é duplo ou se o encadeamento da lista é duplo ou singular.singular.

O que modifica é que O que modifica é que não há mais não há mais necessidade de dois ponteiros para indicar necessidade de dois ponteiros para indicar o início e o fim da listao início e o fim da lista..

Basta marcar um nó da lista para evitar Basta marcar um nó da lista para evitar loops.loops.

171

ExercícioExercício

Considere o seguinte problema que deve Considere o seguinte problema que deve ser implementado em uma lista ser implementado em uma lista simplesmente encadeada;simplesmente encadeada;

Uma sequência de números Deve ser Uma sequência de números Deve ser armazenada em uma lista;armazenada em uma lista;

Pede-se que os elementos dessa lista sejam Pede-se que os elementos dessa lista sejam impressos na ordem inversa com que estão impressos na ordem inversa com que estão encadeado na lista;encadeado na lista;

Ao examinar a sua implementação, busque no Ao examinar a sua implementação, busque no seu dia-a-dia, algo que se assemelhe à seu dia-a-dia, algo que se assemelhe à dinâmica de inclusão dos elementos na lista.dinâmica de inclusão dos elementos na lista.

171

QuestõesQuestões