| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: 
|
 Postano: 22:05 pon, 22. 5. 2017 Naslov: Vezane liste |
    |
|
|
Pozdrav :D
Pokušavam napisati funkciju koja bi dodavala čvorove liste na kraj liste, ali mi nešto u njoj ne štima (zapinje kod učitavanja u mainu). Pojedini čvor liste sastoji se od samo jednog broja i taj broj funkcija prima te stvara novi čvor i isti implementira u listu. Vidi netko grešku?
[code:1]typedef struct _broj
{
int x;
struct _broj *next;
} broj;
broj* dodaj(broj *head, int n)
{
broj *temp, *headtemp; headtemp=(broj*)malloc(sizeof(broj)); temp=(broj*)malloc(sizeof(broj));
headtemp=head; temp->x=n;
while (head->next!=NULL) head=head->next;
temp->next=NULL;
head->next=temp;
return headtemp;
}
int main(void)
{
broj *head, *t, *headtemp; headtemp=(broj*)malloc(sizeof(broj)); int i, b;
t=(broj*)malloc(sizeof(broj));
head=(broj*)malloc(sizeof(broj)); head=NULL;
printf ("Tri broja liste: ");
for (i=0; i<3; i++) {printf ("%d. broj: ", i); scanf("%d", &b); head=dodaj(head, b);}
headtemp=head;
while (head->next!=NULL) {printf ("%d ", head->x); head=head->next;}
head=headtemp;
while (head!=NULL) {t=head; head=head->next; free(t);} free(head); free(t);
return 0;
}[/code:1]
Pozdrav 
Pokušavam napisati funkciju koja bi dodavala čvorove liste na kraj liste, ali mi nešto u njoj ne štima (zapinje kod učitavanja u mainu). Pojedini čvor liste sastoji se od samo jednog broja i taj broj funkcija prima te stvara novi čvor i isti implementira u listu. Vidi netko grešku?
| Kod: | typedef struct _broj
{
int x;
struct _broj *next;
} broj;
broj* dodaj(broj *head, int n)
{
broj *temp, *headtemp; headtemp=(broj*)malloc(sizeof(broj)); temp=(broj*)malloc(sizeof(broj));
headtemp=head; temp->x=n;
while (head->next!=NULL) head=head->next;
temp->next=NULL;
head->next=temp;
return headtemp;
}
int main(void)
{
broj *head, *t, *headtemp; headtemp=(broj*)malloc(sizeof(broj)); int i, b;
t=(broj*)malloc(sizeof(broj));
head=(broj*)malloc(sizeof(broj)); head=NULL;
printf ("Tri broja liste: ");
for (i=0; i<3; i++) {printf ("%d. broj: ", i); scanf("%d", &b); head=dodaj(head, b);}
headtemp=head;
while (head->next!=NULL) {printf ("%d ", head->x); head=head->next;}
head=headtemp;
while (head!=NULL) {t=head; head=head->next; free(t);} free(head); free(t);
return 0;
} |
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 9:47 uto, 23. 5. 2017 Naslov: |
|
|
|
Prvo, ovo nema smisla:
[code:1]headtemp=(broj*)malloc(sizeof(broj));
headtemp=head;[/code:1]
Prvi redak alocira memoriju, a drugi preusmjeri pointer s nje na nesto drugo (na onaj dio memorije na koji pokazuje [tt]head[/tt]). Originalna memorija (alocirana u prvoj lajni) ostaje zauzeta, ali nedostupna.
Ista stvar u [tt]main[/tt]-u. Pointer koji usmjeravamo na neku vec alociranu memoriju ne alociravamo. Na kraju, broj [tt]malloc[/tt]-ova bi trebao biti jednak duljini liste (ili, na SPA, bude za 1 veci).
Sto se tice greske, stvar je u tome (mozda ne samo u tome) da nakon
[code:1]head=NULL;[/code:1]
pointer [tt]head[/tt] pokazuje na [tt]NULL[/tt] (ono sto mu je prije alocirano je izgubljeno, kako sam gore objasnio). Zatim udjes u [tt]dodaj()[/tt] i posaljes mu [tt]head[/tt] koji je (ispravno) jednak [tt]NULL[/tt]. I onda, u iducoj liniji (koju nisam gore citirao) imas
[code:1]while (head->next!=NULL) ...[/code:1]
sto je dereferenciranje [tt]NULL[/tt]-pointera [tt]head[/tt], sto bi trebalo srusiti program.
Kod dodavanja na kraj liste treba razlikovati dva slucaja:[list=1][*] Lista je prazna; i[*] Lista nije prazna.[/list:o]Pogledaj u skripti; tamo je to raspisano.
Prvo, ovo nema smisla:
| Kod: | headtemp=(broj*)malloc(sizeof(broj));
headtemp=head; |
Prvi redak alocira memoriju, a drugi preusmjeri pointer s nje na nesto drugo (na onaj dio memorije na koji pokazuje head). Originalna memorija (alocirana u prvoj lajni) ostaje zauzeta, ali nedostupna.
Ista stvar u main-u. Pointer koji usmjeravamo na neku vec alociranu memoriju ne alociravamo. Na kraju, broj malloc-ova bi trebao biti jednak duljini liste (ili, na SPA, bude za 1 veci).
Sto se tice greske, stvar je u tome (mozda ne samo u tome) da nakon
pointer head pokazuje na NULL (ono sto mu je prije alocirano je izgubljeno, kako sam gore objasnio). Zatim udjes u dodaj() i posaljes mu head koji je (ispravno) jednak NULL. I onda, u iducoj liniji (koju nisam gore citirao) imas
| Kod: | | while (head->next!=NULL) ... |
sto je dereferenciranje NULL-pointera head, sto bi trebalo srusiti program.
Kod dodavanja na kraj liste treba razlikovati dva slucaja:- Lista je prazna; i
- Lista nije prazna.
Pogledaj u skripti; tamo je to raspisano.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
| Postano: 12:16 pet, 9. 6. 2017 Naslov: Postaje... |
|
|
|
Imam dvije funkcije/dva problema: Zadatak me traži da napravim funkciju koja prima pointer na prvi element vezane liste (čiji su elementi željezničke [i]postaje[/i]) i invertira poredak elemenata, ali ne vraća ništa. Napisah dvije verzije iste funkcije koje bi trebale raditi isto, ali prva (koja vraća pointer na prvi element iste invertirane liste) radi, a druga (void) ne (premda su gotovo iste, do na tip koji funkcija vraća).
[code:1]postaja* povratak(postaja* head) // F1 dobro radi
{
postaja *temp, *slj; int da=1;
while (temp!=NULL)
{
if (da) {temp=head->next; head->next=NULL; da=0;}
slj=temp->next;
temp->next=head;
head=temp;
temp=slj;
}
return head;
}[/code:1]
[code:1]void povratak(postaja* head) //F2 krivo radi
{
postaja *temp, *slj; int da=1;
while (temp!=NULL)
{
if (da) {temp=head->next; head->next=NULL; da=0;}
slj=temp->next;
temp->next=head;
head=temp;
temp=slj;
}
return;
}[/code:1]
Algoritam je očito u redu ako radi u F1, ali mi nije jasno zašto, kada u [tt]main[/tt]-u pozovem ispis pomoću [code:1]void ispisi(postaja* ulaz)
{
postaja *head=ulaz;
while (head!=NULL) {printf("%s %d\n", head->naziv, head->v); head=head->next;}
return;
}[/code:1] funkcija F2 ispiše originalan poredak elemenata, a ne obrnut (jer je [tt]head[/tt] očito u funkciji pomaknut na predzadnji, tj. posljednji ne-[tt]NULL[/tt] element liste).
Stručnjaci? :D
Imam dvije funkcije/dva problema: Zadatak me traži da napravim funkciju koja prima pointer na prvi element vezane liste (čiji su elementi željezničke postaje) i invertira poredak elemenata, ali ne vraća ništa. Napisah dvije verzije iste funkcije koje bi trebale raditi isto, ali prva (koja vraća pointer na prvi element iste invertirane liste) radi, a druga (void) ne (premda su gotovo iste, do na tip koji funkcija vraća).
| Kod: | postaja* povratak(postaja* head) // F1 dobro radi
{
postaja *temp, *slj; int da=1;
while (temp!=NULL)
{
if (da) {temp=head->next; head->next=NULL; da=0;}
slj=temp->next;
temp->next=head;
head=temp;
temp=slj;
}
return head;
} |
| Kod: | void povratak(postaja* head) //F2 krivo radi
{
postaja *temp, *slj; int da=1;
while (temp!=NULL)
{
if (da) {temp=head->next; head->next=NULL; da=0;}
slj=temp->next;
temp->next=head;
head=temp;
temp=slj;
}
return;
} |
Algoritam je očito u redu ako radi u F1, ali mi nije jasno zašto, kada u main-u pozovem ispis pomoću | Kod: | void ispisi(postaja* ulaz)
{
postaja *head=ulaz;
while (head!=NULL) {printf("%s %d\n", head->naziv, head->v); head=head->next;}
return;
} |
funkcija F2 ispiše originalan poredak elemenata, a ne obrnut (jer je head očito u funkciji pomaknut na predzadnji, tj. posljednji ne-NULL element liste).
Stručnjaci?
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 15:39 pet, 9. 6. 2017 Naslov: |
|
|
|
Zapitaj se: ako mozemo samo maknuti [tt]return head;[/tt], zasto ga onda stavljamo u [tt]F1[/tt]? ;)
Kad listu invertiras "igranjem" s pointerima, treba vratiti novi pocetak liste, jer se ocito promijenilo koji od elemenata igra tu ulogu. Dakle, kao u F1.
No, ako ne smijes nista vratiti, onda se ocito ne mozemo "igrati" s pointerima (logika: negiraj prethodni paragraf), nego treba mijenjati sadrzaj samih elemenata liste. Za jednostruko vezanu listu, ovo je vrlo nezgodno. Pseudokod:
[code:1]int broj_elemenata_liste(lista) {
...
return /* broj elemenata liste */
}
postaja *de_mi_kti_element_liste(lista, k) {
...
return /* k-ti element liste */;
}
void f2(lista) {
cnt = broj_elemenata_liste(lista);
for (i = 0; i < cnt/2; i++) {
t1 = de_mi_kti_element_liste(lista, i);
t2 = de_mi_kti_element_liste(lista, cnt-i-1);
tmp1 = t1.podatak1; t1.podatak1 = t2.podatak1; t2.podatak1 = tmp1;
tmp2 = t1.podatak2; t1.podatak2 = t2.podatak2; t2.podatak2 = tmp2;
...
}
}[/code:1]
Dakle, tretiras listu kao niz, emulirajuci citanje [tt]k[/tt]-tog elementa preko pomocne funkcije koja "trci" po cijeloj listi. Ruzno i neefikasno (kvadratna slozenost za obicnu, linearnu operaciju), ali to je i poanta zadatka (da se vidi koliko je ruzno i neefikasno).
Zapitaj se: ako mozemo samo maknuti return head;, zasto ga onda stavljamo u F1? 
Kad listu invertiras "igranjem" s pointerima, treba vratiti novi pocetak liste, jer se ocito promijenilo koji od elemenata igra tu ulogu. Dakle, kao u F1.
No, ako ne smijes nista vratiti, onda se ocito ne mozemo "igrati" s pointerima (logika: negiraj prethodni paragraf), nego treba mijenjati sadrzaj samih elemenata liste. Za jednostruko vezanu listu, ovo je vrlo nezgodno. Pseudokod:
| Kod: | int broj_elemenata_liste(lista) {
...
return /* broj elemenata liste */
}
postaja *de_mi_kti_element_liste(lista, k) {
...
return /* k-ti element liste */;
}
void f2(lista) {
cnt = broj_elemenata_liste(lista);
for (i = 0; i < cnt/2; i++) {
t1 = de_mi_kti_element_liste(lista, i);
t2 = de_mi_kti_element_liste(lista, cnt-i-1);
tmp1 = t1.podatak1; t1.podatak1 = t2.podatak1; t2.podatak1 = tmp1;
tmp2 = t1.podatak2; t1.podatak2 = t2.podatak2; t2.podatak2 = tmp2;
...
}
} |
Dakle, tretiras listu kao niz, emulirajuci citanje k-tog elementa preko pomocne funkcije koja "trci" po cijeloj listi. Ruzno i neefikasno (kvadratna slozenost za obicnu, linearnu operaciju), ali to je i poanta zadatka (da se vidi koliko je ruzno i neefikasno).
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
| Postano: 19:14 pet, 9. 6. 2017 Naslov: |
|
|
|
[quote]Kad listu invertiras "igranjem" s pointerima, treba vratiti novi pocetak liste, jer se ocito promijenilo koji od elemenata igra tu ulogu.[/quote]
Pa upravo to mislim da se treba i dogoditi. F2 i pomiče [tt]head[/tt] sve do predzadnjeg elementa koji treba biti prvi element nove liste; pritom svaku "vezu" među elementima obrne.
Nije mi najbistriji tzv. prijenos argumenta u funkciji. Znam da ako imam funkciju prototipa [tt]int fja1 (int broj)[/tt] da će se pri njenom izvršavanju u računalu napraviti "kopija" [tt]broj[/tt]-a i da on neće ostati nepromijenjen. S druge strane, ako funkcija prototipa [tt]int fja2 (int *broj)[/tt] prima pointer, tj. adresu [tt]broj[/tt]-a, onda se i taj broj mijenja kroz funkciju.
Ne bi li bilo logično onda da kad pozovem F2 da se i [tt]head[/tt] promijeni u skladu s time kako s njime baratam? F2 je složena tako da kad se njezino izvršavanje završi da [tt]head[/tt] bude početak invertirane liste. Nije mi jasno zašto [tt]head[/tt] ostane nepromijenjen.
| Citat: | | Kad listu invertiras "igranjem" s pointerima, treba vratiti novi pocetak liste, jer se ocito promijenilo koji od elemenata igra tu ulogu. |
Pa upravo to mislim da se treba i dogoditi. F2 i pomiče head sve do predzadnjeg elementa koji treba biti prvi element nove liste; pritom svaku "vezu" među elementima obrne.
Nije mi najbistriji tzv. prijenos argumenta u funkciji. Znam da ako imam funkciju prototipa int fja1 (int broj) da će se pri njenom izvršavanju u računalu napraviti "kopija" broj-a i da on neće ostati nepromijenjen. S druge strane, ako funkcija prototipa int fja2 (int *broj) prima pointer, tj. adresu broj-a, onda se i taj broj mijenja kroz funkciju.
Ne bi li bilo logično onda da kad pozovem F2 da se i head promijeni u skladu s time kako s njime baratam? F2 je složena tako da kad se njezino izvršavanje završi da head bude početak invertirane liste. Nije mi jasno zašto head ostane nepromijenjen.
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 0:01 sub, 10. 6. 2017 Naslov: |
|
|
|
Yup, my bad; zaboravih na to. Moze i tako. ALI,[list][*]ako imas [tt]f(postaja head)[/tt], nemas sto mijenjati, jer ti funkcija dobije kopiju strukture tipa [tt]postaja[/tt];[*]ako imas [tt]f(postaja *head)[/tt], onda [tt]head[/tt] sadrzi adresu na kojoj se nalazi struktura tipa [tt]postaja[/tt] (ona ista iz liste, ne njena kopija), sto znaci da mozes mijenjati njen sadrzaj, ali ne i taj pointer na nju;[*]ako imas [tt]f(postaja **head)[/tt], onda imas adresu memorije na kojoj se nalazi [tt]*head[/tt], tj. adresu memorije na kojoj se nalazi pointer na strukturu tipa [tt]postaja[/tt]. To znaci da mozes mijenjati i tu adresu ([tt]*head[/tt]) i ono na sto ona pokazuje ([tt]**head[/tt]).[/list:u]Dakle,
[code:1]void f(postaja **head) {
/* tu radis sa *head kako bi inace s head, ili uvedi pomocnu varijablu ako te to zbunjuje */
postaja *tmp_head;
tmp_head = *head;
...
*head = tmp_head;
}[/code:1]
Pogledaj poglavlje 10.2 u skripti iz Prog 1. Nema veze je li nesto [tt]int[/tt] ili [tt]postaja[/tt]. Princip je isti.
Yup, my bad; zaboravih na to. Moze i tako. ALI,- ako imas f(postaja head), nemas sto mijenjati, jer ti funkcija dobije kopiju strukture tipa postaja;
- ako imas f(postaja *head), onda head sadrzi adresu na kojoj se nalazi struktura tipa postaja (ona ista iz liste, ne njena kopija), sto znaci da mozes mijenjati njen sadrzaj, ali ne i taj pointer na nju;
- ako imas f(postaja **head), onda imas adresu memorije na kojoj se nalazi *head, tj. adresu memorije na kojoj se nalazi pointer na strukturu tipa postaja. To znaci da mozes mijenjati i tu adresu (*head) i ono na sto ona pokazuje (**head).
Dakle,
| Kod: | void f(postaja **head) {
/* tu radis sa *head kako bi inace s head, ili uvedi pomocnu varijablu ako te to zbunjuje */
postaja *tmp_head;
tmp_head = *head;
...
*head = tmp_head;
} |
Pogledaj poglavlje 10.2 u skripti iz Prog 1. Nema veze je li nesto int ili postaja. Princip je isti.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
|
