Estrutura de dados

Estruturas de dados e algoritmos são temas fundamentais da ciência da computação, sendo que são utilizados nas mais diversas áreas e com os mais diferentes propósitos. Algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente caracterizam uma estrutura de dados. São a organização e os métodos que manipulam determinada estrutura que lhe conferem singularidade. A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução trivial. O estudo das estruturas de dados está em constante desenvolvimento (assim como o de algoritmos), apesar disso existem estruturas clássicas que têm se mostrado padrões.

Estruturas de dados clássicas

Vectores ou arrays

Vectores, ou arrays, são estruturas de dados lineares e estáticas, isto é, são compostas por um número fixo (finito) de elementos de um determinado tipo de dados. O tempo de acesso aos elementos de um vetor é muito rápido, sendo considerado constante: os elementos são acessados pelo seu índice no vetor. Porém, a remoção de elementos pode ser custosa se não for desejável que haja espaços "vazios" no meio do vetor, pois nesse caso é necessário "arrastar" de uma posição todos os elementos depois do elemento removido.

Essa é uma estrutura muito recomendada para casos em que os dados armazenados não mudarão, ou pouco mudarão, através do tempo.

Lista

Uma Lista é uma estrutura de dados linear. Uma lista ligada é linear e dinâmica, composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula.

Pilha

As pilhas são estruturas baseadas no princípio LIFO (last in, first out), onde os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.

Fila

As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila.

Árvores

Uma árvore é uma estrutura de dados em que cada elemento tem zero ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

(1) uma estrutura vazia (uma árvore vazia);

(2) um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).

Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são comumente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.

Árvores Binárias

Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos. Existem também Árvore de busca binária e seu balanceamento através de árvores AVL.

Tabela de hashing

Estruturas de dados | Ciência da computação

Gourt Home::Gourt :: Estrutura de dados