• Benvenuto, registrati e partecipa alle attività del forum

C++ puntatori e liste

Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#1
Salve,
da buon studente in crisi, ho bisogno di porvi delle domande riguardo questo argomento :-(
(premetto che odio C++, maledetto sia lui per sempre :bang).

Allego il codice base:

Codice:
struct nodo{
    int info;
    nodo *next;
};

typedef nodo* list;
Ok, una sciocchezza per molti, ma non mi è stato mai chiarito ciò: perché nella dicitura "typedef nodo* list" uso il " * "?
List in questo caso non è un puntatore.... o sbaglio?


In più, ci sono due piccoli sottoprogrammi da scrivere tenendo in riferimento le struttura di sopra.
Sottolineo la parte che mi interessa.

1. "Stampa di una lista con un sottoprogramma avente la seguente intestazione: void printList(list h); "
Codice:
void printList(list h) {
    /* stampa ricorsiva */
    if (h!=NULL) {
        cout << " -> " << h->data;
        printList(h->next);
    }
}
2. "Calcolo della lunghezza di una lista con la seguente intestazione: int lenLista(list h);"

Codice:
int lenList(list h) {
     if (h == NULL){
          return 0;
     }else{
         return( 1 + lenList(h->next));
    }
}
Qual è la differenza tra il printList(h->next) e il (1+lenList(h->next)? Sono tutti e due due "incrementatori" del puntatore next, per passare al prossimo nodo o erro?


Vi ringrazio in anticipo per l'aiuto in questo stupido e banale problema, ma purtroppo ho dei dubbi che non riesco a risolvere :-(
 
Ultima modifica:

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#2
Ciao!
Ma guarda un po', anche io devo rispolverare il C++, quindi spero di non lanciare qualche castroneria :asd

1) Usi il "*" perché list è un puntatore a "nodo" quindi lo usi per accedere ai vari "nodo". Se non usassi il "*" praticamente diresti che list è un nodo e non lo puoi usare per accedere ai nodi..

2) Entrambi vanno al nodo successivo, sono scritti in modo diverso perché lo scopo delle funzioni è diverso. La prima funziona così, detta a parole "Entro in un nodo, se esiste stampo il contenuto e proseguo altrimenti mi fermo"
La seconda invece "Entro in un nodo, se esiste ritorno 1 (quindi "sommo 1") e chiamo la funzione che mi va al nodo successivo (che a sua volta sommerà 1 o 0 se il nodo non esiste). Se non esiste sommo 0."

Sperò di essere stato chiaro, ho provato a mettere le cose in parole semplici per farle capire :)
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#3
Ciao!
Ma guarda un po', anche io devo rispolverare il C++, quindi spero di non lanciare qualche castroneria :asd

1) Usi il "*" perché list è un puntatore a "nodo" quindi lo usi per accedere ai vari "nodo". Se non usassi il "*" praticamente diresti che list è un nodo e non lo puoi usare per accedere ai nodi..

2) Entrambi vanno al nodo successivo, sono scritti in modo diverso perché lo scopo delle funzioni è diverso. La prima funziona così, detta a parole "Entro in un nodo, se esiste stampo il contenuto e proseguo altrimenti mi fermo"
La seconda invece "Entro in un nodo, se esiste ritorno 1 (quindi "sommo 1") e chiamo la funzione che mi va al nodo successivo (che a sua volta sommerà 1 o 0 se il nodo non esiste). Se non esiste sommo 0."

Sperò di essere stato chiaro, ho provato a mettere le cose in parole semplici per farle capire :)
ahhhhhhhhhhh
Grazie grazie :)

Quindi nella 2.2), praticamente somma 1 (ma a cosa?) in modo che poi alla fine, venga fuori la lunghezza della lista, giusto?

P.S. Io come soluzione, pensavo di usare una variabile contatore apposita, in questo modo:

Codice:
int cont;
    int lenLista(list h){
        
        if(h!=null){
            cont++;
            lenLista(1+ (h->next) );
        }else{
            return cont;
        }
        
    }
Che ne pensi?


