Estruturas de Dados - Listas Encadeadas, Pilhas e Filas

Prévia do material em texto

Estruturas de Dados - T.332
Capítulo 4 - II
Listas Encadeadas
4.2 Filas e Listas Duplamente Encadeadas
4.3 Listas Circulares
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
1
‹nº›
4.2 Extensões do Conceito de Lista Encadeada
A idéia da Lista Encadeada como foi vista até agora é o modelo mais geral e simples.
Pode ser especializada e extendida das mais variadas formas:
Especializada:
Pilhas encadeadas
Filas
Extendida:
Listas Duplamente Encadeadas
Listas Circulares Simples e Duplas
3
altura
topo
melão
info
próximo
maçã
info
próximo
uva
info
próximo
Pilha Encadeada
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.1 Pilhas Encadeadas
São pilhas onde os elementos são encadeados.
Não há estouro de pilha. 
Como o acesso de dados na pilha é puramente seqüencial, não há perda de eficiência.
Somente duas operações existem:
Empilhar: equivale a adicionar no início
Desempilhar: equivale a retirar do início.
É a forma como tradicionalmente pilhas são implementadas.
3
altura
topo
melão
info
próximo
maçã
info
próximo
uva
info
próximo
Pilha Encadeada
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas
A Fila é uma estrutura de dados que simula uma fila da vida real.
Possui duas operações básicas: 
Incluir no fim da fila
Retirar do começo da fila.
Chamada de Estrutura-FIFO: 
First-In, First-Out - O primeiro que entrou é o primeiro a sair..
Fila
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas
É uma estrutura de dados improtantíssima para:
Gerência de dados/processos por ordem cronológica:
Fila de impressão em uma impressora de rede 
Fila de pedidos de uma expedição ou tele-entrega.
Simulação de processos seqüenciais:
Chão de fábrica: fila de camisetas a serem estampadas.
Comércio: simulação de fluxo de um caixa de supermercado.
Tráfego: simulação de um cruzamento com um semáforo.
Fila
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas
É uma estrutura de dados improtantíssima para:
Gerência de dados/processos por ordem cronológica:
Fila de impressão em uma impressora de rede 
Fila de pedidos de uma expedição ou tele-entrega.
Simulação de processos seqüenciais:
Chão de fábrica: fila de camisetas a serem estampadas.
Comércio: simulação de fluxo de um caixa de supermercado.
Tráfego: simulação de um cruzamento com um semáforo.
Fila
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas
É uma estrutura de dados improtantíssima para:
Gerência de dados/processos por ordem cronológica:
Fila de impressão em uma impressora de rede 
Fila de pedidos de uma expedição ou tele-entrega.
Simulação de processos seqüenciais:
Chão de fábrica: fila de camisetas a serem estampadas.
Comércio: simulação de fluxo de um caixa de supermercado.
Tráfego: simulação de um cruzamento com um semáforo.
Fila
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas
É uma estrutura de dados improtantíssima para:
Gerência de dados/processos por ordem cronológica:
Fila de impressão em uma impressora de rede 
Fila de pedidos de uma expedição ou tele-entrega.
Simulação de processos seqüenciais:
Chão de fábrica: fila de camisetas a serem estampadas.
Comércio: simulação de fluxo de um caixa de supermercado.
Tráfego: simulação de um cruzamento com um semáforo.
Fila
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2 Filas: Representação
Extensão da lista encadeada
Referenciamos o último elemento também.
Adicionamos no fim
Excluímos do início
3
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
Fila
Elemento de Fila
Pseudo-código:
tipo Fila {
 Elemento *inicio;
 Elemento *fim;
 inteiro tamanho;
};
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo CriaFila
Fila* FUNÇÃO criaFila()
	“Retorna ponteiro para uma nova cabeça de fila ou NULO“
	variáveis
		 Fila 	*aFila;
	início
		aFila <- aloque(Fila );
		SE (aFila ~= NULO) ENTÃO
			“So posso inicializar se consegui alocar”
			aFila->tamanho <- 0;
			aFila->início <- nulo;
			aFila->fim <- nulo;
		FIM SE
		RETORNE(aFila);
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila)
2
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila)
2
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila)
3
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila) 
Caso especial: Fila Vazia
0
tam.
inicio fim
uva
info
próximo
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila) 
Caso especial: Fila Vazia
1
tam.
inicio fim
uva
info
próximo
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Adiciona (Fila) 
Inteiro FUNÇÃO adiciona (	Fila *aFila, TipoInfo *dado )
	variáveis
	 	Elemento *novo; “Var. auxiliar para o novo elemento”
	início
		novo <- aloque(Elemento);
		SE (novo = NULO) ENTÃO
		 RETORNE( ErroListaCheia );
		SENÃO
		 SE filaVazia(aFila) ENTÃO
			aFila->inicio <- novo;
		 SENÃO
			aFila->fim->proximo <- novo;
		 FIM SE
		 novo->proximo <- NULO;
		 novo->info <- dado;
	 	 aFila->fim <- novo;
		 aFila->tamanho <- aFila->tamanho + 1;
	 	 RETORNE(aFila->tamanho);
 	 	FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
