Estrutura De Dados
Trabalho Universitário: Estrutura De Dados. Pesquise 862.000+ trabalhos acadêmicosPor: thyse • 9/7/2013 • 859 Palavras (4 Páginas) • 635 Visualizações
Resumo Prova de Estrutura de Dados
Pilhas:
Principais Operações: push() ; pop() ; top()
Aplicação: Calculadoras, compiladores e S.O’s.
Características:
- É uma estrutura linear de dados (ELD).
- LIFO (Last In First Out)
- Possuem a ordem invertida.
- São usadas para acesso rápido aos dados mais recentes.
- Geralmente são pequenas e são melhores implementadas em array[].
- As pilhas dinâmicas ocupam mais memória mas por outro lado não possuem limite.
Filas:
Principais Operações: entrar() ou enqueue() ; sair() ou dequeue() ; primeiro() ; valor()
Aplicação: Qualquer sistema que necessite de ordem de chegada.(Ordem de processos – Buffer de Impressora - uso de Array[]).
Características:
- É uma estrutura linear de dados (ELD).
- FIFO (First In First Out)
- Possuem a ordem preservada.
- Pode ser Circular (não possui início nem fim – uso de Array[])
- As filas dinâmicas ocupam mais memória mas por outro lado não possuem limite.
Listas:
Principais Operações:
• Atômicas: inserirAntesAtual() ; inserirDepoisAtual() ; removerAtual() ; acessarAtual() ; buscar(chave)
• Do Cursor: vaParaPrimeiro() ; vaParaUltimo() ; avançarXPosicoes() ; retrocederXPosicoes()
Aplicação: Qualquer sistema que necessite de um armazenamento temporário de dados. Ex: Lista de e-mails.
- É uma estrutura linear de dados (ELD).
- É uma estrutura “liberal”.
- Possui um atributo chamado cursor que determina uma possibilidade de métodos.
- É necessário varrer todos os elementos para efetuar uma busca.
- As técnicas do “pé atrás” e “da visão além do alcance” só servem para listas simples.
- Possibilidade da lista duplamente encadeada.
Hash:
- Geralmente é um Array de Listas.
- Pode ser uma Lista de Listas, mas é ruim por deixar o acesso extremamente lento, portanto não é recomendado.
- Fator de Carga: É a quantidade média de elementos (chaves) que devem ser alocados em cada posição do array.
- O fator de carga geralmente recomendado é de 2 a 4.
- O tamanho da tabela (Array) é geralmente baseado no Fator de Carga.
- As posições do array também são chamados de grupos e devem ser sempre números.
- Colisão: É quando duas chaves diferentes resultam no mesmo grupo ao passar pela mesma função Hash.
- Chaves Sinônimas: É quando essas chaves sofrem Colisão.
- Quando haver a necessidade de redimensionar a tabela deve-se criar uma nova tabela e re-inserir as chaves novamente com uma nova função Hash.
Características de uma boa função Hash:
- Ela é rápida;
- Distribui uniformemente os dados na tabela;
- Usa todos os dígitos da chave para o cálculo do código Hash (grupo);
...