Please enable JavaScript.
Coggle requires JavaScript to display documents.
ESTRUTURA DE DADOS PERCURSO 03 - Coggle Diagram
ESTRUTURA DE DADOS
PERCURSO 03
APLICAÇÕES COM LISTAS, FILAS E PILHAS
Listas, filas e pilhas são estruturas de dados lineares, ordenadas conforme a ordem que os dados são inseridos ou removidos da estrutura.
PILHA
, os dados são inseridos e removidos sempre na mesma extremidade, denominada de topo da pilha. Essa estrutura é considerada do tipo
LIFO (Last In First Out)
, que significa que significa, na tradução literal, que o primeiro dado a entrar na pilha será o último a sair.
uma
FILA
indica que o primeiro dado a entrar é também o primeiro a sair.
Este é o princípio do
FIFO (First In, First Out).
As operações básicas associadas às filas são as seguintes:
enqueue() – para adicionar um item na fila;
dequeue() – para remover (acessar) um item da fila;
peek() – para obter o elemento na frente da fila, sem removê-lo;
isfull() – para verificar se a fila está cheia;
isempty – para verificar se a fila está vazia.
Já nas
LISTAS
, os dados são armazenados de forma sequencial, em estruturas chamadas de nós. São tipos de listas as
ligadas
e as
duplamente ligadas
.
A diferença entre as duas listas, então, é que a lista duplamente ligada é bidirecional.
APLICAÇÕES COM ÁRVORES
nas árvores, os dados são alocados hierarquicamente: seus elementos se encontram "acima" ou "abaixo" de outros elementos.
Tanto a árvore de regressão quanto a de classificação seguem uma abordagem conhecida como divisão binária recursiva (“recursive binary splitting”),
Top-down porque inicia no topo, centralizando as observações em apenas uma região e, em seguida, dividindo o espaço preditor em dois ramos.
“Gananciosa” em função de o algoritmo ser voltado apenas à divisão atual (buscando a melhor variável disponível), e não com divisões futuras (que poderiam melhorar a árvore).
APLICAÇÕES COM HASHING
Quando falamos em Hashing, estamos nos referindo a uma técnica para localizar um objeto específico em um grupo de objetos semelhantes. Essa técnica é conhecida como T
abela de Dispersão ou Tabela Hash
, pertencente à estrutura de dados dispersa e
projetada para resolver o problema de busca e armazenamento de dados
.
As Tabelas Hash são usadas para armazenar dados em forma de matriz, em que cada dado possui um valor de índice exclusivo. Ou seja, o dado fica associado a uma chave.
A Tabela Hash possui dois elementos essenciais: uma função de hashing e um mecanismo de resolução de colisões.
Endereçamento Aberto ou Hashing Fechado
encadeamento separado ou hashing aberto
uma função hash é eficiente quando identificamos as seguintes propriedades:
APLICAÇÕES COM ENDEREÇAMENTO ABERTO E FECHADO
A técnica de endereçamento aberto (Hashing Fechado) mantém todos os dados na mesma tabela e, para isso, em algumas situações seria preciso ficar procurando slots alternativos na tabela hash até que fosse encontrada uma posição vazia, para acomodar o novo dado.
O hash duplo nos oferece uma das melhores técnicas de hashing com endereçamento aberto. A permutação formada por hash duplo é como uma permutação aleatória, portanto, quase elimina as chances de formação de cluster, pois usa uma função de hash secundária como um deslocamento para lidar com a condição de colisão.
Encadeamento Separado ou Hashing Aberto
, em cada matriz, implementamos uma lista vinculada, conhecida como cadeia.
VANTAGENS
Fácil implementação.
Sempre haverá slots disponíveis para acomodar o novo dado.
Menor possibilidade de colisão.
É indicada quando a sequência de inserções e exclusões são ignoradas
DESVANTAGENS
O armazenamento de chaves em lista vinculada impacta no desempenho do cache. Nesse sentido, o endereçamento aberto possui um desempenho de cache melhor, pois todos os dados são armazenados na mesma tabela.
A tabela hash nunca será totalmente utilizada.
Pode ocorrer lentidão na busca, num cenário O(n), onde n é o número de posições percorrias.
Usa espaço extra para links.