3
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
 sai
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
3
melão
info
próximo
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
 sai
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
2
maçã
info
próximo
uva
info
próximo
tam.
inicio fim
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
Caso especial: Fila Unitária
1
uva
info
próximo
tam.
inicio fim
Não preciso de uma variável auxiliar sai
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
Caso especial: Fila Unitária
0
tam.
inicio fim
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo Retira (Fila)
TipoInfo* FUNÇÃO retiraDoInício( Fila *aFila )
	“Elimina o 1. Elemento de uma fila.
	 Retorna a informação do elemento eliminado ou NULO.”
	variáveis
	 	Elemento *saiu; “Var. auxiliar para o 1. elemento”
		TipoInfo *volta; “Var. auxiliar para o dado retornado”
	início
		SE (filaVazia(aFila)) ENTÃO
		 RETORNE( NULO );
		SENÃO
		 saiu<- aFila->início;
		 volta <- saiu->info;
		 aFila->início <- saiu->proximo; 
		 “Se SAIU for o único, próximo é nulo e está certo.”
		 SE (aFila->tamanho = 1) ENTÃO
			“Fila unitária: devo anular o fim também.”
			aFila->fim <- NULO;
		 FIM SE
		 aFila->tamanho <- aFila->tamanho - 1;
		 LIBERE(saiu);
		 RETORNE(volta);
		FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.2.1 Exercício com Filas
Implemente o TAD Fila com as suas duas operações de manipulação.
Implemente um programa principal de aplicação que utilize uma fila para:
Ler dados de pedidos de solicitação de conserto de computadores da marca HAL pela sua assistencia técnica AssistHAL.
Utilize o seguinte TipoInfo: Nome do Solicitante, Telefone, Data da Entrega (inserida automaticamente), Modelo do Computador e Valor do Conserto, que é um valor chutado.
Após cadastrado um pedido, o sistema deverá informar quando o solicitante poderá contar com o computador pronto, sendo que:
A oficina AssistHAL leva em média duas semanas por pedido.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.3 Listas Duplamente Encadeadas
A Lista Encadeada e a Fila possuem a desvantagem de somente podermos caminhar em uma direção. 
Vimos que para olhar um elemento que “acabamos de passar” precisamos de uma variável auxiliar “anterior”.
Para olhar outros elementos ainda anteriores não temos nenhum meio, a não ser começar de novo.
A Lista Duplamente Encadeada é uma estrutura de lista que permite deslocamento em ambos os sentidos:
Útil para representar conjuntos de eventos ou objetos a serem percorridos em dois sentidos.
Ex.: Itinerários de ônibus, trem ou avião.
Útil também quando realizamos uma busca aproximada e nos movemos para e frente e trás.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.3 Listas Duplamente Encadeadas: Modelagem
3
tam.
dados
melão
doce
caro
maçã
azeda
cara
uva
irkh
barata
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.3 Modelagem: Cabeça de ListaDupla
Necessitamos:
Um ponteiro para o primeiro elemento da lista.
Um inteiro para indicar quantos elementos a lista possue.
Pseudo-código:
	
