Estrutura de dados
Keywords: Estrutura de dados, Algoritmo
| Conteúdo |
Introdução
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 como 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 de
Estruturas de dados clássicas
Listas lineares
Listas lineares são as estruturas mais simples e de manipulação mais fácil. Geralmente armazenam elementos de mesmo tipo que estão relacionados entre si. Ex: registros de clientes, contas bancárias, etc. As listas lineares podem ser alocadas de forma estática (alocação sequencial) ou dinâmica (listas encadeadas). Operações que geralmente estão disponíveis: inserção, remoção, busca, ordenação, modificação de elementos e concatenação.
Pilha
As pilhas são estruturas LIFO (last in, first out), ou seja, os dados que foram inseridos por último na pilha serão os primeiros a serem retirados. Existem duas funções clássicas para pilhas que são a PUSH e a POP, que inserem e retiram dados da pilha, respectivamente.
Fila
As filas são estruturas FIFO (first in, first out), que foram inseridos no inicio são os primeiros a sair.
Á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 (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).
Árvores Binarias
Dado que o objectivo básico de uma estrutura de dados é armazenar informação, cada nó da árvore deve conter um elemento a guardar (por exemplo, um inteiro, um objecto da classe Ponto, uma string, …). No caso particular de uma árvore binária, em que cada nó tem no máximo dois filhos, cada nó tem de ter algum modo de se relacionar com os seus potenciais dois filhos. Deste modo, na implementação que se vai propor, define-se um nó com base: (1) no elemento a guardar; (2) num apontador para o nó esquerdo (o seu endereço em memória) (3) num apontador para o nó direito (o seu endereço em memória)