Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Listas / Pilhas / Filas • Conceitos Preliminares • Listas • Princípios Gerais e Conceitos Básicos • Listas Simplesmente Encadeadas • Listas Duplamente Encadeadas • Listas Circulares • Operações em Listas • Filas • Princípios Gerais e Conceitos Básicos • Operações em Filas • Pilhas • Princípios Gerais e Conceitos Básicos • Operações em Pilhas Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Bibliografia • ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos – Estruturas de Dados: Algoritmos, Análise da Complexidade e Implementações em Java e C/C++ • ZIVIANE, Nivio – Projeto de Algoritmos: com implementações em Java e C++ • SZWARCFITER, Jayme Luiz; MARKENZON, Lilian – Estruturas de dados e seus Algoritmos • CORMEN, Thomas H. et al. – Algoritmos: Teoria e Prática • FARRER, Harry et al. Programação Estruturada de Computadores – Algoritmos Estruturados. Rio de Janeiro: Guanabara Dois, 1985. 260p. • PREISS, Bruno – Estruturas de dados e algoritmos. Rio de Janeiro: Campus, 2001. 584p. • SZWARCFITER, Jayme Luiz; MARKENZON, Lilian – Estruturas de dados e seus Algoritmos • VILLAS, Marcos Vianna; VILLASBOAS, Luiz Felipe P. Programação – Conceitos, Técnicas e Linguagens. Rio de Janeiro: Campus, 1988. 196p. • DEITEL & DEITEL – C# - Como Programar – 2003 • Stellman & Greene – C# - Use a Cabeça – 2ª Edição – 2011 • Material de Aula – Algoritmos e Técnicas de Programação – Aluísio Eustáquio da Silva – 2012 • Material de Aula – Algoritmos e Estruturas de Dados – Tiago Braga – 2012 2 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Listas – Conceitos Gerais Uma estrutura de dados do tipo lista representa um conjunto de dados organizados em ordem linear. Pode ser estática ou dinâmica; homogênea ou heterogênea. Lista Homogênea Estática e Lista Homogênea Dinâmica Lista Heterogênea Estática e Lista Heterogênea Dinâmica Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Listas – Conceitos Gerais Existem cinco tipos diferentes de listas: • Lista simplesmente encadeada e não ordenada. • Lista simplesmente encadeada e ordenada. • Lista duplamente encadeada e não ordenada. • Lista duplamente encadeada e ordenada. • Listas circulares. 3 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada Cada elemento armazena um ou vários dados (estrutura homogênea ou heterogênea) e um ponteiro para o próximo elemento, que permite o encadeamento e mantém a estrutura linear. Operações: • Inserir no início da lista; • Inserir no fim da lista; • Consultar toda a lista; • Remover um elemento da lista; • Remover todos os elementos da lista (esvaziar a lista). Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada 1ª Operação Lista Vazia 2ª Operação Inserção do Número 9 no Início da Lista null Início 9 null # 500 Núm Próx 4 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada 3ª Operação Inserção do Número 3 no Início da Lista 4ª Operação Inserção do Número 5 no Fim da Lista 9 null # 500 Núm Próx 3 500 # 650 Núm Próx 5 null # 700 Núm Próx 9 700 # 500 Núm Próx 3 500 # 650 Núm Próx Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada 5ª Operação Inserção do Número 2 no Fim da Lista 6ª Operação Remoção do Número 9 2 null # 750 Núm Próx 5 750 # 700 Núm Próx 3 700 # 650 Núm Próx 5 750 # 700 Núm Próx 9 700 # 500 Núm Próx 3 500 # 650 Núm Próx 2 null # 750 Núm Próx 5 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# 6 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# 7 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# 8 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Não Ordenada – Códigos em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Ordenada Cada elemento armazena um ou vários dados (estrutura homogênea ou heterogênea) e um ponteiro para o próximo elemento, que permite o encadeamento e mantém a estrutura linear. Tem-se também um campo denominado chave pelo qual uma determinada ordenação é mantida. Operações: • Inserir na lista; • Consultar toda a lista; • Remover um elemento da lista; • Remover todos os elementos da lista (esvaziar a lista). 9 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Ordenada 1ª Operação Lista Vazia 2ª Operação Inserção do Número 3 na Lista null Início 3 null # 500 Núm Próx Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Ordenada 3ª Operação Inserção do Número 8 na Lista 4ª Operação Inserção do Número 5 na Lista 8 null # 650 Num Próx 3 650 # 500 Num Próx 8 null # 650 Num Próx 5 650 # 700 Num Próx 3 700 # 500 Num Próx 10 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Ordenada 5ª Operação Inserção do Número 1 na Lista 6ª Operação Remoção do Número 5 8 null # 650 Núm Próx 3 650 # 500 Núm Próx 1 500 # 750 Núm Próx 5 650 # 700 Núm Próx 3 700 # 500 Núm Próx 1 500 # 750 Núm Próx 8 null # 650 Núm Próx Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Simplesmente Encadeada e Ordenada 7ª Operação Remoção do Número 1 8ª Operação Remoção do Número 8 3 null # 500 Núm Próx 8 null # 650 Núm Próx 3 650 # 500 Núm Próx 11 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Não Ordenada Cada elemento armazena um ou vários dados (estrutura homogênea ou heterogênea) e dois ponteiros: o primeiro, para o próximoelemento, e o segundo, para o elemento anterior. Esses ponteiros permitem o duplo encadeamento e mantêm a estrutura linear. Operações: • Inserir no início da lista; • Inserir no fim da lista; • Consultar toda a lista, do início ao fim ou do fim ao início; • Remover um elemento qualquer da lista; • Remover todos os elementos da lista. Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Não Ordenada 1ª Operação Lista Vazia 2ª Operação Inserção do Número 7 na Lista null Início 7 null # 120 Núm Próx null Ant 12 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Não Ordenada 3ª Operação Inserção do Número 9 no Início da Lista 4ª Operação Inserção do Número 3 no Fim da Lista 7 null # 120 Núm Próx 230 Ant 9 120 # 230 Núm Próx null Ant 3 null # 250 Núm Próx 120 Ant 7 250 # 120 Núm Próx 230 Ant 9 120 # 230 Núm Próx null Ant Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Não Ordenada 5ª Operação Inserção do Número 8 no Fim da Lista 6ª Operação Remoção do Número 9 3 280 # 250 Núm Próx 120 Ant 7 250 # 120 Núm Próx 230 Ant 9 120 # 230 Núm Próx null Ant 8 null Núm Próx 250 Ant # 280 3 280 # 250 Núm Próx 120 Ant 7 250 # 120 Núm Próx null Ant 8 null Núm Próx 250 Ant # 280 13 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Não Ordenada 7ª Operação Remoção do Número 3 8ª Operação Remoção do Número 8 7 280 # 120 Núm Próx null Ant 8 null Núm Próx 120 Ant # 280 7 null # 120 Núm Próx null Ant Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Ordenada Cada elemento armazena um ou vários dados (estrutura homogênea ou heterogênea) e dois ponteiros; o primeiro para o próximo elemento, e o segundo para o anterior, permitindo o duplo encadeamento e mantendo a estrutura linear. Há também um campo denominado chave por meio do qual determinada ordenação é mantida. Operações: • Inserir na lista; • Consultar toda a lista do início ao fim ou do fim ao início; • Remover um elemento da lista; • Remover todos os elementos da lista. 14 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Ordenada 1ª Operação Lista Vazia 2ª Operação Inserção do Número 5 na Lista null Início 5 null # 380 Núm Próx null Ant Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Ordenada 3ª Operação Inserção do Número 8 na Lista 4ª Operação Inserção do Número 3 na Lista 8 null # 250 Núm Próx 380 Ant 5 250 # 380 Núm Próx null Ant 8 null # 250 Núm Próx 380 Ant 5 250 # 380 Núm Próx 350 Ant 3 380 # 350 Núm Próx null Ant 15 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Ordenada 5ª Operação Inserção do Número 7 na Lista 6ª Operação Remoção do Número 7 7 250 # 170 Núm Próx 380 Ant 5 170 # 380 Núm Próx 350 Ant 3 380 # 350 Núm Próx null Ant 8 null Núm Próx 170 Ant # 280 8 null # 250 Núm Próx 380 Ant 5 250 # 380 Núm Próx 350 Ant 3 380 # 350 Núm Próx null Ant Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Lista Duplamente Encadeada e Ordenada 7ª Operação Remoção do Número 3 8ª Operação Remoção do Número 8 5 null # 380 Núm Próx null Ant 8 null # 250 Núm Próx 380 Ant 5 250 # 380 Núm Próx null Ant 16 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Listas Circulares Listas também podem ser implementadas de forma Circular: • Quando são Listas Simplesmente Encadeadas, o último elemento terá seu ponteiro próximo se referenciando ao primeiro elemento; • Quando são Listas Duplamente Encadeadas, o último elemento terá seu ponteiro próximo se referenciando ao primeiro elemento e o primeiro elemento com seu ponteiro anterior apontando para o último elemento. 8 750 # 650 Núm Próx 3 650 # 500 Núm Próx 1 500 # 750 Núm Próx 8 null # 250 Núm Próx 380 Ant 5 250 # 380 Núm Próx 350 Ant 3 380 # 350 Núm Próx null Ant Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas e Filas – Conceitos Gerais As Pilhas e as Filas são consideradas listas especializadas porque elas possuem características próprias de comportamento, embora também possuam operações de inserção, exclusão, alteração, contagem de elementos e pesquisa a maiores e menores valores dentro do conjunto. São estruturas que são organizadas de forma linear e podem ser: • Estáticas, quando a ordem linear é determinada pelos índices dentro de um vetor; • Dinâmicas, quando representadas por elementos encadeados; • Homogêneas, quando possuem somente dados de um determinado tipo primitivo, como um número ou um caractere, por exemplo; • Heterogêneas, quando possuem dados estruturados de tipos diferentes, como o nome e salário de um funcionário, por exemplo. 17 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas As Pilhas são estruturas de armazenamento cujo comportamento segue uma regra básica que se baseia no fato de que o primeiro elemento inserido será o último a ser retirado. São consideradas, portanto, do tipo FILO (First In, Last Out). Cada elemento armazena um ou vários dados (estrutura homogênea ou heterogênea) e um ponteiro para o próximo elemento, permitindo o encadeamento e mantendo a estrutura linear. A estrutura possui um ponteiro chamado TOPO, no qual todas as operações de inserção e remoção acontecem. Assim, as operações ocorrem sempre na mesma extremidade. Além das operações de inserção e remoção, pode-se também listar todos os elementos ou esvaziar a lista. Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas - Rotinas em C# 18 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas - Rotinas em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas - Rotinas em C# 19 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Pilhas - Rotinas em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas As Filas seguem um comportamento que se baseia no princípio de que o primeiro elemento que for inserido será também o primeiro a ser retirado. São consideradas do tipo FIFO (First In, First Out). Cada elemento também armazena um ou vários dados (estrutura homogênea ou heterogênea) e um ponteiro para o próximo elemento, permitindo o encadeamento e mantendo a estrutura linear. A estrutura possui um ponteiro chamado INÍCIO e um chamado FIM, no qual todas as operações de inserção e remoção acontecem. As operações ocorrem nas duas extremidades da estrutura. Pode-setambém listar todos os elementos ou esvaziar a lista. 20 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas - Rotinas em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas - Rotinas em C# 21 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas - Rotinas em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas - Rotinas em C# 22 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Filas - Rotinas em C# Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Exercícios Práticos/ Implementação 23 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Listas / Pilhas / Filas Classes Genéricas do C# • Classe ArrayList • Classe List • Classe Queue • Classe Stack • Classe SortedList • ... Prática em Laboratório
Compartilhar