mauro1855
I'm cool cuz I Fold
Uma dúvida que aparece frequentemente por aqui pelo fórum: O que são, ou como funcionam, listas?
Bem... Imaginem um vector. Quando declaram o vector têm de dizer o tamanho dele à partida... Mas e se não souberem isso? Se eu for o vosso patrão ou professor e vos pedisse um programa que armazene números, mas sem saber quantos números vou armazenar? 5 números? 100 números? 100000 números? Não sei.
Quer dizer, posso continuar a usar vectores se estiver constantemente a realocar o espaço do vector, mas isso não é propriamente elegante, e mesmo tirando a questão da elegância, normalmente recorrem-se sempre a outro tipo de estruturas em detrimento dos vectores nestes casos...
As listas é um caso de uma estrutura dinâmica usada nesses casos... Mas atenção que uma lista não serve simplesmente para substituir um vector, tem muitas outras aplicações, umas mais complexas que outras, em que algumas dessas aplicações dependem mesmo da existência de uma lista para funcionarem correctamente... De qualquer forma, aprender o conceito básico deste tipo de estruturas é essencial na vossa passagem pelo C.
Então mas, muito basicamente, o que é uma lista simplesmente ligada?
É uma estrutura que armazena um ou mais valores (pode ser um inteiro, um char, três floats, ou qualquer coisa) e ainda um ponteiro que aponta para um próximo elemento dessa estrutura...
É como eu ter um quadrado que guarda um valor, aponta para outro quadrado que guarda outro valor, que aponta para outro quadrado e por aí a fora:
O final da lista aponta para NULL.
No que respeita ao código, uma lista tem várias funções auxiliares, que permitem eliminar elementos da lista, inserir valores, eliminar a lista, etc etc...
E pronto, está explicado. Fica aqui o código de um exemplo de aplicação de uma lista simplesmente ligada de inteiros.
Este programa permite:
- Inserir um inteiro (no fim da lista - a lista inicialmente está vazia).
- Procurar um inteiro e dizer se ele faz parte da lista.
- Imprimir todos os inteiros armazenados na lista.
- Eliminar inteiros/blocos da lista.
O que devem observar neste programa é o código, sendo que o funcionamento do programa serve apenas como demonstração das funções usadas...
Bem... Imaginem um vector. Quando declaram o vector têm de dizer o tamanho dele à partida... Mas e se não souberem isso? Se eu for o vosso patrão ou professor e vos pedisse um programa que armazene números, mas sem saber quantos números vou armazenar? 5 números? 100 números? 100000 números? Não sei.
Quer dizer, posso continuar a usar vectores se estiver constantemente a realocar o espaço do vector, mas isso não é propriamente elegante, e mesmo tirando a questão da elegância, normalmente recorrem-se sempre a outro tipo de estruturas em detrimento dos vectores nestes casos...
As listas é um caso de uma estrutura dinâmica usada nesses casos... Mas atenção que uma lista não serve simplesmente para substituir um vector, tem muitas outras aplicações, umas mais complexas que outras, em que algumas dessas aplicações dependem mesmo da existência de uma lista para funcionarem correctamente... De qualquer forma, aprender o conceito básico deste tipo de estruturas é essencial na vossa passagem pelo C.
Então mas, muito basicamente, o que é uma lista simplesmente ligada?
É uma estrutura que armazena um ou mais valores (pode ser um inteiro, um char, três floats, ou qualquer coisa) e ainda um ponteiro que aponta para um próximo elemento dessa estrutura...
É como eu ter um quadrado que guarda um valor, aponta para outro quadrado que guarda outro valor, que aponta para outro quadrado e por aí a fora:
O final da lista aponta para NULL.
No que respeita ao código, uma lista tem várias funções auxiliares, que permitem eliminar elementos da lista, inserir valores, eliminar a lista, etc etc...
E pronto, está explicado. Fica aqui o código de um exemplo de aplicação de uma lista simplesmente ligada de inteiros.
Este programa permite:
- Inserir um inteiro (no fim da lista - a lista inicialmente está vazia).
- Procurar um inteiro e dizer se ele faz parte da lista.
- Imprimir todos os inteiros armazenados na lista.
- Eliminar inteiros/blocos da lista.
O que devem observar neste programa é o código, sendo que o funcionamento do programa serve apenas como demonstração das funções usadas...
Código:
/* Função: Exemplo de Aplicação de Listas Simplesmente Ligadas de Inteiros
* Propósito: Educacional
* Autor: mauro1855 (Zwame.pt)
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _lista{
int valor;
struct _lista * next;
}lista;
lista * cria_lista(){
lista * novo = (lista*)malloc(sizeof(lista));
novo->next = NULL;
return novo;
}
int procura(lista * original, int valor){
lista * aux = original->next;
while(aux != NULL && valor != aux->valor){
aux=aux->next;
}
if(aux != NULL)
return 1;
else
return 0;
}
void inserir(lista * original, int inteiro){
lista * base = original;
lista * aux = original->next;
lista * novo;
if(procura(original, inteiro)){
printf("O inteiro já se encontra na lista. Nenhuma operação efectuada\n");
}else{
while(aux!= NULL){
aux=aux->next;
base=base->next;
}
novo=(lista*)malloc(sizeof(lista));
novo->valor = inteiro;
novo->next = aux;
base->next = novo;
printf("O número foi inserido\n");
}
}
void imprimir(lista * original){
lista * aux = original->next;
if(aux == NULL){
printf("A lista está vazia\n");
}else{
printf("Os valores da lista, por ordem com que foram introduzidos, são: \n");
while(aux!= NULL){
printf("%d\n", aux->valor);
aux=aux->next;
}
}
}
void eliminar(lista * original, int inteiro){
lista * aux = original->next;
lista * base = original;
while(aux!= NULL && aux->valor!=inteiro){
aux=aux->next;
base = base->next;
}
if(aux!= NULL){
base->next=aux->next;
free(aux);
printf("Valor removido\n");
}else{
printf("O Valor não pode ser removido pois não se encontra na lista\n");
}
}
int main(){
int opcao, numero;
lista * estrutura;
estrutura = cria_lista();
printf("*** Funcionamento de Listas de Inteiros ***\n");
printf("Seleccione uma operação: \n");
printf("1 - Inserir inteiro na lista \n");
printf("2 - Imprimir valores da lista \n");
printf("3 - Procurar valor na lista \n");
printf("4 - Eliminar valor da lista\n");
printf("5 - Sair\n");
while(true){
printf("\nIndique o número da operação: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Introduza o inteiro a inserir: ");
scanf("%d", &numero);
inserir(estrutura, numero);
break;
case 2:
imprimir(estrutura);
break;
case 3:
printf("Qual o valor que deseja procurar? ");
scanf("%d", &numero);
if(procura(estrutura, numero))
printf("O valor encontra-se na lista\n");
else
printf("O valor não se encontra na lista\n");
break;
case 4:
printf("Indique o valor da lista a eliminar: ");
scanf("%d", &numero);
eliminar(estrutura, numero);
break;
case 5:
return 0;
default:
printf("Opção Inválida\n");
}
}
}
Última edição:
