1、Uvod v raunalnitvo - I2001/2002Andrej Brodnik1-I 2003/04Rekurzivne podatkovne strukture Kakna je rekurzivna funkcija? Takna, ki za izraun uporablja samo sebe. Iz katerih delov sestoji rekurzivna funkcija? Iz ustavitvenega pogoja ter iz dela deli in vladaj. Podobno pri rekurzivnih podatkovnih struktu
2、rah struktura uporablja sebe za hranjenje dela podatkov.2-I 2003/04Seznam kot RPS Seznam je lahko: prazen ali neprazen e je seznam neprazen sestoji iz: glave in podseznama (slednji je lahko prazen) Primer:1 2 3 4 53-I 2003/04Seznam celih tevil Operacije nad seznamom: tvorjenje in unievanje dodajanje
3、 na zaetku ali na koncu odvzemanje na zaetku ali na koncu poizvedovanje po prvem elementu (glavi) in preostanku seznama (rep) poizvedovanje o dolini in elementu v seznamu4-I 2003/04Seznam v Javi Poseben seznam je prazen seznam null Razred nepraznih seznamov celih tevil:public class list private int
4、myHead= 0;private list myTail= null; / list5-I 2003/04Tvorjenjepublic list(int elt, list lst) this(elt, lst); / listpublic list(int elt) this(elt, null); / list tvorjenje in unievanje dodajanje na zaetku ali na koncu odvzemanje na zaetku ali na koncu poizvedovanje po prvem elementu (glavi) in preost
5、anku seznama (rep) poizvedovanje o dolini in elementu v seznamu6-I 2003/04Dodajanje na zaetku ali na koncupublic list prepend(int elt) list newList= new list(elt, this);return newList; / prependpublic list append(int elt) if (myTail = null) myTail= new list(elt);else myTail= myTail.append(elt);retur
6、n this; / append dodajanje na zaetku ali na koncu odvzemanje na zaetku ali na koncu poizvedovanje po prvem elementu (glavi) in preostanku seznama (rep) poizvedovanje o dolini in elementu v seznamu 7-I 2003/04Poizvedovanja: glava, rep, dolina, .public int head(void) return myHead; public list tail(vo
7、id) return myTail; public int length(void) if (myTail = null) return 1;else return (1 + myTail.length(); / length odvzemanje na zaetku ali na koncu poizvedovanje po prvem elementu (glavi) in preostanku seznama (rep) poizvedovanje o dolini in elementu v seznamu8-I 2003/04Poizvedovanja: . vsebinapubli
8、c boolean search(int elt) if (myHead = elt) return true;else if (myTail = null) return false;else return myTail.search(elt); / search odvzemanje na zaetku ali na koncu poizvedovanje o dolini in elementu v seznamu9-I 2003/04Odvzemanje na zaetku ali na koncupublic list delFirst(void) return myTail; / delFirstpublic list delLast (void) if (myTail = null) return null;else myTail= myTail.delLast();return this; / delLast odvzemanje na zaetku ali na koncu10-I 2003/04
