Mapa Mental - Estruturas Dados

Prévia do material em texto

Estruturas Lineares Pesquisa e Ordenação Vetores e listas são Pesquisa linear é simples, mas estruturas lineares e menos eficiente que a pesquisa estáticas binária Listas encadeadas permitem Pesquisa binária é eficiente, inserção dinâmica de exige dados ordenados para elementos funcionar corretamente Pilha segue LIFO, último Método bolha é simples, mas elemento inserido é possui baixa eficiência para primeiro removido grandes conjuntos Fila segue FIFO, primeiro Métodos de inserção e seleção elemento inserido é direta diferem na forma de primeiro removido ordenar elementos Estruturas Tipos Abstratos Dados Funções Recursivas TAD encapsula dados e operações Dados Função recursiva chama a si para manipulação segura mesma até atingir um caso Implementação do TAD depende da base escolha da estrutura de dados Exemplo clássico: cálculo do Tipos primitivos comuns: fatorial usando recursão inteiro e caractere (char) Recursão pode ser TADs permitem abstração substituída por algoritmos independente do hardware iterativos não-recursivos subjacente Recursão facilita solução de problemas com estrutura repetitiva ou hierárquica Ponteiros e Listas Encadeadas Ponteiros armazenam endereços de memória, não valores numéricos diretamente Árvores e Atravessamentos Listas duplamente encadeadas possuem Tabelas Hash e Colisões referências para elementos anterior e Árvores binárias armazenam dados próximo Tabela hash usa função de hierarquicamente para busca Listas sequenciais não são dinâmicas, espalhamento para distribuir eficiente elementos têm posições fixas no vetor dados uniformemente Atravessamento infixo visita Ponteiros são essenciais para alocação Colisões ocorrem quando subárvore esquerda, raiz e dinâmica e manipulação eficiente de diferentes entradas geram O mesmo subárvore direita memória índice na tabela Representação em parênteses Funções de espalhamento ruins expressa a estrutura hierárquica prejudicam desempenho da tabela da árvore hash Árvores são usadas para guardar e Tabela hash é também chamada de recuperar dados de forma tabela de dispersão ou organizada espelhamento