|
|
1. sor: |
1. sor: |
− | == 5. előadás (2008-03-21) == | + | == 6. előadás (2008-03-28) == |
| | | |
− | ==== Struktúrák igazítása ==== | + | === Ami az eddigiekből kimaradt === |
| | | |
− | A 2/4/8 hosszú adatok (short/int/double/...) csak 2/4/8-cal osztható címen kezdődhetnek.
| + | ==== Felsorolások (enumerátorok), az enum adattípus ==== |
| | | |
− | ~/info2/igazit.c
| + | <code>enum</code> '''típusazonosító''' {'''felsorolás'''} '''változók'''; |
| | | |
− | /* megnézzük, hogy a struktúrában hogy történik az igazítás */ | + | enum hetkoznap {hetfo, kedd, szerda, csutortok, pentek}; |
− | #include <stdio.h>
| + | enum Boolean {true, false} elment=false; |
− |
| + | ... |
− | int main(void) {
| + | enum hetkoznap fogorvos=szerda; |
− | struct igazito {
| + | fogorvos=pentek; |
− | int a;
| + | ... |
− | char b;
| + | elment=true; |
− | double d;
| + | |
− | char f;
| + | |
− | struct igazito *p;
| + | |
− | } ig={1, 'w', 3.4, 'f', &ig};
| + | |
− | | + | |
− | printf("\n%d %p, %c %p, %f %p, %c %p\n%p %p\n",
| + | |
− | ig.a, &ig.a, ig.b, &ig.b, ig.d, &ig.d, ig.f, &ig.f, ig.p, &ig.p);
| + | |
− | return 0;
| + | |
− | }
| + | |
| | | |
| + | Automatikusan 0-tól sorszámozódó int típusok. Az érték megválasztható: |
| | | |
| + | enum t_vegu_szamjegyek {ot=5, hat, het}; |
| | | |
− | === Bináris keresőfák ===
| + | '''típusazonosító''' nélküli '''egyszer használatos''' felsorolások: |
| | | |
| + | enum {tegnap, ma, holnap} mikor=ma; |
| + | ... |
| + | mikor=holnap; |
| | | |
− | '''Bináris fa'''
| + | ==== typedef -- típus definiálása ==== |
− | * csúcs
| + | |
− | * él
| + | |
− | * gyerek
| + | |
− | * szülő
| + | |
− | * bináris fa (ha minden csúcsnak 0, 1 vagy 2 gyereke van)
| + | |
− | * gyökér
| + | |
− | * belső csúcs (akinek van gyereke -- akár a gyökér is lehet belső csúcs)
| + | |
− | * levél (akinek nincs gyereke -- akár a gyökér is lehet levél)
| + | |
− | * bal részfa
| + | |
− | * jobb részfa
| + | |
− | * részfa gyökere
| + | |
| | | |
− | '''A bináris keresőfa''' olyan bináris fa, melynek minden csúcsában egy érték szerepel, és minden csúcsára igaz, hogy a bal részfában szereplő értékek mind legfeljebb akkorák, mint a csúcsban szereplő érték, és a jobb részfában szereplő értékek mind legalább akkorák, mint a csúcsban szereplő érték. Néha kikötik, hogy egy érték csak egyszer szerepelhet (ez egyszerűsíti a bináris fában végzett műveleteket).
| |
| | | |
− | Példa bináris keresőfára:
| |
| | | |
− | 0
| + | ==== esetszétválasztás (switch/case/default) ==== |
− | / \
| + | |
− | / \
| + | |
− | -5 3
| + | |
− | / \ \
| + | |
− | -10 -5 42
| + | |
− | / \
| + | |
− | -5 -2
| + | |
| | | |
− | Alapműveletek bináris keresőfákkal:
| + | ==== Feltételes kifejezés ==== |
− | | + | |
− | * keresés
| + | |
− | * új érték beszúrása
| + | |
− | * érték törlése
| + | |
− | | + | |
− | Egyéb művelet bináris keresőfákkal:
| + | |
− | | + | |
− | * kiegyensúlyozás: a fa átalakítása a benne levő értékek megtartásával úgy, hogy a magassága (jóval) kisebb legyen.
| + | |
− | | + | |
− | Példa kiegyensúlyozásra:
| + | |
− | | + | |
− | 1
| + | |
− | / \
| + | |
− | 0 2 3
| + | |
− | \ / \
| + | |
− | 3 / \
| + | |
− | \ --> / \
| + | |
− | 4 1 5
| + | |
− | \ / \ / \
| + | |
− | 5 0 2 4 6
| + | |
− | \
| + | |
− | 6
| + | |
− | | + | |
− | Kiegyensúlyozott fa (ez egy nem túl precíz fogalom): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal részfában nagyjából ugyanannyi csúcs van, mint a jobb részfában.
| + | |
− | | + | |
− | Részfa magassága: a részfa gyökerétől egyik leveléig menő leghosszabb úton levő csúcsok száma.
| + | |
− | | + | |
− | AVL-fa (precíz fogalom, a kiegyensúlyozott fák egy fajtája): olyan bináris fa, melynek minden csúcsára igaz, hogy a bal részfa magassága és a jobb részfa magassága közti különbség -1, 0 vagy +1.
| + | |
− | | + | |
− | Keresés bináris keresőfában: A feladat az, hogy keressünk egy olyan csúcsot a fában, ahol az adott érték szerepel. Ha több ilyen csúcs is van, akkor bármelyik jó.
| + | |
− | | + | |
− | A bináris fában való keresés (rekurzív) algoritmusa:
| + | |
− | | + | |
− | # A gyökértől indulunk.
| + | |
− | # Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
| + | |
− | # Ha a bal részfa nem üres, és az aktuális csúcsban a kívánt értéknél nagyobb érték szerepel, a bal részfa gyökerével folytatjuk (a 2. lépéstől).
| + | |
− | # Ha a jobb részfa nem üres, és az aktuális csúcsban a kívánt értéknél kisebb érték szerepel, a jobb részfa gyökerével folytatjuk (a 2. lépéstől).
| + | |
− | # A keresést befejezzük, az adott érték nem található meg a fában.
| + | |
− | | + | |
− | Beszúrás bináris keresőfába: A feladat az, hogy szúrjunk be a fába egy új értéket úgy, hogy az továbbra is bináris keresőfa maradjon.
| + | |
− | | + | |
− | Látható, hogy a keresés legfeljebb annyi lépésből áll, amennyi a fa magassága. AVL-fánál (és sok egyéb kiegyensúlyozott fánál is) egy ''n'' csúcsot tartalmazó fa magassága ''O''(log ''n''), tehát a keresés gyors. Szélsőséges esetben, például ha a fa csúcsainak csak jobboldali gyerekük van, az egész fát be kellhet járni (''O''(''n'')).
| + | |
− | | + | |
− | A bináris fa egy csúcsát struktúraként definiáljuk:
| + | |
− | | + | |
− | struct csucs {
| + | |
− | int ertek;
| + | |
− | struct csucs *bal;
| + | |
− | struct csucs *jobb;
| + | |
− | };
| + | |
− | | + | |
− | Példa a fenti bináris fa azon részfájának létrehozására, ami a 3-ból indul lefele:
| + | |
− | | + | |
− | #include <stdlib.h> /* a NULL miatt */
| + | |
− | | + | |
− | int main(int argc, char**argv) {
| + | |
− | struct csucs a, b;
| + | |
− | a.ertek=3;
| + | |
− | a.bal=NULL;
| + | |
− | a.jobb=&b;
| + | |
− | b.ertek=42;
| + | |
− | b.bal=NULL;
| + | |
− | b.jobb=NULL;
| + | |
− | return 0;
| + | |
− | }
| + | |
− | | + | |
− | | + | |
− | | + | |
− | Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.
| + | |
− | | + | |
− | A bináris keresőfába való beszúrás algoritmusa:
| + | |
− | | + | |
− | # A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
| + | |
− | # Paraméterként kapjuk az aktuálisan vizsgálandó részfa gyökerének címét. (Üres fa esetén van lényeges különbség: az üres fa gyökere ugyanis NULL, az üres fa gyökerének címe pedig az a memóriaterület, ahol a NULL-t majd átírjuk másra.)
| + | |
− | # Ha az aktuális gyökér NULL, akkor cseréljük le a beszúrandó csúcsra: a csúcs értéke a beszúrandó érték legyen, a bal és jobb mutatók pedig NULL-ok legyenek.
| + | |
− | # Ha a beszúrandó érték megegyezik az aktuális gyökérben található értékkel, és az aktuális gyökérnek nincs bal gyereke, folytassuk a jobb részfával (a 3. lépéstől). (Az algoritmus e lépés nélkül is jól működne.)
| + | |
− | # Ha a beszúrandó érték legfeljebb akkora, mint az aktuális gyökérben található érték, akkor folytassuk a bal részfával (a 3. lépéstől).
| + | |
− | # Folytassuk a jobb részfával (a 3. lépéstől).
| + | |
− | | + | |
− | Programban:
| + | |
− | | + | |
− | ~/info2/fabeolv.c
| + | |
− | | + | |
− | #include <stdio.h>
| + | |
− | #include <stdlib.h>
| + | |
− |
| + | |
− | struct csucs {
| + | |
− | int ertek;
| + | |
− | struct csucs *bal;
| + | |
− | struct csucs *jobb;
| + | |
− | };
| + | |
− |
| + | |
− | /* Beszúrja a gyoker részfába az uj csúcsot levélként (és egyben NULL-t tesz
| + | |
− | * az uj csúcs bal és jobb mutatóiba.
| + | |
− | */
| + | |
− | void beszur(struct csucs **gyoker, struct csucs *uj) {
| + | |
− | while (*gyoker != NULL) {
| + | |
− | if (uj->ertek <= (*gyoker)->ertek) {
| + | |
− | gyoker = &(*gyoker)->bal;
| + | |
− | } else {
| + | |
− | gyoker = &(*gyoker)->jobb;
| + | |
− | }
| + | |
− | }
| + | |
− | *gyoker = uj;
| + | |
− | uj->bal = NULL;
| + | |
− | uj->jobb= NULL;
| + | |
− | }
| + | |
− |
| + | |
− | void kirajzol(struct csucs *gyoker, int nszokoz) {
| + | |
− | int i;
| + | |
− | for (i=nszokoz; i>0; i--) putchar(' ');
| + | |
− | if (gyoker!=NULL) {
| + | |
− | printf("%d\n", gyoker->ertek);
| + | |
− | kirajzol( gyoker->bal, nszokoz+2);
| + | |
− | kirajzol( gyoker->jobb, nszokoz+2);
| + | |
− | } else printf("-\n");
| + | |
− | }
| + | |
− |
| + | |
− | int main(void) {
| + | |
− | int i, csucsoksz=0;
| + | |
− | struct csucs *gyoker=NULL;
| + | |
− | struct csucs *fa;
| + | |
− |
| + | |
− | printf("Hány csúcsa lesz a fának? ");
| + | |
− | scanf("%d", &csucsoksz);
| + | |
− | fa = (struct csucs*) malloc(csucsoksz*sizeof(struct csucs));
| + | |
− | if(fa == NULL) {
| + | |
− | printf("Nincs eleg memoria!");
| + | |
− | return 0;
| + | |
− | }
| + | |
− | for(i=0; i<csucsoksz; i++) {
| + | |
− | printf("%d. csúcs értéke? ", i+1);
| + | |
− | scanf("%d",&fa[i].ertek);
| + | |
− | beszur(&gyoker, &fa[i]);
| + | |
− | }
| + | |
− | kirajzol(gyoker,1);
| + | |
− | return 0;
| + | |
− | }
| + | |
Automatikusan 0-tól sorszámozódó int típusok. Az érték megválasztható: