Até agora vimos somente como incluir um elemento em uma lista ligada de dados simples. Vamos ver então como fazemos listas ligadas de estruturas.
É oficial! O fim do mundo se aproxima! Desde o início da noite uma chuva de meteoros de proporções bíblicas está caindo sobre o planeta. De várias partes do mundo surgem dados relatando as posições e magnitude das quedas (em uma escala de 0 a 10). Cabe a você registrá-las para posterior análise... se houver um amanhã.
E como faremos isso? A idéia é simples, à medida que os relatos vão chegando, adicionamos cada dado em uma lista. Então, precisaremos de um nó mais ou menos assim:
Vamos agora definir uma estrutura para representar este nó:
#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;
};
Ótimo! Já temos a estrutura de dados. Como vimos antes, precisamos de uma função para inicializar a lista. A nossa função padrão servirá:
#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;
};
impacto *inicializa() {
return(NULL);
}
Agora nos falta definir a estratégia que seguiremos. À primeira vista, nos parece mais direto irmos armazenando os dados na ordem em que chegam, e depois irmos analisando-os na ordem inversa (ou seja, os mais novos primeiro). Então precisamos de uma estrutura do tipo pilha.
Uma pilha é uma estrutura de dados que, pasmem, funciona como uma pilha!
Pense numa pilha de livros. É assim que ela funciona. Se queremos por mais um livro na pilha, onde colocamos? No topo! E se queremos tirar um livro, de onde tiramos? Do topo. Ou seja, seu funcionamento é mais ou menos assim:
Como representamos computacionalmente isso? Com uma lista ligada:
Ou
Então, uma pilha nada mais é do que uma lista ligada que tem como característica o fato de que, se queremos incluir um elemento na lista, temos de incluí-lo no início desta, e se queremos tirar um elemento da lista, tiramos do início desta.
Dessa forma, uma pilha tem as seguintes funções:
Note que não há como eu tirar um elemento do meio da pilha. É como nossa pilha de livros, para retirar um livro do meio, tenho que desempilhar todos os que estão acima. Da mesma forma, para tirar um dado do meio da pilha, tenho que desempilhar os que estão antes dele.
Vejamos, agora, funções para criação, empilhamento e desempilhamento. Para empilhar um elemento no topo da pilha, basta incluir o novo elemento no início da lista. Isso é exatamente o que fizemos na aula passada:
#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 pilha vazia. Retorna ponteiro para seu topo.
*/
impacto *inicializa() {
return(NULL);
}
/*
Inclui um elemento no topo da pilha. Retorna ponteiro para o novo topo, ou NULL em caso de erro.
Param:
topo - topo da pilha
pos - a posição da queda
mag - a magnitude do impacto
*/
impacto *empilha(impacto *topo, coord pos, int mag) {
impacto *p; /* auxiliar */
/* crio o novo nó */
if (!(p = (impacto *)malloc(sizeof(impacto)))) {
/* houve problemas na criação do nó */
return(NULL);
}
/* criei o nó, faço o topo ser o elemento seguinte a ele */
p->prox = topo;
/* carrego os dados nele */
p->local = pos;
p->mag = mag;
/* retorno o novo topo da pilha */
return(p);
}
/*
Imprime a pilha na tela.
Param:
topo - o topo da pilha
*/
void imprime(impacto *topo) {
impacto *p; /* auxiliar */
/* aponto p para o topo da pilha */
p = topo;
/* imprimo cada elemento da pilha */
while (p) {
printf("coordenadas: %d, %d\n",p->local.x,p->local.y);
printf("Magnitude: %d\n",p->mag);
p = p->prox;
}
}
int main() {
impacto *topo; /* topo da pilha */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
char resp; /* indica se continua o laço */
impacto *p; /* auxiliar */
/* inicio a lista */
topo = inicializa();
/* pego as quedas */
do {
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 pilha */
if (!(topo = empilha(topo, queda, mag))) {
printf("Erro na inclusão da nota na lista\n");
exit(1);
}
/* pergunto se há mais dados */
printf("Continua? (s/n) ");
scanf(" %s",&resp);
} while (resp == 's');
/* imprimo a pilha na tela */
imprime(topo);
}
Agora vamos desempilhar. Desempilhar implica retirar um elemento do topo da pilha. E como fazemos isso? Suponha a pilha:
Apontamos para o elemento abaixo do topo da pilha:
Eliminamos o elemento do topo (possivelmente retornando seus valores):
Finalmente, atualizamos o ponteiro para o topo da pilha:
Cuidado! Repare que este algoritmo só funciona se a pilha contiver pelo menos um elemento. Sendo assim, antes de usá-lo, você deve sempre testar se a pilha não está vazia. A implementação deste algoritmo é:
/*
Desempilha um elemento. Abastece valor com os dados do elemento desempilhado. Retorna ponteiro para o novo topo da pilha.
Se a pilha estiver vazia retorna NULL (o mesmo valor que retornaria se a pilha contivesse apenas um elemento, ou seja, é ambíguo). No caso da pilha estar vazia, nada é colocado em valor.
Param:
topo - topo da pilha
valor - onde serão armazenados os dados do elemento do topo
*/
impacto *desempilha(impacto *topo, impacto *valor) {
impacto *p;
/* só faço algo se a pilha não estiver vazia */
if (topo) {
/* aponto p para o elemento abaixo do topo */
p = topo->prox;
/* abasteço valor com os dados do topo (também poderíamos copiar campo por campo
da estrutura coord) */
valor->local = topo->local;
valor->mag = topo->mag;
valor->prox = NULL;
/* removo o topo da pilha */
free(topo);
}
/* retorno o novo topo da pilha */
return (p);
}
Novamente, cuidado! Repare que tanto uma lista vazia quanto uma de um único elemento irão retornar a mesma coisa (NULL, o novo topo)? Então. Sempre teste antes de usar esta função. Esse tipo de ambigüidade pode ser removido, se usarmos ponteiros duplos, mas isso complicaria demais nosso modelo nessa fase do curso. Se você tiver curiosidade, veja aqui como ficariam estas funções com ponteiros duplos.
Nosso programa então 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 pilha vazia. Retorna ponteiro para seu topo.
*/
impacto *inicializa() {
return(NULL);
}
/*
Inclui um elemento no topo da pilha. Retorna ponteiro para o novo topo, ou NULL em caso de erro.
Param:
topo - topo da pilha
pos - a posição da queda
mag - a magnitude do impacto
*/
impacto *empilha(impacto *topo, coord pos, int mag) {
impacto *p; /* auxiliar */
/* crio o novo nó */
if (!(p = (impacto *)malloc(sizeof(impacto)))) {
/* houve problemas na criação do nó */
return(NULL);
}
/* criei o nó, faço o topo ser o elemento seguinte a ele */
p->prox = topo;
/* carrego os dados nele */
p->local = pos;
p->mag = mag;
/* retorno o novo topo da pilha */
return(p);
}
/*
Desempilha um elemento. Abastece valor com os dados do elemento desempilhado. Retorna ponteiro para o novo topo da pilha.
Se a pilha estiver vazia retorna NULL (o mesmo valor que retornaria se a pilha contivesse apenas um elemento, ou seja, é ambíguo). No caso da pilha estar vazia, nada é colocado em valor.
Param:
topo - topo da pilha
valor - onde serão armazenados os dados do elemento do topo
*/
impacto *desempilha(impacto *topo, impacto *valor) {
impacto *p;
/* só faço algo se a pilha não estiver vazia */
if (topo) {
/* aponto p para o elemento abaixo do topo */
p = topo->prox;
/* abasteço valor com os dados do topo (também poderíamos copiar campo por campo
da estrutura coord) */
valor->local = topo->local;
valor->mag = topo->mag;
valor->prox = NULL;
/* removo o topo da pilha */
free(topo);
}
/* retorno o novo topo da pilha */
return (p);
}
/*
Imprime a pilha na tela.
Param:
topo - o topo da pilha
*/
void imprime(impacto *topo) {
impacto *p; /* auxiliar */
/* aponto p para o topo da pilha */
p = topo;
/* imprimo cada elemento da pilha */
while (p) {
printf("coordenadas: %d, %d\n",p->local.x,p->local.y);
printf("Magnitude: %d\n",p->mag);
p = p->prox;
}
}
int main() {
impacto *topo; /* topo da pilha */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
char resp; /* indica se continua o laço */
impacto *p; /* auxiliar */
impacto dados; /* o dado desempilhado */
/* inicio a lista */
topo = inicializa();
/* pego as quedas */
do {
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 pilha */
if (!(topo = empilha(topo, queda, mag))) {
printf("Erro na inclusão da nota na lista\n");
exit(1);
}
/* pergunto se há mais dados */
printf("Continua? (s/n) ");
scanf(" %s",&resp);
} while (resp == 's');
/* agora desempilho os dados */
while (topo) {
topo = desempilha(topo, &dados);
printf("Desempilhou:\n");
printf(" Coordenadas: %d, %d\n", dados.local.x, dados.local.y);
printf(" Magnitude: %d\n", dados.mag);
printf("\nA pilha agora é:\n");
imprime(topo);
}
}
Note, no programa acima, que sempre testo se a pilha está vazia (laço while) antes de desempilhar algo.
Uma outra estrutura de dados que poderíamos adotar é uma fila. Uma fila é uma lista que tem como característica o fato de que o primeiro elemento a entrar nela é o primeiro a sair. Assim, ela funciona como uma fila comum.
Pense numa fila de banco. Quem será o primeiro a ser atendido? O primeiro que chegou. E onde os que chegam depois devem entrar na fila? No final desta.
Assim é uma fila: se quero retirar um elemento, retiro da frente; se quero incluir, incluo no final da fila. Vale lembrar que, da mesma forma que em uma pilha, em uma fila não posso retirar um elemento do meio da fila, ou lá colocar um.
Note também que retirar o elemento do início da fila é o mesmo que desempilhar do topo da pilha (estamos sempre retirando o primeiro elemento da lista). Ou seja, a função é a mesma! Então, para fila, usaremos a mesma função de inicialização e empilhamento, usadas para pilhas, mudando apenas seus nomes.
A inclusão de um elemento, porém, usa um algoritmo diferente: cada novo elemento deve ser posto ao final da fila. E como fazemos isso? Suponha que temos a seguinte fila:
Criamos o elemento novo:
Com um ponteiro auxiliar, apontamos para o início da fila:
Corremos o ponteiro até o final da fila:
Fazemos o elemento seguinte ao final da fila ser o novo elemento:
Pronto! Agora, e se a fila estiver inicialmente vazia, como abaixo?
Nesse caso, apenas criamos o novo elemento:
E fazemos ele ser o início da fila:
Agora vejamos como implementamos isso:
/*
Inclui um elemento no fim da fila. Retorna ponteiro para o novo início, ou NULL em caso de erro.
Param:
inicio - início da fila
pos - a posição da queda
mag - a magnitude do impacto
*/
impacto *inclui(impacto *inicio, coord pos, int mag) {
impacto *q; /* novo elemento */
impacto *p; /* auxiliar */
/* crio o novo nó */
if (!(q = (impacto *)malloc(sizeof(impacto)))) {
/* houve problemas na criação do nó */
return(NULL);
}
/* carrego os valores no nó */
q->local = pos;
q->mag = mag;
q->prox = NULL;
/* vejo se a lista está vazia */
if (!inicio) {
/* retorno o novo início */
return(q);
}
/* a lista possui algo. Aponto p para o início da fila */
p = inicio;
/* vou ao fim da lista (último elemento) */
while (p->prox) p = p->prox;
/* incluo o novo nó ao final da fila */
p->prox = q;
/* retorno o início da fila */
return(inicio);
}
E nosso programa 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 fila vazia. Retorna ponteiro para seu início.
*/
impacto *inicializa() {
return(NULL);
}
/*
Inclui um elemento no fim da fila. Retorna ponteiro para o novo início, ou NULL em caso de erro.
Param:
inicio - início da fila
pos - a posição da queda
mag - a magnitude do impacto
*/
impacto *inclui(impacto *inicio, coord pos, int mag) {
impacto *q; /* novo elemento */
impacto *p; /* auxiliar */
/* crio o novo nó */
if (!(q = (impacto *)malloc(sizeof(impacto)))) {
/* houve problemas na criação do nó */
return(NULL);
}
/* carrego os valores no nó */
q->local = pos;
q->mag = mag;
q->prox = NULL;
/* vejo se a lista está vazia */
if (!inicio) {
/* retorno o novo início */
return(q);
}
/* a lista possui algo. Aponto p para o início da fila */
p = inicio;
/* vou ao fim da lista (último elemento) */
while (p->prox) p = p->prox;
/* incluo o novo nó ao final da fila */
p->prox = q;
/* retorno o início da fila */
return(inicio);
}
/*
Retira um elemento da fila. Abastece valor com os dados do elemento retirado. Retorna ponteiro para o novo início da fila.
Se a fila estiver vazia retorna NULL (o mesmo valor que retornaria se a fila contivesse apenas um elemento, ou seja, é ambíguo). No caso da fila estar vazia, nada é colocado em valor.
Param:
inicio - inicio da fila
valor - onde serão armazenados os dados do elemento do início
*/
impacto *retira(impacto *inicio, impacto *valor) {
impacto *p;
/* só faço algo se a fila não estiver vazia */
if (inicio) {
/* aponto p para o elemento seguinte ao início */
p = inicio->prox;
/* abasteço valor com os dados do início (também poderíamos copiar campo por campo
da estrutura coord) */
valor->local = inicio->local;
valor->mag = inicio->mag;
valor->prox = NULL;
/* removo o início da fila */
free(inicio);
}
/* retorno o novo início da fila */
return (p);
}
/*
Imprime a fila na tela.
Param:
inicio - o início da fila
*/
void imprime(impacto *inicio) {
impacto *p; /* auxiliar */
/* aponto p para o início da fila */
p = inicio;
/* imprimo cada elemento da fila */
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 *inicio; /* início da fila */
coord queda; /* coordenadas da queda */
int mag; /* magnitude do impacto */
char resp; /* indica se continua o laço */
impacto *p; /* auxiliar */
impacto dados; /* o dado retirado */
/* inicio a fila */
inicio = inicializa();
/* pego as quedas */
do {
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 fila */
if (!(inicio = inclui(inicio, queda, mag))) {
printf("Erro na inclusão da nota na lista\n");
exit(1);
}
/* pergunto se há mais dados */
printf("Continua? (s/n) ");
scanf(" %s",&resp);
} while (resp == 's');
/* agora retiro os dados */
while (inicio) {
inicio = retira(inicio, &dados);
printf("\nRetirou:\n");
printf(" Coordenadas: %d, %d\n", dados.local.x, dados.local.y);
printf(" Magnitude: %d\n", dados.mag);
printf("\nA fila agora é:\n");
imprime(inicio);
}
}
Note que aqui também testamos a fila antes de retirar um elemento. Como, para retirar um elemento da fila, usamos a mesma função de desempilhamento, a função de retirada sofre da mesma ambigüidade.
Uma terceira estratégia seria permitir a inclusão (e retirada) de um dado que esteja em uma determinada posição na lista, generalizando tanto a pilha quanto a fila. Para tal, precisamos de uma função que nos diga o número de elementos contidos na lista, e que será útil mais tarde (note que usamos as mesmas estruturas que antes - a coord e a impacto):
/*
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);
}
Note que, no caso da lista estar vazia (cab == NULL), a função retornará 0, indicando, como deveria ser, que a lista não possui elementos.
Agora sim, vamos incluir um elemento em uma posição determinada na lista. Suponha que temos a seguinte lista:
Suponha que queremos incluir na n-ésima posição (na 4ª, por exemplo), como fazemos? Primeiro, alocamos espaço para o novo elemento:
Colocamos um ponteiro no início da lista (1ª posição):
Andamos até a (n-1)ª posição (a 3ª no nosso caso):
Fazemos o campo prox do novo elemento apontar para o nº elemento da lista, ou seja, para o elemento seguinte ao (n-1)º:
Fazemos o elemento seguinte ao (n-1)º ser o novo elemento:
Pronto! O único cuidado que devemos ter é o de sempre checar se a posição em que vamos colocar o novo elemento é válida. Note que o algoritmo acima funciona bem caso queiramos incluir o novo elemento na última posição, ou seja, na (K+1)ª posição de uma lista de K elemento. Mas, e se quisermos incluir na primeira posição? Aí a coisa complica um pouco, pois não temos como fazer p ir à 0ª posição. Nesse caso, agimos como na pilha:
Alocamos o novo elemento:
Apontamos seu campo prox para o início da lista:
Atualizamos o ponteiro para o início da lista:
O código que implementa o algoritmo acima é:
/*
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);
}
Note que se n estiver fora dos limites, nada será feito - você deve testar isso no programa. Vejamos um exemplo de uso:
#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);
}
}
Note que este programa adiciona 5 elementos à lista, colocando sempre cada elemento no final da lista. Ou seja, o programa implementa uma fila.
Bom, agora que incluímos um elemento em uma posição específica da lista, como fazemos para excluir um elemento de uma determinada posição? Suponha a seguinte lista:
E suponha que queremos eliminar o nº elemento (o 3º, por exemplo). Fazemos um ponteiro p apontar para o 1º elemento da lista:
Movemos ele até o nº elemento, ou seja, até o 3º:
Agora fazemos um ponteiro q também apontar para o início da lista:
Movemos q até o (n-1)º elemento, ou seja, até o 2º elemento:
Fazemos o próximo elemento de q ser o elemento que está após p:
E finalmente, removemos p:
Pronto! Note que aqui simplesmente jogamos fora o elemento, sem retornar seu valor. Se o elemento a ser retirado for o primeiro, agimos como no desempilhamento de um item da pilha. O código para este algoritmo é:
/*
Apaga elemento na posição n da lista. Retorna nova cabeça da lista.
Param:
cab - a cabeça da lista
n - a posição a ser apagada
*/
impacto *exclui(impacto *cab, int n) {
impacto *p; /* auxiliar */
impacto *q; /* auxiliar */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= tamanho(cab))) {
/* aponto p para o início da lista */
p = cab;
/* verifico se a posição é a primeira na lista */
if (n == 1) {
/* aponto a cabeça para o segundo elemento na lista */
cab = cab->prox;
/* mato a antiga cabeça */
free(p);
/* retorno a nova cabeça */
return(cab);
}
/* 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 = cab;
/* 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 a cabeça da lista */
return(cab);
}
Como então faríamos para ler o elemento de uma determinada posição? Simples, basta correr a lista, começando no nó cabeça, até a posição, e então retornar o valor lá contido. No caso abaixo, retornamos um ponteiro para o elemento naquela posição:
/*
Retorna ponteiro para elemento na n-ésima posição da lista, ou NULL se a posição for inválida.
Param:
cab - a cabeça da lista
n - a posição a ser buscada
*/
impacto *busca(impacto *cab, int n) {
impacto *p; /* auxiliar */
int i; /* contador */
/* verifico se a posição é válida */
if ((n > 0) && (n <= tamanho(cab))) {
/* aponto p para o início da lista */
p = cab;
/* corro a lista */
for (i=1; i < n; i++) p = p->prox;
/* estou na posição, retorno o elemento */
return(p);
}
/* a posição é inválida */
return(NULL);
}
Por fim, vamos ver como verificamos se um determinado elemento está na lista, retornando sua posição (ou 0 se não estiver):
/*
Retorna a posição de um elemento na lista, ou 0 se ele não estiver lá.
Param:
cab - a cabeça da lista
dado - o elemento buscado
*/
int posicao(impacto *cab, impacto dado) {
impacto *p; /* auxiliar */
int i; /* contador */
/* aponto para a cabeça da lista */
p = cab;
/* indico que esta é a posição 1 */
i = 1;
/* varro a lista */
while (p) {
/* vejo se é o dado buscado */
if ((p->local.x == dado.local.x) &&
(p->local.y == dado.local.y) &&
(p->mag == dado.mag))
return(i);
/* não é. Vou ao próximo elemento */
p = p->prox;
/* marco a posição do elemento para o qual p aponta */
i++;
}
/* não encontrou */
return(0);
}
Copyright© 2005 Norton Trevisan Roman - Direitos Autorais Reservados.