Vimos, até então, como implementar nossas listas ligadas (pilhas, filas etc) usando ponteiros simples. Contudo, havia um problema. Considere o código abaixo:
#include <stdio.h>
#include <stdlib.h>
#define coord struct s_coord
struct s_coord {
int x;
int y;
};
#define impacto struct s_impacto
struct s_impacto {
coord local;
int mag;
impacto *prox;
};
/*
Cria uma lista vazia. Retorna ponteiro para seu início.
*/
impacto *inicializa() {
return(NULL);
}
/*
Retorna o número de elementos da lista.
Param:
cab - a cabeça da lista
*/
int tamanho(impacto *cab) {
impacto *p; /* auxiliar */
int n = 0; /* número de elementos da lista */
/* aponto p para a cabeça da lista */
p = cab;
/* corro a lista, incrementando n */
while (p) {
p = p->prox;
n++;
}
/* retorno o número de elementos da lista */
return(n);
}
/*
Inclui um elemento na n-ésima posição da lista. Se a posição for ilegal, não faz nada.
Retorna a nova cabeça da lista, ou NULL em caso de erro.
Param:
cab - a cabeça da lista
n - o número da posição
pos - as coordenadas da queda
mag - a magnitude do impacto
*/
impacto *inclui(impacto *cab, int n, coord pos, int mag) {
impacto *p; /* auxiliar */
impacto *q; /* o novo elemento */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= (tamanho(cab) + 1))) {
/* aloco o novo elemento */
if (!(q = (impacto *)malloc(sizeof(impacto)))) return(NULL);
/* abasteço seus valores */
q->local = pos;
q->mag = mag;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* faço a cabeça ser o próximo elemento de q */
q->prox = cab;
/* retorno a nova cabeça */
return(q);
}
/* n não é 1, aponto p para a cabeça */
p = cab;
/* vou ao (n-1)-ésimo elemento */
for (i=1; i < (n-1); i++) p = p->prox;
/* faço o n-ésimo elemento ser o próximo de q */
q->prox = p->prox;
/* faço q ser o próximo elemento do (n-1)-ésimo elemento */
p->prox = q;
}
/* retorno a cabeça da lista */
return(cab);
}
/*
Imprime a lista na tela.
Param:
cabeca - o início da lista
*/
void imprime(impacto *cabeca) {
impacto *p; /* auxiliar */
/* aponto p para o início da lista */
p = cabeca;
/* imprimo cada elemento da lista */
while (p) {
printf("\nCoordenadas: %d, %d\n",p->local.x,p->local.y);
printf("Magnitude: %d\n",p->mag);
p = p->prox;
}
}
int main() {
impacto *cabeca; /* cabeça da lista */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
int i; /* contador */
/* inicio a lista */
cabeca = inicializa();
/* pego as 5 quedas */
for (i=1; i<6; i++) {
printf("Entre uma coordenada (x y): ");
scanf("%d %d", &queda.x, &queda.y);
printf("Qual a magnitude (0 a 10): ");
scanf("%d", &mag);
/* incluo o dado na lista, na posição i */
if (!(cabeca = inclui(cabeca, i, queda, mag))) {
printf("Erro na inclusão da nota na lista\n");
exit(1);
}
/* mostro o estado atual da lista */
imprime(cabeca);
}
}
A função inclui nos apresenta 2 problemas básicos. O primeiro é o fato de, se a posição for ilegal, ela simplesmente não fazer nada e não nos avisar do fato. Com isso, podemos tentar incluir um elemento em posição ilegal e achar que ele foi incluído, quando não foi. Uma vez que a função não nos avisa do fato, vamos acabar descobrindo da pior maneira - quando verificarmos os dados. E aí fica realmente difícil achar o problema.
O segundo problema ocorre na alocação. Note que se ela não conseguir alocar espaço para um único elemento ela retorna NULL. Ou seja, ao fazermos:
if (!(cabeca = inclui(cabeca, i, queda, mag))) {
printf("Erro na inclusão da nota na lista\n");
exit(1);
}
cabeca será NULL, caso o elemento não possa ser alocado. Isso faz simplesmente com que percamos a posição na memória de nossa lista, ou seja, perdemos a lista na memória. No caso acima, isso não importa muito, já que saímos do programa caso isso aconteça. Mas e se quiséssemos fazer outra coisa, como pedir ao usuário para liberar mais memória, por exemplo? A única forma seria fazer:
int main() {
impacto *cabeca; /* cabeça da lista */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
int i; /* contador */
impacto *p; /* auxiliar */
/* inicio a lista */
cabeca = inicializa();
/* pego as 5 quedas */
for (i=1; i<6; i++) {
printf("Entre uma coordenada (x y): ");
scanf("%d %d", &queda.x, &queda.y);
printf("Qual a magnitude (0 a 10): ");
scanf("%d", &mag);
/* incluo o dado na lista, na posição i */
p = inclui(cabeca, i, queda, mag);
if (!p) {
/* faz o que precisa */
}
else /* alocou legal */
cabeca = p;
/* mostro o estado atual da lista */
imprime(cabeca);
}
}
Mas isso não parece muito legal. Outra maneira mais elegante seria fazer com que inclui retorne 1 em caso de sucesso e 0 em caso de erro. Então somente teríamos que testar a saída de inclui. Mas inclui precisa mudar a cabeça da lista, como faríamos isso? Como com qualquer outra variável.
Quanto tínhamos que mudar o valor de uma variável que foi passada como parâmetro, como fazíamos? Usávamos ponteiro, ou seja, passávamos o endereço na memória desta variável, para podermos modificá-la, como abaixo:
void mudaValor(int *a) {
/* mudo o valor da variável passada como parâmetro */
*a = 3;
}
int main() {
int b = 2;
printf("%d\n",b); /* imprime 2 */
mudaValor(&b);
printf("%d\n",b); /* imprime 3 */
}
Agimos da mesma forma com ponteiros. Se queremos mudar o valor de um ponteiro, ou seja, mudar para onde ele está apontando, precisamos passar seu endereço à função. O que acontece quando fazemos:
int main() {
int a;
int *p;
a = 2;
p = &a;
*p = 3;
}
Na memória funciona mais ou menos assim: primeiro alocamos um espaço para a variável "a" grande o suficiente para guardar um inteiro, e cujo endereço o compilador conhece (o 0xff1 na figura):
Em seguida alocamos memória para a variável "p", grande o suficiente para caber um endereço, e cujo endereço o compilador também conhece:
Ao fazermos "a = 2" dizemos ao computador para guardar 2 na região de memória correspondente à variável "a". Isso só é possível porque sabemos o endereço de "a":
Com "p = &a" guardamos em p o endereço na memória da variável "a".
Assim podemos dizer que "p aponta para a", ou, em uma notação simbólica:
Finalmente, com "*p = 3", vamos em "p", pegamos o endereço de memória que lá está guardado, vamos àquela posição de memória e guardamos o valor 3 lá. Ou seja, fazemos com que a região da memória apontada por "p" receba o valor 3. Note que isso também muda o valor de "a":
Até aí isso deve ser algo que você já sabe. Agora o que talvez você não saiba: posso usar o esquema acima com qualquer variável, inclusive ponteiros. Considere o código abaixo:
int main() {
int a = 2;
int b = 5;
int *p;
int **pp;
p = &a;
*p = 3;
pp = &p;
**pp = 4;
*pp = &b;
*p = 8;
**pp = 7;
}
O que essa complicação toda faz? Inicialmente, alocamos espaço para a s 4 variáveis ("a", "b", "p" e "pp"). "a" e "b" serão grandes o suficiente para guardarem valores inteiros, sendo que de cara armazenamos os valores 2 e 5 nelas, respectivamente. Da mesma forma, "p" e "pp" serão grandes o suficiente para guardarem endereços:
Quando fazemos "p = &a" guardamos o endereço da variável "a" na variável "p" (como acima):
e ao fazermos "*p = 3", guardamos o valor 3 na região de memória apontada por "p", ou seja, na região de memória cujo endereço guardamos em "p":
E agora, o que acontece quando fazemos "pp = &p"? Antes de mais nada, como "pp" é definido? "int **pp". Isso significa que "pp" é ponteiro para ponteiro de inteiro, ou seja, ele guardará o endereço de uma variável que guarda, por sua vez, o endereço de um inteiro na memória. Dessa forma, ao fazermos "pp = &p", estamos armazenando o endereço da variável "p" em "pp":
Isso na nossa notação fica:
Quando fazemos "**pp = 4" é o mesmo que fazermos "*(*pp) = 4". Ou seja, primeiro visitamos a região da memória apontada por "pp" (com "*pp"), pegando o valor lá guardado (no caso, o valor de "p", ou seja, um endereço). Então visitamos a região da memória correspondente a este endereço (com "**pp"), e lá armazenamos o valor 4. Dessa forma mudamos o valor da variável apontada por "p", ou seja, "a":
Ao fazermos "*pp = &b", vamos à região da memória apontada por "pp", ou seja, a região da memória cujo endereço guardamos em "pp" (no caso, "p"), e guardamos lá o endereço da variável "b":
Na prática o que fizemos? O mesmo que "p = &b", ou seja, fizemos "p" apontar para "b". Para provar isso, o que acontece quando fazemos "*p = 8"? Vamos à posição de memória apontada por p e armazenamos o valor 8 lá. Ou seja, armazenamos o valor 8 na variável "b":
Finalmente, o que acontece quando fazemos "**pp = 7;"? Visitamos a região da memória apontada por "pp" (com "*pp"), pegando o valor lá guardado (no caso, o valor de "p", ou seja, um endereço). Então visitamos a região da memória correspondente a este endereço (com "**pp"), e lá armazenamos o valor 4. Dessa forma mudamos o valor da variável apontada por "p", ou seja, "b":
Estude um pouco o programa acima até ter certeza de que entendeu como a coisa funciona.
Agora, e se a variável apontada fosse uma estrutura? Agimos de modo semelhante:
#include <stdio.h>
#include <stdlib.h>
#define coord struct s_coord
struct s_coord {
int x;
int y;
};
int main() {
coord c1;
coord c2;
coord *p;
coord **pp;
c1.x = 2;
c1.y = 3;
c2.x = 9;
c2.y = 10;
printf("c1 = (%d,%d)\n", c1.x, c1.y);
printf("c2 = (%d,%d)\n", c2.x, c2.y);
p = &c1;
p->x = 4;
(*p).y = 5; /* alternativa a p->x */
printf("c1 = (%d,%d)\n", c1.x, c1.y);
printf("c2 = (%d,%d)\n", c2.x, c2.y);
pp = &p;
(*pp)->x = 7;
(*pp)->y = 8;
printf("c1 = (%d,%d)\n", c1.x, c1.y);
printf("c2 = (%d,%d)\n", c2.x, c2.y);
*pp = &c2;
printf("c1 = (%d,%d)\n", c1.x, c1.y);
printf("c2 = (%d,%d)\n", c2.x, c2.y);
printf("c2 = (%d,%d)\n", p->x, p->y);
printf("c2 = (%d,%d)\n", (*pp)->x, (*pp)->y);
}
A saída deste programa é:
c1 = (2,3) c2 = (9,10) c1 = (4,5) c2 = (9,10) c1 = (7,8) c2 = (9,10) c1 = (7,8) c2 = (9,10) c2 = (9,10) c2 = (9,10)
Repare como é feito: "*pp" é um endereço para uma estrutura. Quando fazemos "(*pp)->x = 7", pegamos o endereço na memória da estrutura ("*pp"), visitamos esta região da memória e, então, vamos ao local correspondente ao campo x dessa região, lá armazenando o valor 7.
Ao fazermos "*pp = &c2" estamos guardando o endereço de "c2" na região da memória apontada por "pp", ou seja, em "p". Dessa forma estamos fazendo "p" apontar para "c2", o que é comprovado pelos 3 últimos printf.
Agora nosso próximo passo é pegar a função inclui, abaixo:
/*
Inclui um elemento na n-ésima posição da lista. Se a posição for ilegal, não faz nada.
Retorna a nova cabeça da lista, ou NULL em caso de erro.
Param:
cab - a cabeça da lista
n - o número da posição
pos - as coordenadas da queda
mag - a magnitude do impacto
*/
impacto *inclui(impacto *cab, int n, coord pos, int mag) {
impacto *p; /* auxiliar */
impacto *q; /* o novo elemento */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= (tamanho(cab) + 1))) {
/* aloco o novo elemento */
if (!(q = (impacto *)malloc(sizeof(impacto)))) return(NULL);
/* abasteço seus valores */
q->local = pos;
q->mag = mag;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* faço a cabeça ser o próximo elemento de q */
q->prox = cab;
/* retorno a nova cabeça */
return(q);
}
/* n não é 1, aponto p para a cabeça */
p = cab;
/* vou ao (n-1)-ésimo elemento */
for (i=1; i < (n-1); i++) p = p->prox;
/* faço o n-ésimo elemento ser o próximo de q */
q->prox = p->prox;
/* faço q ser o próximo elemento do (n-1)-ésimo elemento */
p->prox = q;
}
/* retorno a cabeça da lista */
return(cab);
}
e modificá-la de modo que ela retorne 1 em caso de sucesso, 0 em caso de posição ilegal, e -1 em caso de erro de alocação, sempre atualizando a cabeça da lista. Conforme o que foi discutido, a nova função fica:
/*
Inclui um elemento na n-ésima posição da lista. Retorna 1 em caso de sucesso, 0 se a posição for ilegal e -1 caso não consiga alocar espaço para o novo elemento.
Param:
pcab - ponteiro para a cabeça da lista
n - o número da posição
pos - as coordenadas da queda
mag - a magnitude do impacto
*/
int inclui(impacto **pcab, int n, coord pos, int mag) {
impacto *p; /* auxiliar */
impacto *q; /* o novo elemento */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= (tamanho(cab) + 1))) {
/* aloco o novo elemento */
if (!(q = (impacto *)malloc(sizeof(impacto)))) return(-1);
/* abasteço seus valores */
q->local = pos;
q->mag = mag;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* faço a cabeça ser o próximo elemento de q */
q->prox = *pcab;
/* atualizo a cabeça */
*pcab = q;
/* retorno sucesso */
return(1);
}
/* n não é 1, aponto p para a cabeça */
p = *cab;
/* vou ao (n-1)-ésimo elemento */
for (i=1; i < (n-1); i++) p = p->prox;
/* faço o n-ésimo elemento ser o próximo de q */
q->prox = p->prox;
/* faço q ser o próximo elemento do (n-1)-ésimo elemento */
p->prox = q;
/* retorno sucesso (note que a cabeça não precisou ser atualizada) */
return(1);
}
/* deu erro */
return(0);
}
Vamos ver o programa como um todo:
#include <stdio.h>
#include <stdlib.h>
#define coord struct s_coord
struct s_coord {
int x;
int y;
};
#define impacto struct s_impacto
struct s_impacto {
coord local;
int mag;
impacto *prox;
};
/*
Cria uma lista vazia. Retorna ponteiro para seu início.
*/
impacto *inicializa() {
return(NULL);
}
/*
Retorna o número de elementos da lista.
Param:
cab - a cabeça da lista
*/
int tamanho(impacto *cab) {
impacto *p; /* auxiliar */
int n = 0; /* número de elementos da lista */
/* aponto p para a cabeça da lista */
p = cab;
/* corro a lista, incrementando n */
while (p) {
p = p->prox;
n++;
}
/* retorno o número de elementos da lista */
return(n);
}
/*
Inclui um elemento na n-ésima posição da lista. Retorna 1 em caso de sucesso, 0 se a posição for ilegal e -1 caso não consiga alocar espaço para o novo elemento.
Param:
pcab - ponteiro para a cabeça da lista
n - o número da posição
pos - as coordenadas da queda
mag - a magnitude do impacto
*/
int inclui(impacto **pcab, int n, coord pos, int mag) {
impacto *p; /* auxiliar */
impacto *q; /* o novo elemento */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= (tamanho(*pcab) + 1))) {
/* aloco o novo elemento */
if (!(q = (impacto *)malloc(sizeof(impacto)))) return(-1);
/* abasteço seus valores */
q->local = pos;
q->mag = mag;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* faço a cabeça ser o próximo elemento de q */
q->prox = *pcab;
/* atualizo a cabeça */
*pcab = q;
/* retorno sucesso */
return(1);
}
/* n não é 1, aponto p para a cabeça */
p = *pcab;
/* vou ao (n-1)-ésimo elemento */
for (i=1; i < (n-1); i++) p = p->prox;
/* faço o n-ésimo elemento ser o próximo de q */
q->prox = p->prox;
/* faço q ser o próximo elemento do (n-1)-ésimo elemento */
p->prox = q;
/* retorno sucesso (note que a cabeça não precisou ser atualizada) */
return(1);
}
/* deu erro */
return(0);
}
/*
Imprime a lista na tela.
Param:
cabeca - o início da lista
*/
void imprime(impacto *cabeca) {
impacto *p; /* auxiliar */
/* aponto p para o início da lista */
p = cabeca;
/* imprimo cada elemento da lista */
while (p) {
printf("\nCoordenadas: %d, %d\n",p->local.x,p->local.y);
printf("Magnitude: %d\n",p->mag);
p = p->prox;
}
}
int main() {
impacto *cabeca; /* cabeça da lista */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
int i; /* contador */
/* inicio a lista */
cabeca = inicializa();
/* pego as 5 quedas */
for (i=1; i<6; i++) {
printf("Entre uma coordenada (x y): ");
scanf("%d %d", &queda.x, &queda.y);
printf("Qual a magnitude (0 a 10): ");
scanf("%d", &mag);
/* incluo o dado na lista, na posição i */
switch (inclui(&cabeca, i, queda, mag)) {
case 0:
printf("Posição inválida\n");
break;
case -1:
printf("Não conseguiu alocar\n");
break;
default:
printf("Tudo ok\n");
}
/* mostro o estado atual da lista */
imprime(cabeca);
}
}
Da mesma forma, a exclusão de um elemento na lista fica:
#include <stdio.h>
#include <stdlib.h>
#define coord struct s_coord
struct s_coord {
int x;
int y;
};
#define impacto struct s_impacto
struct s_impacto {
coord local;
int mag;
impacto *prox;
};
/*
Cria uma lista vazia. Retorna ponteiro para seu início.
*/
impacto *inicializa() {
return(NULL);
}
/*
Retorna o número de elementos da lista.
Param:
cab - a cabeça da lista
*/
int tamanho(impacto *cab) {
impacto *p; /* auxiliar */
int n = 0; /* número de elementos da lista */
/* aponto p para a cabeça da lista */
p = cab;
/* corro a lista, incrementando n */
while (p) {
p = p->prox;
n++;
}
/* retorno o número de elementos da lista */
return(n);
}
/*
Inclui um elemento na n-ésima posição da lista. Retorna 1 em caso de sucesso, 0 se a posição for ilegal e -1 caso não consiga alocar espaço para o novo elemento.
Param:
pcab - ponteiro para a cabeça da lista
n - o número da posição
pos - as coordenadas da queda
mag - a magnitude do impacto
*/
int inclui(impacto **pcab, int n, coord pos, int mag) {
impacto *p; /* auxiliar */
impacto *q; /* o novo elemento */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= (tamanho(*pcab) + 1))) {
/* aloco o novo elemento */
if (!(q = (impacto *)malloc(sizeof(impacto)))) return(-1);
/* abasteço seus valores */
q->local = pos;
q->mag = mag;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* faço a cabeça ser o próximo elemento de q */
q->prox = *pcab;
/* atualizo a cabeça */
*pcab = q;
/* retorno sucesso */
return(1);
}
/* n não é 1, aponto p para a cabeça */
p = *pcab;
/* vou ao (n-1)-ésimo elemento */
for (i=1; i < (n-1); i++) p = p->prox;
/* faço o n-ésimo elemento ser o próximo de q */
q->prox = p->prox;
/* faço q ser o próximo elemento do (n-1)-ésimo elemento */
p->prox = q;
/* retorno sucesso (note que a cabeça não precisou ser atualizada) */
return(1);
}
/* deu erro */
return(0);
}
/*
Imprime a lista na tela.
Param:
cabeca - o início da lista
*/
void imprime(impacto *cabeca) {
impacto *p; /* auxiliar */
/* aponto p para o início da lista */
p = cabeca;
/* imprimo cada elemento da lista */
while (p) {
printf("\nCoordenadas: %d, %d\n",p->local.x,p->local.y);
printf("Magnitude: %d\n",p->mag);
p = p->prox;
}
}
/*
Apaga elemento na posição n da lista. Retorna 1 se ok e 0 em caso de posição inválida.
Param:
pcab - ponteiro para a cabeça da lista
n - a posição a ser apagada
*/
int exclui(impacto **pcab, int n) {
impacto *p; /* auxiliar */
impacto *q; /* auxiliar */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= tamanho(*pcab))) {
/* aponto p para o início da lista */
p = *pcab;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* aponto a cabeça para o segundo elemento na lista */
*pcab = (*pcab)->prox;
/* mato a antiga cabeça */
free(p);
/* retorno ok */
return(1);
}
/* n não é 1, vou ao n-ésimo elemento com p */
for (i=1; i < n; i++) p = p->prox;
/* aponto q para a cabeça */
q = *pcab;
/* vou ao (n-1)-ésimo elemento com q */
for (i=1; i < (n-1); i++) q = q->prox;
/* faço o próximo elemento de q ser o elemento que está após p */
q->prox = p->prox;
/* elimino p */
free(p);
/* retorno ok */
return(1);
}
/* deu erro */
return(0);
}
int main() {
impacto *cabeca; /* cabeça da lista */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
int i; /* contador */
/* inicio a lista */
cabeca = inicializa();
/* pego as 5 quedas */
for (i=1; i<6; i++) {
printf("Entre uma coordenada (x y): ");
scanf("%d %d", &queda.x, &queda.y);
printf("Qual a magnitude (0 a 10): ");
scanf("%d", &mag);
/* incluo o dado na lista, na posição i */
switch (inclui(&cabeca, i, queda, mag)) {
case 0:
printf("Posição inválida\n");
break;
case -1:
printf("Não conseguiu alocar\n");
break;
default:
printf("Tudo ok\n");
}
/* mostro o estado atual da lista */
imprime(cabeca);
}
/* excluo o 3o elemento */
if (exclui(&cabeca, 3))
printf("Exclusão feita com sucesso\n");
else
printf("Posição inválida\n");
/* imprimo a lista */
imprime(cabeca);
}
Copyright© 2005 Norton Trevisan Roman - Direitos Autorais Reservados.