Lista ligada em C, simplesmente não entendo.

[rica mourao 0]

Bom dia a todos,

 

Pessoal estou com dificuldades em entender e implementar um programa sobre lista ligada.

 

Antes de começar a explicar minha dúvida, gostaria de saber na prática quando precisamos utilizar uma lista ligada?

 

Eu não consigo ver uso desse tipó de estrutura na prática =/.

 

Bem vamos ao meu problema:

 

Uma lista ligada nada mais é que um elemento (nó) ligando-se a outro elemento, certo?

 

Para criar um nó eu utilizaria o seguinte código:

 

struct no
{
 int inf;
 struct no *prox;
};

struct no *cria_no(int x)
{
   struct no *inicio;
   inicio=(struct no*) malloc(sizeof (struct no));
   inicio-> inf = x;
   inicio-> prox = NULL;
   return inicio;

}

 

Dentro do main eu criaria uma variavel do tipo struct nó.

Essa váriavel receberia o endereço do novo nó (cria_no).

 

ex:

 

int main()
{
 int i,j;
 struct no *inicio;
 int controle;

 controle = 0;


do
{

   printf("Digite os numeros: ");
   scanf("%d", &j);

  if(j!=0)
  {


   inicio = cria_no(j);

  }

 

Bom criar o nó, inserir o elemento dentro do nó (inf) eu consigo.

 

O problema é que não sei fazer um nó ligar-se ao outro.

 

Por que preciso criar uma lista ligada que receba em cada nó um número inteiro.

Se o usuário digitar zero então devo correr a lista ligada e fazer um printf desses elementos.

 

Me disseram que preciso de um ponteiro que diz quando minha lista começa, a partir desse elemento eu conseguiria correr os outros elementos (o inicio criaria um link com os próximos nós?).

 

Se alguém puder me dar um exemplo didático, ou algum site bom que me ajude a implementar uma lista ligada simples, procurei no google e não encontrei exemplos fáceis de entender.

 

Eu agradeço de coração.

 

Obrigado.

[guidjos 65]

Em primeiro lugar, saiba que é comum não entender este tipo de coisa a princípio. O importante é pensar com calma e de forma clara. Vamos lá.

 

Listas são estruturas de dados importantes porque permitem organizar dados relacionados em memória de forma que seu uso seja prático. A ideia de uma lista é também encontrada muito comumente no mundo: você com certeza já falou em listas de compras, dos melhores times, de alunos, etc. Listas são importantes pois permitem operações simples e bem-definidas sobre um conjunto de dados. Além disso, podem ser usadas para implementar outras estruturas de dados importantes, como filas e pilhas.

 

Elas podem ser definidas recursivamente: uma lista não-vazia é um elemento seguido de uma lista potencialmente vazia. Aqui, chamamos o primeiro elemento de cabeça, e o restante da lista de cauda. Pensando assim, a lista (1, 2, 3) é composta pela cabeça 1 e a cauda (2, 3), que por sua vez é composta pela cabeça 2 e pela cauda (3), que por sua vez é composta pela cabeça 3 e pela cauda (). Geralmente este tipo de definição é expresso usando um operador de construção de lista, comumente chamado de cons. O que ele faz é criar uma lista a partir de um elemento e de outra lista. Em nosso exemplo acima:

 

(1, 2, 3) == 1 cons (2 cons (3 cons ()))

 

De fato, em linguagens que fornecem listas, como Haskell ou Lisps, notações de como [1, 2, 3] ou (list 1 2 3) são na verdade 'atalhos' para expressar diversas construções seguidas:

 

-- Haskell: [1, 2, 3]
1 : (2 : (3 : []))

 

; Scheme: (list 1 2 3)
(cons 1 (cons 2 (cons 3 ())))

 

Em C, para mantermos o aspecto de flexibilidade de tamanho das listas, geralmente usamos ponteiros para designar a conexão entre um elemento e sua cauda. Observe seu código:

 

struct no
{
 int inf;
 struct no *prox;
};

struct no *cria_no(int x)
{
   struct no *inicio;
   inicio=(struct no*) malloc(sizeof (struct no));
   inicio-> inf = x;
   inicio-> prox = NULL;
   return inicio;
}

 

A linha importante no momento é inicio->prox = NULL;. Ela diz que o elemento criado é o último elemento de alguma lista (mesmo que seja uma lista com apenas 1 elemento). Para ligar dois elementos, crie dois nós e relacione-os através do ponteiro prox do tipo struct no:

 

#include <stdio.h>
#include <stdlib.h>

struct no
{
 int valor;
 struct no *prox;
};

struct no *cons(int v, struct no *cauda)
{
   struct no *novo = malloc(sizeof *novo);

   if (!novo)
   {
fprintf(stderr, "\n\tErro de alocacao de memoria. Abortando.\n");
exit(EXIT_FAILURE);
   }

   novo->valor = v;
   novo->prox  = cauda;

   return novo;
}


void imprimir(struct no *lista)
{
   printf("(");

   while (lista && lista->prox)
   {
printf("%d, ", lista->valor);
lista = lista->prox;
   }

   printf("%d)\n", lista->valor);
}


int main(void)
{
   struct no *lista = cons(1, cons(2, cons(3, NULL)));

   imprimir(lista);

   // implementar: destruir(lista);
}

 

Para compilar o código acima, use:

 

gcc -std=c99 -Wall -Wextra -pedantic -Werror [nome_entrada.c] -o [nome_saída]

 

Implementamos o operador abstrato cons como struct no *cons(int v, struct no *cauda) (ou seja, uma função em C). Esta operação é também conhecida como prepend. Há outra chamada append, que faz com que um elemento seja inserido ao final da lista, ao invés do início. Sugiro que a implemente, bem como a rotina de destruição indicada acima para liberar a memória dos elementos alocados.

 

Se tiver mais dúvidas, pode perguntar.

[GBecker 51]

rica mourao,

 

Não só a lista, mas as outras estruturas de dados(fila e pilha) também são complicadas de entender. Por isso começar pela lógica ou algorítimo no papel, ou seja, com desenhos. Facilita bastante o entendimento da "coisa"(foi assim que aprendi o conceito destas e de muitas coisas =P).

Segue um link que explica listas através de desenhos e códigos aqui.

 

E aqui, um link com mais código.

 

Bom, quanto a utilidade. No meu caso utilizo lista na recepção de pacotes numa conexão serial. Como eu não sei o tamanho total dos dados que vou receber, cada pacote que recebo eu aloco os dados em um novo nodo da minha lista.

 

Uma lista ligada simples, pode ser descrita como um vetor. O primeiro nodo seria a posição '0' do vetor e o final seria o ponteiro do proximo nó apontado para nada(NULL).

 

Espero ter ajudado, FLW! :grin:

[rica mourao 0]

Olá pessoal boa tarde,

 

Agradeço muito a ajuda que vocês me forneceram,, com certeza agora consigo entender o que está acontecendo no programa que estou visualizando na faculdade.

 

Acabei de ter certeza que a lista é uma estrutura muito importante no dia-a-dia.

 

Caso tenha alguma dúvida na implementação do código procuro vocês novamente.

 

Obrigado.