Estrutura de dados

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Uma árvore binária é uma estrutura de dados.

Na Ciência da computação, uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.[1] [2]

Diferentes tipos de estrutura de dados são adequadas a diferentes tipos de aplicação e algumas são altamente especializadas, destinando-se a algumas tarefas específicas. Por exemplo, as B-trees são particularmente indicadas para a implementação de bases de dados , enquanto que a implementação de compiladores geralmente requer o uso de tabela de dispersão para a busca de identificadores.

Estruturas de dados e algoritmos são temas fundamentais da ciência da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente, caracterizam uma forma, uma estrutura de dados. A organização e os métodos para manipular essa estrutura é que lhe conferem singularidade e diminuição do espaço ocupado pela memória RAM, além de tornar o código-fonte do programa mais enxuto e simplificado.

As estruturas de dados são chamadas tipos de dados compostos que dividem-se em homogêneos (vetores e matrizes) e heterogêneos (registros):

  • As estruturas homogêneas são conjuntos de dados formados pelo mesmo tipo de dado primitivo.
  • As estruturas heterogêneas são conjuntos de dados formados por tipos de dados primitivos diferentes (campos do registro) em uma mesma estrutura.

A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução relativamente simples. O estudo das estruturas de dados está em constante desenvolvimento (assim como o de algoritmos), mas, apesar disso, existem certas estruturas clássicas que se comportam como padrões.

Estruturas de dados clássicas[editar | editar código-fonte]

Vetores ou arrays[editar | editar código-fonte]

VetoresPB, ou vectoresPE 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: o acesso aos elementos é feito 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[editar | editar código-fonte]

Uma Lista é uma estrutura de dados linear. Uma lista ligada, também chamada de encadeada, é linear e dinâmica, é composta por nós que apontam para o próximo elemento da lista, o ultimo elemento apontará para nulo. Para compor uma lista encadeada, basta guardar seu primeiro elemento. loja 1 loja2

Fila[editar | editar código-fonte]

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 DEQUEUE só pode ser aplicada se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.

Pilha[editar | editar código-fonte]

A pilha é uma estrutura de dados baseada no princípio LIFO (LAST in, FIRST out), na qual os dados que foram inseridos primeiros na pilha serão os últimos a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH(Empilha), que insere um dado no topo da pilha, e POP(Desempilha), que remove o item no topo da pilha.

Árvores[editar | editar código-fonte]

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

  1. uma estrutura (uma árvore);
  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 habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.

Árvores binárias[editar | editar código-fonte]

Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos. São muito utilizadas como estruturas de buscas, como árvores de busca binária e árvores AVL.

Grafo[editar | editar código-fonte]

Deque[editar | editar código-fonte]

Tabela de hashing[editar | editar código-fonte]

Referências

  1. Paul E. Black (ed.), Data structure. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology, 2004. Versão online .
  2. Data structure. Encyclopædia Britannica (2009) Online


Livro: Estruturas de Dados, Autor: Paulo Veloso/Cleusio dos Santos/Paulo Azeredo/Antonio Furtado, 1984, Editora Campus, ISBN 85-7001-352-3

Ver também[editar | editar código-fonte]