Estruturas de dados: Técnicas de encadeamento, Slides de Estruturas de Dados e Algoritmos

Baixe Estruturas de dados: Técnicas de encadeamento e outras Slides em PDF para Estruturas de Dados e Algoritmos, somente na Docsity! 1 Técnicas de Encadeamento Estruturas de Dados Prof. Alex Sandro alexscunha@yahoo.com.br 2 Técnicas de Encadeamento
Lista com ponteiro para o último nó  Seja a representação da lista abaixo:  Situação: Qualquer operação que exija o acesso ao último nó da lista sempre necessitará de um caminhamento sobre os demais nós da lista, a partir do primeiro  Solução Utilizar uma segunda variável, do tipo ponteiro para um nó, para endereçar o último nó. Lista 5 Lista com Descritor
Exemplo de uma lista com nó descritor
Características  Ponteiro para o primeiro nodo;  Ponteiro para o último nodo;  Informação sobre o tamanho da lista. 6 Lista Circular Simplesmente Encadeada
Técnica:  Substituir o indicador nulo do último nó da lista pelo endereço do primeiro nó.
Representação
Vantagem:  Dado um determinado nó, podemos percorrer toda a lista  Basta apenas caminhar através de links! Lista A B C Lista Circular Simplesmente Encadeada
Observação:  Cuidado para não entrar em laço infinito!!!  Detecção do fim da lista deve ser feita de forma correta!
Solução:  Uso de uma variável ponteiro que assume como valor inicial o endereço do nodo inicial  Condição parada: percorrer até encontrar o endereço do nodo inicial.
E para implementar uma lista duplamente encadeada circular? O que vai ser modificado? 10 Deque
Exemplos:  Composição de um trem  Vagões são inseridos e retirados, sempre nas extremidades  Balsa  Automóveis podem entrar e sair por qualquer uma das extremidades
Formas de representação  Sequencial  Lista duplamente encadeada circular, apenas com as operações de interesse
Ilustração e1 e2 e3 en... 11 Deque
Operações  Criação de deque vazio;  Verificar se o deque está cheio;  Verificar se o deque está vazio;  Obter o elemento do início;  Obter o elemento do final;  Inserir um elemento no início;  Inserir um elemento no final;  Remover o primeiro elemento;  Remover o último elemento;  Varredura do deque. Estrutura de Dados
Bibliografia VILLAS, M.; FERREIRA,A.; LEROY,P., MIRANDA, C., BOCKMAN,C. “Estruturas de dados: conceitos e técnicas de implementação”. Rio de Janeiro: Campus, 1993.