Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Vezane liste (zadatak)
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 22:05 pon, 22. 5. 2017    Naslov: Vezane liste Citirajte i odgovorite

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 Very Happy
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]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 9:47 uto, 23. 5. 2017    Naslov: Citirajte i odgovorite

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
Kod:
head=NULL;

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:
  1. Lista je prazna; i
  2. 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.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 15:18 uto, 23. 5. 2017    Naslov: Citirajte i odgovorite

:thankyou:
Thank you


[Vrh]
Korisnički profil Pošaljite privatnu poruku
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 12:16 pet, 9. 6. 2017    Naslov: Postaje... Citirajte i odgovorite

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? Very Happy


[Vrh]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:39 pet, 9. 6. 2017    Naslov: Citirajte i odgovorite

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? Wink

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.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 19:14 pet, 9. 6. 2017    Naslov: Citirajte i odgovorite

[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]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 0:01 sub, 10. 6. 2017    Naslov: Citirajte i odgovorite

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.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan