Vezane liste
Select messages from
# through # FAQ
[/[Print]\]

Forum@DeGiorgi -> Programiranje 1 i 2

#1: Vezane liste Autor/ica: krilo PostPostano: 22:05 pon, 22. 5. 2017
    —
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;
}

#2:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 9:47 uto, 23. 5. 2017
    —
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.

#3:  Autor/ica: krilo PostPostano: 15:18 uto, 23. 5. 2017
    —
Thank you

#4: Postaje... Autor/ica: krilo PostPostano: 12:16 pet, 9. 6. 2017
    —
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

#5:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 15:39 pet, 9. 6. 2017
    —
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).

#6:  Autor/ica: krilo PostPostano: 19:14 pet, 9. 6. 2017
    —
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.

#7:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 0:01 sub, 10. 6. 2017
    —
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.



Forum@DeGiorgi -> Programiranje 1 i 2


output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.

Powered by phpBB © 2001,2002 phpBB Group
Theme created by Vjacheslav Trushkin