Imprimă pagina - Weird List

Titlul: Weird List
Scris de: Cosmin Negruseri din Martie 16, 2012, 21:31:20

http://infoarena.ro/blog/weird-list

Titlul: Răspuns: Weird List
Scris de: Radu Grigore din Martie 16, 2012, 23:46:26

Poti sa aloci clona contiguu (cu malloc(sizeof(node)*size)) sau trebuie fiecare nod separat?

Titlul: Răspuns: Weird List
Scris de: Cosmin Negruseri din Martie 16, 2012, 23:51:36

Fiecare nod separat.

Titlul: Răspuns: Weird List
Scris de: MciprianM din Martie 17, 2012, 00:12:49

Se poate sa existe doua noduri diferite care sa aiba cel de-al doilea pointer spre acelasi element?

Titlul: Răspuns: Weird List
Scris de: Cosmin Negruseri din Martie 17, 2012, 00:19:35

Titlul: Răspuns: Weird List
Scris de: Florea Mihai Alexandru din Martie 17, 2012, 00:40:51

Parcurgem lista de 2 ori. Prima data pentru fiecare nod original, cream un nou nod si pentru acesta setam pointarul random spre pointerul random original din lista data, iar pointerul random al nodului original il setam catre nodul nou creat. La a 2-a parcurgere "corectam" legaturile.

Niste "pseudocod" ca sa fie mai clar:

Cod:

x = first;
prev = null;
while (x != null) {
   y = new Node();
   if (prev != null) prev->next = y;
   y->rnd = x -> rnd;
   x->rnd = y;
   x = x->next;
   prev = y;
}

for (x = first; x != NULL; x=x->next) {
   y = x->rnd;
   x->rnd = y->rnd;
   y->rnd = y->rnd->rnd;
}

Dap nu merge in caz ca exista legaturi random inapoi in lista.

Titlul: Răspuns: Weird List
Scris de: Cosmin Negruseri din Martie 17, 2012, 00:42:51

edit

Hmm, cred ca le incurci pe acolo. Verifica pe cateva exemple.

Titlul: Răspuns: Weird List
Scris de: MciprianM din Martie 17, 2012, 00:53:26

Si eu cred ca am gasit solutia:

http://pastie.org/private/kyheitcuspp4bosfxhkq (http://pastie.org/private/kyheitcuspp4bosfxhkq)

Titlul: Răspuns: Weird List
Scris de: Cosmin Negruseri din Martie 17, 2012, 00:56:15

Da Ciprian, a ta e buna :thumbup: Cred ca tre sa pun probleme mai grele :).

Titlul: Răspuns: Weird List
Scris de: Giurgea Mihnea din Martie 20, 2012, 20:17:03

Se poate modifica lista originala?

Titlul: Răspuns: Weird List
Scris de: Andrei Grigorean din Martie 21, 2012, 21:46:52

Da.

infoarena

Comunitate - feedback, proiecte si distractie => Blog => Subiect creat de: Cosmin Negruseri din Martie 16, 2012, 21:31:20