Algoritmos Listas Lineares

4443 palavras 18 páginas
Algoritmos e
Estruturas de Dados I
Listas Lineares versão 1.8

Prof. D.Sc. Fabiano Oliveira fabiano.oliveira@ime.uerj.br Listas Lineares
● Lista Linear é o nome dado a uma estrutura que agrupa diversos elementos que, de alguma forma, relacionam-se entre si
○ Cada elemento possui um identificador distinto chamado de chave e possivelmente outros campos
Ex.: Lista Linear de Alunos (chave: matrícula), Logs de
Acesso a Sistemas (chave: data/hora e usuário), etc.

Listas Lineares
● Para decidir como uma Lista Linear deve ser implementada, devemos considerar quais operações serão exigidas da lista
● Operações comuns:






Impressão
Inserção
Remoção
Busca
Ordenação (veremos adiante no curso)

Listas Lineares
● Dependendo das operações que uma lista linear deve atender, a lista pode ser classificada como:
○ Deque: inserções e remoções apenas em pontas da lista ■ Pilha: inserções e remoções numa mesma ponta da lista
■ Fila: inserções numa ponta, remoções em outra

Aplicações de Pilhas e Filas?

Listas Lineares
● Dependendo da forma de alocação dos elementos em memória, outra classificação pode ser feita:
○ Alocação Sequencial: elementos ocupam memória em posições contíguas. Os elementos admitem acesso aleatório, pois suas posições podem ser calculadas
○ Alocação Encadeada: elementos não necessariamente ocupam posições contíguas em memória. Elementos devem ser consultados a partir das posições de elementos já conhecidos, avançando-se ou retrocedendo-se a partir destes

Listas Lineares
● As listas podem além ser classificadas como ordenadas ou não-ordenadas, dependendo se os elementos são mantidos ordenados por chave

Listas Lineares
● Qual tipo de lista é o melhor? A resposta será sempre "DEPENDE!". O uso dos elementos (ou seja, as operações sobre a lista) é que determinará qual é o melhor tipo de lista para o problema em questão

Alocação Sequencial
Impressão, Busca, Inserção, Remoção

Relacionados

  • Listas Lineares
    2241 palavras | 9 páginas
  • Aula 05 Listas Lineares
    1016 palavras | 5 páginas
  • Listalinear 2
    1280 palavras | 6 páginas
  • fundamentos de rede
    1272 palavras | 6 páginas
  • 632101 AED 6 Listas Pilhas Filas
    2643 palavras | 11 páginas
  • Livro Algoritmia E Estrutura De Dados
    4192 palavras | 17 páginas
  • Algoritmos de busca e ordenação
    1240 palavras | 5 páginas
  • Relatório técnico de analise experimental da complexidade de algoritmos em classificação de dados em tempo linear
    4795 palavras | 20 páginas
  • O trabalho
    5576 palavras | 23 páginas
  • Lista lineares encadeadas
    2507 palavras | 11 páginas