[C] Disperazione liste concatenate

[D4rkAng3l]

Ragazzi per favore aiutatemi..l'1 avrò l'esame di programmazione 1 che verte sulle liste concatenate ma ho serie difficoltà a capirle...sarò scemo ma ce la devo fare...

In teoria ho capito come funzionano (dichiaro una struttura che contiene i dati e il puntatore al prossimo elemento che è un'altra struttura dello stesso tipo).

Ora sul manuale fà vedere solo la funzione di inserzione ma non tutto il programma e non ci capisco molto..specialmente non riesco a vedere come venga allocata la memoria per una nuovo nodo....

Non è che potreste passarmi il codice di un programma che:
"Continua a chiedere un un nome e un indirizzo (da mettere nei campi di una struttura) finchè non viene immesso un valore sentinella, e li memorizzi in una lista (lista non ordinata...semplicemente l'ultimo elemento inserito stà nell'ultimo nodo)....

Vi prego, vi prego, vi pregoooo

[71104]

non capisco dove starebbe il problema, dimmi più precisamente cos'è che non sai fare; per allocare memoria per un nuovo nodo basta usare la malloc: la malloc semplicemente alloca un nuovo blocco di memoria con una dimensione di N bytes (dove N sarebbe il parametro che gli passi) e ne restituisce il puntatore; alla fine per liberare il blocco basta passarlo a free. ricorda però che se il nodo contiene dei campi stringa devi allocare memoria anche per quelli, e alla fine liberare anche quella memoria. esempio:

typedef struct _nodo {
    char *info;
    struct _nodo *next;
} nodo, *lista;

allocazione e inizializzazione di un nodo:

nodo *n = (nodo*)malloc(sizeof(nodo));
n->info = (char*)malloc(...);  // la dimensione della stringa da metterci la stabilisci tu
n->next = ...;  // il prossimo nodo della lista lo stabilisci tu

deallocazione:

free(n->info);
free(n);

tutto qua

[D4rkAng3l]

mi incasino a concepire quel programma...non è che potresti farmi vedere il codice di quello che ho descritto sopra per favore? lo sò come funziona malloc....te ne sarei infinitamente grato

[71104]

vabbè va, nella mia enorme bontà, guarda che cosa ti ho postato:

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

typedef struct _nodo {
	char *nome, *indirizzo;
	struct _nodo *next;
} nodo, *lista;

nodo *crea(char *nome, char *indirizzo) {
	nodo *n = (nodo*)malloc(sizeof(nodo));
	n->nome = (char*)malloc(strlen(nome) + 1);
	strcpy(n->nome, nome);
	n->indirizzo = (char*)malloc(strlen(indirizzo) + 1);
	strcpy(n->indirizzo, indirizzo);
	n->next = NULL;
	return n;
}

void libera(nodo *n) {
	free(n->nome);
	free(n->indirizzo);
	free(n);
}

int main() {
	char nome[100], indirizzo[100];
	char *sentinella = "fine";
	lista l = NULL;
	nodo *ultimo = NULL;
	while (1) {
		printf("nome: ");
		scanf("%s", nome);
		if (!stricmp(nome, sentinella)) {
			break;
		}
		printf("indirizzo: ");
		scanf("%s", indirizzo);
		if (!stricmp(indirizzo, sentinella)) {
			break;
		}
		if (ultimo) {
			ultimo->next = crea(nome, indirizzo);
			ultimo = ultimo->next;
		}
		else {
			ultimo = crea(nome, indirizzo);
			l = ultimo;
		}
	}
	// qui di seguito scrivo il codice per la deallocazione,
	// ma non sono sicuro che rientri negli obiettivi dell'esercizio,
	// quindi casomai lasciala perdere.
	ultimo = l;
	while (ultimo) {
		nodo *n = ultimo;
		ultimo = n->next;
		libera(n);
	}
	return 0;
}

non l'ho provato, quindi potrebbe non funzionare, però intanto spero che tu capisca come si fa
ciao

[D4rkAng3l]

Ciao,
grazie per il tuo codice...ho provato a tirare giù da quello il diagramma di flusso, a rifarlo e a commentarlo...credo di aver più o meno capito ma c'è sempre qualcosa che mi sufgge...puoi vedere se dai miei commenti c'è qualche errore logico-concettuale?

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

/* Dichiaro il tipo struct _nodo e poi lo rinonimo in nodo e *lista con un
   typedef */

typedef struct _nodo{
    char *nome;
    char *indirizzo;
    struct _nodo *next; // Puntatore ad un'altra struttura di tipo struct _nodo
} nodo, *lista;

nodo *crea(char *, char *);

int main(void){
    
    char nome[100];
    char indirizzo[100];
    char *sentinella = "fine";
    
    /* Dichiaro un puntatore l di tipo lista (quindi puntatore a struct _nodo
       e lo imposto a NULL */
    
    lista l = NULL;
    
    /* Dichiaro un puntatore ultimo di tipo nodo e lo imposto a NULL */
    
    nodo *ultimo = NULL;
    
    while(1){
        printf("Inserire un nome: ");
        scanf("%s", nome);        // Inserisce il nome nel vettore di char nome
        
        if (!stricmp(nome, sentinella)) {
			break;
		}
		
        printf("Inserire un indirizzo: ");
        scanf("%s", indirizzo);  // Inserisce l'indirizzo nel vettore indirizzo
        
        if (!stricmp(indirizzo, sentinella)) {
			break;
		}
		
		if(ultimo){ // Se il valore di ultimo non è nullo la lista non è vuota
		    
		    /* per cui imposto il campo next della struttura che forma il nodo
               della lista puntato da ultimo con l'indirizzo emesso in output
               dalla funzione crea alla quale passo nome ed indirizzo immessi */
            ultimo -> next = crea(nome, indirizzo);
            
            /* Ultimo punta all'ultimo nodo creato quindi ora è uguale al campo
               next della struttura appena creata */
            ultimo = ultimo -> next;
        }
        
        else{            // Se il valore di ultimo è nullo la lista è vuota
           
           /* La funzione crea creerà il primo nodo della lista e al puntatore
              ultimo sarà assegnato l'indirizzo del primo nodo  */
           ultimo = crea(nome, indirizzo);
           l = ultimo;
       }
   }
   
   return 0;
}

/* La funzione crea() riceve come argomenti i puntatori ai vettori di caratteri
   name ed indirizzo, alloca dinamicamente la memoria per il nuovo nodo da
   inserire nella lista e vi inserisce dentro i dati immessi dall'utente nei
   campi della struttura che forma il nodo */

nodo *crea(char *nome, char *indirizzo){
    
    nodo *n;    // Dichiaro un puntatore di tipo nodo ovvero alla struttura
    
    /* Alloca dinamicamente la memoria per il nuovo nodo da inserire in coda
       alla lista e attribuisce l'indirizzo di questa zona di memoria ad n */
    
    n  = (nodo *)malloc(sizeof(nodo));
    
    /* Accedi al campo nome della struttura appena creata puntata da n ed
       alloca quì dentro un vettore di caratteri pari al numero di caratteri
       che compongono il nome +1 */
    
    n -> nome = (char *)malloc(strlen(nome)+1);
    strcpy(n->nome, nome);    // Dopo aver allocato lo spazio copia il nome
    
    /* Accedi al campo indirizzo della struttura appena creata puntata da n ed
       alloca quì dentro un vettore di caratteri pari al numero di caratteri
       che compongono l'indirizzo +1 */
    
    n -> indirizzo = (char *)malloc(strlen(indirizzo)+1);
    strcpy(n->indirizzo, indirizzo);// Dopo aver allocato lo spazio copia l'ind
    
    n -> next = NULL;    // Setta a NULL il campo next puntato da n
}

La cosa che mi sfugge è perchè ho 2 differenti typedef del tipo struct _nodo
ovvero: nodo, *lista ?
Ora non ho inserito l'ultima funzione che rilibera la memoria...ma questa istruzione nel main:
lista l = NULL; cioè l servivà a quella funzione...nel resto del programma da me implementato è inutile o sbaglio?

Grazie

[71104]

Originariamente inviato da D4rkAng3l

Ciao,
grazie per il tuo codice...ho provato a tirare giù da quello il diagramma di flusso, a rifarlo e a commentarlo...credo di aver più o meno capito ma c'è sempre qualcosa che mi sufgge...puoi vedere se dai miei commenti c'è qualche errore logico-concettuale?

ho letto tutto; ancora non capisco cosa c'è che non è chiaro: i commenti dicono cose sensate e il programma a occhio e croce funziona (vabbè che è quasi uguale al mio )

La cosa che mi sfugge è perchè ho 2 differenti typedef del tipo struct _nodo ovvero: nodo, *lista ?

premesso che in questo programmetto scrivere

nodo*

è esattamente uguale a scrivere

lista

, ho definito questi due tipi separati a scopi più che altro semantici: concettualmente parlando "nodo" è una struttura che rappresenta un nodo della lista, mentre "lista" concettualmente è una lista vera e propria, che possiamo rappresentare come un puntatore al suo primo elemento (per questo è dichiarata come un puntatore a un nodo). se tu prendi il codice e in ogni punto dove compare la parola "lista", al posto di "lista" ci metti "nodo*", il tutto funziona lo stesso.

Ora non ho inserito l'ultima funzione che rilibera la memoria...ma questa istruzione nel main:
lista l = NULL; cioè l servivà a quella funzione...nel resto del programma da me implementato è inutile o sbaglio?

veramente non ho ben capito quest'ultima domanda: considera tutte le volte che allochi una zona di memoria con malloc, quando hai finito di usarla devi sempre liberarla con free, o almeno sarebbe buona regola farlo; in progetti molto grossi a volte se non usi free va a finire che riempi molto facilmente uno spazio di memoria esorbitante a causa dei leaks, e tra parentesi se il tuo è un programma che accede all'esterno (ad esempio un server tcp/ip) qualche hackerazzo potrebbe molto facilmente sfruttare i tuoi leaks per riempire la RAM e causare un DoS rallentando il server (tutto questo per dire che i memory leaks tra l'altro possono facilmente avere delle implicazioni di sicurezza).
ora tu nel tuo codice le istruzioni per la deallocazione non ce le hai messe, e alla fine anche se non sarebbe buona norma va bene lo stesso così per 2 motivi:
1) il tuo programma è molto semplice e deve solo creare la lista e poi terminare; quando termina il sistema operativo cancella tutto il suo heap e quindi dealloca tutto quello che hai allocato, quindi non crei nessun problema al sistema
2) la deallocazione non credo che rientri nei fini dell'esercizio, che sembra piuttosto vertere sulla gestione delle liste.