Grazie ancora per l'aiuto tempestivo!
 

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#4
ahhhhhhhhhhh
Grazie grazie :)

Quindi nella 2.2), praticamente somma 1 (ma a cosa?)
Devi entrare un pochino nel metodo della ricorsione..
Vediamo se riesco a spiegarmi.
Funziona così
Parte la funzione. Il nodo a cui punta il puntatore esiste? Si, allora ritorno 1 + il risultato della funzione che verifica l'esistenza del nodo successivo che ritorna 1 in caso positivo e 0 in caso negativo (e si stoppa in quest'ultimo caso) quindi la funzione ritornerà il numero dei nodi della lista
Anche la tua soluzione andrebbe bene, ma quella dell'esempio è molto più elegante :) ed è meglio che ti abitui così (piano piano con il tempo, ovviamente)
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#5
Devi entrare un pochino nel metodo della ricorsione..
Vediamo se riesco a spiegarmi.
Funziona così
Parte la funzione. Il nodo a cui punta il puntatore esiste? Si, allora ritorno 1 + il risultato della funzione che verifica l'esistenza del nodo successivo che ritorna 1 in caso positivo e 0 in caso negativo (e si stoppa in quest'ultimo caso) quindi la funzione ritornerà il numero dei nodi della lista
Anche la tua soluzione andrebbe bene, ma quella dell'esempio è molto più elegante :) ed è meglio che ti abitui così (piano piano con il tempo, ovviamente)
Per "fortuna" il corso di C++ si fermerebbe solo a questo semestre, ed ammetto che non gradirei un suo ritorno in qualche altro corso :D
Comunque grazie per l'aiuto! :)


Ma non finisce qua ahhaha
ho un altro stupido dubbio, su una variabile (credo che almeno sia tale) che spunta fuori da booh

Il sottoprogramma deve copiare una lista dentro un'altra lista, e questa è la soluzione del prof:

Codice:
list copyList(list h) {

 list ch = NULL, aux;
 while (h != NULL) {
 aux = (node*) new node;
 aux->data = ch->data;
 aux->next = NULL;
 ch = insertTail(ch, aux);
 h = h->next;
 }
 return ch;
}
Ma precisamente, questo aux, chi è?
Da dove spunta fuori?
 

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#6
Per sapere.. Che facoltà fai e a che anno sei?

Allora, prima avevi scritto

Codice:
typedef nodo* list;
Quindi, quando scrive

Codice:
 list ch = NULL, aux;
Qua dichiara aux, è un list, cioè un puntatore a nodo

Di nulla! :D
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#7
Codice:
 list ch = NULL, aux;
Qua dichiara aux, è un list, cioè un puntatore a nodo

