[c] - linked list

[ilgrigio]

Ciao a tutti!
ho un esercizio da risolvere che proprio nn ho capito, premetto che sono alle prime armi con le linked lists .
ecco il testo :
Gestione camere d'albergo - simulare in C la linked list tramite due array statici : il primo contenente le informazioni (può essere anche un array di struct), il secondo array contenente i link(puntatori ai nodi della lista).
E' necessario creare prima una "lista libera" inizializzando l'array dei link in modo che ogni componente punti alla componente successiva. La "lista libera" corrisponde alla memoria in cui allocare la lista delle informazioni : infatti i nodi da inserire nella linked list delle informazioni sono prelevati dalla lista libera, mentre i nodi da eliminare dalla lista delle informazioni vanno restituiti alla lista libera.

--------------------------------

Non ho capito bene il testo e ho difficoltà a capire come impostare l'algoritmo. Che pensate? Secondo voi devo far uso solo di array statici o usare :

struct linked_list {
DATA d;
struct linked_list *next;
};

typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;

[NeoNum6]

simulare in C la linked list tramite due array statici


se dici che devi simulare una lista con array statici vuole dire che quella struttura che dici tu(che è una lista) non va bene...

[Prince_81]

Anche io sto affrontando lo stesso esercizio e non ho ancora capito bene se qualcuno vuol riaprire l'argomento ne sarò lieto.

Anche se è stato aperto nel 2006:doh:

[Prince_81]

La struttura creata da ilgrigio non va bene perchè utilizza i puntatori io dovrei invece creare una lista con array statici come dici l'esercizio, qualcuno di voi saprebbe guidarmi sulla creazione della struttura?

Per esempio

struct nodo{int nome[30];int pnext;}persona[100];

[NeoNum6]

La struttura creata da ilgrigio non va bene perchè utilizza i puntatori io dovrei invece creare una lista con array statici come dici l'esercizio, qualcuno di voi saprebbe guidarmi sulla creazione della struttura?

Per esempio

struct nodo{int nome[30];int pnext;}persona[100];

Prince_81: che vuoi fare? spiegati meglio.

[cionci]

Una lista con array statici la puoi simulare tranquillamente.
Crei un array di struct.
La struttura dati sarà di questo tipo:

struct nodo
{
xxxx info;
int next;
int free;
};

free ha valore 0 o 1 a seconda se l'elemento è libero o meno. next contiene l'indice dell'array contenente l'elemento successivo della lista, -1 se è l'elemento in coda alla lista. Ovviamente bisogna mantenere l'indice a quello che sarà l'elemento in testa alla lista.

Questo se non si utilizzano i puntatori. Volendo si potrebbero comunque utilizzare i puntatori facendo in modo che next punti direttamente all'indirizzo del prossimo elemento all'interno del vettore.
Inoltre volendo si può ottimizzare l'inserimento (nel caso sopra la ricerca della posizione in cui inserire un nuovo elemento è O(n) perché bisogna ricercare il primo elemento libero) mantenendo un altro vettore, come coda circolare o come stack (forse meglio il secondo per il principio di località), in cui inserire tutti gli indici che contengono gli elementi liberi nell'altro vettore (ovviamente free non serve più).

[Prince_81]

cionci sei stato molto chiaro ma non ho capito una cosa l'array lista_libera lo devo creare? perchè l'esercizio lo consiglia ma non so se è obbligatorio. se si iniziano da 1 gli elementi?

[cionci]

Puoi utilizzarlo o meno, se non lo utilizzi devi immettere un flag "free" nella struttura dati che indica se quell'elemento è libero o meno. Se lo utilizzi però fallo sotto forma di stack, perché viene proprio carino ;)

[Prince_81]

se decido si usare l'array listalibera devo inserirlo nella struct cioè

struct nodo {char nome[20];int next;
int listalibera[9];};

oppure sarebbe meglio come un array esterno alla struct ? secondo me la seconda soluzione è la migliore.

[cionci]

Ovviamente come array esterno ;)

[Prince_81]

Da come ho capito l'ultimo elemento di questo array cioè listalibera deve essere -1 per segnalare la fine dei posti vuoti è vero?

Scusami per le troppe domande è solo che questo esercizio mi sta facendo impazzire

[Oceans11]

Da come ho capito l'ultimo elemento di questo array cioè listalibera deve essere -1 per segnalare la fine dei posti vuoti è vero?

Scusami per le troppe domande è solo che questo esercizio mi sta facendo impazzire

scusate l'intromissione! :)

Cmq da quel che ho capito, no non deve essere -1.

L'ultimo elemento di listalibera deve puntare all'ultimo elemento della lista e basta! Poi è un array....lo sai che quello è l'ultimo!;)

[Prince_81]

listalibera quindi parte da 0 o da 1 ? :muro:

[cionci]

