Az adatszerkezetek osztályozása 2. Az R reláció szerint • 2.3 Szekvenciális adatszerkezetek A szekvenciális adatszerkezet olyan rendezett pár amelynél az R reláció tranzitív lezártja teljes rendezési reláció. Szekvenciális adatszerkezetben az egyes adatelemek egymás után helyezkednek el. Reprezentáció: folytonos ábrázolás esetén vektorral, szétszórt ábrázolás esetén kétirányban láncolt listával Pl.: láncolt lista A láncolt lista olyan adatszerkezet, amelynek minden eleme tartalmaz egy (vagy több) mutatót (pointer) egy másik, ugyanolyan típusú adatelemre.
2
Egyirányú láncolt lista • Dinamikus, homogén adatszerkezet, azaz azonos típusú véges adatelemek sorozata. • Adatelem: Adat (információs rész) Követő elem címére mutató mutató
• Jelölése : L=[a1 a2 ... an ] vagy q=[x1 x2 ... xn ] Ha n=0, akkor L=[ ] ⇒ üres lista. • Létezik első és utolsó eleme (kivéve: üres lista) • Minden elemnek létezik rákövetkezője (kiv. utolsó) és minden elemnek létezik megelőzője (kiv. első)
3
Egyirányú láncolt lista
• Egyszerű lista, lineáris lista, lánc • A lánc első elemének a címét egy listamutató változó, vagy fejelt lista esetén a lista feje tartalmazza. (A listafej nem tartalmaz információs részt.) • A lánc végét az jelzi, hogy az utolsó elem a rákövetkező elem mutatójaként NIL-t tartalmaz. 4
Speciális listafogalmak • Üres (empty) lista: [] • Lista feje (head): a lista első eleme • Lista farka (tail): az a lista, mely az első elem elhagyásával keletkezik • Lista vége (end): a lista utolsó eleme • A lista mérete: a lista elemeinek száma |q|=n 5
A lista alapműveletei A szokásos adatszerkezeti műveletek értelmezéséhez
• Hozzáférés (access) Az i. elem kiválasztása: q[i]→xi . Ha i ∉[1..n] akkor a hozzáférés eredménye: []
• Allista (sublist) képzés Tetszőleges rész kiválasztása a kezdő és végelemmel: q[i..j]→[xi, xi+1,… xj,] (i < j) Ha i<1 vagy hiányzik, akkor az allista a lista elejétől indul, ha j>n vagy hiányzik, akkor az allista a lista végéig megy.
• Konkatenáció (concatenation) Két lista egyesítése: q =[x1, x2,… xn,] és r =[y1, y2,… ym] Ekkor q&r = [x1, x2,… xn, y1, y2,… ym] 6
Műveletek listán • Létrehozás Az üres listából kiindulva konkatenációval rendeljük hozzá az elemeket, mint egyelemű listákat.
• Bővítés A q listát a k. elem után bővíteni akarjuk az x elemmel: q ’ = q[1,…, k] & [x] & q[k+1, …,n] (allistával hasonlóan)
• Törlés Fizikai törlés. A k. elem törlése q ’ = q[1,…, k-1] & q[k+1, …,n]
• Csere A k. elemet cserélem x-re: q ’ = q[1,…, k-1] & [x] & q[k+1, …,n]
7
Műveletek listán • Rendezés Adatelemek értéke szerint bármely módszerrel növekvő vagy csökkenő sorrendbe rendezem a saját helyén, vagy létrehozáskor rendezett listát hozok létre. • Keresés Teljes keresés, rendezett listánál lineáris vagy bináris keresés. • Feldolgozás A definiált műveletek alapján. 8
Szélső elemek kezelése 1. Access head Hozzáférés a legelső elemhez. q[1] 2. Push Egy elemmel bővítem a listát az elején [x]&q 3. Pop Törlöm az első elemet. q[2,…] 4. Access end Hozzáférés az utolsó elemhez: q[|q|] 5. Inject A listát a végén bővítem q&[x] 6. Eject Törlöm az utolsó elemet. q[…, |q|-1]
9
Elem beszúrás a lánc elejére
10
Elem beszúrás a lánc végére
Hatékonysága rossz, mert az utolsó elem megtalálásához mindig végig kell járnunk az egész láncot. Megoldás: tároljuk el a lánc végét jelző mutatót is.
11
Elem beszúrás a lánc belsejébe
Egy adott elem elé való beszúrást általában egyszerűbb úgy megvalósítani, hogy az elem utáni beszúrás algoritmusát alkalmazzuk, majd megcseréljük az új és az adott elemben levő információkat. Ezzel a módszerrel elkerülhetjük, hogy az egész láncot végig kelljen járnunk ahhoz, hogy megtaláljuk a beszúrandó elem előtti elemet. 12
Első elem törlése
13
Utolsó elem törlése
14
Közbenső elem törlése
15
Kétirányban láncolt lista
• Ha gyakran kell a lista előző eleméhez hozzáférnünk, akkor célszerű minden egyes elemet kiegészíteni még egy pointerrel, az előző elem felé. Ekkor kétirányban láncolt listát kapunk.
16
Gyűrű • Egy ciklikus listát gyűrűnek nevezünk. • A lánc bármely eleméből kiindulva elérhetjük a lista valamennyi másik elemét. • Az első elemet felismerhetjük, ha teszteljük a Fej pointerrel való egyezést. A gyűrűkön végzett műveletek (beszúrás, törlés, elemek bejárása) hasonló a lineáris listáknál leírtakhoz. Figyelnünk kell azonban arra, hogy a lista végét nem jelzi többé nil pointer. 17
Gyűrű Kezdo
Adat
Adat
Adat
Koveto
Koveto
Koveto
Listafej Koveto Elozo
Adat
Adat
Adat
Koveto
Koveto
Koveto
Elozo
Elozo
Elozo
18
Verem (stack) • Leggyakrabban alkalmazott adatszerkezet a tömb után. • Olyan speciális lista, ahol a megengedett műveletek: – Push (egy elemmel bővítés az elején) – Pop (törlöm az első elemet) – Top (Access helyett)
• Last In First Out elnevezés rövidítésként LIFO • Homogén, dinamikus 19
Verem reprezentációja 1. Folytonos Vektorral, ahol az első elem mindig a verem alja, kell egy mutató, ami a verem tetejét mutatja. Belső elem eléréséhez törölni kell a felette levőket. l
A verem alja
n
a verem teteje 20
Verem reprezentációja 2. Szétszórt
Egyirányban láncolt lista. A listafej mindig az aktuális első elemre mutat. Ide kell beszúrni az új elemet adatfelvételnél.
fej
NIL 21
Verem • A verem minden komoly szoftverben megjelenik. • Általában olyan helyzetben alkalmazzák, amikor egy 5893 sorrend megfordítása a cél. A sorrend gyakran időrendi sorrend (pl. a hívási láncon visszafele lépkedésnél). • Rekurzív algoritmusoknál is használják.
3985 3 9 8 5
22
Műveletek veremmel • Létrehozás Üres verembe az érkezés sorrendjében pakoljuk bele az elemeket. • Bővítés PUSH művelet (csak a verem tetején) • Törlés POP művelet (csak a verem tetején) • Keresés, rendezés, csere, bejárás nincs • Elérés TOP (a verem legfelső eleme érhető el) • Feldolgozás Az alapműveletekkel
23
Sor (queue) • FIFO (First In First Out) • Új elemet a sor végére lehet bevinni, hozzáférni a sor elejéhez lehet. • Egy speciális lineáris lista, ahol az értelmezett műveletek: – Access head (hozzáférés az első elemhez) – POP helyett GET (Első elem törlése) – Inject helyett PUT (végén bővítem) • „egyirányú egynyomtávú alagút”
24
Sor (queue) • Tipikus felhasználása: Az adatoknak feldolgozás előtt sorba kell állni, várakozniuk kell az erőforrásokhoz való hozzáférésre (programvégrehajtás, perifériához való hozzáférés, billentyűzetpuffer).
• Kevésbé fontos szerepe van mint a veremnek. • Reprezentációja: – Folytonos ábrázolás esetén: vektor – Szétszórt ábrázolás esetén: egyirányban láncolt lista
25
Folytonos ábrázolási lehetőségek 1. Fix kezdetű sor 2. Vándorló sor 3. Ciklikus sor
26
1. Fix kezdetű sor • A sor első elemének indexe 1, rögzített. • Az indexmutató a sor végét jelöli. • Egy sor lehet üres és teli. • Bővíteni a sor végén lehet, hozzáférni csak az 1-es indexű elemhez lehet, ekkor az egész sort eggyel balra kell tolni. • Tetszőleges elemhez való hozzáféréshez az előtte lévő elemek fizikailag törlődnek. 27
2. Vándorló sor • A sor elejét is végét is indexmutató jelöli. • Bővíteni az utolsó, V indexű elem után lehet, hozzáférni csak az E indexű elemhez lehet. • Ha nincs több szabad tárhely, akkor az egész vektor visszatolódik a tárhely elejére. 1
n x
x E
x E
x
x
x
V
V
x 28
3. Ciklikus sor • A sor elejét is végét is indexmutató jelöli. • Nincs nagytömegű adatmozgás, a sor ciklikusan vándorol körbe. • Ha a vektor utolsó eleme már foglalt, a vektor elején folytatom az új elemek bevitelét. 1
n x
x E
x
x
x
V 29
Kétvégű sor (dequeue) • A sor mindkét végén lehet bővíteni és mind a két végén lévő elemhez hozzá lehet férni. • Tekinthető két aljánál összeillesztett veremnek is. • Speciális esetei: – Input korlátozott kettős sor RPUT nem engedett – Output korlátozott kettős sor RGET nem engedett
• Memóriakezelési gondok megoldásánál szokták alkalmazni. RPUT GET
PUT RGET 30
Sztring (string) • Speciális lista, melynek elemei az ábécé szimbólumai. (Szigorítjuk: karakterek) • Sztringhez kapcsolódó fogalmak: – Részsztring (allista) – Konkatenáció (egyesítés) – Hossz (length), karakterek száma – Üres string
31
Műveletek sztringekkel • • • • • • • •
Létrehozás (megadom az összes elemét) Bővítés (bárhol részsztringgel bővítek) Törlés (fizikai törlés, részsztring törlése) Csere (részsztringet részsztringre, hossz mindegy) Rendezés, bejárás nem értelmezett. Elérés: közvetlen Keresés (részsztringet keresek) Feldolgozás (később)
32
Sztring reprezentációja folytonos ábrázolással Karakterenként 1 byte, belső kód alapján. 1. Fix hosszon – Leghosszabb sztring méretéhez igazodni kell. (rövidebb sztring végén szóközök) – Kényelmes, de pazarló
33
Sztring reprezentációja folytonos ábrázolással 2. Változó hosszon – Minden sztringnek csak a szükséges helyet foglalom le (minden karakter 1 byte). – Meddig tart a sztring? Jelöljük hol kezdődnek a sztringek, azaz tároljuk le előtte a hosszát. – Nehezebb kezelés, meg kell tudni különböztetni a hosszjelzőt a tényleges karakterektől (Pascal). 34
Sztring reprezentációja folytonos ábrázolással 2. Változó hosszon –
Készíthető egy információs táblázat is
Kezdeti cím
–
A sztring hossza
Végjeleket is alkalmazhatok, ekkor a sztring végjeltől végjelig tart. 35
Minden láncolt listaelem egy-egy karaktert tartalmaz. Sok mutató ⇒ sok hely ⇒ csak elmélet Karakter helyett részsztring a listaelemben? Tördelés a probléma.
36
Mintaillesztés (pattern matching) Feladat: Adott egy sztring, keressük meg hogy egy adott másik sztring előfordul-e benne, ha igen, akkor hol? (képfeldolgozás, szövegben keresés csere) Jelölés: Alapsztring: a[1…N] (a= 100111010010100010100111000111) Keresendő sztring : p[1…M] (p=10100111)
37
I. Mezítlábas algoritmus 1. 2.
Karakterenként hasonlítunk Egyezés esetén következő karakter, különben az alapsztringben visszalépünk oda, ahonnan a mintasztring legutolsó hasonlítását kezdtük, és az alapsztring következő a mintasztring legelső karakterével kezdjük újra a vizsgálatot. 100111010010100010100111000111 10100111 100111010010100010100111000111 10100111 100111010010100010100111000111 10100111
38
I. Mezítlábas algoritmus 100111010010100010100111000111 10100111 A mintasztringet addig tolom eggyel jobbra, amíg egyezést nem találunk vagy a végére nem érünk. Az algoritmus lassú, az összes lehetséges esetet végigvizsgálja. 39
II. Knuth-Morris-Pratt mintaillesztés • Cél: a szöveg minden egyes karakterét csak egyszer felhasználni összehasonlításban • Pl.: T=”kirándulnak a kirándulók a hegyekbe” P=”kiránduló” • Mivel csak egy ‘k’ van P-ben, az első eltérést adó pozícióba ugorhatunk. (8) • az eltolással.
