Várias estruturas de dados complexas podem ser criadas utilizando simultaneamente structs e ponteiros. Uma destas estruturas é a lista encadeada. Uma lista encadeada é uma seqüência de structs, que são os nós da lista, ligados entre si através de ponteiros. Esta seqüência pode ser acessada através de um ponteiro para o primeiro nó, que é a cabeça da lista. Cada nó contém um ponteiro que aponta para a struct que é a sua sucessora na lista. O ponteiro da última struct da lista aponta para NULL, indicando que se chegou ao final da lista. Esta estrutura de dados é criada dinamicamente na memória (utiliza-se malloc() e free()), de modo que se torna simples introduzir nós nela, retirar nós, ordenar os nós, etc. Não vamos entrar em detalhes sobre todos os algoritmos que poderíamos criar em uma lista encadeada, pois isto geralmente é feito em cursos de algoritmos e estruturas de dados, não se incluindo no escopo deste curso. Aqui, veremos somente formas de se criar uma lista encadeada em C e também maneiras simples de percorrer esta lista.
Supondo que queiramos criar uma lista encadeada para armazenar os produtos disponíveis em uma loja. Poderíamos criar um nó desta lista usando a seguinte struct:
struct Produto {
int codigo; /* Codigo do produto */
double preco; /* Preco do produto */
struct Produto *proximo; /* Proximo elemento da lista
encadeada de Produtos */
};
Note que esta struct possui, além dos campos de dados
codigo e preco, um campo adicional que é um ponteiro para uma struct do tipo Produto. É
este campo que será utilizado para apontar para o próximo nó da lista encadeada. O
programa a seguir faz uso desta struct, através de um novo tipo criado por um typedef,
para criar uma lista de produtos de uma loja:
#include <stdio.h>
#include <stdlib.h>
/* Estrutura que será usada para criar os nós da lista */
typedef struct tipo_produto {
int codigo;
/*
Codigo do produto */
double preco;
/*
Preco do produto */
struct tipo_produto *proximo; /* Proximo elemento da
lista encadeada de Produtos */
} TProduto;
/* Prototipos das funcoes para inserir e listar produtos */
void inserir(TProduto **cabeca);
void listar (TProduto *cabeca);
int main()
{
TProduto *cabeca = NULL; /*
Ponteiro para a cabeca da lista */
TProduto *noatual;
/* Ponteiro
a ser usado para percorrer a lista no momento de desalocar seus elementos*/
char q;
/*
Caractere para receber a opcao do usuario */
do {
printf("\n\nOpcoes: \nI -> para inserir
novo produto;\nL -> para listar os produtos; \nS -> para sair \n:");
scanf("%c", &q);
/* Le a opcao do usuario */
switch(q) {
case 'i': case 'I':
inserir(&cabeca); break;
case 'l': case 'L':
listar(cabeca); break;
case 's': case 'S':
break;
default:
printf("\n\n Opcao nao valida");
}
fflush(stdin); /* Limpa o
buffer de entrada */
} while ((q != 's') && (q != 'S') );
/* Desaloca a memoria alocada para os elementos da lista */
noatual = cabeca;
while (noatual != NULL)
{
cabeca = noatual->proximo;
free(noatual);
noatual = cabeca;
}
}
/* Lista todos os elementos presentes na lista encadeada */
void listar (TProduto *noatual)
{
int i=0;
while( noatual != NULL) /* Enquanto nao chega no fim
da lista */
{
i++;
printf("\n\nProduto numero %d\nCodigo: %d
\nPreco:R$%.2lf", i, noatual->codigo, noatual->preco);
noatual = noatual->proximo;
/* Faz noatual apontar para o proximo no */
}
}
/* Funcao para inserir um novo no, ao final da lista */
void inserir (TProduto **cabeca)
{
TProduto *noatual, *novono;
int cod;
double preco;
printf("\n Codigo do novo produto: ");
scanf("%d", &cod);
printf("\n Preco do produto:R$");
scanf("%lf", &preco);
if (*cabeca == NULL) /* Se ainda nao existe nenhum
produto na lista */
{
/* cria o no cabeca */
*cabeca = (TProduto *)
malloc(sizeof(TProduto));
(*cabeca)->codigo = cod;
(*cabeca)->preco = preco;
(*cabeca)->proximo = NULL;
}
else
{
/* Se ja existem elementos na lista, deve percorre-la ate' o seu final e inserir o novo
elemento */
noatual = *cabeca;
while(noatual->proximo != NULL)
noatual =
noatual->proximo; /* Ao final do while, noatual aponta para o ultimo
no */
novono = (TProduto *)
malloc(sizeof(TProduto));/* Aloca memoria para o novo no */
novono->codigo = cod;
novono->preco = preco;
novono->proximo = NULL;
noatual->proximo = novono;
/* Faz o ultimo no apontar para o novo no */
}
}
É interessante notar que, no programa anterior não existe limite para o número de produtos que se vai armazenar na lista. Toda vez que for necessário criar um novo produto, memória para ele será alocada e ele será criado no final da lista. Note que a função inserir recebe o endereço do ponteiro cabeça da lista. Qual a razão disto? A razão é que o endereço para o qual a cabeça da lista aponta poderá ser modificado caso se esteja inserindo o primeiro elemento na lista. Tente entender todos os passos deste programa, pois ele possui várias das características presentes em programas que manipulam listas encadeadas. Também é importante notar que várias outras estruturas de dados complexas podem ser criadas com structs contendo ponteiros que apontam para outras structs.
AUTO AVALIAÇÃO
Crie uma struct para descrever restaurantes. Os campos devem armazenar o nome do restaurante, o endereço, o tipo de comida (brasileira, chinesa, francesa, italiana, japonesa, etc) e uma nota para a cozinha (entre 0 e 5). Crie uma lista encadeada com esta struct e escreva um programa que:
a) Insira um novo restaurante na lista;
b) Leia uma lista de restaurantes a partir de um arquivo;
c) Grave a lista de restaurantes para um arquivo;
d) Liste todos os restaurantes na tela;
e) Liste os restaurantes com cozinha com nota superior a um determinado valor, determinado pelo usuário;
f) Liste todos os restaurantes com determinado tipo de comida, determinado pelo usuário.
Curso de C do CPDEE/UFMG - 1996 - 1999