uvod v ra unalni tvo - i

1、Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,1,Uvod v ra?unalni?tvo - I,2001/2002Andrej Brodnik,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,2,Rekurzivne podatkovne strukture,Kak?na je rekurzivna funkcij

2、a?Tak?na, ki za izra?un uporablja samo sebe.Iz katerih delov sestoji rekurzivna funkcija?Iz ustavitvenega pogoja ter iz dela deli in vladaj.Podobno pri rekurzivnih podatkovnih strukturahstruktura uporablja sebe za h

3、ranjenje dela podatkov.,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,3,Seznam kot RPS,Seznam je lahko: prazen ali neprazen?e je seznam neprazen sestoji iz: glave in podseznama (slednji je lahko prazen)Primer:1

4、 2 3 4 5,,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,4,Seznam celih ?tevil,Operacije nad seznamom:tvorjenje in uni?evanjedodajanje na za?etku ali na koncuodvzemanje na za?etku ali na koncupoizvedovanje po p

5、rvem elementu (glavi) in preostanku seznama (rep)poizvedovanje o dol?ini in elementu v seznamu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,5,Seznam v Javi,Poseben seznam je prazen seznam nullRazred nepraznih s

6、eznamov celih ?tevil:public class list { private int myHead= 0; private list myTail= null; …} // list,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,6,Tvorjenje,public list(int elt, list lst) { thi

7、s(elt, lst); } // list public list(int elt) { this(elt, null); } // list,tvorjenje in uni?evanjedodajanje na za?etku ali na koncuodvzemanje na za?etku ali na koncupoizvedovanje po prvem elementu (glavi) in p

8、reostanku seznama (rep)poizvedovanje o dol?ini in elementu v seznamu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,7,Dodajanje na za?etku ali na koncu,public list prepend(int elt) { list newList= new list(elt,

9、this); return newList;} // prependpublic list append(int elt) { if (myTail == null) myTail= new list(elt); else myTail= myTail.append(elt); return this;} // append,dodajanje na za?etku ali na koncuodvzemanje

10、na za?etku ali na koncupoizvedovanje po prvem elementu (glavi) in preostanku seznama (rep)poizvedovanje o dol?ini in elementu v seznamu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,8,Poizvedovanja: glava, rep,

11、dol?ina, ...,public int head(void) { return myHead; }public list tail(void) { return myTail; }public int length(void) { if (myTail == null) return 1; else return (1 + myTail.length());} // length,odvzemanje na z

12、a?etku ali na koncupoizvedovanje po prvem elementu (glavi) in preostanku seznama (rep)poizvedovanje o dol?ini in elementu v seznamu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,9,Poizvedovanja: ... vsebina,publ

13、ic boolean search(int elt) { if (myHead == elt) return true; else if (myTail == null) return false; else return myTail.search(elt);} // search,odvzemanje na za?etku ali na koncupoizvedovanje o dol?ini in el

14、ementu v seznamu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,10,Odvzemanje na za?etku ali na koncu,public list delFirst(void) { return myTail;} // delFirstpublic list delLast (void) { if (myTail == null)

15、 return null; else { myTail= myTail.delLast(); return this; }} // delLast,odvzemanje na za?etku ali na koncu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,11,Neprazni seznami,Razred list vsebuje sezna

16、me, ki niso prazniObstaja posebna konstanta null, ki predstavlja prazen seznamRaz?irimo razred list tako, da bodo seznami v njem poleg lastnosti nepraznih seznamov ?e:bili lahko prazniimeli ime, ki ga dobijo ob tvorj

17、enju ali ga spremenili kasnejebomo poizvedovali ali so seznami prazni in po imenu,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,12,Razred eltList,public class eltList {/* ----------------------------------------

18、-----[ data ]--- */ private list myList= null; private String myName; /* ostalo za (malo) domaco nalogo *//* --------------------------------[ create / destruct ]--- */ public eltList(String name) { this(null, n

19、ame); }; public eltList(String name, int elt) { myFirst= new list(elt); myName= name; } // eltList,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,13,Razred eltList,/* -----------------------------------

20、--------[ update ]--- */public void prepend(int element) { if (myFirst == null) myFirst= new list(elt); else myFirst= myFirst.prepend(elt);} // prepend/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - *

21、/public void delLast(void) { if (myFirst == null) return; myFirst= myFirst.delLast();} // delLast… /* ostalo za (malo) domaco nalogo */ …,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,14,Dvojno rekurzivni s

22、eznam,Rekurzivno dvojni seznam je, kot obi?ajni seznam lahko: prazen ali neprazen?e je seznam neprazen sestoji iz: glave in dveh podseznamov (vsak od slednjih je lahko prazen),Predavanje: 8,UR-I 2003/04© Andrej Br

23、odnik, UP,15,Dvojno rekurzivni seznam,2,7,6,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,16,Dvojno rekurzivni seznam,Dvojno rekurzivni seznam imenujemo dvojno (binarno) drevoGlavo pri drevesu imenujemo koren in

24、podseznama levo poddrevo ter desno poddrevoObstajajo seveda tudi k-terno rekurzivni seznami, ki jih podobno imenujemo k-i?ka drevesata drevesa imajo (do) k poddrevesin (do) k-1 elemetov v korenu,Predavanje: 8,UR-I 200

25、3/04© Andrej Brodnik, UP,17,Primer dvojnega drevesa,Posebno drevo je prazno drevo nullRazred nepraznih dreves celih ?tevil:public class tree { private int root= 0; private tree left= null; private tree

26、right= null; …} // tree,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,18,Tvorjenje,public tree(int elt, tree newLeft, tree newRight) { this(elt, newLeft, newRight); } // tree public tree(

27、int elt) { this(elt, null, null); } // tree,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,19,Dodajanje,Dodajanje na za?etku (vrhu / korenu) public tree prepend(int elt) { tree newTree= new tree(elt, th

28、is, null); return newTree; } // prependali na koncu (pri listih)public tree append(int elt) { if (right == null) right= new tree(elt); else right= right.append(elt); return this;} // append,P

29、redavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,20,Poizvedovanja,Poizvedovanja: koren, poddrevo public int value(void) { return root; } public list leftSubtree(void) { return left; } public list righ

30、tSubtree(void) { return right; }Poizvedovanja: vi?ina public int height(void) { int leftHeight; int rightHeight; if (left == null) leftHeight= 0; else leftHeight= left.height(); if (

31、right == null) rightHeight= 0; else rightHeight= right.height(); return (1 + max(leftHeight, rightHeight)); } // height,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,21,Poizvedovanja,Poizve

32、dovanja: vsebinapublic boolean search(int elt) { boolean found; if (root == elt) return true; if (left == null) found= false; else found= left.search(elt); if ( !found ) if (right !=

33、 null) found= right.search(elt); return found;} // search,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,22,Obhodi in izpisi,Prvi (preorder)public void preorder(void) { system.io.println(me); // PRE - pred

34、 if (left != null) left.preorder(); if (myRight != null) right.preorder();} // preorderVmesni (inorder)public void inorder(void) { if (left != null) left.inorder(); system.io.println(me); // IN -

35、 vmes if (right != null) right.inorder();} // inorderZadnji (postorder) - (mala) doma?a naloga,Predavanje: 8,UR-I 2003/04© Andrej Brodnik, UP,23,Zaklju?ek,Ogledali smo si:Rekurzivne podatkovne strukture: