Tehetséggondozás az informatikában
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…