Estrutura de dados

Estruturas de dados básicos

Array

O tipo mais simples de estrutura de dados é uma matriz linear. Também conhecida como matriz unidimensional. Um array contém vários valores do mesmo tipo (Inteiro, Flutuador, Cordão, etc.). O acesso a elementos dentro da matriz é muito rápido. Um array é normalmente de tamanho fixo. Após o tamanho do array ser definido no início, pode não ser possível aumentar o tamanho do array sem criar um novo array maior e copiar todos os valores para o novo array. Na informática, uma estrutura de dados de array ou simplesmente um array é uma estrutura de dados que consiste em uma coleção de elementos (valores ou variáveis), cada um identificado por pelo menos um índice ou chave de array. Um array é armazenado para que a posição de cada elemento possa ser computada a partir de seu tuple indexado por uma fórmula matemática.

Por exemplo, um conjunto de 10 variáveis inteiras, com índices de 0 a 9, pode ser armazenado como 10 palavras nos endereços de memória 2000, 2004, 2008, 2036, de modo que o elemento com índice i tenha o endereço 2000 + 4 × i.

Como o conceito matemático de uma matriz pode ser representado como uma grade bidimensional, as matrizes bidimensionais também são às vezes chamadas de matrizes. Em alguns casos, o termo "vetor" é usado na computação para se referir a uma matriz, embora tuplos em vez de vetores sejam o equivalente matemático mais correto. Matrizes são freqüentemente usadas para implementar tabelas, especialmente tabelas de pesquisa; a palavra tabela é às vezes usada como sinônimo de matriz.

As matrizes estão entre as estruturas de dados mais antigas e mais importantes, e são utilizadas por quase todos os programas. Eles também podem ser usados para implementar muitas outras estruturas de dados, tais como listas e strings. Eles exploram efetivamente a lógica de endereçamento dos computadores. Na maioria dos computadores modernos e em muitos dispositivos de armazenamento externo, a memória é uma matriz unidimensional de palavras, cujos índices são seus endereços. Os processadores, especialmente os processadores vetoriais, são freqüentemente otimizados para operações de array.

As matrizes são úteis porque os índices de elementos podem ser computados em tempo de execução. Entre outras coisas, esta característica permite uma única declaração iterativa para processar arbitrariamente muitos elementos de uma matriz. Por essa razão, os elementos de uma estrutura de dados de uma matriz devem ter o mesmo tamanho e devem usar a mesma representação de dados. O conjunto de tuplos de índice válidos e os endereços dos elementos (e, portanto, a fórmula de endereçamento dos elementos) são normalmente, mas nem sempre, fixos enquanto a matriz estiver em uso.

O termo array é freqüentemente usado para significar tipo de dados array, um tipo de dado fornecido pela maioria das linguagens de programação de alto nível que consiste em uma coleção de valores ou variáveis que podem ser selecionados por um ou mais índices computados em tempo de execução. Os tipos de array são freqüentemente implementados por estruturas de array; entretanto, em algumas linguagens, eles podem ser implementados por tabelas de hash, listas vinculadas, árvores de busca ou outras estruturas de dados.

Lista vinculada

Uma estrutura de dados ligada é um conjunto de informações/dados ligados entre si por referências. Os dados são freqüentemente chamados de nós. As referências são muitas vezes chamadas de links ou ponteiros. A partir daqui, as palavras nó e ponteiro serão usadas para estes conceitos.

Em estruturas de dados interligados, os indicadores são apenas desreferenciados ou comparados para igualdade. Assim, as estruturas de dados vinculados são diferentes das arrays, que requerem a adição e subtração de ponteiros.

Listas vinculadas, árvores de busca e árvores de expressão são todas estruturas de dados vinculadas. Elas também são importantes em algoritmos tais como a classificação topológica e a união de conjuntos.

Pilha

