Problema lista concatenata semplice

Kripta

il 20 giu 2015, 18:06

11 risposte

Kripta

Pochi posts

Iscritto da: giu, 2015

Messaggi:: 10

Problema lista concatenata semplice

20 giu 2015, 18:37

Ciao a tutti!
Ho un problema che credo si risolva facilmente, ma non so dove sbattere la testa: Lista concatenata usando i puntatori.
L'utente deve semplicemente immettere dei dati in una quantità a piacere e il programma deve prenderli e metterli in una lista concatenata (una pila) per poi ristamparli nell'ordine in cui sono stati immessi. Tutto qui.
Il professore ci ha fatto prendere il libro "Fondamenti di informatica e programmazione in C" di S. G. Kochan, ma nel libro ad esempio non viene mai menzionata la funzione malloc con cui io devo operare per allocare dinamicamente la memoria e tutto è descritto all'acqua di rose come se fosse una favoletta. Risultato: ho capito perfettamente in teoria come una programma deve svolgersi, nella pratica non ho capito assolutamente niente.

Io so che devo avere un puntatore di testa che inzialmente non punta a nulla, ma appena viene inserito il primo dato dall'utente, *testa deve puntare a mio dato usando la struttura del tipo:

typedef struct nodo Nodo;

struct nodo
{
	char n;
	Nodo *next;
};

e i successivi dati inseriti devono puntare l'uno all'altro nell'ordine in cui vengono messi.
Ho cercato ovunque su internet ma tutti risolvono problemi in cui la lista non è così semplice e quindi il problema non essendo generalizzato è per me complicato da astrarre e usare per il mio caso. Molti non usano nemmeno i puntatore ma gli array, ma io sono obbligato ad usarli per gli esercizi.

esempio:
testa-->puntatore(elemento1)-->puntatore(elemento2)-->...-->puntatore(elementoN)-->NULL

Qualcuno riesce a farmi un esempio per riuscire a capire cosa devo fare nella pratica?
Vi ringrazio tantissimo

11 Risposte

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21392
Re: Problema lista concatenata semplice
20 giu 2015, 18:43
Dai un'occhiata a

https://it.wikipedia.org/wiki/Lista_concatenat

a partire da

Implementazione nei linguaggi

Kripta

Pochi posts

Iscritto da: giu, 2015

Messaggi:: 10

Re: Problema lista concatenata semplice

20 giu 2015, 19:12

Ti ringrazio. Seguendo quello che c'è scritto su Wikipedia, sono arrivato a scrivere un programma che riporto sotto, il problema è che mi restituisce infinite volte il primo valore che l'utente immette.. why?

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

typedef struct nodo Nodo;

struct nodo
{
	char car;
	Nodo *next;
};

Nodo add_nodo(char c, Nodo **p)
{
	Nodo *n = (Nodo *) malloc(sizeof (Nodo));
	n -> next = *p;
	*p = n;
	n -> car = c;

	return *n;
}

void stampa(Nodo *n)
{
	if ( n == NULL )
	{
		printf("La lista è vuota\n");
	}
	while ( n != NULL )
	{
		printf("%c ", n->car);
	}
}


int main()
{
	Nodo *n = NULL;
	char c;
	while ( c != '*' )
	{
		c = getchar();
		add_nodo(c, &n);
		stampa(n);
	}



exit(EXIT_SUCCESS);
}

Kripta

Pochi posts

Iscritto da: giu, 2015

Messaggi:: 10

Re: Problema lista concatenata semplice

20 giu 2015, 19:21

Problema in parte risolto, ora però il programma mi restituisce i valori che ho immesso, ma sembra "a caso", senza un'apparente logica..

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

typedef struct nodo Nodo;

struct nodo
{
	char car;
	Nodo *next;
};

Nodo add_nodo(char c, Nodo **p)
{
	Nodo *n = (Nodo *) malloc(sizeof (Nodo));
	n -> next = *p;
	*p = n;
	n -> car = c;

	return *n;
}

void stampa(Nodo *n)
{
	if ( n == NULL )
	{
		printf("La lista è vuota\n");
	}
	while ( n != NULL )
	{
		printf("%c", n->car);
		n = n->next;
	}
}


int main()
{
	Nodo *n = NULL;
	char c;
	while ( c != '*' )
	{
		c = getchar();
		add_nodo(c, &n);
		stampa(n);
	}



exit(EXIT_SUCCESS);
}

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21392
Re: Problema lista concatenata semplice
20 giu 2015, 20:12
La chiamata a