Di nulla! :D
Ah, non sapevo che le dichiarazioni potessero essere fatte anche in questa maniera...
qualcosa mi sfugge, probabilmente devo rileggere meglio :-(

Cioè, per dichiarare aux come puntatore a nodo, non dovrei scrivere "List aux"?


Grazie ancora!
Per sapere.. Che facoltà fai e a che anno sei?
Ingegneria informatica, primo anno.
Arrivo dall'Istituto tecnico dove C++ non lo abbiamo mai lontanamente visto, abbiamo fatto molto Java (e JSP - Servlet), PHP - HTML - CSS - JavaScript (diciamo su necessità).
 

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#8
Ah, non sapevo che le dichiarazioni potessero essere fatte anche in questa maniera...
qualcosa mi sfugge, probabilmente devo rileggere meglio :-(
Grazie!
Praticamente con
Codice:
list ch = NULL, aux;
Dichiara sia "ch" e lo fa puntare a null, sia "aux" solo che non lo fa puntare a niente... E che io sappia queste cose non vanno fatte :nono o per lo meno non è "elegante" avere un puntatore non inizializzato

Ingegneria informatica, primo anno.
Arrivo dall'Istituto tecnico dove C++ non lo abbiamo mai lontanamente visto, abbiamo fatto molto Java (e JSP - Servlet), PHP - HTML - CSS - JavaScript (diciamo su necessità).
Sospettavo, anche io a ingegneria informatica a Pisa ho fatto C++ al primo semestre... Uno dei pochi esami che ho fatto lol

Io ho fatto uno scientifico (mannaggia a me) e non abbiamo mai fatto assolutamente nulla di informatica ma comunque il primo esame di C++ solitamente non è niente di che, è l'unico che ho passato senza problemi
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#9
Praticamente con
Codice:
list ch = NULL, aux;
Dichiara sia "ch" e lo fa puntare a null, sia "aux" solo che non lo fa puntare a niente... E che io sappia queste cose non vanno fatte :nono o per lo meno non è "elegante" avere un puntatore non inizializzato
Nooo ho capito, mamma mia sono diventato davvero un rammollito... Che svista, devo comprarmi delle lenti di ingrandimento, altro che occhiali :-(

Sospettavo, anche io a ingegneria informatica a Pisa ho fatto C++ al primo semestre... Uno dei pochi esami che ho fatto lol

Io ho fatto uno scientifico (mannaggia a me) e non abbiamo mai fatto assolutamente nulla di informatica ma comunque il primo esame di C++ solitamente non è niente di che, è l'unico che ho passato senza problemi
Ahh guarda, io sono a Dalmine (sede di Bergamo).
Mi trovo bene ma il corso di C++ (che praticamente ho visto che anche tu, e i miei amici al Poli, fanno identico) lo trovo praticamente inutile.

Io ho "fortuna" che arrivo da un tecnico, ma per chi non ha mai programmato (come alcuni che arrivano dal linguistico o da licei in cui non hanno mai scritto una riga di codice) deve essere incredibilmente tosta già solo iniziare (non che per me non lo sia... anzi).

In bocca al lupo anche a te allora, spero che le tue sessioni vadano meglio della mia attuale :D

Se ho altro (e sicuramente ne avrò ahahha), in questi giorni prima dell'esame mi farò risentire!

Grazie ancora di tutto ;)
 

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#10
Mi trovo bene ma il corso di C++ (che praticamente ho visto che anche tu, e i miei amici al Poli, fanno identico) lo trovo praticamente inutile.
Noi siamo arrivati alle classi.. Un po' dopo queste cose :sisi
Ti dirò, davvero quello di C++ per me è stato l'esame più facile anche se non avevo mai programmato in vita mia lol

In bocca a lupo anche a te! Uh, per caso la sessione non ti sta andando bene? Un classico per ingegneria.. La mia media degli esami all'anno fa pena come quella del 70% degli studenti
 

iSamurai

Utente attivo
Iscritto dal
15 Novembre 2018
Messaggi
118
#11
Dichiara sia "ch" e lo fa puntare a null, sia "aux" solo che non lo fa puntare a niente... E che io sappia queste cose non vanno fatte :nono o per lo meno non è "elegante" avere un puntatore non inizializzato
Più che poco elegante è potenzialmente unsafe in linguaggi a più basso livello non assegnare un valore al momento della creazione perché non hai idea di cosa possa contenere e quindi rischi di avere comportamenti anomali nell'uso; in linguaggi più astratti questo rischio viene coperto da interprete/compilatore che mettono un valore di default "sano" ma sarebbe comunque meglio avere un valore predefinito (per onor di cronaca credo che versioni moderne dei compilatori C/C++ mettano un valore di default per evitare questo problema, probabilmente comunque è disattivabile questa cosa con qualche flag per ottenere maggiori performance ma devi effettivamente sapere quello che stai facendo).
 
Ultima modifica:

Fefolino

Utente attivo
Iscritto dal
9 Dicembre 2018
Messaggi
145
5.00 stelle/a
#12
Più che poco elegante è potenzialmente unsafe in linguaggi a più basso livello non assegnare un valore al momento della creazione perché non hai idea di cosa possa contenere e quindi rischi di avere comportamenti anomali nell'uso; in linguaggi più astratti questo rischio viene coperto da interprete/compilatore che mettono un valore di default "sano" ma sarebbe comunque meglio avere un valore predefinito (per onor di cronaca comunque credo che versioni moderne dei compilatori C/C++ comunque mettano un valore di default per evitare questo problema, probabilmente comunque è disattivabile questa cosa con qualche flag per ottenere maggiori performance ma devi effettivamente sapere quello che stai facendo).
Yes, è quello che intendevo con "non andrebbero fatte", la prof del corso ci diceva che un puntatore non inizializzato punta a un indirizzo non conosciuto e quindi la possibilità di fare casini è elevata, ma poi ho effettivamente visto che in c++ i puntatori vengono inizializzati di default a null..
 

iSamurai

Utente attivo
Iscritto dal
15 Novembre 2018
Messaggi
118
#13
Altre risposte, ho appena finito di leggere tutta la discussione
Salve,
da buon studente in crisi, ho bisogno di porvi delle domande riguardo questo argomento :-(
(premetto che odio C++, maledetto sia lui per sempre :bang).

Allego il codice base:

Codice:
struct nodo{
    int info;
    nodo *next;
};

typedef nodo* list;
Ok, una sciocchezza per molti, ma non mi è stato mai chiarito ciò: perché nella dicitura "typedef nodo* list" uso il " * "?
List in questo caso non è un puntatore.... o sbaglio?
Typedef assegna dei nomi alternativi a dei tipi di dato già esistenti, in pratica stai dicendo "quando creo una variabile di tipo list in realtà sto creando una variabile di tipo nodo*".

2. "Calcolo della lunghezza di una lista con la seguente intestazione: int lenLista(list h);"

Codice:
int lenList(list h) {
     if (h == NULL){
          return 0;
     }else{
         return( 1 + lenList(h->next));
    }
}
Qual è la differenza tra il printList(h->next) e il (1+lenList(h->next)? Sono tutti e due due "incrementatori" del puntatore next, per passare al prossimo nodo o erro?
Stai sommando 1 al risultato di lenList applicato ad una sottoparte della lista, provo a farti un esempio con gli array
(fatto in js perché così si può semplicemente aprire la console di un browser e provarla al volo)
JavaScript:
function arrayLength(arr) {
    if(typeof arr[0] === "undefined") {
        return 0;
    } else {
        return 1 + arrayLength(arr.slice(1));
    }
}
2 spiegazioni veloci, con typeof verifico il tipo dell'elemento nell'indice 0 dell'array (primo modo veloce che mi è venuto in mente per verificare se ho l'array [] come parametro), slice(1) mi ritorna un sotto array composto dagli elementi di arr tranne il primo.
Vediamo passo per passo cosa accade se invoco la funzione così
arrayLength([1,2,3])

Primo passo, arr vale [1,2,3], arr[0] vale 1 quindi vado nel ramo else, per cui ritornerò come risultato 1 + arrayLength([2, 3])
Secondo passo, arr vale [2,3], arr[0] vale 2 quindi vado nel ramo else, per cui ritornerò come risultato 1 + arrayLength([3])
Terzo passo, arr vale [3], arr[0] vale 3 quindi vado nel ramo else, per cui ritornerò come risultato 1 + arrayLength([])
Quarto passo, arr vale [], arr[0] non ha un valore definito quindi vado nel ramo true, per cui ritornerò come risultato 0

A questo punto quindi posso ricominciare a salire
- arrayLength([]) vale 0
- arrayLength([3]) vale 1 + 0, quindi 1
- arrayLength([2,3]) vale 1 + 1, quindi 2
- arrayLength([1,2,3]) vale 1 + 2, quindi 3

In ricorsione in pratica cerchi di ridurre un problema finché non diventa così banale da avere una risposta vera al 100%, se il problema è troppo grande semplicemente continui a spezzarlo.

ahhhhhhhhhhh
Grazie grazie :)

Quindi nella 2.2), praticamente somma 1 (ma a cosa?) in modo che poi alla fine, venga fuori la lunghezza della lista, giusto?

P.S. Io come soluzione, pensavo di usare una variabile contatore apposita, in questo modo:

Codice:
int cont;
    int lenLista(list h){
     
        if(h!=null){
            cont++;
            lenLista(1+ (h->next) );
        }else{
            return cont;
        }
     
    }
Che ne pensi?


Grazie ancora per l'aiuto tempestivo!
Questa soluzione è sbagliata e pericolosissima perché stai sfruttando un side effect, è sbagliato a prescindere perché cont non è inizializzato a 0, ma supponiamo un momento che lo sia, cosa accade se faccio questo?
lenLista([1,2,3]);
Otterrò 3 come risultato giusto?
E se faccio questo
lenLista([1,2,3]);
lenLista([1,2]);

Dovrei ottenere 3 e 2 giusto? Però cont dopo la prima chiamata ha 3 come valore, quindi dopo la seconda chiamata cosa otterrò?
Sì otterrò 5 come risultato, avrei dovuto assegnare cont a 0 dopo la prima chiamata per ottenere un risultato corretto.

Cerca se possibile di usare funzioni pure (funzioni il cui output dipende solo ed esclusivamente dai suoi input) perché sono molto più facili da gestire e sicure, è pure più semplice dimostrarne la correttezza formale perché appunto non hai side effect come questo a deturparti l'output.
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#14
Vi ringrazio tutti e due per il tempo dedicatomi!

In bocca a lupo anche a te! Uh, per caso la sessione non ti sta andando bene? Un classico per ingegneria.. La mia media degli esami all'anno fa pena come quella del 70% degli studenti
Grazie e crepi!
No, la sessione è andata da schifo, ma credo per errore mio.
Ho studiato ma male, e di base non mi ritengo un cervellone (sebbene il voto con cui sono uscito dalla maturità possa far intendere ben altro).
Nel secondo semestre proverò a cambiare strategia come metodo di studio... Ci provo, per fortuna almeno quest'anno non pago la retta.


Comunque in rete ho trovato questa pagina: http://www.science.unitn.it/~brunato/labpro1/lista.html
Mi sembra molto chiara e facile da comprendere, che ne pensate?
 

iSamurai

Utente attivo
Iscritto dal
15 Novembre 2018
Messaggi
118
#15
Avrei da ridire e non poco sul modo di usare il for, trovo abbastanza controintuitivo poi lavorare su una struttura dati con cicli while anziché andare di ricorsione (e non venitemi a dire che i cicli sono più performanti, è materiale didattico quindi le performance contano poco e niente, inoltre qualsiasi compilatore decente ormai ottimizza la tail recursion come se fosse un ciclo, ci sono 0 scuse per non scrivere buon codice).
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#16
Avrei da ridire e non poco sul modo di usare il for, trovo abbastanza controintuitivo poi lavorare su una struttura dati con cicli while anziché andare di ricorsione (e non venitemi a dire che i cicli sono più performanti, è materiale didattico quindi le performance contano poco e niente, inoltre qualsiasi compilatore decente ormai ottimizza la tail recursion come se fosse un ciclo, ci sono 0 scuse per non scrivere buon codice).
Grazie, ho poi optato allora per la ricorsione ;)