No non deve essere così, dovresti semplicemente mettere 0 nei posti vuoti e 1 nei posti occupati. Scorrertelo fino a trovare un posto libero (a 0) per fare un inserimento, poi al momento dell'eliminazione di un nodo basta inserire zero nel indice corrispondente.
Secondo faresti meglio a gestirlo come stack, è molto più semplice: all'inizio il vettore devi riempirlo con tutti gli indici (sono tutti liberi). Al momento dell'inserimento recuperi l'indice di un elemento libero dalla testa dello stack, al momento dell'eliminazione reinserisci l'indice dell'elemento nuovamente libero nello stack.

[cionci]

L'ultimo elemento di listalibera deve puntare all'ultimo elemento della lista e basta! Poi è un array....lo sai che quello è l'ultimo!;)
Perché questa cosa ? Secondo me deve solamente indicare che un nodo è presente/assente.

[cionci]

Prince_81: però mi sorge un dubbio: come ti è stato chiesto di implementare questa lista ? Perché l'esercizio dice una cosa diversa da quella che dico io. Quella diciamo è un'implementazione un po' particolare.

[Prince_81]

Siimullare in C una linked lliistt ttramiitte due array sttattiicii:: iill priimo
conttenentte lle iinformaziionii (può essere anche un array dii
sttructt),, iill secondo array conttenentte ii lliink (punttattorii aii nodii
delllla lliistta)..
[È necessario creare prima una “lista libera”, inizializzando l’array
dei link in modo che ogni componente punti alla componente
successiva. La lista libera corrisponde alla memoria in cui allocare
la lista delle informazioni: infatti i nodi da inserire nella linked list
delle informazioni, sono prelevati dalla lista libera; mentre i nodi da
eliminare dalla lista delle informazioni vanno restituiti alla lista
libera.]

l'esercizio consiglia

array di struct NODO {INFO, pnext}
simula la memoria dove saranno
allocati i nodi della lista lineare
ListaDati.
p_Libera
Per rendere dinamica la gestione della
“memoria simulata” viene creata inizialmente
la lista lineare ListaLibera (con p_Libera
puntatore alla sua testa)

[cionci]

Ah che complicazioni inutili :muro:
Un nodo che fa parte della lista libera è un nodo non appartenente alla lista vera e propria. Un nodo della lista libera punta sempre ad un nodo della lista libera, tranne l'ultimo che punterà a -1 (stessa cosa per la lista vera e propria).
Ti devi ovviamente tenere un indice esterno che punta al primo elemento della lista libera ed un indice esterno che punta al primo elemento della lista vera e propria.
La lista libera è composta solo da "puntatori" a next (in questo caso non sono puntatori, ma indici del vettore).
Ad esempio se sono liberi gli elementi 2, 3, 4, 6, 8 su 10 elementi, il puntatore esterno punterà a 2. Il contenuto del vettore sarà:

x, x, 3, 8, 6, x, -1, x, 4, x (supponendo che siano linkati così: 2->3->8->4->6)

Gli inserimenti di indici liberi ti converrà farli in testa. Così come l'aggiunta di nodi liberi.

[Oceans11]

Perché questa cosa ? Secondo me deve solamente indicare che un nodo è presente/assente.

io intendevo una cosa del genere (vedi allegato)

[cionci]

io intendevo una cosa del genere (vedi allegato)
Sì, ha senso, però per trovare un elemento libero ti devi scorrere tutta la lista.

[Oceans11]

Sì, ha senso, però per trovare un elemento libero ti devi scorrere tutta la lista.

beh in effetti....:rolleyes:

però mi sembra proprio semplice così, anche se ammetto che l'idea dello stack è di gran lunga più elegante

[cionci]

però mi sembra proprio semplice così,
Sicuramente più semplice di tenersi le due liste come richiesto dal suo esercizio :D

[Oceans11]

Sicuramente più semplice di tenersi le due liste come richiesto dal suo esercizio :D

Bah a dirla tutta, il testo di quell'esercizio è proprio contorto secondo me........lo sto leggendo e rileggendo, ma la mia comprensione peggiora di volta in volta :muro:

sarò io!?!

[cionci]

sarò io!?!
Non sei tu, tranquillo :D A meno che non lo sia anche io :muro:

[Prince_81]

quindi lista libera la creo in questo modo:

void lista_libera(int x[]){
int i;

for(i=0;i<7;i++){
x[i]=i+1;
}
x[i++]=-1;
}

[cionci]

Sì

[Prince_81]

non capisco queste immagini relative ai nodi le metto in allegato

[Prince_81]

ecco la seconda, perchè next viene decrementato a -1 se dovrebbe puntare al nodo successivo?

[marco.r]

Siimullare in C una linked lliistt ttramiitte due array sttattiicii:: iill priimo
conttenentte lle iinformaziionii (può essere anche un array dii
sttructt),, iill secondo array conttenentte ii lliink (punttattorii aii nodii
delllla lliistta)..
[È necessario creare prima una “lista libera”, inizializzando l’array
dei link in modo che ogni componente punti alla componente
successiva. La lista libera corrisponde alla memoria in cui allocare
la lista delle informazioni: infatti i nodi da inserire nella linked list
delle informazioni, sono prelevati dalla lista libera; mentre i nodi da
eliminare dalla lista delle informazioni vanno restituiti alla lista
libera.]

