[C/C++]: Spiegazione delle "liste"

[awè]

E' da poco che ho a ke fare con il linguaggio C....
Non riesco a capire le liste......
Siccome a giorni dovrò sostenere un esame di programmazione... vorrei che qualcuno gentilmente mi potesse dare una mano.....
Attendo con ansia ke qualcuno mi risponda

[MItaly]

Non riesco a capire le liste......

Un po' generico, no? Qual'è il problema precisamente?

[mondobimbi]

dai una occhiata qui
o fai una ricerca su google "liste linkate"
ciao
sergio

[awè]

non riesco a capire in fase di programmazione.....
le linee di codice.......

premetto che sò inizializzare una lista.... come ad esempio:

struct prova
{
int info;
struct prova *next; /*con questa linea di codice faccio riferimento al prossimo elemento della lista*/
}

Fin qui ci sono....
Però ora arriva il bello..... quando mi trovo in questa situazione:

int *p;
p = p->next;

cioè che significa questa istruzione.......

io vorrei più che altro un disegno ke mi spiegasse il tutto, o meglio un disegno ke mi spiegasse il ragionamento o funzionamento delle liste in linguaggio c....

grazie....

p.s.
saranno ridicole queste cose per qualcuno ma io è da poco ke ho a ke fare con un linguaggio di programmazione tutto nuovo, quindi penso sia legittimo avere delle difficoltà agli inizi.

[pablo1986]

Originariamente inviato da awè
non riesco a capire in fase di programmazione.....
le linee di codice.......

premetto che sò inizializzare una lista.... come ad esempio:

struct prova
{
int info;
struct prova *next; /*con questa linea di codice faccio riferimento al prossimo elemento della lista*/
}

Fin qui ci sono....
Però ora arriva il bello..... quando mi trovo in questa situazione:

int *p;
p = p->next;

cioè che significa questa istruzione.......

io vorrei più che altro un disegno ke mi spiegasse il tutto, o meglio un disegno ke mi spiegasse il ragionamento o funzionamento delle liste in linguaggio c....

grazie....

p.s.
saranno ridicole queste cose per qualcuno ma io è da poco ke ho a ke fare con un linguaggio di programmazione tutto nuovo, quindi penso sia legittimo avere delle difficoltà agli inizi.

int *p


è un puntatore ad un intero


p=p->next;
vuol dire

FAI PUNTARE A P IL NODO PUNTATO DAL SUO CAMPO NEXT

per esempio(mnolto banale)

hai un p che punta al nodo A e attaccato al nodo A c'è il nodo B

come sai il campo next di A punta a B (essendo questi nodi legati tra loro)
se hai che p punta ad A
facendo

p=p->next

ora p non punterà piu' ad A ma a B,ovvero al NODO PUNTATO DA NEXT (P->NEXT)




ti farei anche il disegnino ma è una cosa lunga

[infinitejustice]

Se ti aiuti con uno schemino grafico su carta è semplice.
Ti scrivo i passi per una lista linkata singolarmente (ogni nodo punta al successivo, ma non al precedente).

1. Innanzitutto crei la tua struttura. Al suo interno ci vuole, oltre ai dati, un puntatore alla struttura stessa. Il giochino è fondamentalmente questo: ogni struttura ti indica (punta) a quella a lei successiva, quindi tu, avendo un puntatore alla prima della lista, puoi scorrerle tutte attraverso il puntatore. Cmq un po di codice...

struct myLinkedList {
int x;
struct myLinkedList *next;
} *first, *new;

Ho dichiarato anche due puntatori: il primo, first, come dice il nome, punta e punterà SEMPRE al primo elemento della lista. Non perderlo mai se no non hai modo di recuperarlo.

Il secondo puntatore lo usi per creare nuovi elementi, come indica il nome.

La prima cosa che ti conviene fare è first = NULL. In questo modo, quando andra ia scorrere la lista, e quindi tutti i suoi elementi, saprai quando fermarti proprio perchè sai che dopo quello che sarà ultimo ci sarà NULL.

Ed inoltre, se ci pensi, la lista è inizialmente vuota.

2. Creazione di un elemento.

if(!(new = (struct myLinkedList *)malloc(sizeof(struct myLinkedList))))
abort(); //errore nell'allocazione di memoria per il nuovo elemento.

Fatto ciò tu hai un nuovo elemento "vergine". Devi inizializzare i suoi campi e poi agganciarlo alla lista. Quindi new->x = 10;