P.S. Sul fatto che il codice sia ottimizzato o meno... non voletemi male, io voglio semplicemente passare l'esame :patpat
La realizzazione di software in C++ la lascio volentieri ad altri :asd


Comunque, tanto per cambiare mi è venuto un altro grosso dubbio :bonk

Possibile che abbia ciò?

Codice:
struct volo{

    int prezzo;
    int posti;
}

struct nodo{
    volo info;
    nodo *next;
}
Cioè, nella struttura nodo dove ho il puntatore *next, ho il campo informativo di tipo volo...

Ed in questo caso, nel caso lavorassi con non so, un puntatore (nodo *q), per risalire ad esempio al prezzo, come dovrei fare? Così va bene?
Codice:
q->info->prezzo




Dubbio 2

Con una struttura semplice come questa
Codice:
struct nodo{
    int info;
    nodo *next;
}

typedef nodo* list;
il prof riporta ciò:
"Creazione di un nuovo nodo:"
Codice:
nodo *createNode(int d);
Perché c'è "*" prima di createNode?
 
Ultima modifica:

iSamurai

Utente attivo
Iscritto dal
15 Novembre 2018
Messaggi
118
#17
Grazie, ho poi optato allora per la ricorsione ;)

P.S. Sul fatto che il codice sia ottimizzato o meno... non voletemi male, io voglio semplicemente passare l'esame :patpat
La realizzazione di software in C++ la lascio volentieri ad altri :asd


