Adatszerkezetek I.

A MIU-nyelvet azok és csak azok a szavak alkotják, amelyek az MI axiómából levezethetők, amelyek a kiindulási MI szóból a szabályok egymást követő alkalmazásával előállíthatóak – a szavak közötti leszármazási viszony pedig tálcán kínálja azok fában való elrendezését:

MI┬─MIU──MIUIU──MIUIUIUIU──MIUIUIUIUIUIUIUIU──MIUIUIUIUIUIUIUIUIUIUIUIUIUIUIUIU
  └─MII┬─MIIU───MIIUIIU────MIIUIIUIIUIIU──────MIIUIIUIIUIIUIIUIIUIIUIIU
       └─MIIII┬─MIIIIU───┬─MIIIIUIIIIU──────┬─MIIIIUIIIIUIIIIUIIIIU
              │          │                  ├─MUIUIIIIU
              │          │                  ├─MIUUIIIIU
              │          │                  ├─MIIIIUUIU
              │          │                  └─MIIIIUIUU
              │          ├─MUIU───────────────MUIUUIU
              │          └─MIUU───────────────MIUUIUU
              ├─MIIIIIIII┬─MIIIIIIIIU───────┬─MIIIIIIIIUIIIIIIIIU
              │          │                  ├─MUIIIIIU
              │          │                  ├─MIUIIIIU 
              │          │                  ├─MIIUIIIU
              │          │                  ├─MIIIUIIU
              │          │                  ├─MIIIIUIU
              │          │                  └─MIIIIIUU
              │          ├─MIIIIIIIIIIIIIIII┬─MIIIIIIIIIIIIIIIIU
              │          │                  ├─MIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
              │          │                  ├─MUIIIIIIIIIIIII
              │          │                  ├─MIUIIIIIIIIIIII
              │          │                  ├─MIIUIIIIIIIIIII
              │          │                  ├─MIIIUIIIIIIIIII
              │          │                  ├─MIIIIUIIIIIIIII
              │          │                  ├─MIIIIIUIIIIIIII
              │          │                  ├─MIIIIIIUIIIIIII
              │          │                  ├─MIIIIIIIUIIIIII
              │          │                  ├─MIIIIIIIIUIIIII
              │          │                  ├─MIIIIIIIIIUIIII
              │          │                  ├─MIIIIIIIIIIUIII
              │          │                  ├─MIIIIIIIIIIIUII
              │          │                  ├─MIIIIIIIIIIIIUI
              │          │                  └─MIIIIIIIIIIIIIU
              │          ├─MUIIIII──────────┬─MUIIIIIUIIIII
              │          │                  ├─MUUII
              │          │                  └─MUIIU
              │          ├─MIUIIII──────────┬─MIUIIIIIUIIII
              │          │                  └─MIUUI
              │          ├─MIIUIII──────────┬─MIIUIIIIIUIII
              │          │                  └─MIIUU
              │          ├─MIIIUII────────────MIIIUIIIIIUII
              │          ├─MIIIIUI────────────MIIIIUIIIIIUI
              │          └─MIIIIIU────────────MIIIIIUIIIIIU
              └─MUI────────MUIUI────────────┬─MUIUIU
                                            └─MUIUIUIUI

A fenti ábrából rögtön adódik a szavak felsorolásának, illetve előállításának kézenfekvő módja is:

• alkalmazzuk az MI szóra alkalmazható összes szabályt (U, D), így előállítva a fa gyökerét követő szint elemeit (MIU, MII),
• vegyük e szint első elemét (MIU), alkalmazzuk arra az egyetlen lehetséges szabályt (D), és illesszük be a keletkezett szót a következő szintre (MIUIU);
• folytassuk az MII szóval, illetve az erre alkalmazható szabályokkal (U, D): ha az így kapott utódokat elhelyeztük a fában (MIIU, MIIII), végeztünk e szinttel;
• a következő szintre lépve az ott található három szó utódai adják a rákövetkező szint elemeit, és így tovább.

Azaz a szélességi bejárás (BFS: breadth-first search) algoritmusát követve folyamatosan kapjuk a következő szintre beilleszthető elemeket (amelyek egyúttal garantálják, hogy a bejárásnak soha nem lesz vége) – érdemes elgondolkodni azon, mi lenne akkor, ha a mélységi bejárás (DFS: depth-first search) útját követnénk.

Ha csak azt a célt tűznénk ki magunk elé, hogy az előállított szavakat írjuk a képernyőre, akkor is szükség lenne arra, hogy egyes szavakat –legalábbis átmenetileg– tároljunk: az éppen vizsgált szó fiait nem veszíthetjük el addig, amíg eljutunk azok fiainak előállításáig.

Erre az első pillanattól szükségünk van (nem mellesleg alapos okunk van azt feltételezni, hogy a fa felépítése során egyre hosszabb a feldolgozásra váró szavak sora):

MI, majd utána MIU, MII
(úgy tűnik, itt eldobhatjuk az MI szót)
MIU, MII, majd utánuk MIUIU
(úgy tűnik, itt eldobhatjuk a MIU szót)
MII, MIUIU, majd utánuk MIIU, MIIII
(úgy tűnik, itt eldobhatjuk a MII szót)

A fenti gondolatmenet alapján célszerűnek tűnik a szavakat egy listában elhelyezni (a halmaz már csak azért sem jöhet szóba, mert ott az elemeknek nincs sorrendje: nem tudjuk, hogy melyekkel kell a következő körben foglalkoznunk).

Ha valakinek a fentiek elolvasása után rossz érzése, hiányérzete van, az egyáltalán nem baj: a szavakból felépíthető fa kapcsán pontosításra, az ennek tárolására szolgáló lista elején álló szavak elhagyása kapcsán pedig helyesbítésre lesz szükség – hamarosan szembesülni fogunk azzal, hogy az elmondottak lényeges kiegészítésre szorulnak…