[C] liste dinamiche

[sharkkk]

Passo passo sto cercando di comprendere a fondo l'utilizzo dei puntatori e mi sono imbattuto in questo codice elementare.
Ma cosa fa esattamente passo per passo?

typedef struct lista{
       int val;
       struct lista* next;
       } LIST;

int main(){...

    LIST* element;
     element = (LIST*)malloc(sizeof(LIST));

LIST* element;
- Creo un puntatore di tipo LIST, che ha un valore casuale e che non punta a nulla.

element = (LIST*)malloc(sizeof(LIST));
- malloc(sizeof(LIST)) alloca tanta memoria per element tanta quanto ne occupa il tipo LIST
- element = (LIST*)malloc(sizeof(LIST)); fa un cast al tipo LIST* perchè element è di tipo LIST*

Le domande sono:
a) Quello che ho scritto è giusto?
b) Ma in quale punto creo una nuova istanza di tipo LIST in cui posso già accedere agli elementi della struttura?
c) perche devo fare la malloc se faccio LIST* element? con questa dichiarazione element non è già grande quanto LIST?


p.s.
LIST* testa;
testa = NULL;

testa = NULL; imposta tutti gli elementi della struttura a NULL oppure il puntatore non punta piu ad una struttura ma solo a NULL?



grazie a chiunque mi aiuterà

[Daniels118]