Uma pilha é uma estrutura básica de dados que pode ser logicamente pensada como estrutura linear representada por uma pilha ou pilha física real, uma estrutura onde a inserção e a exclusão de itens ocorre em uma extremidade chamada topo da pilha. O conceito básico pode ser ilustrado pensando em seu conjunto de dados como uma pilha de placas ou livros onde você só pode retirar o item superior da pilha para remover coisas da mesma. Esta estrutura é usada em toda a programação.

A implementação básica de uma pilha também é chamada de estrutura "Last In First Out"; no entanto, existem diferentes variações de implementações de pilhas.

Existem basicamente três operações que podem ser realizadas em pilhas. Elas são:

• inserindo ("empurrando") um item em uma pilha
• apagar ("popping") um item da pilha
• exibir o conteúdo do item superior da pilha ("espreitar")

Fila

Uma fila é um tipo de dado abstrato ou uma estrutura de dados linear, na qual o primeiro elemento é inserido de uma extremidade (a "cauda"), e a eliminação do elemento existente ocorre da outra extremidade (a "cabeça"). Uma fila é uma estrutura "First In First Out". "First In First Out" significa que os elementos colocados na fila primeiro sairão primeiro, e os elementos colocados na fila por último sairão por último. Um exemplo de uma fila são filas de pessoas esperando. A primeira pessoa na fila sai primeiro, e a última pessoa na fila sai em último.

O processo de adicionar um elemento a uma fila é chamado de "enfileiramento" e o processo de remover um elemento de uma fila é chamado de "dequeuing".

Gráfico

Um gráfico é um tipo de dado abstrato que se destina a implementar os conceitos de gráfico e hipergrafia a partir da matemática.

Uma estrutura de dados gráficos consiste em um conjunto finito (e possivelmente mutável) de pares ordenados, chamados de bordas ou arcos, de certas entidades chamadas de nós ou vértices. Como na matemática, diz-se que uma borda (x,y) aponta ou vai de x para y. Os nós podem fazer parte da estrutura gráfica, ou podem ser entidades externas representadas por índices inteiros ou referências. Uma estrutura de dados gráficos também pode associar a cada borda algum valor de borda, como uma etiqueta simbólica ou um atributo numérico.

Árvore

A árvore é uma das estruturas de dados avançados mais poderosas. Ela aparece frequentemente em assuntos avançados como Inteligência Artificial (IA) e design. Surpreendentemente, a árvore é importante em uma aplicação muito mais básica - a manutenção de um índice eficiente.

Quando uma árvore é usada há uma grande chance de que um índice seja usado. O tipo mais simples de índice é uma lista ordenada de campos-chave. Uma árvore normalmente tem uma estrutura definida. No caso de uma árvore binária, você pode usar uma busca binária para localizar qualquer item sem ter que olhar para cada item.

O tipo de dados da árvore é um tipo de gráfico, o que significa que muitos algoritmos feitos para atravessar um gráfico também funcionam com uma árvore, entretanto, os algoritmos podem ser muito semelhantes e devem ter um nó inicial dedicado, ou seja, o nó sem outros nós que se ligam a ele.

O problema com uma simples lista ordenada ocorre quando você começa a adicionar novos itens e tem que manter a lista ordenada - pode ser feita de forma razoavelmente eficiente, mas requer algumas modificações. Além disso, um índice linear não é fácil de compartilhar porque todo o índice precisa ser "bloqueado" quando um usuário o edita, enquanto um "ramo" de uma árvore pode ser bloqueado, deixando os outros ramos editáveis por outros usuários (já que não podem ser afetados).

Mesa de haxixe

Uma tabela hash é um array onde cada índice aponta para uma lista vinculada com base em um valor hash. Um valor hash é um valor determinado por uma função hash. Uma função hash determina um valor único com base nos dados que ela está armazenando. Isto permite o acesso aos dados em tempo constante, porque o computador sempre sabe onde procurar.

Cada nó aponta para outro nó.