Estrutura de dados
Origem: Wikipédia, a enciclopédia livre.
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.
Índice |
[editar] Estruturas de dados clássicas
[editar] 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.
[editar] 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.
[editar] 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.
[editar] 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.
A operação ENQUEUE sempre pode ser executada, uma vez que teoricamente uma fila não tem limite. A operação DEQUEUE só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.
[editar] Árvores
Uma árvore é uma estrutura de dados em que cada elemento tem zero ou mais elementos associados, podendo definir-se uma árvore recursivamente como:
- uma estrutura vazia (uma árvore vazia);
- 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.
[editar] Á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.