Comunque, tanto per cambiare mi è venuto un altro grosso dubbio :bonk

Possibile che abbia ciò?

Codice:
struct volo{

    int prezzo;
    int posti;
}

struct nodo{
    volo info;
    nodo *next;
}
Cioè, nella struttura nodo dove ho il puntatore *next, ho il campo informativo di tipo volo...

Ed in questo caso, nel caso lavorassi con non so, un puntatore (nodo *q), per risalire ad esempio al prezzo, come dovrei fare? Così va bene?
Codice:
q->info->prezzo
Le struct sono corrette, per quanto riguarda l'accesso invece la "freccia dei poveri" è una shortcut, foo->bar è l'equivalente di (*foo).bar, ha senso usarla solo quindi se stiamo parlando di puntatori, in tutti gli altri casi usi il "."; nel tuo caso quindi dovresti fare
q->info.prezzo

Dubbio 2

Con una struttura semplice come questa
Codice:
struct nodo{
    int info;
    nodo *next;
}

typedef nodo* list;
il prof riporta ciò:
"Creazione di un nuovo nodo:"
Codice:
nodo *createNode(int d);
Perché c'è "*" prima di createNode?
"*" Ti serve perché stai ritornando un puntatore.
 
Iscritto dal
28 Ottobre 2018
Messaggi
404
5.00 stelle/a
#18
Le struct sono corrette, per quanto riguarda l'accesso invece la "freccia dei poveri" è una shortcut, foo->bar è l'equivalente di (*foo).bar, ha senso usarla solo quindi se stiamo parlando di puntatori, in tutti gli altri casi usi il "."; nel tuo caso quindi dovresti fare
q->info.prezzo


