[c] - linked list

[Oceans11]

Originariamente inviato da cionci

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

beh in effetti....

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

[cionci]

Originariamente inviato da Oceans11

però mi sembra proprio semplice così,

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

[Oceans11]

Originariamente inviato da cionci

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

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

sarò io!?!

[cionci]

Originariamente inviato da Oceans11

sarò io!?!

Non sei tu, tranquillo A meno che non lo sia anche io

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

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

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