3. Inserimento del nuovo elemento nella lista.
Qui c'è il trick di tutto ed entrano in gioco i puntatori. Tu hai first che punta al primo elemento della lista. first->next punta al secondo, first->next->next al terzo e cosi via.
Non importa quanti elementi ci siano, first punta sempre al primo. Se non vi sono elementi punta a NULL.

Quello che fai tu è dire a new che l'elemento a lui successivo è quello che ORA è primo
new->next = first;
...dopodichè aggiorni first in modo che punti al NUOVO primo elemento (perche ora first punta al secondo e a te serve che punti al primo, sempre), quindi...
first = new;

E' importante l'ordine dei due comandi, perche se lo inverti ti salta tutto.

4. Per scorrere gli elementi fai un ciclo finchè non trovi NULL...

struct myLinkedList *current;
current = first;
while(current != NULL)
current = current->next; //passo al successivo

E' importante creare un nuovo puntatore, perche se usi direttamente first poi perdi gli elementi.


Volendo puoi integrare una funzione di sorting che te la tenga costantemente ordinata.

[awè]

per quanto riguarda le funzioni.........
chi mi potrebbe dare una mano?

Allora, spiego le mie incertezze......

1. Ho una funzione.
la dichiaro prima del main() dichiarandola con il suo prototipo.

all'interno del main() come faccio a capire quando è il momento opportuno di fare la chiamata alla funzione?

2. quali parametri o meglio quali argomenti devo passare alla funzione?

3. quando devo passare alla funzione un puntatore ad intero o a carattere (mi è noto che un puntatore a carattere sarebbe un puntatore al primo elemento di una stringa).

Vorrei che qualcuno chiarisca bene le mie incertezze e con alcuni esempi.
Grazie.

[pablo1986]

Originariamente inviato da awè
per quanto riguarda le funzioni.........
chi mi potrebbe dare una mano?

Allora, spiego le mie incertezze......

1. Ho una funzione.
la dichiaro prima del main() dichiarandola con il suo prototipo.

all'interno del main() come faccio a capire quando è il momento opportuno di fare la chiamata alla funzione?

2. quali parametri o meglio quali argomenti devo passare alla funzione?

3. quando devo passare alla funzione un puntatore ad intero o a carattere (mi è noto che un puntatore a carattere sarebbe un puntatore al primo elemento di una stringa).

Vorrei che qualcuno chiarisca bene le mie incertezze e con alcuni esempi.
Grazie.

scusa se posso semorare scortese


MA MI SEMBRANO DOMANDE MOLTO GENERICHE

devi fare eserrcizio, poio quando trovi qualcosa che nn riesci a comprendere chiedi pure
postando la traccia che non riesci a svolgere ma cosi' le domande da te poste sono molto
generiche

[infinitejustice]

all'interno del main() come faccio a capire quando è il momento opportuno di fare la chiamata alla funzione?

Guardala cosi. Una funzione è un blocco di codice indipendente che svolge (possibilmente) un compito preciso. Generalmente quando ti viene dato un compito ti viene detto cosa devi fare, ma sei tu a decidere come farlo.

Visto che la funzione ti serve per fare qualcosa che ti servirà una o piu volte (se no, perche farla?) allora la chiamerai quando hai bisogno di fare quel compito... magari perchè ti serve il risultato per proseguire o per confrontarlo con altri valori.

Quando hai un problema da risolvere, scomponilo in tante parti separate, piu piccole e quindi piu semplici da svolgere. Per ognuna di esse crei una funzione, poi le invochi nell'ordine corretto.

quali parametri devo passare alla funzione?

Questo lo dovrai sapere tu in base a quello che devi fare. Sicuramente devi passargli dei parametri del tipo richiesti dalla funzione. Es. se devi lavorare su un triangolo e la funzione calcolaArea ti chiede base ed altezza (numeri reali) gli passerai due double (o float).

Pensa sempre a cosa deve fare la funzione. Di cosa ha bisogno. E cosa ti restituisce.

quando devo passare alla funzione un puntatore ad intero o a carattere

Quando la funzione lo richiede espressamente...

void funzioneProva(int *, int);

E' plausibile pensare che questa funzione voglia come primo parametro un puntatore ad intero (magari un vettore) e come secondo un intero (la dimensione).

Se sei tu che programmi... sei tu che decidi cosa fa una funzione e di cosa ha bisogno, quindi sei tu che stabilisci se andrà a lavorare con dei puntatori.

[awè]

Dopo aver dichiarato una lista.....

struct elementi
{
int x;
struct elementi *next;
}

la devo passare ad una funzione......

void inserisci (struct elementi **, int);

perchè in questo caso viene passato un doppio puntatore?