"*" Ti serve perché stai ritornando un puntatore.
Ohhh perfetto, grazie grazie grazie mille!! :redwine
Post unito automaticamente


Ragazzi, scusate ancora il disturbo... :-(

Mi pare che il prof abbia fatto un errore....

Allora, la struttura è questa:

Codice:
struct nodo{
        int info;
        nodo *next;
    };
  
typedef *nodo list;

E sotto, nella soluzione al quesito "scrivere un sottoprogramma per creare un nuovo nodo, con l'intestazione che segue, scrive:
Codice:
nodo *createNode(int d) {
nodo *p;
p = new nodo; /* Creazione nuovo nodo */
p->data = d;
p->next = NULL;
return p;
}
Ma non avevamo definito che il tipo nodo *p ora è "list"?
E quindi dovrebbe non dovrebbe essere così?

Codice:
nodo *createNodo(int d){
    list a = new list;
    a->info = d;
    a->next = NULL;
      
    return a;
}
Post unito automaticamente

Scusate, ma ora mi sto confondendo:
Codice:
list insertHead(list h, nodo *el) {
if (h == NULL) return el;
if (el == NULL) return h;

el->next = h;
return el;
}
Qua il sottoprogramma è di "tipo list", ma restituisce un puntatore di tipo nodo...
 
Ultima modifica:
Top

Caro utente, ti ringraziamo per essere quì.

Ci siamo accorti che stai utilizzando un AdBlock o qualche estensione che impedisce il caricamento completo della pagina.

Non abbiamo banner fastidiosi, animazioni flash o popup irritanti.

I nostri proventi ci aiutano a coprire i costi di gestione del sito, recuperare eventuale materiale per la redazione e continuare il nostro operato.

Per favore, aggiungi hwreload.it alla whitelist o disabilita direttamente la tua estensione che blocca la pubblicità.

Ti ringraziamo per l'attenzione.