[es] - Linked list

DARK_MESSIAH
Student

Član broj: 302569
Poruke: 22
82.118.5.*

+6 Profil

^{01.08.2012. u 02:00 - pre 142 meseci}

Imam zadanu listu (jednostruka, gdje u strukturi imam Cvor *sljedeci i int broj)...
Zadatak mi je da zamijenim pozicije drugom i četvrtom članu liste.
Ja sam to uradio ovako:

Code:
void *zamijeni(Cvor *glava)
{
    Cvor *tmp = glava;
    while(tmp -> sljedeci -> sljedeci != NULL)
    {
        tmp = tmp -> sljedeci;
        Cvor *tmp2 = tmp -> sljedeci;
        tmp -> sljedeci = glava;
        Cvor *tmp3 = glava -> sljedeci;
        glava -> sljedeci = NULL;
        tmp2 -> sljedeci = tmp3;
        glava = tmp2;
    }
}

Ali u zadatku kad hoću da pozovem funkciju, ne dešava se ništa. Lista i dalje ostaje ista... Pa da vas pitam jesam li pogriješio u implementaciji ove funkcije "zamijeni" ili je negdje drugo greška u zadatku?

_{[Ovu poruku je menjao Mihajlo Cvetanović dana 01.08.2012. u 10:29 GMT+1]}

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Linked list - pitanje

^{01.08.2012. u 10:21 - pre 142 meseci}

Za ovaj zadatak ne treba ti petlja, jer treba da uradiš samo jednu stvar, da zameniš mesta drugom i četvrtom elementu liste. Petlja može da posluži da pronađeš drugi i četvrti element (može i bez petlje), ali sama zamena treba da bude van petlje. Kad tražiš elemente koje treba zameniti bolje je zapravo da pronađeš prethodni element svakom kojeg tražiš, jer ti trebaju prethodni elementi da lepo prepovežeš sve elemente.

Postoji i jedno "trik" rešenje. Umesto da prevezuješ elemente možeš da zameniš sadržaj čvorova. Ovo može biti prihvatljivo rešenje, ali i ne mora, zavisi od toga šta se tačno traži.

Odgovor na temu

DARK_MESSIAH
Student

Član broj: 302569
Poruke: 22
82.118.5.*

+6 Profil

Re: Linked list - pitanje

^{01.08.2012. u 13:50 - pre 142 meseci}

Hmm, pa treba mi petlja da nađem članove (baš onako kako ste rekli). Jer čvorovi nisu fiksni. U zadatku su još i razne funkcije dodavanja i brisanja čvorova. A ne mogu mijenjati sadržaj čvorova jer ovo mi je ispitni zadatak :D i potrebne su mi samo implementacije.

Btw, ako neko ima kakav materijal za preporučiti da se tiče ovog vezanja liste, mijenjanje pozicija itd... bio bih veoma zahvalan. (Mislim na slikovita objašnjenja, ne kod.)

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Linked list - pitanje

^{01.08.2012. u 14:44 - pre 142 meseci}

Zamislimo da nisu u pitanju drugi i četvrti element liste, nego N-ti i M-ti. Šta sve treba uraditi da ta dva elementa zamene mesta?

1. Element M-1 treba da pokazuje na element N
2. Element M treba da pokazuje na ono na šta je pokazivao element N
3. Element N-1 treba da pokazuje na element M
4. Element N treba da pokazuje na ono na šta je pokazivao element M

Recimo da imaš nekako pokazivače na ova četri elementa koja treba promeniti. Treba nam i dva pomoćna pokazivača koji će pokazivati na ono na šta trenutno pokazuju M i N. Recimo da se zovu m_prethodni, m, m_sljedeci, n_prethodni, n, n_sljedeci. Svi su tipa "pokazivač na Cvor", odnosno Cvor*. Ovo je kod koji ih podešava:

Code:

m_prethodni->sljedeci = n;
m->sljedeci = n_sljedeci;
n_prethodni->sljedeci = m;
n->sljedeci = m_sljedeci;

Ali kako doći do ovih šest pokazivača? U opštem slučaju treba ti petlja u kojoj bi brojao do čvorova M i N, ali u ovom slučaju do svega se može doći i ručno. Ako je M drugi, a N četvrti imamo sledeće:

Code:

m_prethodni = glava;
m = m_prethodni->sljedeci;
m_sljedeci = m->sljedeci;
n_prethodni = m_sljedeci;
n = n_prethodni->sljedeci;
n_sljedeci = n->sljedeci;

Bolje bi bilo da funkcija bude opšteg tipa, odnosno da ima parametre koji su pozicije dva elementa koja treba zameniti. Za to ti treba petlja, i ako želiš takvo rešenje probaj da ga sam napraviš.

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Linked list - pitanje

^{01.08.2012. u 14:47 - pre 142 meseci}

Za funkciju opšteg tipa specijalan slučaj je ako je jedan od dva elementa prvi u nizu. Možda je drugi specijalan slučaj ako su dva elementa susedna (možda i nije, mrzi me sad da razmišljam).

Odgovor na temu