tipo ListaDupla {
	ElementoDuplo	*dados;
	inteiro 	tamanho;
};
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.3 Modelagem: Elemento de Lista Dupla
Necessitamos:
Um ponteiro para o elemento anterior na lista.
Um ponteiro para o elemento sucessor na lista.
Um ponteiro para a informação que vamos armazenar. 
Pseudo-código:
	
tipo ElementoDuplo {
	ElementoDuplo 	*anterior;
	ElementoDuplo 	*sucessor;
	TipoInfo 	*info;
};
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.4 Modelagem da Lista Duplamente Encadeada
Aspecto Funcional:
Colocar e retirar dados da lista.
Testar se a lista está vazia e outros testes.
Inicializa-la e garantir a ordem dos elementos.
3
tam.
dados
melão
doce
caro
maçã
azeda
cara
uva
irkh
barata
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Modelagem da Lista Duplamente Encadeada
Operações: Colocar e retirar dados da lista:
AdicionaDuplo(listaDupla, dado)
AdicionaNoInícioDuplo(listaDupla, dado)
AdicionaNaPosiçãoDuplo(listaDupla, dado, posição)
AdicionaEmOrdemDuplo(listaDupla, dado)
RetiraDuplo(listaDupla)
RetiraDoInícioDuplo(listaDupla)
RetiraDaPosiçãoDuplo(listaDupla, posição)
RetiraEspecíficoDuplo(listaDupla, dado)
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Modelagem da Lista Duplamente Encadeada
Operações: Testar a lista e outros testes:
ListaVaziaDuplo(listaDupla)
PosicaoDuplo(listaDupla, dado)
ContemDuplo(listaDupla, dado)
Operações: Inicializar ou limpar:
CriaListaDupla()
DestroiListaDupla(listaDupla)
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo CriaListaDupla
ListaDupla* FUNÇÃO criaListaDupla()
	“Retorna ponteiro para uma nova cabeça de lista ou NULO“
	variáveis
		ListaDupla	*aLista;
	início
		aLista <- aloque(ListaDupla);
		SE (aLista ~= NULO) ENTÃO
			“So posso inicializar se consegui alocar”
			aLista->tamanho <- 0;
			aLista->dados <- nulo;
		FIM SE
		RETORNE(aLista);
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo ListaVaziaDuplo
Booleano FUNÇÃO listaVaziaDuplo(ListaDupla *aLista)
	início
		SE (aLista->tamanho = 0) ENTÃO
			RETORNE(Verdade)
		SENÃO
			RETORNE(Falso);
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNoInícioDuplo
Procedimento:
Testamos se é possível alocar um elemento.
Fazemos o sucessor deste novo elemento ser o primeiro da lista.
Fazemos o seu antecessor ser NULO.
Fazemos a cabeça de lista apontar para o novo.
Parâmetros:
O tipo info (dado) a ser inserido.
ListaDupla.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNoInícioDuplo
novo
2
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNoInícioDuplo
novo
2
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
Caso novo->suc não seja nulo...
Faço novo->suc->ant ser novo...
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNoInícioDuplo
novo
3
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNoInícioDuplo
Inteiro FUNÇÃO adicionaNoInícioDuplo(	ListaDupla *aLista, 
							TipoInfo *dado )
	variáveis
	 	ElementoDuplo *novo; “Var. auxiliar para o novo elemento”
	início
		novo <- aloque(ElementoDuplo);
		SE (novo = NULO) ENTÃO
		 RETORNE( ErroListaCheia );
		SENÃO
		 novo->suc <- aLista->dados;
		 novo->ant <- NULO;
		 novo->info <- dado;
	 	 aLista->dados <- novo;
		 SE (novo->suc ~= NULO) ENTÃO
			novo->suc->ant <- novo;
		 FIM SE;
		 aLista->tamanho <- aLista->tamanho + 1;
	 	 RETORNE(1);
 	 	FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