[D4rkAng3l]

Originariamente inviato da 71104

ho letto tutto; ancora non capisco cosa c'è che non è chiaro: i commenti dicono cose sensate e il programma a occhio e croce funziona (vabbè che è quasi uguale al mio )


premesso che in questo programmetto scrivere

nodo*

è esattamente uguale a scrivere

lista

, ho definito questi due tipi separati a scopi più che altro semantici: concettualmente parlando "nodo" è una struttura che rappresenta un nodo della lista, mentre "lista" concettualmente è una lista vera e propria, che possiamo rappresentare come un puntatore al suo primo elemento (per questo è dichiarata come un puntatore a un nodo). se tu prendi il codice e in ogni punto dove compare la parola "lista", al posto di "lista" ci metti "nodo*", il tutto funziona lo stesso.


veramente non ho ben capito quest'ultima domanda: considera tutte le volte che allochi una zona di memoria con malloc, quando hai finito di usarla devi sempre liberarla con free, o almeno sarebbe buona regola farlo; in progetti molto grossi a volte se non usi free va a finire che riempi molto facilmente uno spazio di memoria esorbitante a causa dei leaks, e tra parentesi se il tuo è un programma che accede all'esterno (ad esempio un server tcp/ip) qualche hackerazzo potrebbe molto facilmente sfruttare i tuoi leaks per riempire la RAM e causare un DoS rallentando il server (tutto questo per dire che i memory leaks tra l'altro possono facilmente avere delle implicazioni di sicurezza).
ora tu nel tuo codice le istruzioni per la deallocazione non ce le hai messe, e alla fine anche se non sarebbe buona norma va bene lo stesso così per 2 motivi:
1) il tuo programma è molto semplice e deve solo creare la lista e poi terminare; quando termina il sistema operativo cancella tutto il suo heap e quindi dealloca tutto quello che hai allocato, quindi non crei nessun problema al sistema
2) la deallocazione non credo che rientri nei fini dell'esercizio, che sembra piuttosto vertere sulla gestione delle liste.

ah ok grazie mille...per quanto riguardava la domanda era solo per capire se in questa versione potevo evitare di inserire la variabile l perchè tanto non la usavo mai visato che non ho ancora visto la deallocazione della memoria...

sisi il programma è uguale al tuo...visto che mi trovo questo argomento parecchio ostico ho presto il tuo listato e per capirlo mi sono fatto il grafico dell'algoritmo su un foglio e poi dal foglio me lo sono andato a riscrivere il codice...e a mettere i commenti...per farmi chiarezza nella mia testa principalmente...

Ancora grazie mille..stò morendo d'ansia per questo esame perchè il programma da studiare sulle liste è ancora moltooo vasto e ho solo 2 settimane...lo sò in 2 settimane si può fare..però AIUTOOO ho il panico

[71104]

mah, non vedo cosa ci sia di tanto vasto da studiare sulle liste...
programmazione 1 io l'ho data senza studiare niente...

[D4rkAng3l]

Originariamente inviato da 71104

mah, non vedo cosa ci sia di tanto vasto da studiare sulle liste...
programmazione 1 io l'ho data senza studiare niente...

beato te, per me non è così...ci devo perdere tanto tempo...forse sarò stupido ma non me lo trovo così banale come argomento