PDA

Visualizza la versione completa : [C] Problema lista dinamica con puntatore al successivo e puntatore all'ultimo


SivaCorp
14-02-2012, 19:08
Salve a tutti. Ho un quesito di informatica che mi si era posto nell'esame di informatica e ancora adesso non riesco a risolvere.
Ho una lista con una struttura dati così:

typedef struct nodo{
int val;
struct nodo *succ;
struct nodo *ult;
}NODO;

typedef struct NODO *LISTA;

Praticamente la lista ha un puntatore *succ che punta all'elemento successivo e un puntatore *ult che punta sempre all'ultimo elemento. Vien da se che quindi l'ultimo elemento avrà il puntatore *succ che vale NULL (non essendoci altri elementi) e il puntatore *ult che punta alla struttura nodo di se stesso (essendo l'ultimo elemento appunto). Non riesco a capire come faccio a fare puntare a nodi precendenti l'ultimo elemento. Di conseguenza non riesco a buttare giù questa funzione: "Devo dichiarare la funzione di inserimento di un nodo in testa sia nel caso fosse vuota sia nel caso ci fossero già degli elementi".

oregon
14-02-2012, 19:24
Originariamente inviato da SivaCorp
come faccio a fare puntare a nodi precendenti l'ultimo elemento.

Non capisco perché devi preoccuparti dell'ultimo nodo se devi aggiungere un nodo in testa ...

Prova a spiegare meglio il tuo dubbio con un esempio pratico.

SivaCorp
14-02-2012, 19:35
Originariamente inviato da SivaCorp
Praticamente la lista ha un puntatore *succ che punta all'elemento successivo e un puntatore *ult che punta sempre all'ultimo elemento

Perchè praticamente la struttura del nodo ha due puntatori, una che punta al nodo successivo e una che punta all'ultimo nodo, se inserisco il nodo in testa so che il puntatore successivo è quello precedentemente puntato da testa ma come faccio a far puntare il puntatore all'ultimo elemento?

Provo a farvi un esempio pratico:

void inserisciInTesta(LISTA *l, int informazione)
{
NODO *punt;
punt=(Nodo*)malloc(sizeof(NODO));
punt->val=informazione;
punt->succ=*lista;
punt->ult=ult; /*IN QUESTA RIGA HO IL DUBBIO-- punt->ult a cosa deve essere uguale? Nel senso come faccio ad assegnarli a punt->ult il puntatore dell'ultimo elemento?*/
*Lista=punt;
}

ramy89
14-02-2012, 23:49
Non è un problema, se aggiungi elementi solo in testa dovrai cambiare il valore di ult solo una volta :


void inserisciInTesta(LISTA l, int informazione) // non serve un puntatore, il tipo
{ // LISTA è già un puntatore a NODO
NODO *punt,*temp=l->succ;
punt=(Nodo*)malloc(sizeof(NODO));
punt->val=informazione;
if(temp==NULL) // Significa che la lista è vuota
{
...
}
else // la lista non è vuota
{
...
}
}


Ora puoi scrivere la funzione completa.Se la lista è vuota devi aggionare anche il valore di ult e collegare il nodo creato con la sentinella.Se non è vuota devi devi anche collegarlo al (all' ex-) primo elemento della lista.

Loading