Estruturas de dados: listas, filas, pilhas e árvores. Flashcards
O que são estruturas de dados?
Estruturas de dados são objetos que armazenam dados
de forma eficiente, oferecendo certos “serviços” para o
usuário (ordenação eficiente dos dados, busca por meio
de palavras chave, etc).
Abstração
Uma estrutura de dados abstrai as características
principais de uma atividade que envolve armazenamento
de informações.
Por exemplo, a estrutura de fila armazena dados de forma
que o dado há mais tempo na estrutura é o primeiro a ser
retirado.
Pilhas
Uma pilha é uma estrutura de dados em que o acesso é
restrito ao elemento mais recente na pilha.
Operações básicas de pilhas
As operações básicas realizadas com uma pilha são:
push: inserir no topo;
pop: retirar do topo;
top: observar o topo.
Em uma pilha “ideal”, operações básicas devem ocorrer
em O(1), independentemente do tamanho N da pilha (ou
seja, em tempo constante).
Avaliação de expressões
Pilhas são muito usadas no processamento de linguagens,
por exemplo em compiladores.
Uma aplicação importante é a conversão e avaliação de
expressões numéricas.
Existem três tipos de notações para expressões
numéricas:
1 infixa, onde operador entre operandos: (A + B);
2 pós-fixa, onde operador segue operandos: (AB+) (notação
polonesa reversa);
3 pré-fixa, onde operador precede operandos: (+AB)
(notação polonesa).
Filas
Uma fila é uma estrutura em que o acesso é restrito ao
elemento mais antigo.
Operações básicas:
enqueue: inserir na fila;
dequeue: retirar da fila.
A implementação mais comum de uma fila é por “arranjo
circular”.
Lista ligada
Esse tipo de estrutura é muito flexível e pode acomodar
inserção e retirada de dados de locais arbitrários.
A vantagem desse tipo de estrutura é a flexibilidade
permitida no uso da memória.
A desvantagem é que alocar memória é uma tarefa
demorada (mais lenta que acesso a arranjos).
Vetor ou Array
é uma estrutura de dados estática. Segundo DEITEL (2016, pág. 192), Arrays são estruturas de dados consistindo em itens de dados do mesmo tipo relacionados.
Array multidimensional (matrizes)
m resumo, trata-se de um vetor de vetores. De acordo com DEITEL (2005, pág. 223), os arrays com duas dimensões costumam ser utilizados para representar tabelas de valores que consistem nas informações dispostas em linhas e colunas.
Árvores
São estruturas de dados baseadas em listas encadeadas que possuem um nó superior também chamado de raiz que aponta para outros nós, chamados de nós filhos, que podem ser pais de outros nós. Nas árvores os dados estão dispostos de forma hierárquica.
Tabela de espelhamento/dispersão/hash
É uma opção de estrutura que serve para organizar e armazenar dados de forma a agilizar o processo de pesquisa. Isso ocorre porque dada uma chave, a função Hash decide em qual endereço dessa tabela aquele valor deve ser armazenado.
Árvore binária
Cada nó tem no máximo dois filhos, chamados de filho da esquerda e filho da direita.
Árvore binária de busca
Uma estrutura de dados fundamental na ciência da computação que permite uma busca eficiente.
Árvore perfeitamente balanceada
Para todo nó da árvore, os números de nós das suas duas subárvores diferem no máximo em um.
Árvore B
Muito usada na implementação de índices em bancos de dados.
Tipos de busca
Busca sequencial, busca de registros ordenados e busca binária.
Busca sequencial
É o método mais simples de realizar uma busca que consiste em uma varredura de chaves primárias (são identificadas para diferenciar os registros entre si), utilizando vetores. Durante esta varredura o argumento de busca é comparado com a chave primária de cada registro até ser encontrado o valor desejado.
Busca de registros ordenados
Se os registros estiverem ordenados em ordem crescente ou decrescente, várias técnicas poderão ser empregadas para aumentar a eficiência da operação de busca.
Busca binária
A busca binária é um método que pode ser aplicado a registros ordenados, armazenadas e disponíveis de acesso direto, ou seja, ela parte do propósito de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for à chave, a busca é terminada com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor e finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