Ciao,
a) la descrizione che hai dato è giusta;
b) la domanda non ha una risposta soddisfacente, nel senso che LIST è una struttura, ovvero una definizione di come sono organizzati i dati in memoria, il concetto di istanza è legato alla programmazione ad oggetti, anche se spesso viene utilizzato in modo improprio. La funzione malloc alloca la memoria necessaria, poi, facendo il casting del puntatore, istruisci il programma a trattare quell'area di memoria come se vi si trovasse una struttura LIST.
c) LIST* alloca solo lo spazio per un puntatore, lo spazio per la struttura va allocato separatamente, o con malloc, oppure dichiarando la variabile con LIST (senza asterisco), però tieni presente che sono due operazioni diverse e non sempre interscambiabili (la prima alloca nell'heap, la seconda sullo stack).

In fine, testa = NULL imposta la variabile testa - che è un puntatore - a NULL; se prima puntava a qualche elemento, questo resterà allocato in memoria, disperso (ma non diventa NULL, e mai potrebbe farlo, e solo memoria).

[Daniels118]

Ora che ci penso, sarebbe meglio dire che il programma è già istruito a trattare element come una LIST; assegnando a element un'indirizzo, indichi al programma dove si trova la memoria da utilizzare quando accedi ai campi di element.

[sharkkk]

grazie daniel

quindi scrivere
LIST* element; oppure void* element ipoteticamente a questo livello sarebbero la stessa cosa visto che non stanno puntando a nulla?

penso di aver capito che il primo puntatore, con la malloc, eredita la dichiarazione di LIST, tramite cui posso accedere agli elementi della struttura (con il dovuto cast).

pero ho visto un esercizio di un professore e lui senza fare la malloc o la new, in una funzione, accede ai campi di un puntatore a struttura. (il programma funziona correttamente, C++)

//Funzione che crea una lista di n interi prendendoli da tastiera
lista* crea_lista(int n){
	lista *l,*aux;
    lista *root=NULL;
    cout<<"Inserire "<<n<<" interi crescenti \n";
    for (int i=0; i<n; i++) {
        aux= new lista;
        if (root==NULL)
        	root=aux;
        else
        	l->next=aux;
        l=aux;
        cin>>l->val;
        l->next=NULL;
    }
    return (root);
}

aux correttamente viene allocato ma l no, eppure lui accede al campo next (l->next=aux;)
come fa?

[Daniels118]

LIST* element e void* element hanno lo stesso effetto in termini di memoria, ovvero allocano 4 byte (8 su sistemi a 64 bit) per un puntatore, naturalmente il compilatore si arrabbia di brutto se dichiari element come void* e poi scrivi element.next

malloc alloca solo memoria, il casting in questo caso serve per evitare che un programmatore inesperto o distratto faccia in modo inconsapevole assegnazioni tra dati di tipo diversi. Il compilatore tratta element come LIST anche se non gli assegni un indirizzo allocato con malloc. Ovviamente questo comporta l'accesso ad aree di memoria protette o peggio, dove sono conservati altri dati, facendo crashare il programma. L'assegnazione di un indirizzo valido ad element serve per riservargli uno spazio che non sia già utilizzato o che potrebbe essere utilizzato in futuro.

aux= new lista; alloca spazio per un elemento lista e assegna l'indirizzo ad aux;
l=aux; assegna ad l lo stesso indirizzo di aux, pertanto l punta alla stessa area di memoria allocata in precedenza;
if (root==NULL) questa condizione assicura che l'accesso al campo next attraverso il puntatore l avvenga solo alla seconda iterazione, per cui l è già stato inizializzato con un indirizzo valido.

[sharkkk]

Originariamente inviato da Daniels118

aux= new lista; alloca spazio per un elemento lista e assegna l'indirizzo ad aux;
l=aux; assegna ad l lo stesso indirizzo di aux, pertanto l punta alla stessa area di memoria allocata in precedenza;
if (root==NULL) questa condizione assicura che l'accesso al campo next attraverso il puntatore l avvenga solo alla seconda iterazione, per cui l è già stato inizializzato con un indirizzo valido.

mi ero lasciato sfuggire che quell'else avveniva nella prima iterazione


credo di aver capito per bene tutto anche se ora con questa cosa mi hai mandato in panico

Il compilatore tratta element come LIST anche se non gli assegni un indirizzo allocato con malloc.

se la malloc è facoltativa, quindi LIST* element basterebbe da solo per ereditare la dichiarazione della struttura (e farci tutte le operazioni)?
a questo punto void* element farebbe la medesima cosa?



p.s.
un mio professore tempo fa disse che il primo elemento di un array, il primo elemento di una struttura, una funzione sono in realtà dei puntatori, è esatto?
anche le classi?

[Daniels118]

malloc non è facoltativa, semplicemente se non la usi il compilatore non ti da errore, ma quando esegui il programma ottieni risultati imprevedibili e comunque non desiderabili. Al posto di malloc potresti utilizzare new, ma una delle due la devi utilizzare comunque.
C'è una terza possibilità, ovvero quella di allocare un LIST invece di un LIST*, ma non è la stessa cosa rispetto agli altri due metodi. Se ti interessa approfondire questo aspetto chiedilo esplicitamente.

LIST* element; basta a far capire al compilatore che element è un puntatore ad un area di memoria e che element ha dei campi definiti come indicato in "typedef struct lista".
LIST* element; basta anche ad allocare lo spazio sufficiente per un puntatore, che nel nostro sorgente chiameremo element.
LIST* element; non alloca la memoria necessaria per una struttura di tipo LIST; per quello bisogna usare malloc o new.
void* element; fa la stessa cosa di LIST* element; ma poi il compilatore non saprebbe che element ha dei campi chiamati val e next, quindi ti darebbe errore se provassi ad accedervi tramite element.

[Daniels118]

Per puntatore si intende una variabile che non contiene direttamente un dato utile all'elaborazione, ma indica il luogo dove si trova questo dato (o un altro puntatore).
Qualunque dato risiede in memoria, e pertanto ha un indirizzo. Tu puoi definire un puntatore e farlo puntare a qualunque indirizzo. Puoi anche valorizzare un puntatore in modo che punti nel mezzo di una struttura.

Quello che probabilmente ti ha detto il tuo professore è che:
il puntatore ad un array punta al primo elemento in quell'array;
il puntatore ad una struttura punta al primo campo in quella struttura;
il puntatore ad una stringa punta al primo carattere in quella stringa.

Una funzione è una porzione di codice che risiede in memoria, quindi ha un indirizzo, di conseguenza un puntatore potrebbe puntare ad una funzione. I puntatori a funzioni vengono utilizzati per chiamare le funzioni dinamicamente; l'utilizzo più comune ed ignorato dei puntatori a funzione in ambiente windows è la registrazione della callback per la gestione dei messaggi, indispensabile per la creazione delle finestre.

[sharkkk]

Originariamente inviato da Daniels118

malloc non è facoltativa, semplicemente se non la usi il compilatore non ti da errore, ma quando esegui il programma ottieni risultati imprevedibili e comunque non desiderabili. Al posto di malloc potresti utilizzare new, ma una delle due la devi utilizzare comunque.
C'è una terza possibilità, ovvero quella di allocare un LIST invece di un LIST*, ma non è la stessa cosa rispetto agli altri due metodi. Se ti interessa approfondire questo aspetto chiedilo esplicitamente.

LIST* element; basta a far capire al compilatore che element è un puntatore ad un area di memoria e che element ha dei campi definiti come indicato in "typedef struct lista".
LIST* element; basta anche ad allocare lo spazio sufficiente per un puntatore, che nel nostro sorgente chiameremo element.
LIST* element; non alloca la memoria necessaria per una struttura di tipo LIST; per quello bisogna usare malloc o new.
void* element; fa la stessa cosa di LIST* element; ma poi il compilatore non saprebbe che element ha dei campi chiamati val e next, quindi ti darebbe errore se provassi ad accedervi tramite element.

ora mi hai tolto ogni dubbio.

ho letto, e credo di aver capito che es. LIST element non si usa molto nei casi in cui abbiamo bisogno di usare e rimuovere strutture, perche occuperemmo memoria inutile sullo stack, mentre tramite LIST* element dinamicamente posso allocare/liberare lo spazio occupato in memoria (nello heap invece che sullo stack) dalla struttura

[Daniels118]

Una precisazione: dichiarare una variabile (o un puntatore) ha sempre effetti diversi a seconda che lo si faccia in una funzione o all'esterno.
Nel primo caso lo spazio per la variabile viene allocato nello stack e deallocato all'uscita dalla funzione: se la funzione non viene mai richiamata, quella variabile non occuperà mai spazio; nel caso di funzioni ricorsive la "stessa" variabile può essere allocata più volte contemporaneamente in memoria.
Nel secondo caso, la variabile finisce nell'area dati, che si trova fisicamente nel file eseguibile e quindi contribuisce alle sue dimensioni; queste variabili esistono per tutta l'esecuzione del programma, anche se non vengono utilizzate.

Il motivo principale per cui non vediamo spesso strutture allocate direttamente sullo stack è che esso è un'area abbastanza piccola e allocarvi una struttura (che può avere anche molti campi) può facilmente saturarlo, producendo un errore di stack overflow. Per lo stesso motivo array con molti elementi vengono sempre allocati con malloc invece che dichiararli con la dimensione tra parentesi quadre.
Ci sono poi delle vere e proprie esigenze, come far persistere la variabile all'uscita di una funzione; in questo caso è d'obbligo l'allocazione nell'heap, perchè lo stack viene sempre liberato al return.

[sharkkk]

a questo punto allora daniele la domanda è d'obbligo, lo stack generalmente che dimensioni ha?

immaginandosi un giorno di trovarsi davanti ad un progetto importante, presumo che questa domanda sia particolarmente importante.

la sua dimensione dipende dalla macchina, è possibile aumentare lo spazio di memoria riservato allo stack, come è possibile sapere la sua dimensione?

[Daniels118]

Parlando di PC, lo stack è parte della memoria e per questo può essere dimensionato dal programma stesso.
Nei sistemi Windows la dimensione dello stack per il thread principale di un programma è specificata nell'header del file eseguibile e può essere modificata inserendo gli opportuni parametri in fase di link; la dimensione predefinita è 1 MB, che è più che sufficiente anche per progetti importanti, basta che non allochi strutture enormi sullo stack. Per i thread secondari avviati con CreateThread è possibile specificare una dimensione diversa o quella predefinita.

Per i sistemi Unix non so, ma suppongo ci sia qualcosa di simile.

Per completezza aggiungo che molti microcontroller hanno uno stack hardware che ovviamente non può essere ingrandito.