Listas Ligadas Simples - Estruturas de Dados FATEC Jundiaí

ESTRUTURAS DE DADOS LISTAS LIGADAS SIMPLES Prof Ms Peter Jandl Junior ADS FATEC Jundiaí LISTAS LIGADAS SIMPLES Uma organização muito flexível para listas a qual pode constituir base para construção de filas pilhas e outras estruturas de dados 10052022 C 20132022 PJANDL 2 LISTAS LIGADAS SIMPLES Cada elemento nodo ou nó da lista ligada simples ou lista simplesmente ligada contém Um dado simples primitivo ou um objeto e Uma ligação para um próximo elemento próximo nodo Cada novo elemento deve ser encadeado a outro previamente existente na lista Uso de sentinela referência para início da lista ou outro ponto de interesse 10052022 C 20132022 PJANDL 3 LISTAS LIGADAS SIMPLES Elementos podem ser Adicionados no início ou no fim da lista Inseridos entre quaisquer dois elementos sucessivos da lista Removidos de qualquer posição da lista Mas lista simples só pode ser percorrida em direção ao final navegação unidirecional 10052022 C 20132022 PJANDL 4 LISTAS LIGADAS SIMPLES Em todos os casos Os elementos existentes não precisam ser movimentados pois sua localização na memória não é alterada Apenas as ligações com os elementos afetados são alteradas ou seja apenas o nodos envolvidos 10052022 C 20132022 PJANDL 5 LISTAS LIGADAS SIMPLES 10052022 C 20132022 PJANDL 6 Cada elemento referencia apenas outro ou seja um próximo ou sucessor O último elemento aponta para null fim da lista É necessário uma referência para o primeiro elemento da lista A navegação só pode ser realizada para frente ie em direção ao final da lista LISTAS LIGADAS SIMPLES Nas listas ligadas simples cada elemento ou nodo pode ser definido como uso da classe NodoLigado Esta contém Um campo para dados Um campo para ligação com outro nodo Construtores para facilitar seu uso 10052022 C 20132022 PJANDL 7 LISTAS LIGADAS SIMPLES 10052022 C 20132022 PJANDL 8 dado prox dado prox null inicio Sentinela uma referência do mesmo tipo que os elementos da lista que aponta para o primeiro elemento início da lista Em cada elemento o campo proximo aponta para o elemento seguinte Em cada elemento o campo dado armazena o conteúdo do elemento ou uma referência para o objeto que representa o conteúdo O campo proximo do último elemento contém null para indicar o fim da lista LISTAS LIGADASAPLICAÇÃO São particularmente úteis na implementação de estruturas de dados comuns como Listas situação natural onde operações são realizadas sobre sentinela para início ou seus elementos Pilhas operações sobre o topo equivalem à manipular apenas sentinela para início da lista ligada Filas entrada de elementos pode ser feita mediante uso de sentinela para último elemento da lista saída de elementos pode ser feita mediante uso de sentinela para início da lista 10052022 C 20132022 PJANDL 9 LISTAS LIGADAS SIMPLESIMPLEMENTAÇÃO 10052022 C 20132022 PJANDL 10 LISTAS LIGADAS SIMPLES 10052022 C 20132022 PJANDL 11 LISTA LIGADA CAMPOS E CONSTRUTOR DEFAULT 10052022 C 20132022 PJANDL 12 LISTA LIGADA ADICIONAROBJECT E COMPRIMENTO 10052022 C 20132022 PJANDL 13 LISTA LIGADA INSERIR INT OBJECT 10052022 C 20132022 PJANDL 14 LISTA LIGADA ELEMENTOINT 10052022 C 20132022 PJANDL 15 LISTA LIGADA REMOVERINT 10052022 C 20132022 PJANDL 16 LISTA LIGADA TOSTRING REPRESENTAÇÃO TEXTUAL 10052022 C 20132022 PJANDL 17 LISTA LIGADA VAZIA 10052022 C 20132022 PJANDL 18 LISTA LIGADAINTERFACE Interface desta estrutura de dados permite uma série de operações genéricas Construção Obtenção do número de elementos Adição fim da lista Inserção Remoção e Consulta para qualquer posição válida Representação textual Lista vazia 10052022 C 20132022 PJANDL 19 PILHA Uma pilha poderia ser constituída das seguintes operações Construção Obtenção do número de elementos Adição no topo Remoção no topo Consulta Representação textual Lista vazia 10052022 C 20132022 PJANDL 20 PILHA COM LISTA LIGADA SIMPLES Aplicação da estratégia da decoração 10052022 C 20132022 PJANDL 21 FILA Uma fila poderia ser constituída das seguintes operações Construção Obtenção do número de elementos Adição no final Remoção do início Consulta Representação textual Lista vazia 10052022 C 20132022 PJANDL 22 FILA COM LISTA LIGADA SIMPLES Aplicação da estratégia da decoração 10052022 C 20132022 PJANDL 23 EXERCÍCIOS 10052022 C 20132022 PJANDL 24 EXERCÍCIOS 1 Escreva um programa que utilize uma Pilha para armazenar 10 valores inteiros dados pelo usuário apresentandoos após sua entrada 2 Escreva um programa que armazene até 20 strings palavras dadas pelo usuário separando em duas Pilhas distintas as palavras no singular e plural terminadas em s A string fim finaliza a sequência Exiba os valores das duas Pilhas após sua entrada Nestes exercícios utilize a nova classe Pilha desenvolvida 10052022 C 20132022 PJANDL 25 EXERCÍCIOS 3 Escreva um programa que armazene em uma Pilha valores inteiros dados pelo usuário Depois da entrada exibir os valores remover todos os elementos pares existentes e exibir novamente a Pilha 4 Escreva um programa que armazene em uma Pilha uma quantidade de valores reais e aleatórios definida pelo usuário Depois de fornecida tal quantidade entrada preencher a Pilha exibir os valores remover os elementos um a um e exibir novamente a Pilha 5 Refaça os exercícios de 1 a 4 usando a implementação de Fila 6 Refaça os exercícios de 1 a 4 usando a implementação de Lista Nestes exercícios utilize a nova classe Pilha desenvolvida Depois refaça todos com Fila e Lista 10052022 C 20132022 PJANDL 26