Data da última atualização: 24/04/2000
copyright Adriano Cruz 1999
Neste capítulo iremos discutir alguns aspectos de listas e como podemos implementar esta estrutura de dados em C. Não iremos abordar extensivamente este assunto, mas apenas discutir os algoritmos mais importantes e mostrar como eles podem ser implementados em C.
As operações mais frequentes em listas são a busca, inserção e remoção de um determinado elemento. Outras operações que costumam ocorrer são a alteração de um elemento particular da lista, ordenação dos elementos da lista segundo uma determinada chave, procura do último ou do primeiro elemento da lista, etc.
Os elementos da lista podem ser armazenados em posições contíguas da memória e neste caso temos uma lista seqüencial. Podemos também armazenar os elementos em posições quaisquer da memória e neste caso temos de armazenar em cada elemento um indicador de onde está o próximo elemento da lista. Este último método é conhecido como alocação encadeada.
O programa list0201.c mostra
um exemplo de busca em uma lista seqüencial. O algoritmo, contido
na função busca1, é
simples e percorre a lista toda até encontrar o elemento.
A função recebe a lista e o elemento a ser procurado. Note que
o número de elementos na lista n é conhecido pelo
algoritmo.
/* Programa list0201.c */
#include <stdio.h>
#define MAX 4
struct Taluno {
char nome[40];
unsigned long int dre;
};
int busca1 ( struct Taluno t[], unsigned long int );
void le ( struct Taluno t[]);
void imprime ( struct Taluno t[]);
void main ()
{
int aluno;
unsigned long dre;
char linha[80];
struct Taluno turma[MAX];
le (turma); /* le dados da turma de MAX alunos */
imprime (turma); /* imprime dados para verificar se correto */
/* uso sscanf, mais seguro que scanf */
puts("Qual o DRE a procurar? "); gets(linha);
sscanf(linha, "%lu", &dre);
aluno = busca1 (turma, dre);
if (aluno == -1)
puts("Nao ha aluno com este dre.");
else
printf("O aluno com dre %lu chama-se %s\n",
turma[aluno].dre, turma[aluno].nome);
exit(0);
}
void le (struct Taluno t[]) {
int i;
char linha[80];
for (i=0; i<MAX; i++) {
puts("Nome ? "); gets (t[i].nome);
puts("DRE ? "); gets(linha);
sscanf(linha, "%lu", &t[i].dre);
}
}
void imprime (struct Taluno t[]) {
int i;
puts("Dados da turma");
for (i=0; i<MAX; i++) {
printf("\nAluno %d\n", i);
printf("Nome = %s\n", t[i].nome);
printf("Nome = %lu\n", t[i].dre);
}
}
/* Busca um elemento na lista L */
int busca1 (struct Taluno turma[], unsigned long int dre) {
int i=0; int aluno=-1;
/* vou assumir que a lista contem MAX alunos */
while (i < MAX) {
if ( turma[i].dre == dre) {
aluno = i;
i=MAX;
}
else i++;
}
return aluno; /* se -1 nao achei, senao indice do aluno */
}
No exemplo anterior são feitas duas comparações a
cada interação ( i < MAX e turma[i].dre ==
dre). Para diminuir o número de comparações vamos
usar um artifício simples: colocar uma posição extra
no final da lista e sempre que for necessário buscar um elemento
na lista, o seu valor será inserido nesta posição extra.
Deste modo sempre acharemos o elemento na lista. No entanto, se o elemento
estiver no final da lista significa que o elemento não foi encontrado.
Observar que a lista passa ter agora uma posição a mais,
que é reservada para o elemento a ser procurado.
O programa list0202.c mostra um exemplo de busca em uma lista seqüencial com uma posição a mais.
/* programa list0202.c */
#include <stdio.h>
/* A lista cabem 4 elementos o elemento 5
e para a elemento a ser procurado
*/
#define MAX 5
struct Taluno {
char nome[40];
unsigned long int dre;
};
int busca1 ( struct Taluno t[], unsigned long int );
void le ( struct Taluno t[]);
void imprime ( struct Taluno t[]);
void main ()
{
int aluno;
unsigned long dre;
char linha[80];
struct Taluno turma[MAX];
le (turma);
imprime (turma);
puts("Qual o DRE a procurar? "); gets(linha);
sscanf(linha, "%lu", &dre);
aluno = busca1 (turma, dre);
if (aluno == -1)
puts("Nao ha aluno com este dre.");
else
printf("O aluno com dre %lu chama-se %s\n",
turma[aluno].dre, turma[aluno].nome);
exit(0);
}
void le (struct Taluno t[]) {
int i;
char linha[80];
for (i=0; i<MAX-1; i++) {
puts("Nome ? "); gets (t[i].nome);
puts("DRE ? "); gets(linha);
sscanf(linha, "%lu", &t[i].dre);
}
}
void imprime (struct Taluno t[]) {
int i;
puts("Dados da turma");
for (i=0; i<MAX-1; i++) {
printf("\nAluno %d\n", i);
printf("Nome = %s\n", t[i].nome);
printf("Nome = %lu\n", t[i].dre);
}
}
/* Busca um elemento na lista L */
int busca1 (struct Taluno turma[], unsigned long int dre) {
int i=0;
turma[MAX-1].dre=dre;
while (turma[i].dre != dre) i++;
if (i != MAX-1 ) return i;
else return -1;
}
Os exemplos anteriores assumiam dois fatos a cerca da lista: a lista está
cheia e desordenada. Quando a lista está ordenada a procura pode
ser interrompida antes de chegar ao fim da lista. Neste algoritmo ao invés
de procurar o elemento, o teste é se o elemento da lista é
menor que o procurado.
O programa list0203.c mostra um exemplo de busca em uma lista ordenada. Para facilitar vamos mostrar apenas a rotina busca_ord que executa este algoritmo, já que todo o restante do programa é similar ao anterior. No arquivo indicado na ligação mostramos o arquivo todo.
/* programa list0203.c */
/* Busca um elemento na lista L */
int busca_ord ( Taluno turma[], unsigned long int dre) {
int i=0;
turma[MAX-1].dre=dre;
while (turma[i].dre < dre) i++;
if (i == (MAX-1) || turma[i].dre != dre ) return -1; /* nao achei. */
else return i;
}
Um algoritmo mais eficiente para busca em uma lista ordenada é o
algoritmo de busca binária. Primeiro o algoritmo procura o elemento
no elemento do meio da tabela. Caso não esteja ele descarta a metade
onde o elemento não está e passa a procurar no meio da metade
que sobrou. O algoritmo vai dividindo a lista em duas metades, sempre descartando
a metade onde o elemento não está.
O programa list0204.c mostra um exemplo de busca binária em uma lista ordenada. Para facilitar vamos mostrar somente a rotina busca_bin que implementa este algoritmo.
/* programa list0204.c */
/* Busca um elemento na lista L */
int busca_bin ( Taluno t[], unsigned long int dre) {
int inf=0, sup=MAX-1, achou=-1, meio;
while (inf <= sup)
{
meio = 0.5*(inf+sup);
if (t[meio].dre == dre)
{
achou=meio;
inf = sup+1;
}
else if (t[meio].dre<dre)
inf = meio+1;
else sup = meio - 1 ;
}
return achou;
}
Agora passaremos a apresentar algoritmos para inserir e remover elementos
de uma lista. Ambos os algoritmos utilizam a rotina de busca para inserir
e remover.
Primeiro vamos apresentar um algoritmo de inserção que não precisa que a lista esteja ordenada. Neste algoritmo o elemento, caso ele não já esteja na lista, é inserido após o último elemento. O algoritmo de remoção move, a partir do último elemento até o elemento seguinte ao que será removido, todos os elementos uma posição para à esquerda.
O exemplo list0206.c abaixo mostra um programa que inclui estes dois algoritmos. Como a lista não estará sempre cheia, já que estaremos removendo e inserindo elementos a todo instante, iremos modificar as rotinas de busca. A modificação adiciona uma variável n que contém o número de elementos na lista no instante em questão. O programa pede ao usuário que indique através de uma letra qual operação deseja executar. As operações possíveis são as seguintes: [I]nserir, [R]emover, [L]istar e [S]air. Para facilitar o entendimento a lista utilizada contém somente números inteiros. O exercício 1, pede a construção de um programa similar a este, apenas modificando a lista de modo que ela contenha uma estrutura mais complexa.
/* programa list0206.c */
/* Busca um elemento na lista L */
#define MAX 5
#include <stdio.h>
#include <ctype.h>
char meu_menu();
void insere(int item[], int *n);
void meu_remove(int item[], int *n);
void listar(int item[], int n);
void ordena(int item[], int n);
int busca_bin (int item[], int n, int x);
void main()
{
int item[MAX];
int n=0, sair=0;
int a, b, t;
char opcao;
do {
opcao = meu_menu();
switch (opcao) {
case 'i':
insere(item, &n);
break;
case 'r':
meu_remove(item, &n);
break;
case 'l':
listar(item, n);
break;
case 's':
sair = 1;
break;
default:
puts("Opcao invalida.");
break;
}
} while (!sair);
}
void ordena(int item[], int n){
int a, b, t;
for (a=1; a<n; ++a)
{
t = item[a];
for (b=a-1; b>=0 && t < item[b]; b--) {
item[b+1]=item[b];
}
item[b+1]=t;
}
}
int busca_bin (int item[], int n, int x) {
int inf=0, sup, meio, achou=-1;
sup = n-1;
while (inf <= sup) {
meio = 0.5*(inf+sup);
if (item[meio]==x) {
achou=meio;
inf = sup + 1;
}
else if (item[meio]<x)
inf = meio+1;
else
sup = meio-1;
}
return achou;
}
void listar (int item[], int n) {
int i;
for (i=0; i<n; i++) printf("elemento %d = %d \n", i, item[i]);
}
char meu_menu () {
char opcao, linha[80];
// limpa();
puts("Qual a sua opcao?");
puts("[L]istar, [I]nserir, [R]emover, [S]air");
gets(linha);
sscanf(linha, "%c", &opcao);
return tolower(opcao);
}
void imprime (int item[])
{
int i;
for (i=0; i<5; i++) {
printf("%d ", item[i]);
}
printf("\n");
}
void insere (int item[], int *n) {
int t;
char linha[80];
printf("Valor a inserir? ");
gets(linha); sscanf(linha, "%d", &t);
if (*n < MAX-1) {
if ( busca_bin(item, *n, t) == -1) {
item[*n] = t;
*n=*n+1;
ordena (item, *n);
}
else puts("Elemento ja existe na tabela.");
}
else puts("Lista ja cheia.");
}
void meu_remove (int item[], int *n) {
int x, indice, i;
char linha[80];
if (*n != 0) {
printf("Valor a remover? ");
gets(linha); sscanf(linha, "%d", &x);
indice = busca_bin(item, *n, x);
printf("Indice = %d\n", indice);
if (indice != -1) {
for (i=indice; i<*n; i++) item[i] = item[i+1];
*n = *n - 1;
}
else puts("Nao existe este elemento.");
}
else puts("Lista vazia");
}
Uma imagem simples pode ilustrar o funcionamento das pilhas. Considere um restaurante onde os clientes do tipo self-service. Neste restaurante, para se servirem, os clientes retiram pratos e os empregados colocam pratos limpos em uma pilha. Observe que os empregados colocam pratos no topo da pilha, o mesmo local de onde os clientes retiram os pratos.
O exemplo list0207.c, listado abaixo, mostra um programa que permite inserir e retirar elementos de uma pilha.
/* programa list0207.c */
/* Exemplo de pilha */
#define MAX 10
#include <stdio.h>
#include <ctype.h>
char meu_menu();
void insere(int item[], int *topo);
void meu_remove(int item[], int *topo);
void listar(int item[], int topo);
void main()
{
int item[MAX];
int topo=-1, sair=0;
char opcao;
do {
opcao = meu_menu();
switch (opcao) {
case 'i':
insere(item, &topo);
break;
case 'r':
meu_remove(item, &topo);
break;
case 'l':
listar(item, topo);
break;
case 's':
sair = 1;
break;
default:
puts("Opcao invalida.");
break;
}
} while (!sair);
}
void listar (int item[], int topo) {
/* Esta rotina esta aqui somente para depuracao */
int i;
for (i=0; i<topo; i++) printf("elemento %d = %d \n", i, item[i]);
}
char meu_menu () {
char opcao, linha[80];
// limpa();
puts("Qual a sua opcao?");
puts("[L]istar, [I]nserir, [R]emover, [S]air");
gets(linha);
sscanf(linha, "%c", &opcao);
return tolower(opcao);
}
void insere (int item[], int *topo) {
int t;
char linha[80];
printf("Valor a inserir? ");
gets(linha); sscanf(linha, "%d", &t);
if (*topo < MAX) {
*topo=*topo+1;
item[*topo] = t;
printf("Topo = %d\n", *topo);
}
else puts("Pilha cheia.");
}
void meu_remove (int item[], int *topo) {
int x;
if (*topo != -1) {
x = item[*topo];
*topo = *topo-1;
printf("Retirei %d da pilha.\n", x);
}
else puts("Lista vazia");
}
Uma pilha pode ser usada para avaliar expressões em notação
polonesa. Nesta notação não são necessários
parênteses para indicar a ordem em que as operações
serão avaliadas. Abaixo mostramos exemplos de expressões
na notação parentizada e em notação polonesa
reversa.
| Parênteses | Polonesa Reversa |
| a + b | a b + |
| (a + b) - c | a b + c - |
| (a + b) * (c -d) | a b + c d - * |
| (a + ( b * c )) | a b c * + |
| (a + b) * c ) | a b + c * |
Observar que cada operando atua sobre os dois elementos que o precedem
na expressão. Caso fossemos colocando estes operandos em uma pilha,
poderíamos sempre que encontrarmos um operador tirar dois operandos
da pilha, executarmos a operação e em seguida guardarmos
o resultado na pilha novamente. A figura pilhaex
mostrada abaixo ilustra o que acontece na pilha caso tenhamos que avaliar
a expressão 3 4 5 * + .
O exemplo list0212.c, listado abaixo, mostra um programa que avalia uma expressão em notação polonesa reversa. Notar que o programa assume que a expressão está gramaticalmente correta.
/* programa list0212.c */
/* Calculo de expressao em notacao polonesa reversa */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 80
#define VERDADE 1
#define FALSO 0
typedef struct {
float item[MAX];
int top;
} pilha;
void imprime(pilha );
float avalia (const char *);
int eOperando (char );
int eOperador (char );
float pop (pilha *);
void push (pilha *, float);
float oper (char , float ,float);
void main()
{
char exp[MAX];
puts("Entre com a expressão ?");
gets(exp);
puts ("Expressão original é "); puts(exp);
printf("O resultado da expressao e %f\n", avalia(exp));
}
float avalia (const char *expr) {
int position;
char symb;
pilha opndstk;
float opnd1, opnd2, value;
opndstk.top = -1; /* pilha vazia */
position = 0; /* primeiro simbolo da expressao */
symb = expr[position];
while (symb != '\0') {
if (eOperando(symb)) {
value = atof(&symb);
push(&opndstk, value);
// imprime(opndstk);
}
else if (eOperador(symb)) {
opnd2 = pop(&opndstk);
opnd1 = pop(&opndstk);
value = oper(symb, opnd1, opnd2);
push(&opndstk, value);
// imprime(opndstk);
}
if (position < MAX) {
position++;
symb = expr[position];
}
} /* fim do while e da avaliacao */
return pop(&opndstk);
}
float oper (char symb, float op1, float op2) {
switch(symb) {
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/':
if (op2) return op1/op2;
else {
puts("Divisao por zero");
exit(1);
}
}
exit(1);
}
float pop (pilha *p) {
if (p->top >= 0) {
p->top--;
return p->item[p->top+1];
}
else {
puts("Underflow");
exit(1);
}
}
void push (pilha *p, float op) {
if (p->top < MAX - 1){
p->top++;
p->item[p->top] = op;
}
else {
puts("Overflow");
exit(1);
}
}
/* Esta funcao serve so para depuracao do programa */
void imprime (pilha p){
int i;
printf("\nPilha = ");
for (i=0; i<=p.top; i++) printf("%f ", p.item[i]);
printf("\n");
}
int eOperador (char c)
{
if (c == '*' || c == '/' || c == '+' || c == '-') return VERDADE;
else return FALSO;
}
int eOperando (char c)
{
if (!eOperador(c) && (c != ' ')) return VERDADE;
else return FALSO;
}
void listar (struct tElemento *ptlista) {
int i=0;
struct tElemento *pont;
pont = ptlista;
while (pont) {
printf("Elemento %d = %d\n", i++, pont->info);
pont = pont->prox;
}
}
Outros algoritmos relevantes em listas são: busca, inserção e
remoção. Para facilitar a busca e localização dos nós a serem
removidos e das posições de inserção modificaremos
a lista para incluir o que costuma ser chamado de nó cabeça. Neste tipo
de lista o primeiro nó não irá conter informação, ele
apenas faz com que o algoritmo de busca não necessite diferenciar o primeiro nó
dos demais. A figura
lista encadeada com nó cabeça ilustra esta lista.
A rotina de busca que iremos mostrar é um algoritmo simples que tem como protótipo ponteiros para ponteiros. O primeiro **ant aponta para o nó anterior ao nó procurado e **ponte aponta para o nó procurado.
void busca ( tElemento *ptlista, int x, tElemento **ant, tElemento **ponte) {
/* *ptlista ponteiro para inicio da lista
x elemento a ser procurado
**ant ponteiro para ponteiro do elemento anterior
**pont ponteiro para ponteiro do elemento procurado
*/
tElemento *ptr;
*ant = ptlista; /* aponta no anterior */
*ponte = NULL; /* aponta no procurado, se nao achar retorna nulo */
ptr = ptlista->prox; /* aponta no procurado */
while (ptr) { /* procura enquanto houver chance */
if (ptr->info < x) { /* ainda nao chegou no no */
*ant = ptr;
ptr = ptr->prox;
}
else { /* pode ser aqui */
if (ptr->info == x) *ponte = ptr; /* achou */
ptr = NULL; /* nao estava na lista */
}
}
}
Esta rotina é parte do programa
list0215.c que inclui rotinas para
remoção e inserção de elementos em uma lista encadeada simples.
A figura remocao de lista encadeada com nó cabeça ilustra o algoritmo de remoção, que tem o código mostrado abaixo.
void remover ( tElemento *ptlista) {
int x;
char linha[80];
tElemento **ant, **pont;
printf("Valor a remover? ");
fgets(linha, 80, stdin); sscanf(linha, "%d", &x);
ant = ( tElemento **) malloc(sizeof ( tElemento *));
pont = ( tElemento **) malloc(sizeof ( tElemento *));
busca (ptlista, x, ant, pont);
if (*pont) {
(*ant)->prox = (*pont)->prox;
printf("Retirei %d\n", (*pont)->info);
free(*pont);
}
else puts("Nao achei na lista.");
}
O algoritmo de inserção tem o seguinte código:
void insere ( tElemento *ptlista) {
tElemento *pt, /* ponteiro para o novo no a inserir */
**ant, /* ponteiro para ponteiro na lista */
**pont; /* ponteiro para ponteiro do no anterior */
int x;
char linha[80];
printf("Valor a inserir? ");
fgets(linha, 80, stdin); sscanf(linha, "%d", &x);
ant = ( tElemento **) malloc(sizeof ( tElemento *));
pont = ( tElemento **) malloc(sizeof ( tElemento *));
busca (ptlista, x, ant, pont);
if (!*pont) {
pt = ( tElemento *) malloc(sizeof( tElemento));
pt->info = x;
pt->prox = (*ant)->prox;
(*ant)->prox = pt;
} else puts("Elemento ja existe na tabela.");
}
O algoritmo de busca em uma lista encadeada pode ser melhorado se
modificarmos a lista de modo que ela passe a ser circular como está
mostrado na figura listcirc abaixo.
Neste caso o algoritmo não tem como testar o final da lista. A solução é armazenar o dado que se está procurando no nó cabeça. Ao término do algoritmo a chave é sempre encontrada, e pode-se descobrir se ela pertencia ou não a lista pelo ponteiro que foi dado como resposta. Caso o ponteiro termine apontando para o nó cabeça, podemos afirmar que o elemento não se encontra na lista.
Os algoritmos de procura, inserção e remoção
em uma lista circular encadeada estão mostrados no programa
list0223.c.
O algoritmo de busca aparece como parte das rotinas de inserção
e remoção. Neste algoritmos primeiro se procura o elemento
depois se decide o que fazer. No algoritmo de busca, caso o elemento já
exista na lista, não há nada a fazer, caso contrário
o ponteiro ant aponta para o elemento
após o qual o novo elemento será inserido. No algoritmo de
remoção, a busca termina apontando para o elemento a ser
removido (ponteiro pont) ou com a indicação que o elemento
não se encontra na lista (pont
apontando para o nó cabeça).
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
struct tElemento {
int info;
struct tElemento *prox;
};
char tela();
struct tElemento *cria_no();
void insere (struct tElemento *, int );
void meu_remove (struct tElemento *, int);
void listar(struct tElemento *);
void main()
{
struct tElemento *ptlista;
char linha[80];
char opcao;
int sair = 0, valor;
ptlista = cria_no();
ptlista->prox=ptlista;
do {
opcao
= tela();
switch
(opcao) {
case 'i':
puts("Qual dado a inserir?"); gets(linha);
sscanf(linha, "%d", &valor);
insere(ptlista, valor);
break;
case 'r':
puts("Qual dado a remover?"); gets(linha);
sscanf(linha, "%d", &valor);
meu_remove(ptlista, valor);
break;
case 'l':
listar(ptlista);
break;
case 's':
sair = 1;
break;
default:
puts("Opcao invalida.");
break;
}
} while (!sair);
}
char tela () {
char opcao, linha[80];
puts("Qual a sua opcao?");
puts("[L]istar, [I]nserir, [R]emover,
[S]air");
gets(linha);
sscanf(linha, "%c", &opcao);
return tolower(opcao);
}
void listar (struct tElemento *ptlista) {
int i=0;
struct tElemento *pont;
pont = ptlista->prox;
while (pont != ptlista) {
printf("Elemento
%d = %d\n", i++, pont->info);
pont
= pont->prox;
}
}
void insere (struct tElemento *ptlista, int valor) {
struct tElemento *pont, *ant, *pt;
/* Aqui esta o algoritmo de busca em uma lista circular */
ant = ptlista; pont = ptlista->prox;
ptlista->info = valor;
while (pont->info < valor) {
ant = pont;
pont = pont->prox;
}
if (pont->info == valor && pont != ptlista)
puts("Elemento ja existe na
tabela.");
else {
pt = cria_no();
pt->info = valor;
pt->prox = pont;
ant->prox = pt;
}
}
void meu_remove (struct tElemento *ptlista, int valor) {
struct tElemento *pont, *ant;
ant = ptlista; pont = ptlista->prox;
ptlista->info = valor;
while (pont->info < valor) {
if (pont->info
< valor) {
ant = pont;
pont = pont->prox;
}
}
if (pont->info == valor && pont != ptlista)
{
ant->prox = pont->prox;
free(pont);
}
else puts("Elemento nao existe na tabela.");
}
struct tElemento *cria_no() {
struct tElemento *pt;
if (( pt = (struct tElemento
*) malloc(sizeof(struct tElemento)) ) == NULL )
{
puts("Nao há espaço.");
exit(1);
}
pt->info = -1;
pt->prox = NULL;
return pt;
}
typedef struct {
char nome[40];
unsigned long int dre;
} Taluno;
typdef struct {
int n; /* numero de elementos na lista em determinado instante */
Taluno alunos[50]; /* lista propriamente dita */
} Tlista;
Solução: list0205.c
.