stampa(n);

mettila fuori dal ciclo, magari ti appare più chiaro.
K
Kripta
Pochi posts
Iscritto da
giu, 2015
Messaggi:
10
Re: Problema lista concatenata semplice
21 giu 2015, 10:42
Ho provato a mettere all'esterno del ciclio il print, il problema ora è che non mi restituisce il primo valore immesso e non me li restituisce nell'ordine in cui li ho immessi, ma al contrario..
Queste liste concatenate si stanno rivelando per me un incubo.. ç_ç
O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21392
Re: Problema lista concatenata semplice
21 giu 2015, 11:07
Che siano visualizzate al contrario è ovvio perché sono inserite in testa. Se inserisci a b c la lista diventa

a

b -> a

c -> b -> a

e quindi la visualizzazione sarà c b a

Ma non è un problema.

Comunque la getchar accetta anche l'invio che finisce nella lista come il * finale.
Quindi è meglio modificare così
```
   char c=0;
   while ( c != '*' )
   {
      c = getchar();
	  if(c!='*' && c!='\n')
		add_nodo(c, &n);
   }

   stampa(n);
```
P.S. Alla fine del main non si usa exit ma return
K
Kripta
Pochi posts
Iscritto da
giu, 2015
Messaggi:
10
Re: Problema lista concatenata semplice
21 giu 2015, 11:12
E se io volessi far controllare i dati da un'altra funzione o stamparli nell'ordine in cui l'utente li ha inseriti? Perchè ora praticamente il mio puntatore di testa punta all'ultimo elemento inserito e così come nella sequenza che hai scritto tu, ma vorrei che puntasse al primo e di conseguenza gli altri al secondo, al terzo, etc.. Posso invertire in qualche modo la sequenza?
O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21392
Re: Problema lista concatenata semplice
21 giu 2015, 11:25
Oltre ai suggerimenti che ti ho dato nel precedente post, devi modificare la funzione add_nodo che "aggiunge in testa" in modo che "aggiunga in coda". Per questo leggi questo
K
Kripta
Pochi posts
Iscritto da
giu, 2015
Messaggi:
10
Re: Problema lista concatenata semplice
21 giu 2015, 16:39
Ho seguito nuovamente il tuo consiglio, e ho fatto la funzione:
```
Nodo add_nodo(char c, Nodo **p) 
{

	if ( p == NULL )
	{
		Nodo *n = (Nodo *) malloc(sizeof (Nodo));
		n -> next = NULL;
		*p = n;
		n -> car = c;
	}
	else 
	{
		Nodo *n = (Nodo *) malloc(sizeof (Nodo)); 
		n = n -> next;
		n -> next = NULL; 
		n -> car = c; 
	}

	return *n;

}
```
Però il compilatore mi dice:
ennesimapila.c: In function ‘add_nodo’:
ennesimapila.c:32:9: error: ‘n’ undeclared (first use in this function)
ennesimapila.c:32:9: note: each undeclared identifier is reported only once for each function it appears in
ennesimapila.c:34:1: warning: control reaches end of non-void function [-Wreturn-type]

Kripta

Pochi posts

Iscritto da: giu, 2015

Messaggi:: 10

Re: Problema lista concatenata semplice

21 giu 2015, 17:27

Ho capito l'errore di n, ma ora ho errore di segmentazione

ecco qua di nuovo:

Nodo add_nodo(char c, Nodo **p) 
{

	if ( p == NULL )
	{
		Nodo *n = (Nodo *) malloc(sizeof (Nodo));
		n -> next = *p;
		*p = n;
		n -> car = c;
	return *n;
	}
	else 
	{
		Nodo *n = (Nodo *) malloc(sizeof (Nodo)); 
		n = n -> next;
		n -> next = NULL; 
		n -> car = c; 
	return *n;
	}


}

O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21392
Re: Problema lista concatenata semplice
21 giu 2015, 18:46
La prima parte, nel caso di lista vuota, deve essere
```
   if ( *p == NULL )
   {
      Nodo *n = (Nodo *) malloc(sizeof (Nodo));
	  n->car = c;
	  n->next = NULL;
      *p = n;
      return *n;
   }
```
ma la seconda la devi rivedere tutta ... occhio anche al ciclo while che ti dovrebbe portare alla fine della lista e che non hai messo ...

Devi accedere o registrarti per scrivere nel forum

11 risposte