[C++] chi mi spiega un po' a cosa servono le liste

[nacre]

in pratica per cosa possono essere utilizzate
grazie.
ciao.

[dany-]

Le usi quando devi allocare degli elementi in maniera dinamica, in pratica quando non sai se e' sufficiente allocare 30 Mb di vettore perche' potrebbe essere poco... oppure troppo! :gren:

Ciao
Daniele

[nacre]

potresti essere piu' preciso.
grazie.
ciao dalla nacre.

[dany-]

Bhe, una lista è un insieme di blocchi di memoria ognuno dei quali ha al suo interno le informazioni che servono (es. nome, cognome, .. o altro) e uno spazio per un puntatore ad un altro blocco di memoria (l'elemento successivo). La creazione avviene dinamicamente (a run time).

Credo che l'utilizzo principale sia dovuto al fatto che allochi gli elementi dinamicamente.

Una variante delle liste sono gli alberi (es. di albero: quello delle directory).

Ciao
Daniele

[nacre]

ciao dalla nacre e buon weekend.

[iloiacorb]

Comunque una lista oppure un albero come vuoi possorno essere utilizzati come indici, ovvero comme strutture per una consultazione rapida, quindi applicate ad un DB, oppure ad un'insieme di file caricati in memoria come se fossero i capitoli di un libro.
Si possono creare Spool di stampe, se si considera come una coda.
Comunque come è stato detto può essere utilizzato come un semplice vettore, o per creare una rubrica.
Comunque se ti registri inwww.studenti.it e cerchi su informatica C++ troverai tantissime tesine e spiegazioni su liste, alberi e code

[r0x]

typedef struct
{
    int number; // informazione
    Nodo* next; // puntatore al nodo successivo
} Nodo;

Se si hanno quattro nodi definiti come sopra e inizializzati in modo opportuno (...), un esempio di lista può essere questo:

A -> B -> C -> D

Dove con la freccia indico che ogni nodo "sa" che nodo si trova davanti ad esso, informazione che si ottiene dal puntatore 'next'. Ecco come può essere creata in breve quella lista:

void main()
{
    Nodo A, B, C, D;
    Nodo* primoElemento = &A;

    A.number = 1;
    B.number = 2;
    C.number = 3;
    D.number = 4;

    A.next = &B; // A.next punta a B, A -> B
    B.next = &C; // B.next punta a C, B -> C
    C.next = &D; // C.next punta a D, C -> D
}

Il tutto si risolve in:

A -> B -> C -> D

Una volta ottenuta questa struttura, la si può facilmente scorrere attraverso i campi 'next'. Se in questo caso volessi il generico 3° elemento della lista:

const unsigned indiceNodo = 3;
Nodo* nodoDaCercare = primoElemento; // punta quindi ad 'A'

for( unsigned i = 1; i < indiceNodo; i++ )
    nodoDaCercare = nodoDaCercare->next;

Ed ecco che con questo breve codice avremo un puntatore 'nodoDaCercare' a 'C'.

La flessibilità di una lista sta nel fatto che può essere gestita in modo dinamico (come ha detto dany), senza il problema di riallocare tutti gli elementi. Ad es., se si volesse aggiungere un elemento alla fine:

A -> B -> C -> D -> E

Basterebbe creare un nuovo nodo 'E', scorrere tutta la lista, e far puntare 'D.next' a questo nuovo nodo creato.

N.B.: per far sì che "ci si accorga" di essere arrivati alla fine della lista, per convenzione si imposta il campo 'next' dell'ultimo elemento a NULL (sinonimo di '0', puntatore nullo), altrimenti si rischia un ciclo di scorrimento infinito!

Questo è uno dei più semplici esempi di tipo di dato astratto. Altri possono essere pile (o stack), code, alberi ecc. ecc., usati cmq a seconda delle proprie esigenze.

Spero di essere stato chiaro.

Ciao.

P.S.: non hai specificato il linguaggio nel quale intendevi avere la spiegazione, quindi l'ho scritto con quello a me più congeniale. :adhone: Se hai problemi col C fammi sapere così al limite te lo traduco in un altro linguaggio, se posso.

[hmesfet]

1)tipico esempio di lista è una rubrica
il cui numero di utenti memorizzati
cambia diminuendo(cancellazione)o
aumentando(inserzione)
Quindi la "base dati" non puo' essere "statica"
ovvero fissata all'atto della stesura del
programma,ma "varia" durante l'esecuzione
del programma(inserisco,cancello)siamo
cioè in presenza di un fenomeno "dinamico"
(il numero di utenti della rubrica cambia)
da cui la dizione "Allocazione Dinamica"
2)le variabili "statiche" sono referenziate
tramite il loro "identificatore" o nome
simbolico(int numero;numero:identificatore)
questo meccanismo ci permette di evitare
di lavorare sulle locazioni di memoria,
il compilatore riserva uno spazio di memoria
di dimensione pari al "tipo"(int 4 byte,char 1 byte)
a cui noi (inconsapevoli)acccediamo tramite il suo
identificatore,fregandocene della reale tecnica
di gestione della memoria.
Ma qualunque oggetto che risiede in memoria
deve avere un indirizzo di memoria,nel caso
statico il meccanimo dell'identificatore
ci permette di poter fare ameno della conoscenza
dell'indirizzo,se si vuole conoscere si procede cosi':
int a;
int *pI=a;
a=2;
printf("%p,%Fp\n",pI,pI);
/*stampo l'indirizzo di a*/
Nel caso "dinamico",non esiste l'identificatore
in quanto le variabili dinamiche vengono allocate
durante l'esecuzione del programma,che facciamo?
Usiamo l'altro metodo(l'unico possibile)
ovvero i puntatori,che sostituiscono l'identificatore.
esempio
char *p;
if(p=(char*)malloc(sizeof(char)))==NULL)
perror("malloc");
/*con questa istruzione creo una variabile dinamica*/
/*il cui identificatore è il puntatore p*/
/*quindi se ci voglio scrivere dentro qualcosa*/
*p='l';
Le liste sono un insieme di variabili dinamiche
legate tra loro tramite puntatori
esempio di lista
/******************************************/
/* lista per rubrica */
/******************************************/
typedef struct user
{
char nome[30];
char cognome[30];
struct user *successivo;/*puntatore che lega le variabili dinamiche*/
}Utente;

/*creo la lista*/
Utente *Phead=NULL;
Utente *Pcorr=NULL;
Utente Aux;
char car;
printf("Iserisci i dati per gli utenti\n");
while(car!='n')
{
printf("NOME: ");
scanf("%s",Aux.nome);
printf("COGNOME: ");
scanf("%s",Aux.cognome);
/*creo la prima variabile dinamica*/
if((Pcorr=(Utente*)malloc(sizeof(Utente)))==NULL)
{
perror("malloc()");
return -1;
}
/*riempio i suoi campi*/
(*Pcorr)=Aux;
/*faccio il collegamento*/
Pcorr->successivo=Phead;
Phead=Pcorr;
printf("finire?[y/n]\n");
scanf("%c",&car);
}
free(Phead);
/*in tal modo possiamo inserire quanti utenti vogliamo*/
/*senza che sia stata fissata la dimensione delle */
/*struct da usare*/