Procedimento:
Testamos se há elementos.
Decrementamos o tamanho.
Se o elemento possuir sucessor, o antecessor do sucessor será NULO.
Liberamos a memória do elemento.
Devolvemos a Informação.
Parâmetros:
ListaDupla.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
saiu
volta
3
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
saiu
volta
2
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - DisciplinaEstruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
saiu
volta
2
tam.
dados
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
ant
info suc
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
2
tam.
dados
maçã
azeda
cara
uva
irkh
barata
ant
info suc
ant
info suc
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDoInícioDuplo
TipoInfo* FUNÇÃO retiraDoInício( ListaDupla *aLista )
	“Elimina o 1. Elemento de uma lista duplamente encadeada.
	 Retorna a informação do elemento eliminado ou NULO.”
	variáveis
	 	ElementoDuplo *saiu; “Var. auxiliar para o 1. elemento”
		TipoInfo *volta; “Var. auxiliar para o dado retornado”
	início
		SE (listaVaziaDuplo(aLista)) ENTÃO
		 RETORNE( NULO );
		SENÃO
		 saiu <- aLista->dados;
		 volta <- saiu->info;
		 aLista->dados <- saiu->suc;
		 SE (aLista->dados ~= NULO) ENTÃO
			aLista->dados->ant <- NULO;
		 FIM SE
		 aLista->tamanho <- aLista->tamanho - 1;
		 LIBERE(saiu);
		 RETORNE(volta);
		FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNaPosiçãoDuplo
Praticamente idêntico à lista encadeada.
Procedimento:
Testamos se a posição existe e se é possível alocar elemento.
Caminhamos até a posição.
Adicionamos o novo dado na posição. 
Incrementamos o tamanho.
Parâmetros:
O dado a ser inserido.
A posição onde inserir.
Lista.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaNaPosição
 Inteiro FUNÇÃO adicionaNaPosiçãoDuplo( ListaDupla *aLista, TipoInfo *info, 
					 inteiro posição )
	“Adiciona novo elemento na posição dada.
	 Retorna a novo numero de elementos da lista ou erro.”
	variáveis
	 ElementoDuplo *novo, *anterior; “Ponteiros auxiliares”
	início
	 SE (posição > aLista->tamanho + 1) ENTÃO
		RETORNE( ErroPosição )
	 SENÃO
		SE (posição = 1) ENTÃO
		 RETORNE(adicionaNoInícioDuplo(aLista, info);
		SENÃO
		 novo <- aloque(Elemento);
		 SE (novo = NULO) ENTÃO
		 RETORNE( ErroListaCheia );
		 SENÃO
		 anterior <- aLista->dados;
		 REPITA (posição - 2) VEZES
			anterior <- anterior->suc;
		 novo->suc <- anterior->suc;
		 SE (novo->suc ~= NULO ENTÃO “SE o novo não é o último da lista”
		 novo->suc->ant <- novo; “Seto o antecessor do sucessor do novo”
		 FIM SE
		 novo->info <- info;
		 anterior->suc <- novo;
		 novo->ant <- anterior;
		 aLista->tamanho <- aLista->tamanho + 1;
		 RETORNE(aLista->tamanho);
		 FIM SE
	 FIM SE
	 FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosiçãoDuplo
Mais simples que a Lista Encadeada.
Procedimento:
Testamos se a posição existe.
Caminhamos até a posição.
Retiramos o dado da posição. 
Decrementamos o tamanho.
Parâmetros:
A posição de onde retirar.
Lista.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosiçãoDuplo
4
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
jaca
irkh
barata
eliminar
Posições > 1
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosição
Posições > 1
4
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
jaca
irkh
barata
eliminar
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosição
Posições > 1
3
maçã
azeda
cara
uva
irkh
barata
melão
doce
caro
jaca
irkh
barata
eliminar
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosição
Posições > 1
3
maçã
azeda
cara
melão
doce
caro
jaca
irkh
barata
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo RetiraDaPosição
TipoInfo* FUNÇÃO retiraDaPosição( Lista *aLista, inteiro posição )
	“Elimina o Elemento na posição posição de uma lista.
	 Retorna a informação do elemento eliminado ou NULO.”
	variáveis
	 	Elemento *anterior, *eliminar; “Var. auxiliar para elemento”
		TipoInfo *volta; “Var. auxiliar para o dado retornado”
	início
	 SE (posição > aLista->tamanho) ENTÃO
		RETORNE( NULO );
	 SENÃO
		SE (posição = 1) ENTÃO
		 RETORNE( retiraDoInício(aLista) );
		SENÃO
		 anterior <- aLista->dados;
		 REPITA (posição - 2) VEZES
			anterior <- anterior->proximo;
		 eliminar <- anterior->proximo;
		 volta <- eliminar->info;
		 anterior->proximo <- eliminar->proximo;
		 aLista->tamanho <- aLista->tamanho - 1;
		 LIBERE(eliminar);
		 RETORNE(volta);
		FIM SE
	 FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaEmOrdemDuplo
Idêntico à lista encadeada.
Procedimento:
Necessitamos de uma função para comparar os dados (maior)
Procuramos pela posição onde inserir comparando dados.
Chamamos adicionaNaPosiçãoDuplo.
Parâmetros:
O dado a ser inserido.
ListaDupla.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo AdicionaEmOrdemDuplo
Inteiro FUNÇÃO adicionaEmOrdem(ListaDupla *aLista, TipoInfo dado)
	variáveis
	 ElementoDuplo *atual;	“Variável auxiliar para caminhar”
	 inteiro 	 posição;
	início
	 SE (listaVaziaDupla(aLista)) ENTÃO
	 RETORNE(adicionaNoInícioDuplo(aLista, dado));
	 SENÃO
	 atual <- aLista->dados;
	 posição <- 1;
	 ENQUANTO (atual->sucessor ~= NULO E
			 maior(dado, atual->info)) FAÇA 
		 “Encontrar posição para inserir”	
		 atual <- atual->sucessor;
		 posição <- posição + 1;
		FIM ENQUANTO
		SE maior(dado, atual->info) ENTÃO “Parou porque acabou lista”
	 RETORNE(adicionaNaPosiçãoDuplo(aLista,dado,posição + 1));
		SENÃO
	 RETORNE(adicionaNaPosiçãoDuplo(aLista, dado, posição));
		FIM SE
 	 FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmos Restantes: Lista Duplamente Encadeada
Por conta do Aluno:
Operações de inclusão e exclusão:
AdicionaDuplo(listaDupla, dado)
RetiraDuplo(listaDupla)
RetiraEspecíficoDuplo(listaDupla, dado)
Operações: Inicializar ou limpar:
DestroiListaDupla(listaDupla)
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
Algoritmo DestroiListaDupla
FUNÇÃO destroiListaDupla(ListaDupla *aLista)
	variáveis
	 ElementoDuplo *atual, *anterior; “Variável auxiliar para caminhar”
	início
	 SE (listaVaziaDupla(aLista)) ENTÃO
		LIBERE(aLista);
	 SENÃO
	 	atual <- aLista->dados; 
	 	ENQUANTO (atual ~= NULO) FAÇA 
		 “Eliminar até o fim”	
		 anterior <- atual;
		 “Vou para o próximo mesmo que seja nulo.”	
		 atual <- atual->sucessor;
		 “Liberar primeiro a Info”	
		 LIBERE(anterior->info);
		 “Liberar o elemento que acabei de visitar.”	
		 LIBERE(anterior);
		FIM ENQUANTO
		LIBERE(aLista);
	 FIM SE
	fim;
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.4.1 Exercício com Lista Duplamente Encadeada
Implemente o TAD Lista Duplamente Encadeada com funções para todas as suas operações.
Implemente um Módulo aplicativo programa principal que gerencie uma lista representando um itinerário de um trem. O programa deverá:
Utilizar um tipo info que represente uma estação de trem tendo:
Nomeda estação
Hora de chegada e de saída
Hora de chegada e saída na volta.
Aceitar o cadastro de uma estação. O programa coloca a estação na posição por ordem de hora de saída na ida. 
O programa deverá informar ao usuário dados sobre uma parada solicitada pelo usuário por nome:
Quando o trem chega na ida e na volta, qual a estação anterior e qual a estação que vem depois.
Prazo: 2 semanas.
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›
4.2.4.1 Exercício com Lista Duplamente Encadeada
4
Gaspar
09:00
09:15
22:30
22:50
Blumenau
12:00
13:00
21:30
21:50
Itajai
24:00
06:00
24:00
06:00
Trombudo
17:00
18:00
17:00
18:00
EFSC
INE - UFSC - Disciplina Estruturas de Dados - Prof. Dr. Aldo von Wangenheim
Página ‹nº›