l'esercizio consiglia

array di struct NODO {INFO, pnext}
simula la memoria dove saranno
allocati i nodi della lista lineare
ListaDati.
p_Libera
Per rendere dinamica la gestione della
“memoria simulata” viene creata inizialmente
la lista lineare ListaLibera (con p_Libera
puntatore alla sua testa)

L'esercizio e' spiegato un po' male, nel senso che prima sembra si debbano usare due array distinti (con tipi diversi) e invece nel suggerimento sembra si consigli di usarne uno solo, da usare sia per la lista vera e propria sia che per la lista libera. Mi sembra che questo sia piu' sensato. In questo modo minimizzi l'uso della memoria (usi un solo array) e garantisci prestazioni asintotiche migliori. Inoltre funziona anche quando vuoi creare piu' liste da un unico array


Io farei qualcosa cosi'

typedef ... Info;
typedef size_t Ptr;

#define MEMORY_SIZE ...
#define NULL_NODE MEMORY_SIZE

struct Node { Info data; Ptr next; };

Node memory[MEMORY_SIZE];

Ptr myList;

void initFreeList();
Ptr nodeAlloc();
void nodeFree(Ptr);
...

nodeAlloc e nodeFree sono due funzioni che usi per "allocare memoria" (i.e. farti dare il prossimo elemento dalla lista libera e poi liberarlo), ad esempio

void append( Ptr list, Info value )
{
while ( memory[list].next != NULL_NODE )
list = memory[list].next;
memory[list].next = nodeAlloc();
list = memory[list].next;
memory[list].data = value;
memory[list].next = NULL_NODE;
}

L'aspetto carino dell'approccio e' che puoi tenere "nascosto" il puntatore alla memoria libera e scrivere gli algoritmi semplicemente usanto nodeAlloc e nodeFree, a mo' di malloc e free. Se fai cosi' poi l'implementazione del resto dovrebbe venirti abbastanza naturale (al netto del sostituire quello che in C sarebbe "ptr->x" con "memory[ptr].x")

[cionci]

Ah ok, stanno cercando di fare una finezza :D -1 perché è l'ultimo elemento della lista occupata. Comunque è spiegato veramente malissimo.
In pratica ti puoi gestire tutto con due soli vettori, uno di informazioni (mettiamo che siano interi) ed uno di indici. Di fatto il nodo è composto dalla sola informazione, non c'è next come avevamo detto.
Mettiamo che la situazione sia questa (8 elementi):
- lista dei liberi: 1 -> 5 -> 3 -> 7
- lista occupati (fra parentesi il valore delle informazioni): 6 (1) -> 0 (2) -> 2 (3) -> 4 (4)

I due vettori saranno (D = Dati. P = Puntatori):

p_liberi = 1
p_occupati = 4

D I
0 2 2
1 x 5 <--- p_liberi
2 3 4
3 x 7
4 4 -1 <--- fine lista occupati
5 x 3
6 1 0 <--- p_occupati
7 x -1 <--- fine lista liberi

In pratica la lista degli occupati e dei liberi convivono nello stesso vettore.

[marco.r]

Vado a memoria (non ce l'ho sotto mano) ma mi sembra che sia piu' o meno come e' spiegato nel Cormen.

[Prince_81]

i vostri esempi sono molto buoni, quello ci cionci mi sembra però più semplice e comprensibile per me, forse lui ha capito bene quello che il mio esercizio vuole.

Cionci non vorrei essere ripetitivo ma l'array degli indici va sempre inizializzato come ti ho fatto vedere nell'algoritmo di prima?
void lista_libera(int x[]){
int i;

for(i=0;i<7;i++){
x[i]=i+1;
}
x[i++]=-1;
}

se si il primo elemento è uguale a 1 ma per inserire un elemento in cima all'indice dell'array informazioni mi serve un indice uguale a 0 è questo che mi confonde ora, cioè quando io estraggo un nodo da lista libera questo parte da 1 ???

p_liberi all'inizio è inizializzato a 0 o a 1????????????????

mentre p_occupati all'inizio è inizializzato a -1???

[Prince_81]

Finalmente ho capito cosa mi confondeva nell'esempio che vi ho fornito con le immagini, era la visaulizzazione delle informazioni che io prentendevo avvenisse partendo dalla lettera A, mentre la testa è p_data ed è da li che bisogna iniziare a leggere le informazioni, ecco un immagine di quanto detto.

[Prince_81]

Grazie ragazzi e soprattutto a te Cionci che hai capito fin da subito cosa voleva l'esercizio e con i tuoi esempi mirati mi hai guidato verso la soluzione.