Estrutura de Dados e Algoritmos

O que é Estrutura de Dados?

Estrutura de dados é uma estrutura organizada de dados na memória de um computador ou em qualquer dispositivo de armazenamento, de forma que os dados possam ser utilizados de forma correta.

As estruturas encontram muitas aplicações no desenvolvimento de sistemas, sendo que algumas são altamente especializadas e utilizadas em tarefas específicas.

Usando as estruturas adequadas através de algoritmos, podemos trabalhar com grande ou pequenas quantidades de dados, como aplicações em bancos de dados ou serviços de busca.

O que é Algoritmo?

Um algoritmo é um conjunto de instruções estruturadas e ordenadas, seu objetivo é realizar uma tarefa ou operação específica.

Os algoritmos são utilizados para manipular dados nas estruturas de várias formas, como por exemplo: inserir, excluir, procurar e ordenar dados.

Em uma estrutura de dados devemos saber como realizar um determinado conjunto de operações básicas, como por exemplo:

• Inserir Dados
• Excluir Dados
• Localizar um elemento
• Percorrer todos os itens constituintes da estrutura para visualização
• Classificar, que se resume em colocar os itens de dados em uma determinada ordem (numérica, alfabética, etc.)

Principais estruturas de dados

• Vetores e Matrizes
• Registro
• Lista
• Pilha
• Fila
• Árvore
• Tabela Hash
• Grafos
  

Vetores e Matrizes

Vetores e Matrizes ou Arrays são estruturas de dados simples que podem auxiliar quando há muitas variáveis do mesmo tipo em um algoritmo.

Para conhecer algumas estruturas de dados, pode ser utilizado o Portugol.

Vetor

Vetor ou array uni-dimensional é uma variável que armazena várias variáveis do mesmo tipo. É uma estrutura de dados indexada, que pode armazenar uma determinada quantidade de valores do mesmo tipo.

Exemplo de Vetores:

• Abra o Portugol e crie um novo arquivo.
• Digite a linha de comando dentro da funcao inicio(): inteiro numeros[] = {39, 45, 54, 55} e a linha escreva(numeros[4])
• Será apresentado um erro pois não existe o índice 4, o vetor se inicia em zero.
• Para exibir todos os elementos do vetor podemos utilizar o comando:

para (inteiro posicao = 0; posicao <= 3; posicao++){ escreva(numeros[posicao], " ") }

Do lado direito do Portugol Webstudio é possível ver alguns exemplos de código.

Matriz

Matriz ou array multi-dimensional é um vetor de vetores. É um vetor que possui duas ou mais dimensões.

Registros

Um registro é uma estrutura que fornece um formato especializado para armazenar informações em memória.

Enquanto Arrays nos permitem armazenar vários dados de um único tipo de dados, o recurso de Registro nos permite armazenar mais de um tipo de dados.

Um registro é composto por campos que especificam cada uma das informações que o compõem.

Um registro de um cliente, por exemplo, podem conter os campos: cpf, nome, endereço e contato, e são tipos de dados diferentes.

Toda estrutura de registro tem um nome (ex: livro), e seus campos podem ser acessados por meio deo uso do operador ponto (.). Por exemplo, para acessar o preço de um livro, poderíamos utilizar a seguinte declaração: livro.preco

Listas

Estrutura de Dados do tipo lista, armazena dados de um determinado tipo em uma ordem específica.

A diferença entre listas e arrays é a de que as listas possuem tamanho ajustável, enquanto arrays possuem tamanho fixo.

Existem dois tipos de listas: Ligadas e Duplamente ligadas.

Lista ligada: Na estrutura do tipo lista existem os nós onde cada um dos nós conhece o valor que está sendo armazenado em seu interior além de conhecer o elemento posterior a ele: por isso ela é chamada de "lista ligada", pois os nós são amarrados com essa indicação de qual é o próximo nó.

Lista Duplamente Ligada:As listas duplamente ligadas constituem uma variação das listas ligadas. A grande diferença das listas duplamente ligadas para as listas ligadas é que elas são bidirecionais. Vimos que, naturalmente, não conseguimos "andar para trás" em listas ligadas, pois os nós de uma lista ligada sabem somente quem é o próximo elemento. Nas listas duplamente ligadas, os nós sabem quem é o próximo elemento e também quem é o elemento anterior, o que permite a navegação reversa.

Pilhas

Uma Pilha é uma estrutura de dados que serve como uma coleção de elementos, e permite o acesso a somente um item de dados armazenado. O acesso aos itens de uma pilha é restrito - somente um item pode ser lido ou removido por vez.

Dois tipos de pilhas: LIFO ou UEPS e FIFO ou PEPS

LIFO ou UEPS: A estrutura do tipo PILHA LIFO (Last in First Out) ou UEPS (Último que Entra Primeiro que Sai), apresenta o seguinte critério: o primeiro elemento a ser retirado é o último que tiver sido inserido.

FIFO ou PEPS: A estrutura do tipo PILHA FIFO (First in First Out) ou PEPS (Primeiro que Entra Primeiro que Sai), apresenta o seguinte critério: o primeiro elemento a ser retirado é o primeiro que tiver sido inserido.

Filas

A estrutura do tipo Fila admite remoção de elementos e inserção de novos sujeita à seguinte regra de operação: O elemento removido é o que está na estrutura há mais tempo ou seja, o primeiro objeto inserido na fila é também o primeiro a ser removido seguindo o conceito FIFO.

Árvore

É uma estrutura de dados que organiza seus elementos de forma hierárquica, onde existe um elemento que fica no topo da árvore, chamado de raiz e existem os elementos subordinados a ele, que são chamados de nós ou folhas.

Para fazer uma busca num vetor precisamos percorrer o vetor do indice 0 até encontrar o que procura. Se o vetor está ordenado a busca é feita até que um determinado elemento seja encontrado ou para quando o próximo elemento deveria está a direita do item procurado. Quando um vetor não está ordenado, para fazer uma busca é preciso percorrer todo o vetor ou até encontrar o que procura. A busca num vetor muito grande é demasiadamente lenta, por isso foi criado a estrutura de dados chamado de Árvore (tree)

Numa estrutura tipo arvore a busca começa pelo meio que é a folha ou nó raíz e percorre os outros nós.

Tabela Hash

Uma tabela hash, de dispersão ou espalhamento é uma estrutura de dados especial, que associa chaves de pesquisa a valores. É uma generalização da idéia de array, porém utiliza uma função denominada Hashing para espalhar os elementos, fazendo com que os mesmos fiquem de forma não ordenada dentro do "array" que define a tabela.

A tabela hash permite a associação de "valores" a "chaves". Valores: é a posição ou índice onde o elemento se encontra, enquanto Chave: é parte da informação que compõe o elemento a ser manipulado.

Espalhar facilita a busca na estrutura de dados, pois a partir de uma chave podemos acessar de forma rápida uma posição do "array".

Grafos

Grafos são estruturas que permitem programar a relação entre objetos. Os objetos são os vértices ou "nós" do grafo e os relacionamentos são as arestas.