Problema lista concatenata semplice

di il
11 risposte

Problema lista concatenata semplice

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

  • Re: Problema lista concatenata semplice

    Dai un'occhiata a

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

    a partire da

    Implementazione nei linguaggi
  • Re: Problema lista concatenata semplice

    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);
    }
  • Re: Problema lista concatenata semplice

    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);
    }
  • Re: Problema lista concatenata semplice

    La chiamata a

    stampa(n);

    mettila fuori dal ciclo, magari ti appare più chiaro.
  • Re: Problema lista concatenata semplice

    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.. ç_ç
  • Re: Problema lista concatenata semplice

    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
  • Re: Problema lista concatenata semplice

    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?
  • Re: Problema lista concatenata semplice

    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

  • Re: Problema lista concatenata semplice

    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]
  • Re: Problema lista concatenata semplice

    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;
    	}
    
    
    }
  • Re: Problema lista concatenata semplice

    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