Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
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;
+
}
+

A lap 2008. március 27., 23:06-kori változata

Tartalomjegyzék

6. előadás (2008-03-28)

Ami az eddigiekből kimaradt

Felsorolások (enumerátorok), az enum adattípus

enum típusazonosító {felsorolás} változók;

enum hetkoznap {hetfo, kedd, szerda, csutortok, pentek};
enum Boolean {true, false} elment=false;
...
enum hetkoznap fogorvos=szerda;
fogorvos=pentek;
...
elment=true;

Automatikusan 0-tól sorszámozódó int típusok. Az érték megválasztható:

enum t_vegu_szamjegyek {ot=5, hat, het};

típusazonosító nélküli egyszer használatos felsorolások:

enum {tegnap, ma, holnap} mikor=ma;
...
mikor=holnap;

typedef -- típus definiálása

esetszétválasztás (switch/case/default)

Feltételes kifejezés

Személyes eszközök