Programozás I. C nyelv 12. előadás Bináris fa, bináris kereső fa, kupac, időkezelő függvények Veszprémi Egyetem Heckl István,
[email protected]
1
Fogalmak • Fa: összefüggő, körmentes gráf, azaz bármely két csúcsa között pontosan egy út van • Bináris fa: olyan fa, amelynek csúcspontjaiból maximum 2 részfa nyílik • A fát tekintjük irányítottnak, ekkor az élek a szülőktől a gyerekek felé mutatnak
2
Fogalmak • Szülő: egy csomópont megelőző csomópontja – a gyökeret kivéve valamennyi csomópontnak van szülője • Ős: egy csomópont szülője és a gyökér által meghatározott út valamely csomópontja • Gyerek: az adott csomópontot közvetlenül követő elem – bináris fáknál megkülönböztethetünk bal, illetve jobb oldali gyerekeket – a gyerekek egymásnak testvérei • Leszármazott: azon csomópontok halmaza, amelyek irányított úton elérhetőek az adott csomópontból 3
Fogalmak • • • •
Mélység / magasság: a fa leghosszabb útjának hossza Gyökér: az a csomópont, amelynek nincs őse Levél: olyan csomópont, amelynek nincs gyereke Szintszám: a fa gyökeréhez a 0 szintszám tartozik, a további csomópontokhoz pedig mindig 1 -gyel nagyobb szintszám, mint a szülő szintszáma
4
Példa • • • • •
Szülő: 7 Ős: {2,7} Bal gyerek: 1 Jobb gyerek: 5 Leszármazottak: {1, 5}
• • • •
Levelek: {1, 5, 8, 3} 2. szint: {4, 9} Gyökér: 2 Mélység: 4 5
Bináris fák bejárása • Fajtái: – preorder – inorder – postorder • A bejárások rekurzívak és az aktuális elem feldolgozásának helyét jelölik
6
Bináris fák bejárása • Preorder bejárás: - a gyökér feldolgozása - a bal részfa preorder bejárása - a jobb részfa preorder bejárása - eredmény: 1, 2, 4, 5, 3, 6, 7 Step 1 Step 3 Step 2 1
2
4
3
5
6
7
7
Bináris fák bejárása • Inorder bejárás: – a bal részfa inorder bejárása – a gyökér feldolgozása – a jobb részfa inorder bejárása – eredmény: 4, 2, 5, 1, 6, 3, 7 – bináris keresőfákból növekvő sorrendben olvassa ki Step 2 az értékeket Step 3
Step 1 1
2
4
3
5
8
6
7
Bináris fák bejárása • Postorder bejárás: – a bal részfa postorder bejárása – a jobb részfa postorder bejárása – a gyökér feldolgozása – eredmény: 4, 5, 2, 6, 7, 3, 1 – matematikai kifejezések kiértékelésekor használják Step 3 Step 2 Step 1 1
2
4
3
5
9
6
7
Bináris keresőfa • Bináris keresőfa (bst - binary search tree): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal oldali leszármazottak kulcs értékei nem nagyobbak, mint az aktuális elem kulcs értéke, a jobb oldali leszármazottak kulcsértékei pedig nagyobbak • Bináris keresőfa felépítése: – új elem bekérése – indulás a gyökértől – ha az új elem kulcsa nem nagyobb, mint az aktuális elem kulcsa, akkor balra egyébként jobbra megyünk – ha adott irányba nincs elem, akkor oda beszúrjuk az új elemet 10
• Elemek: 12, 23, 8, 25, 10, 18
11
Bináris keresőfa • A bináris keresőfa előnye a listával szemben, hogy egy elem gyorsabban megtalálható – a fa mélysége általában kisebb, mint a lista hossza • Adott kulcsú elem keresése: – indulás a gyökértől – ha a keresett elem és az aktuális elem kulcsa: • megegyezik, akkor végeztünk • ha az előbbi kisebb, akkor jobbra megyünk • ha az előbbi nagyobb, akkor balra megyünk • A fa felépítése függ az elemek sorrendjétől • Ha az elemek beszúrása sorrendben történik, akkor a fa 12 lánccá degenerálódik (legrosszabb eset)
Bináris keresőfa adatszerkezet megvalósítása • Implementálás: – döntsd el, hogy van-e szülő mutató – válaszd ki a tárolni kívánt adatokat • külön struktúrában tároljuk vagy nem? – határozd meg a kulcs elemet – döntsd el, hogy reprezentálod a fát: mutató, sentinel, osztály – válaszd ki a megvalósítandó függvényeket • függvény implementálásakor rajzold le az összes lehetséges esetet • beszélő neveket használj 13
#include <stdio.h> #include <stdlib.h> struct node { int key; struct node *less, *bigger; int data1; }; void printNode(struct node* cs) { printf("[key:%d, data1: %d]", cs->key, cs->data1); } void createNode(struct node* act) { // filling up the node with data printf("Creating a new node\n"); printf("key:"); scanf("%d", &act->key); printf("data1:"); scanf("%d", &act->data1); } 14
Magyarázat • struct node: fa csomópont típusának a meghatározása – nincs külön struktúra az adatoknak • printNode: egy csomópont kiírása • createNode: csomópont adatainak a bekérése – paraméter átadás cím szerint, hogy ne kelljen pluszban rekordot másolni
15
void printTree(struct node* cs) { if (!cs) return; if(cs->less) printTree(cs->less); printNode(cs); if(cs->bigger) printTree(cs->bigger); } void freeTree(struct node* cs) { if (!cs) return; if(cs->less) freeTree(cs->less); if(cs->bigger) freeTree(cs->bigger); free(cs); }
16
Magyarázat • A fa listázása inorder sorrendben történik, mert így kapjuk meg az elemeket növekvő sorrendben – először kilistázzuk rekurzívan az adott csomópontnál kisebb elemeket – az adott csomópontot – majd az adott csomópontnál nagyobb elemeket • A fa törlése postorder sorrendben történik, egy elemet akkor törölhetünk, ha mindkét részfáját már töröltük – egy elem törlése után már nem hivatkozhatunk a less és bigger adattagjaira 17
struct node* searchNode(struct node* root, int key) { if (!root) return NULL; struct node* act = root; while (act) { if (act->key==key) return act; if (key<=act->key) act = act->less; else act = act->bigger; } return NULL; } struct node* smallestNode(struct node* act) { // return the smallest element in subtree rooting at act if (!act) return NULL; if (!act->less) return act; return smallestNode(act->less); 18 }
Magyarázat • searchNode adott kulcsú elemet keres meg • smallestNode a részfa legkisebb elemét keresi meg – rekurzív – a jobb szélső gyerek a legkisebb, a balszélső a legnagyobb • Mindét függvény a keresőfa tulajdonságot használja ki
19
smallest of 31
search: 25 1
12
root
12
2 (25>12) er gg bi
bi gg er
23
23
1
le
gg er
20
31
er gg bi
le ss
3 (25>23) bi
ss
start
20
31 2
le
ss
le ss
4 (25<31)
25
le ss
ss le
24
25
3
24 20
struct node** linkAddressToInsert(struct node* act, int key) { // return the address of the less or bigger pointer of the node to where key // have to be inserted if (key<=act->key) { if (act->less) return linkAddressToInsert(act->less, key); else return &act->less; } else { if (act->bigger) return linkAddressToInsert(act->bigger, key); else return &act->bigger; } } 21
void insertNode(struct node** root, struct node* cs) { struct node* act = *root, *newNode, **linkAdress; newNode = (struct node*)malloc(sizeof(struct node)); *newNode=*cs; newNode->less=NULL; newNode->bigger=NULL; if (*root==NULL) { *root=newNode; return; } linkAdress=linkAddressToInsert(*root, cs->key); *linkAdress=newNode; }
22
Magyarázat • linkAddressToInsert: – a beszúrás szabályai szerint megkeresi azt a csomópontot, amely az adott kulcsú elem szülője lesz – visszaadja a less illetve bigger mutatók közül a megfelelőnek a címét – ha csak a szülőnek adjuk vissza a címét, akkor utána még vizsgálni kell, hogy melyik mutatója megfelelő • insertNode két esetet vizsgál: – még nem létezik a fa: a gyökeret módosítani kell – már létezik a fa: meg kell keresni az új elem szülőjét – létezik nem rekurzív változat is 23
insert 18 **root
12 bi gg
NULL
er
23 bi
le
gg
ss
*linkAddress
er
20 NULL
31 le
ss
NULL
NULL
25 le
ss
18
NULL
24 NULL
NULL
24
void insertNode(struct node** root, struct node* cs) { // non-recursive struct node* act = *root, *newNode; newNode = (struct node*)malloc(sizeof(struct node)); *newNode=*cs; newNode->less=NULL; newNode->bigger=NULL; if (*root==NULL) { *root=newNode; return; } while (1) { if (newNode->key<=act->key) { if (act->less == NULL) { act->less = newNode; return; } else act = act->less; } else { if (act->bigger == NULL) { act->bigger = newNode; return; } else act = act->bigger; } } // while end }
25
struct node** linkAddressTo(struct node* root, struct node* child) { // address of the less or bigger pointer of the parent of 'child' // this is the address of the link pointing to child if (!root || !child || child==root) return NULL; struct node* act = root; int key=child->key; while (act) { if (act->less==child) return &act->less; // return according to address if (act->bigger==child) return &act->bigger; if (key<=act->key) act = act->less; else act = act->bigger; } return NULL; }
26
Magyarázat • Adott elem szülőjének a less illetve bigger mutató közül a megfelelőnek a címét adja vissza – ha csomópontokban lenne parent mutató, akkor erre a függvényre nem lenne szükség
27
void deleteNode(struct node** root, int key) { struct node *del, **linkAddressToDel, *newChild, *sub, **linkAddressToSub; if (*root==NULL) return; // no tree del=searchNode(*root, key); if (!del) return; // key not found linkAddressToDel=linkAddressTo(*root, del); if (del->less==NULL || del->bigger==NULL) {// 0,1 child if (del->less==NULL && del->bigger==NULL) newChild=NULL; // 0 child else if (del->less==NULL) newChild=del->bigger; // 1 child else newChild=del->less; // 1 child if (linkAddressToDel) *linkAddressToDel=newChild; else *root=newChild; free(del); return; 28 }
// 2 children sub=smallestNode(del->bigger); linkAddressToSub=linkAddressTo(*root, sub); if (linkAddressToDel) *linkAddressToDel=sub; else *root=sub; sub->less=del->less; sub->bigger=del->bigger; *linkAddressToSub=NULL; free(del); }
29
Magyarázat • Csomópont törlésnél két eset van, a törlendő csomópontnak (del): – 0 vagy 1 gyereke van – 2 gyereke van • Mindkét esetben vizsgálni kell, hogy a gyökeret töröljüke, ha igen akkor módosítani kell
30
Magyarázat • Két gyerekű csomópont törlésekor a keresőfa tulajdonság megőrzése érdekében del helyére át kell mozgatni a kulcs szerinti szomszédját sub-t – lehetséges sub értékek: • smallestNode(del->bigger): a jobb oldali részfa legkisebb eleme • biggestNode(del->smaller): a bal oldali részfa legnagyobb eleme – sub-nak 0 vagy 1 gyereke van
31
delete 24 **root
12
er gg bi
bi gg
NULL
er
s
er
le s
le
gg
ss le
24
NULL
s
25
*linkAddressToDel
NULL
NULL
s
le
ss
NULL
le s
NULL
31 le s
20
er gg bi
bi
ss
23
*del NULL
32
b ig g
er
ss
er le
le
ss
gg
ss
bi
le ss
le
er
er
gg
b ig g
bi
33
le
ss
ge
r
er
b ig
ss
gg
le
bi
ss
er le
ss
gg
le
bi
s les
34
void main() { struct node *root=NULL, newNode, node1={12, 0, 0, 12}, node2={23, 0, 0, 20}, node3={20, 0, 0, 7}, node4={31, 0, 0, 9}, node5={25, 0, 0, -1}, node6={24, 0, 0, 2}; // createNode(&newNode); insertNode(&root, &newNode); insertNode(&root, &node1); insertNode(&root, &node2); insertNode(&root, &node3); insertNode(&root, &node4); insertNode(&root, &node5); insertNode(&root, &node6); printf("\nOrdered node list: "); printTree(root); if (searchNode(root, 25)) printf("\n25 is found in the tree\n"); deleteNode(&root, 23); printf("\nOrdered node list after deleting 23: "); printTree(root); freeTree(root); 35 }
Kupac (heap) • Definíció: teljes fa: olyan fa, amelynek a szintjei jobbról balra folytonosan vannak feltöltve • Max-kupac: olyan teljes bináris fa, amelynek minden csúcsára igaz, hogy a gyerekek kulcsértékei nem nagyobbak, mint a szülők kulcsértékei – a gyökér a legnagyobb kulcsú • Elsőbbségi sornak is hívják
36
Kupac megvalósítása • Történhet: – felhasználói adatszerkezetként az előbbi példához hasonlóan – tömbként • általában ha kupac rendezést valósítjuk meg és csak a kulcs a hasznos adat • minden bináris fa tárolható tömbként – nem bővíthető dinamikusan
37
Bináris fa reprezentálása tömbbel • A tárolás szabályai: – a fa gyökerét a tömb első eleme tárolja – a k csomópont bal gyereke a tömb [2*k+1], jobb gyereke pedig a [2*k+2] helyet foglalja el – a d mélységű bináris fa tárolásához 2^d elemet tartalmazó tömbre van szükség • annál hatékonyabb, minél teljesebb a fa
38
void exchange(int* a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; } void downheap(int* a, int size, int parent) { // the children of a[v] are already heaps // the root a[v] may violate the heap property // modify the tree to force the heap property int left=2*parent+1, right=2*parent+2, maxChild=left; if (left>=size) return; // a[v] has no children if (right<size && a[right]>a[left]) maxChild=right; // if there are two children and the right is bigger, then it will be maxChild if (a[parent]>=a[maxChild]) return; // it is a heap else { exchange(a, parent, maxChild); // force heap property at the top downheap(a, size, maxChild); // force heap property in the changed subtree } 39 }
Magyarárzat • downheap: egy bináris fát kupaccá alakit, amennyiben a gyökér bal és jobb oldali gyereke eredetileg már kupac – ha a gyökérre nem érvényes a kupac tulajdonság, akkor fel kell cserélni a nagyobb értékű gyerekkel és a meg kell hívni újra a függvényt a módosult részfára – létezik nem rekurzív algoritmus is – magyarul felszívárog-nak hívják a függvényt, mert a maximumot hozza a gyökerébe
40
24 42
heap
31
25
26 5
20
downheap
42 31 25
26 24
20
5 41
void buildheap(int a[], int n) { // first create the basic heaps (they have 2 or elements) // when v==n/4-1, we regard such a tree whose two subtrees are already heaps // the new root may violate the heap property for (int v=n/2-1; v>=0; v--) downheap(a, n, v); } void heapsort(int* a, int n) { buildheap(a, n); while (n>1) { n--; exchange(a, 0, n); // put the biggest of the current heap into its final place in the array // put the most right leaf at the top of the heap downheap(a, n, 0); // force the heap property on the decread heap } 42 }
Magyarázat • buildheap: először kicsi aztán egyre nagyobb kupacokat hoz létre, addig míg minden csomópont része nem lesz a kupacnak – egy különálló csomópont kupacnak tekinthető – két kupacból egy új közös gyökér és a downheap segítségével lehet nagyobb kupacot létrehozni
43
44
24 0
42
26 31
25
3
4
5
6
24 42 26 25 31 20 5
downheap 0
31
26 24
2
5
20 42
25
1
20
1
2
3
4
5
6
42 31 26 25 24 20 5 5 45
Magyarázat • heapsort: maxremove segítségével meghatározzuk először a legnagyobb elemet, aztán a maradék kupacból a legnagyobbat, stb. – maxremove nincs külön megírva • törli a gyökeret • berakja helyére a legalsó szint levelei közül a jobb szélsőt • meghívja az új gyökérre downheap-t
46
42 0
31
2
3
4
5
6
42 31 26 25 24 20 5
26 24
25
1
5
20 5
0
31
26 24
25
3
4
5
6
5 31 26 25 24 20 5
downheap 0
25
26 24
2
20
31
5
1
20
1
2
3
4
5
6
31 25 26 5 24 20 5 47
void printArray(int* array, int size) { int idxI=0; printf("["); for (;idxI<size;idxI++) printf("%d ", array[idxI]); printf("]"); } void main() { int a[]={15, 23, 48, 6, 89, 54, 2, 12}; int size = sizeof (a) / sizeof( int); printArray(a, size); heapsort(a, size); printArray(a, size); }
48
Egyéb fa típusú adatszerkezetek • Kiegyenlített fa: olyan bináris keresőfa, amely biztosítja, hogy ne legyenek benne aránytalanul hosszú ágak – a hatékonyság a mélységétől függ • Binomiális kupac: olyan kupac, amely támogatja kupacok egyesítését • Bxy-fa: – levelek azonos szinten vannak – az elemek rendezettek – egy csúcsnak x-y eleme lehet • S-fa: olyan kiegyenlített bináris kereső fa amelyben a gyakran használt elemek vannak elől 49 – így azok gyorsan elérhetőek
Az időkezelés header fájlai • Az idő és a dátum kezeléséhez a következő deklarációs állományokat kell beépíteni a programunkba: – #include
– #include <sys\timeb.h>
50
asctime függvény • 26 karakteres sztringben adja vissza a *tblock struktúrában tárolt dátumot és időt • Példa: char *asctime(const struct tm *tblock) Sun Jun 19 04:08:30 1994\n\0
51
clock függvény • clock_t clock(void); • Processzor idő lekérdezése – visszatérési értéke a program indulása óta eltelt processzor idő belső egységben – ANSI C kompatibilis • A függvény segítségével két esemény közötti intervallum határozható meg – Ha az időértéket másodpercben kívánjuk megkapni, a visszaadott értéket el kell osztani a CLK_TCK konstanssal 52
ctime függvény • char *ctime(const time_t *time) • A dátumot és az időt sztringgé alakítja , és a 26 karakteres sztringre mutató pointerrel tér vissza • *time paraméter értéke a time függvény hívásával állítható be – ANSI C kompatibilis
53
Példa
#include void main() { time_t now; now=time((time_t *)NULL); printf(”It’s %.24s”,ctime(&now)); }
54
difftime függvény • A függvény a megadott két time_t típusú időpont különbségét határozza meg másodpercekben • double difftime(time_t time2,time_t timer);
55
ftime függvény • Az aktuális időpontot és dátumot a timeb típusú struktúrába tölti • a timeb struktúra szerkezete : struct timeb{ long time;/*1970.1.1 éjfél óta eltelt idő(mp)*/ short millitm;/*a másodpercek törtrésze (ms)*/ short timezone;/*a helyi és a GMT idő eltérése (mp)*/ short dstflag;/*0 ha nincs nyári időszámítás*/ 56
};
gmtime függvény • Az aktuális dátumot és az időpontot Greenwich-i idővé (GMT) konvertálja és egy struct tm típusú struktúrába tölti • time feltöltését a time hívásával végezhetjük • A tm struktúra definíciója a time.h include file-ban található • Visszatérési értéke a struktúrára mutató pointer • DOS specifikus • struct tm *gmtime(const time_t *timer);
57
localtime függvény • A helyi time_t típusú dátumot és az ídőpontot egy struct tm típusú struktúrába tölti • struct tm *localtime(const time_t *timer);
58
A tm struktúra szerkezete: struct tm{ int tm_sec;/*másodperc*/ int tm_min;/*perc*/ int tm_hour;/*óra (0-23)*/ int tm_mday;/*hónap napja (0- 31)*/ int tm_mon;/*hó (0-11)*/ int tm_year;/*év (a naptári év- 1900)*/ int tm_wday;/*a hét napja (0-6 ;vasárnap=0)*/ int tm_yday;/*az év napja (0-365)*/ int tm_isdst;/*0 ha nincs nyári időszámítás*/ }; 59
mktime függvény • Kitölti a tm struktúra hiányzó adattagjait és time_t formátumúra alakítja a struktúrában tárolt időt és dátumot • time_t mktime(struct tm *t);
60
stime függvény • A rendszeridőt és a dátumot állítja be • A tp pointer mutat az idő értékére, amely 1970.január 1. 00:00:00 óra(GMT) óta eltelt időt tartalmazza másodpercekben • int *stime(time_t *tp);
61
time függvény • Az aktuális időt kérdezi le • Visszatérési értékként és a nem NULL timer paraméterrel kijelölt objektumban megadja az aktuális időt (1970. Január 1. 00:00:00 óra GMT óta eltelt idő másodpercekben • ANSI C és UNIX kompatibilis
62
Példa #include void main() { int j,it,eltelt,s; for(j=0;j<2;j++) { it[j].s=ido_sec(&it[j]); } int eltelt=it[1].s-it[0].s; }
63
tzsed függvény • a TZ környezeti változó értéke alapján beállítja a daylight, timezone és tzname globális változókat • Szökő napok?
64
