Estrutura de dados
Em ciência da computação e tecnologia de software , uma estrutura de dados é um objeto usado para armazenar e organizar dados . É uma estrutura porque os dados são organizados e vinculados de uma forma específica para permitir um acesso eficiente aos mesmos e ao seu gerenciamento .
As estruturas de dados não se caracterizam apenas pelos dados que contêm, mas sobretudo pelas operações sobre esses dados que permitem e implementam o acesso e a gestão.
Explicação
A especificação ( definição ) de estruturas de dados é geralmente realizada através de uma descrição exata ( especificação ) do gerenciamento de dados e das operações necessárias para isso. Esta especificação específica define o comportamento geral das operações e, portanto, abstrai da implementação específica da estrutura de dados.
Se o foco da consideração for deslocado para a implementação concreta das operações, um tipo de dados abstrato é freqüentemente usado em vez do termo estrutura de dados . A transição da estrutura de dados para um tipo de dados abstrato não está claramente definida, mas depende unicamente do ponto de vista. Tendo em vista os requisitos de memória em constante mudança de muitas estruturas de dados, também se fala em tipos de dados dinâmicos , que são tecnicamente baseados no gerenciamento de memória dinâmica .
Além de sua forma básica, a maioria das estruturas de dados tem muitas especializações que foram especificadas especificamente para o cumprimento de uma determinada tarefa. Por exemplo, como uma especialização da estrutura de dados em árvore , as árvores B são particularmente adequadas para implementações de banco de dados .
Com muitos algoritmos , os requisitos de recursos, ou seja, o tempo de execução necessário e os requisitos de espaço de armazenamento, dependem do uso de estruturas de dados adequadas.
Estruturas de dados básicas
As estruturas de dados a seguir geralmente foram desenvolvidas e otimizadas para programação imperativa clássica . Outros paradigmas de programação, como a programação funcional, podem exigir estruturas de dados diferentes.
registro
Conjuntos de dados (também chamados de 'tuplas' ou registros em inglês ) são as estruturas de dados mais simples. Eles geralmente incorporam valores que contêm outros valores em um número e sequência fixos. Os registros de dados são geralmente identificados por um ou mais dos elementos que eles contêm, geralmente chamados de campo de dados .
(Dados) campo (também matriz)
O campo ( também chamado de array ) é a estrutura de dados mais simples usada. Várias variáveis do mesmo tipo de dados básicos são salvas aqui. O acesso aos elementos individuais é possível por meio de um índice. Do ponto de vista técnico, corresponde ao valor que se adiciona ao endereço inicial do array na memória para obter o endereço do objeto. As únicas operações necessárias são armazenamento indexado e leitura indexada , que podem acessar diretamente qualquer elemento da matriz. No caso unidimensional, a matriz é freqüentemente referida como um vetor e no caso bidimensional como uma tabela ou matriz . Os arrays não são de forma alguma restritos a apenas duas dimensões, mas podem ser usados em qualquer número de dimensões. Por causa de sua simplicidade e importância fundamental, a maioria das linguagens de programação oferece uma implementação concreta dessa estrutura de dados como uma matriz de tipo de dados composta no escopo da linguagem básica.
Tabela de alocação
A tabela de atribuição (também matriz associativa ou par de valores-chave) é um caso especial em que os dados armazenados não são acessados por meio de um índice numérico, mas por meio de uma chave . Uma forma possível de implementar uma matriz associativa é com a tabela hash .
muito
Outro caso especial é a quantia. Aqui você não pode acessar valores específicos usando um índice ou chave. Está desordenado. Corresponde a uma tabela de atribuição com chaves que só podem aparecer uma vez, mas sem valores.
(Lista encadeada
A lista (vinculada) é uma estrutura de dados para o armazenamento dinâmico de qualquer número de objetos. Cada elemento de lista de uma lista encadeada contém como um recurso especial uma referência ao próximo elemento, por meio do qual a totalidade dos objetos se torna uma cadeia de objetos. As operações pertencentes a uma lista são relativamente não especificadas. Eles são freqüentemente usados em estruturas de dados mais complexas e seus elementos são geralmente acessados diretamente em vez de por meio de operações por razões de eficiência. As listas oferecidas em bibliotecas de programas são geralmente muito mais complexas em termos de sua estrutura de dados subjacente e muitas vezes não representam nenhuma lista real, mas aparecem para o mundo exterior como tal. As listas são sempre estruturas lineares. Se predecessores e sucessores são vinculados bidirecionalmente, fala-se de uma lista duplamente vinculada.
Fila
Em uma fila (Inglês Inglês fila ) pode ser qualquer número de objetos a serem armazenados, no entanto, os objetos armazenados podem ser lidos novamente apenas na mesma ordem em que foram armazenados. Isso corresponde ao princípio FIFO . Para a definição e, portanto, a especificação da fila, é irrelevante quais objetos estão armazenados nela. Pelo menos as operações pertencem a uma fila
- enfileirar para colocar um objeto na fila e
- desenfileirar para ler o objeto salvo primeiro e removê-lo da fila.
Uma fila geralmente é implementada como uma lista encadeada, mas também pode usar uma matriz internamente; neste caso, o número de elementos é limitado.
Pilha de memória
Em uma pilha de memória ( pilha em inglês ) podem ser armazenados objetos de qualquer número, porém, os objetos armazenados podem ser lidos novamente, apenas na ordem inversa. Isso corresponde ao princípio LIFO . Para a definição e, portanto, a especificação da pilha, é irrelevante quais objetos estão armazenados nela. Pelo menos as operações pertencem a uma pilha
- empurre para colocar um objeto na pilha e
- pop para ler o último objeto salvo novamente e removê-lo da pilha.
- ( top ou peek para ler o item principal sem excluí-lo)
A operação top não é obrigatória, mas geralmente é implementada para substituir pop / push , pois muitas vezes é interessante "testar" o elemento superior. Uma pilha geralmente é implementada como uma lista, mas também pode ser um vetor.
Deque
O deque (fila dupla) é uma estrutura de dados semelhante à fila ou à pilha de memória. Ele combina as propriedades de ambas as estruturas de dados. A diferença é que os dados podem ser lidos, inseridos ou removidos em qualquer uma das extremidades.
Fila de prioridade
Uma especialização da fila é a fila de prioridade, também conhecida como fila de prioridade . Fila de prioridade chamada. Isso se desvia do princípio FIFO . A execução da operação de enfileiramento , também chamada de operação de inserção neste caso , classifica o objeto na fila de prioridade de acordo com uma determinada prioridade que cada objeto carrega. A operação de desenfileiramento sempre retorna o objeto com a prioridade mais alta. As filas prioritárias são implementadas principalmente com heaps .
gráfico
Como estrutura de dados, um gráfico permite superar a unidirecionalidade do link. As operações aqui são também inserir , apagar e encontrar um objeto. As representações de grafos mais conhecidas no computador são a matriz de adjacência , a matriz de incidência e a lista de adjacência . Os gráficos planos podem ser mapeados usando uma estrutura de dados de meia-borda .
árvore
Árvores são formas especiais de gráficos na teoria dos grafos . Normalmente, apenas out-trees são usados como estrutura de dados . A partir da raiz, vários objetos do mesmo tipo podem ser ligados entre si, de forma que a estrutura linear da lista seja quebrada e uma ramificação ocorra. Como as árvores são uma das estruturas de dados mais comumente usadas na ciência da computação, existem muitas especializações.
Em árvores binárias, por exemplo, o número de filhos é no máximo dois, e em árvores com altura balanceada , também se aplica que as alturas das subárvores esquerda e direita em cada nó não diferem muito.
No caso de árvores ordenadas, especialmente árvores de pesquisa , os elementos são armazenados na estrutura da árvore de maneira ordenada para que os elementos possam ser encontrados rapidamente na árvore. Uma distinção adicional é feita aqui entre árvores de busca binárias com árvores AVL (incluindo árvores Fibonacci ) como uma versão balanceada e árvores B , bem como uma variante, as árvores B * . As especializações de árvores B são novamente 2-3-4 árvores , que geralmente são implementadas como árvores vermelhas e pretas .
Estruturas de árvore geométricas, como a árvore R e suas variantes, não são classificadas, mas "aninhadas" . Aqui, apenas as subárvores são pesquisadas que se sobrepõem à área solicitada.
Embora as árvores sejam multidimensionais em sua estrutura, a interligação dos objetos costuma ser unidirecional. A concatenação dos objetos armazenados começa na raiz da árvore e a partir daí na direção dos nós da árvore.
Heap
O heap combina a estrutura de dados de uma árvore com as operações de uma fila prioritária. Além das operações minimamente necessárias, como insert , remove e extractMin , o heap geralmente possui outras operações, como merge ou changeKey . Dependendo da ordem de prioridade na fila de prioridade, um heap mínimo ou um heap máximo é usado. Outras especializações do heap são o heap binário , o heap binomial e o heap de Fibonacci . Os montes são construídos principalmente com árvores.
Treap
A Treap combina as propriedades das árvores ( "árvores" ) e pilhas.
Tabela de hash
A tabela hash ou tabela hash é uma estrutura de índice especial na qual a posição da memória pode ser calculada diretamente. As tabelas de hash competem com as estruturas de árvore, que, ao contrário das tabelas de hash, podem reproduzir todos os valores de índice em uma ordem, mas requerem maior esforço administrativo para fornecer o índice. Ao usar uma tabela hash para pesquisar volumes de dados, também se fala do método hash . Uma tabela hash distribuída pode ser usada para grandes quantidades de dados .
Esforço de armazenamento e computação de estruturas de dados
| cirurgia | Variedade | Array dinâmico |
Lista ligada |
Árvore balanceada |
Tabela de hash |
|---|---|---|---|---|---|
| Inserção / exclusão no início |
N / D | Θ ( n ) | Θ (1) | Θ ( log n ) | Θ ( 1 ) a Θ ( n ) |
| Inserção / exclusão no final |
N / D | Θ (1) | Θ (1) | ||
| Inserção / exclusão no meio |
N / D | Θ ( n ) | pesquisa + Θ (1) |
||
| procurar | Θ ( n ) | Θ ( n ) | Θ ( n ) | Θ ( log n ) | Θ ( 1 ) a Θ ( n ) |
| Espaço de armazenamento adicional em comparação com a matriz |
0 | 0, Θ ( n ) | Θ ( n ) | Θ ( n ) | Θ ( n ) |
| Acesso a qualquer / item aleatório | Θ (1) | Θ (1) | Θ ( n ) | Θ ( n ) | Θ ( n ) |
Veja também
literatura
- Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed: Fundamentos de estruturas de dados em C . International Thomson Publishing, Bonn 1994, ISBN 3-929821-00-1 .
- Chris Okasaki: Estruturas de dados puramente funcionais . Cambridge University Press, Cambridge 1999, ISBN 0-521-66350-4
- Thomas Ottmann, Peter Widmayer: Algoritmos e Estruturas de Dados . 4ª edição. Spectrum Academic Publishing House, Heidelberg 2002, ISBN 3-8274-1029-0 .
- Hanan Samet: Fundamentos de Estruturas de Dados Multidimensionais e Métricas. Elsevier, Amsterdam 2006, ISBN 0-12-369446-9
- Niklaus Wirth : Algoritmos e estruturas de dados em Pascal . 5ª edição. Teubner, Stuttgart 2000, ISBN 3-519-22250-7
- Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures . Ed.: Springer. Springer, Berlin Heidelberg 2014, ISBN 978-3-642-05471-6 .
Evidência individual
- ^ Dan Schmidt The Perl Journal 1999: Construindo um Hash melhor
- ↑ Assumindo que a lista vinculada lembra um ponteiro da posição final dos dados, caso contrário, o final da lista deve primeiro ser determinado com o tempo necessário Θ ( n ).
- ↑ Gerald Kruse. Notas da aula do CS 240 ( página não está mais disponível , pesquise nos arquivos da web ) Informação: O link foi automaticamente marcado como defeituoso. Verifique o link de acordo com as instruções e, em seguida, remova este aviso. : Listas vinculadas mais: Compensações de complexidade ( página não está mais disponível , pesquise em arquivos da web ) Informação: O link foi automaticamente marcado como defeituoso. Verifique o link de acordo com as instruções e, em seguida, remova este aviso. . Juniata College. Primavera de 2008.
- ↑ Supondo que um buffer seja reservado para expansões.
