632101_AED (6) - Listas & Pilhas & Filas

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