Em Ciência da computação, uma
Abaixo uma definição básica das principais estrutura de dados. Nos próximos dias estarei postando na área Códigos do site o código-fonte para essas estruturas.
Estruturas de dados clássicas
Vetores, 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.
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, com exceção do último, que não aponta para ninguém. Para compor uma lista encadeada, basta guardar seu primeiro elemento.
As Pilhas são estruturas baseadas no princípio LIFO (last in, first out), na qual 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.
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 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.
Uma Àrvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:
- uma estrutura (uma árvore);
- um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
- Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)
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.
Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por “setas”.
Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar uma mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais económico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.
Outro exemplo da utilização de grafos são as redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.
Outro exemplo banal é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade. Grafos têm sido utilizados para representar o formalismo das Redes Complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido (Ver mais nesse link).