Estruturas de Dados - Conceitos Básicos

Prévia do material em texto

Kleber's Blog
Blog sobre tecnologia, computação e projetos relacionados
Estrutura de dados – conceitos básicos
Em 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 de modo eficiente. 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.
 
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:
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).
3. 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).