Predavanje 9 - Vezane liste

1. Definicija

Vezana lista je skup cvorova (eng. node) koji se sastoje od podataka istog tipa i veze ( eng. link) na iduci cvor.

Vezana lista nije osnovni tip podatka u C-u i postoje vise razlicitih implementacija vezane liste. Dvije najcesce koriste polja i pokazivace. Mi cemo koristiti implementaciju sa pokazivacima.

Cvor se sastoji od podataka jednostavnih ili slozenih i adrese (veze) na iduci cvor liste, prazni cvor (eng. dummy node) ili NULL.

Sama vezana lista moze se prikazati ovako:

Vezane liste kao i polja organiziraju podatke sekvencijalno. Polazeci od nekog od cvorova mi slijedimo vezu dok ne dodjemo na kraj liste koji je jedan od iduca tri tipa:

2. Kreiranje vezanih listi i jednostavan primjer upotrebe

Pretpostavimo da zelimo konstrurati vezanu listu cijelih brojeva. Tada u C-u postupamo ovako.

1. Deklaracija

typedef struct cvor_liste_integera* veza; struct cvor_liste_integera{ int a; /* podatak cvora*/ veza iduci; /*pokazivac na iduci cvor liste*/ };

2. Alokacija i inicijalizacija

veza x, pocetak_liste; int i; /* alociramo listu od 10 cijelih brojeva koja zavrsava za NULL, kreirajuci najprije pocetak koji spremimo za kasniju upotrebu */ x=(veza) malloc(sizeof *x); x->a=0; x->iduci=NULL; pocetak_liste=x; for(i=1; i<10; i++){ x= (x->iduci=(veza) malloc(sizeof *x)); x->a=i; x->iduci=NULL; } /* primjer upotrebe vezane liste kako smo oznacili kraj liste sa NULL imamo vrlo jednostavan nacin kretanja kroz listu */ for (x=pocetak_liste; x!=NULL; x=x->iduci) printf("%d\n", x->a);

2. Vezane liste i polja

Kao sto smo rekli i polja dopustaju sekvencijalnu organizaciju podataka, ali ona je implicitna (dana je pozicijom u polju).

Prednosti polja nad vezanim listama:

Prednosti vezanih listi nad poljima

3. Primjer kruzne liste -Josephusov problem

Pretpostavimo da imamo N ljudi koji su numeriran brojevima od 1 do N i raporedjeni u krug tako da brojevi rasporedjeni uzastopno i rastu u smjeru suprotnom od kazaljke na satu. Nadalje ova skupina ljudi dogovorila se da ce izabrati svog lidera na ovaj nacin. Zadali prirodan broj M i redom ce se iz kruga izbacivati svaki M-ti covjek do na kraju ne ostane samo jedan koji ce biti lider. (Pogledajte Knuthov The Art of Computer Programming Volume I str. 162 zadatak 22 za malo drugaciju formulaciju Joesphusovog problema.) Slijedeca slika ilustrira N=9 i M=5.

#include <stdlib.h> #include <stdio.h> typedef struct osoba* veza; struct osoba { int a; veza iduci; }; main(int argc, char *argv[]){ int i; /*OOPS ne pazimo imamo li dovoljno argumenata na komadnoj liniji i jesu li 1 i 2 argument prirodni brojevi kod pisanja programa treba provjeravati, je li trazeni input zaista onakav kakav trazimo i ako nije onda treba poduzeti neku smislenu akciju npr. obavijestiti korisnika i predloziti mu da ponovi input i sl. buduci da mi ilustriramo algoritme sa vezanim listama, mi cemo ignorirati ovakve probleme i pretpostavljati da je korsinik "dobronamjeran" */ int N=atoi(argv[1]); int M=atoi(argv[2]); veza x; veza pocetak = malloc(sizeof *pocetak); pocetak->a = 1; /*gradimo kruznu listu i zato je kraj liste zapravo pocetak*/ pocetak->iduci = pocetak; /* kreiramo i ostatak liste*/ x = pocetak; for (i = 2; i <= N; i++){ x = (x->iduci = malloc(sizeof *x)); x->a = i; x->iduci = pocetak; } /*trazimo lidera*/ while (x != x->iduci){ /* preskacemo M ljudi pocevsi od x */ for (i = 1; i < M; i++) x = x->iduci; /*izbacimo M-tog u ovom obilasku sa liste */ x->iduci = x->iduci->iduci; } /*ispisemo liderov broj */ printf("%d\n", x->a); }

Napomena: slozenost ovog algoritma jest ocigledno O(MN).

4. Inverzna lista

Pretpostavimo da imamo listu danu sa pokazivacem pocetni i krajem specificiranim sa NULL. Zelimo kreirati inverznu listu. Iduca funkcija vraca pokazivac inverzna na prvi element inverzne liste.

veza inverzna_lista(veza pocetni){ veza y, t, inverzna; inverzna=NULL; /*ovo ce biti kraj nove liste*/ y=pocetni; while(y!=NULL){ t=y->iduci; y->iduci=inverzna; inverzna=y; y=t; } return inverzna; }

5. Dvostruko povezane liste

Cvorovi dvostruko povezane liste sadrze vezu ne samo na idcui element nego i na prethodni element liste. Rad sa takvim listama analogan je gore opisanom radu sa jednostrukim listama. Vidite zadatak 5 dolje.

6. Zadaci za vjezbu (tezi zadaci oznaceni zvijezdicom)

1. Napisite funkciju koji vraca broj elemenata kruzne liste. Napisite i test program.

2. Napisite funkciju koja preseli najveci element cjelobrojne liste na kraj liste. Napisite i test program.

3. Napisite funkciju koja sortira elemente cjelobrojne liste u rastucem poretku. Napisite i test program.

4.* Napisite funkciju koja kao argument uzima pokazivace x i y na dva cvora kruzne liste te umece element koji slijedi cvor x na mjesto cvora koji slijedi cvor koji slijedi y.

5. Napisite program koji realizra kreiranje dvostruke liste, te umetanje i brisanje elementa sa ovakve liste.

6. Napisite program koji oslobadja memoriju citave vezane liste.

7. Napisite program koji realizira zbrajanje i mnozenje proizvoljno velikih pozitivnih cijelih brojeva zapisanih u dekadskom sustavu. Brojeve realizirajte kao vezane liste.

8. Napisite program koji realizira zbrajanje i mnozenje proizvoljno velikih polinoma cijelih brojeva. Polinome realizirajte kao vezane liste.

9.* Implementirajte dijeljenje i kompoziciju polinoma sa cjelobrojnim koeficijentima.