[C] kazalčni seznam

Evo, delam funkcijo oz. program, ki sprejme kazalčni seznam in ga obrne, se pravi, da elementi potem nastopajo v novem seznamu od zadnjega do prvega. Funkcija očitno deluje pravilno, težave pa imam pri izpisu testnega seznama oziroma obrnjenega testnega seznama. Originalni seznam mi izpiše brez težav, ko pa hočem izpisat obrnjen seznam, pa mi program zamrzne. Sem kaj spregledal? :S

Pa še koda:

#include<stdio.h>
#include<stdlib.h>

struct el
{
int vrednost;
struct el *next;
};


void obrni(struct el **zac)
{

struct el *p,*nov,*dod;

if (zac==NULL)
	return;

p=*zac;
while(p!=NULL)
{
if(nov==NULL)
{
	dod=(struct el *)malloc(sizeof(struct el));
	dod->vrednost=p->vrednost;
	dod->next=NULL;
	nov=dod;
}
else
{
	dod=(struct el *)malloc(sizeof(struct el));
	dod->vrednost=p->vrednost;
	dod->next=nov;
	nov=dod;
}
p=p->next;
}
*zac=nov;

}

int main()
{
struct el *sez,*prvi,*drugi,*tretji,*cetrti,*r,**psez;

//elementi seznama
prvi=(struct el *)malloc(sizeof(struct el));
prvi->vrednost=1;
prvi->next=NULL;
drugi=(struct el *)malloc(sizeof(struct el));
drugi->vrednost=2;
drugi->next=NULL;
tretji=(struct el *)malloc(sizeof(struct el));
tretji->vrednost=3;
tretji->next=NULL;
cetrti=(struct el *)malloc(sizeof(struct el));
cetrti->vrednost=4;
cetrti->next=NULL;
sez=prvi;
prvi->next=drugi;
drugi->next=tretji;
tretji->next=cetrti;

//izpis seznama
r=sez;
while(r!=NULL)
{
printf("%d\n",r->vrednost);
r=r->next;
}

psez=&sez;
obrni(psez);
printf("Obrnjeno: \n");

//izpis obrnjenega seznama
r=sez;

while(r!=NULL)
{
printf("%d\n",r->vrednost);
r=r->next;
}

return 0;
}

popster je 4. sep 2010 ob 12:49 izjavil:

Si pogledal do katere vrstice gre uredu,

72.psez=&sez;
 73.obrni(psez);

mislim da se nekje tu ustavi, probaj napisat kjeri error je javlo in do katere vrstice pride.. (sorry sem začetnik)

Ni javlo nobenga errorja, samo zamrzlno je... Sem pa probu izpisat obrnjen seznam po korakih... se pravi z:

//izpis: 4
printf("%d\n",r->vrednost);
r=r->next;
//izpis: 3
printf("%d\n",r->vrednost);
r=r->next;
//izpis: 2
printf("%d\n",r->vrednost);
r=r->next;
//izpis: 1
printf("%d\n",r->vrednost);
r=r->next;

Če tole zaženem, mi lepo izpiše obrnjen seznam, če pa za izpis uporabim while zanko, kot je napisana zgoraj v programu, pa zamrzne. Pri temule izpisu po korakih po zadnji vrstici r kaže na NULL, če se ne motim. Zudi če napišem še en korak izpisa, mi enako zamrzne, ampak to se mi zdi logično, saj r->vrednost ne obstaja, če r kaže na NULL. Ni mi pa jasno, zakaj mi zamrzne v primeru izpisa z zanko while, saj bi mogel it ven iz zanke po izpisu enice, ker v naslednjem koraku r že kaže na NULL, kar je izstopni pogoj... Ne vem, kje narobe razmišljam.

Senitel je 4. sep 2010 ob 13:25 izjavil:

Jup, težava je pointer na pointer...

 psez=sez;
 obrni(psez);
 

Kaj je tukaj težava? Saj pri izpisu po korakih je isto pointer na pointer, pa mi normalno izpisuje...

Senitel je 4. sep 2010 ob 15:03 izjavil:

Ah, spregledal kako gre zadeva v funkcijo...
Sicer pa C/C++ ne inicializirata elementarnih tipov! Tako da uni kazalci na začetku funkcije obrni sploh niso nujno NULL, oziroma lahko kažejo kamor koli.

Glede inicializacije maš najbrž res prov, ampak zgleda, da to ne povzroča težav v delovanju te funkcije. Problem je samo pri izpisu obrnjenega seznama z while zanko. Kot da bi zanka laufala v neskončnost...

Sem pa poskusu funkcijo spremenit tko, da vrača pointer na obrnjen seznam. Enaka zgodba. Res mi kazalci niso čisto jasni, ampak tale "zamrznitev" me je pa presenetla...

Kadar zmrzne, ne dobim nič na konzolo. Ampak ko delam tist izpis po korakih, mi pravilno izpiše seznam (torej obrnjeno), tko da iz tega sklepam, da s funkcijo obrni ni nič narobe.

Senitel je 4. sep 2010 ob 15:48 izjavil:

...oziroma saj je čisto logično. Tale del

 if(nov==NULL)
 {
 dod=(struct el *)malloc(sizeof(struct el));
 dod->vrednost=p->vrednost;
 dod->next=NULL;
 nov=dod;
 }
 

se ti nikoli ne izvede, ker "nov" na začetku ni NULL ampak je kar neki. Potem stvar jasno kar leti nekam v tri krasne, ker zadnji element nima next = NULL ampak ima next = kar neki.

Ahaaaa, to bo to. :) Najprej nisem vedu, zakaj naj bi blo pomembno, kam kažejo pointerji na začetku. Itak, kle preverjam, če je NULL in mi je za vsak element seznama skočil v "else", čeprav bi mi mogl prvič v "if"... Ja, se vidi, da mi manjka še precej izkušenj. Najlepša hvala!!!

Neki takega bi blo performancno gledano mnogo boljše (z glave napisano, nisem probal, sam verjetno bi moglo delat):

void obrni(struct el **zac)
{
  struct el *p, *prev, *next;
  p = *zac;
  prev = NULL;
  while (p != NULL) {
    next = p->next;
    p->next = prev;
    prev = p;
    p = next;
  }
  *zac = prev;
}

Ti pa po nepotrebnem dupliciraš vse strukture. Pa tako kot je rekel xordie, bo treba kak free dodat (za vsak malloc moras tekom programa tocno 1x poklicat free, torej vsaka pot skozi program, kjer imas 1 malloc mora imet nekje tudi free).