Estrutura de Dados

Estruturas de dados são formas genéricas de se estruturar informação de modo a serem registradas e processadas pelo computador. 

Alguns exemplos: 

• lista ordenada; 
• vetores;
• pilhas;
• listas; 
• árvores; 
• grafos; etc. 

Contudo estas só adquirem significado quando associadas a um conjunto de operações, que visam, de um modo geral, manipulá-las (algoritmos).

Listas, Pilhas e Filas

Agora vamos ver um pouco sobre algumas estruturas de dados. 

LISTAS

• Estrutura linear;
• Podem ser concatenadas para formar apenas uma ou divididas;
• Adequadas para aplicações nas quais não é possível prever a demanda por memória, logo o espaço de memória é proporcional ao número de elementos da mesma;
• Uteis para manipulação simbólica, gerência de memória, simulação e compiladores;
• Para trabalhar com listas geralmente são necessárias as seguintes operações: 

1. Criar lista vazia;
2. Inserir Elemento;
3. Retirar Elemento;
4. Localizar Elemento;
5. Ordenar. 

Nas listas devemos guardar o encadeamento dos elementos, o que é feito guardando junto com a informação de cada elemento um ponteiro para o próximo elemento. 

Exemplos de algoritmos para as operações básicas com listas usando C:

Struct lista
{
Int info;
Struct lista* prox;
o };
Typedef struct lista Lista;

Lista * cria (void)
{
Return NULL;
}

Lista * insere (Lista * l, int i)
{
Lista * Novo=(Lista*) malloc (sizeof(Lista));
Novo->info=i;
Novo->prox=l;
Return Novo;
}
  
int vazia (Lista* l)
{
if (l ==NULL)
return 1;
else
return 0;
}

Lista* busca (Lista* l, int v)
{
Lista* p;
for (p=l; p!=NULL; p=p->prox)
if (p->info == v)
return p;
return NULL; /* não achou o elemento */
}

void imprime (Lista* l)
{
Lista* p; /* variável auxiliar para percorrer a lista */
for (p = l; p != NULL; p = p->prox)
printf(“info = %d\n”, p->info);
}

Lista* retira (Lista* l, int v) {
Lista* ant = NULL; /* ponteiro para elemento anterior */
Lista* p = l; /* ponteiro para percorrer a lista*/
/* procura elemento na lista, guardando anterior */
while (p != NULL && p->info != v) {
ant = p;
p = p->prox;
}
/* verifica se achou elemento */
if (p == NULL)
return l; /* não achou: retorna lista original */
/* retira elemento */
if (ant == NULL) {
/* retira elemento do inicio */
l = p->prox;
}
else {
/* retira elemento do meio da lista */
ant->prox = p->prox;
}
free(p);
return l;
} 

Há ainda as listas circulares e as duplamente encadeadas.

PILHAS

• É uma lista linear em que todas as inserções e retiradas são feitas em apenas um extremo da lista, o topo. (Ex.: Pilha de livros);
• Lifo (Last in, First Out – Ultimo que entra é o primeiro que sai);
• Ideal para o processamento de estruturas aninhadas de profundidade imprevisível;
• Utilizadas para implementar a recursividade;
• Operações: Pilha Vazia, Empilha, Desempilha e Tamanho.

Exemplos de algoritmos de implementação de pilha usando vetor em C: 

#define MAX 100
struct pilha {
int n;
float vet[MAX];
};

Pilha* cria (void)
{
Pilha* p = (Pilha*) malloc(sizeof(Pilha));
p->n = 0; /* inicializa com zero elementos */
return p;
}

void Empilha (Pilha* p, float v)
{
if (p->n == MAX) { /* capacidade esgotada */
printf("Capacidade da pilha estourou.\n");
exit(1); /* aborta programa */
}
/* insere elemento na próxima posição livre */
p->vet[p->n] = v;
p->n++;
}

float Desempilha (Pilha* p)
{
float v;
if (vazia(p)) {
printf("Pilha vazia.\n");
exit(1); /* aborta programa */
}
/* retira elemento do topo */
v = p->vet[p->n-1];
p->n--;
return v;
}

int vazia (Pilha* p)
{
return (p->n == 0);
}

void libera (Pilha* p)
{
free(p);

}

FILAS

• Lista linear em que todas as inserções são realizadas em um extremo da lista e todas as retiradas no extremo oposto. Ex.: Lista de Espera;
• Fifo (First in, first out – Primeiro que entra é o primeiro que sai);
• Utilizadas para regular a ordem na qual tarefas devem receber processamentos segundo a ordem “1º que chega” é o “1º atendido”. Ex.: Sistema Operacional;
• Operações: criar, inserir, retirar, verificar se está vazio, liberar a fila.

Algoritmos básicos de implementação da fila usando vetor em C:

#define N 50
struct fila {
int ini, fim;
float vet[N];
};
Fila* cria (void)
{
Fila* f = (Fila*) malloc(sizeof(Fila));
f->ini = f->fim = 0; /* inicializa fila vazia */
return f;
}

void insere (Fila* f, float v)
{
if (incr(f->fim) == f->ini) { /* fila cheia: capacidade esgotada */
printf("Capacidade da fila estourou.\n");
exit(1); /* aborta programa */
}
/* insere elemento na próxima posição livre */
f->vet[f->fim] = v;
f->fim = incr(f->fim);
}

float retira (Fila* f)
{
float v;
if (vazia(f)) {
printf("Fila vazia.\n");
exit(1); /* aborta programa */
}
/* retira elemento do início */
v = f->vet[f->ini];
f->ini = incr(f->ini);
return v;
}
int vazia (Fila* f)
{
return (f->ini == f->fim);

}

Obs: Filas e Pilhas podem ser implementadas utilizando Listas, pois como sabemos os vetores limitam a quantidade de memória, e alterá-las em tempo de execução seria muito caro, logo a utilização de listas torna as mesmas dinâmicas.