[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

[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]

Originariamente inviato da 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];

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]

Originariamente inviato da 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

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 ?

[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]

Originariamente inviato da Oceans11

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
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]

Originariamente inviato da cionci

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

io intendevo una cosa del genere (vedi allegato)

[cionci]

Originariamente inviato da Oceans11

io intendevo una cosa del genere (vedi allegato)

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