Adatszerkezetek�2022.10.18

Ismétlés

Mohó algoritmusok

​

​

,,optimálisnak tűnő döntés”

​

Nem minden probléma oldható meg mohó algoritmussal és nem mindig ad optimális megoldást.

Pénzváltás probléma

​

​

• Egy nyugdíjas elmegy a postára, hogy felvegye 79.845 Ft-os nyugdíját. Hogyan tudja a postai pénztáros kifizetni neki ezt az összeget úgy, hogy a kifizetéshez a lehető legkevesebb darab címletet használja?

​

​

​

Pénzváltás probléma

​

​

A pénztáros az alábbi címleteket fogja adni:

3 db 20.000 Ft-os = 60.000 Ft

1 db 10.000 Ft-os = 10.000 Ft

1 db 5.000 Ft-os = 5.000 Ft

2 db 2.000 Ft-os = 4.000 Ft

1 db 500 Ft-os = 500 Ft

1 db 200 Ft-os = 200 Ft

1 db 100 Ft-os = 100Ft

2 db 20 Ft-os = 40 Ft

1 db 5 Ft-os = 5 Ft 79.845 Ft

Ez összesen 13 db papír pénzt, illetve pénzérmét jelent.

​

​

​

Levélfeladás

​

​

Nyugdíjasunk szeretne feladni egy levelet, mely 1400 Ft-ba kerül. Hogyan lehet ezt megtenni, ha a lehető legkevesebb számú bélyeget szeretnénk a borítékra tenni.

​

Rendelkezésre álló bélyegcímletek:

3.500 Ft

1.000 Ft

700 Ft

340 Ft

210 Ft

100 Ft

10 Ft

​

​

Adatszerkezetek

Az adatszerkezetek

​

​

Az adatszerkezet adatok tárolására és szervezésére szolgáló módszer (konstrukció), amely lehetővé teszi a(z adatokhoz való) hatékony hozzáférést és (a) módosításokat.

​

Tanult absztrakt adatszerkezetek:

• Lista
• Verem
• Sor
• Prioritás sor
• Kupac

Az adatszerkezetek

​

​

Leggyakoribb műveletek (H: adatok dinamikus halmaza, k: kulcsmező)

KERES(H,k)

BESZÚR(H,k) (Push)

TÖRÖL(H,k) (Pop)

MIN(H)

MAX(H)

ELŐZŐ(H,k)

KÖV(H,k)

Az adatszerkezetek

​

​

Adatszerkezet: absztrakt adatszerkezet konkrét megvalósítása.

​

– Egy programozási nyelven is lehet több megvalósítás,

– bizonyos műveletek hatékonyabbak,

– megfelelő absztrakt adatszerkezet megválasztása fontos az algoritmushoz,

– megfelelő adatszerkezet megválasztása kulcs az implementáció optimális futásidejéhez!

Az adatszerkezetek

​

​

Adatszerkezet: absztrakt adatszerkezet konkrét megvalósítása.

​

– Egy programozási nyelven is lehet több megvalósítás,

– bizonyos műveletek hatékonyabbak,

– megfelelő absztrakt adatszerkezet megválasztása fontos az algoritmushoz,

– megfelelő adatszerkezet megválasztása kulcs az implementáció optimális futásidejéhez!

Láncolt listák

Láncolt listák

​

​

Minden elem egy adatból és egy (vagy több) mutatóból áll.

A mérete futás során módosítható.

Láncolt listák

​

​

Típusai:

Egyirányú lista:

• Minden elem egy adatot és egy rákövetkező elemre mutató pointert/referenciát tárol.
• Az utolsó elem pedig egy NULL-ra mutat.

​

Például:

6 → 9 → 5 → NULL

Láncolt listák

​

​

Kétirányú lista:

• Minden elem két pointert/referenciát tárol az adat mellett.
• Egyet a rákövetkező elemre, egy másikat a megelőzőre.
• Előnye, hogy mindkét irányban bejárható és törlésnél nem kell tudnunk a megelőző csúcs címét.
• Az első és utolsó eleme is NULL.

​

Például: NULL ← 1 ↔ 2 ↔ 3 → NULL

​

Láncolt listák

​

​

Körben láncolt lista:

• Az összes elem egy körbe van kötve.
• Nincs NULL elem a ,,végén”, az utolsó csúcs rákövetkező pointere az első elemre mutat.
• Lehet egyirányú és kétirányú láncolt is.
• Előnye, hogy bármelyik elemet kijelölhetjük kezdő elemnek.

​

Láncolt listák

​

​

Példa:

• Közvetlen elérésű tömb megvalósítás esetén mi a műveletigénye a keresésnek, törlésnek, beszúrásnak, i. elem kiolvasásának?

​

• Átméretezés?

​

• Láncolt listás megvalósításnál mik az előző műveletek igényei?

​

Tömb

​

​

Ugyanolyan típusú elemeket tárol, a mérete előre definiált kell legyen és nem lehet megváltoztatni futás során

Legyen n a tömb mérete. Ekkor:

– Elérési idő: O(1), mert az elemek egymás után folyamatosan tárolódnak a memóriában

– Beszúrás: O(n) legrosszabb esetben, ha a tömb elejére akarunk beszúrni és minden eddigi elemet arrébb kell rakni.

– Törlés: O(n) legrosszabb esetben, ha a tömb elejéről törlünk és minden további elemet egyel előre kell rakni

– Keresés: O(log n), ha rendezett a tömb (bináris keresés) és O(n), ha nem (szekvenciális keresés)

​

Listák vagy tömbök – Hozzáférési idő

​

​

• Tömbök
• - Konstans elérési idő O(1)

​

• Listák
• Minden NODE 2 paraméterrel rendelkezik
• Adat és a LINK
• Az első elem a HEAD node, melyet kezelünk a függvényekkel
• Elemről elemre haladunk
• Nem konstans idő O(n)

​

Listák vagy tömbök – Memória igény

​

​

Tömbök

• Fix méret
• Felesleges memória
• 7 elemhez 7x4=28 byte
• Komplex típusoknál ez „gyorsan” növekszik
• 7x16 = 112 byte
• Túl nagy tömb/kevés memória

Listák

• Nincs szükségtelen memória
• Extra memória a mutatóknak
• 3 elemhez 8x3=24byte
• Komplex típusoknál ez „lassan” növekszik
• 3x(16+4)=60 byte
• Óriási adat/sok kicsi memória

​

Listák vagy tömbök – Elem beszúrásának költsége

​

​

Tömbök

• Elejére
• Az elem beszúrásához minden elemet odébb kell tenni. O(n) idő
• 2. Hátuljára
• O(1) – ha nincs tele a tömb
• O(n) – ha tele van a tömb
• 3. Belsejébe - O(n)

Listák

• Elejére
• Az elem beszúrásához csak egy címet kell átcserélnünk. O(1) idő
• 2. Hátuljára
• O(n) végig kell menni a teljes listán.
• 3. Belsejébe - O(n)

​

​

​

Három szcenárió: 1. elejére, 2. hátuljára, 3. belsejébe

​

​

Listák vagy tömbök – Használat

​

​

✓ 🗴

Verem

Verem

​

​

• A verem egy LIFO (last in, first out) adatszerkezet
• Két műveletet támogat:
• push: egy elemet hozzáadunk az eddigiekhez úgy, hogy a verem tetejére tesszük
• pop: az utoljára beszúrt elemet veszi ki a veremből (a tetejéről)

Verem

​

​

Legyen n a verem mérete. Ekkor:

• Elérési idő: O(1), de csak a verem tetején lévő elemet tudjuk elérni
• Beszúrás: O(1), mert mindig a tetejére pakolunk
• Törlés: O(1), de csak a tetején lévő elemet tudjuk törölni

Verem

​

​

Feladat:

Egy V veremben kezdetben egyetlen szám, az 1 van. Utána n-szer végrehajtjuk a

Veremből (V, x)

y = 2x;

z = 2x+1;

Verembe (V, y);

Verembe (V, z);

műveleteket.

Mi lesz ezután a Veremből (V, x) eredménye?

Mi lesz az eredmény, ha sort használunk verem helyett?

Verem

​

​

Feladat:

Egy V veremben kezdetben egyetlen szám, az 1 van. Utána n-szer végrehajtjuk a

Veremből (V, x)

y = 2x;

z = 2x+1;

Verembe (V, y);

Verembe (V, z);

műveleteket.

Mi lesz ezután a Veremből (V, x) eredménye?

Mi lesz az eredmény, ha sort használunk verem helyett?

Sor

Sor

​

​

A sor egy FIFO (first in, first out) adatszerkezet.

Két műveletet támogat:

• enqueue: egy új elemet adunk hozzá úgy, hogy a sor végére szúrjuk be
• dequeue: az első elemet töröljük a sorból

Sor

​

​

Legyen n a sor mérete. Ekkor:

• Elérési idő: O(n) legrosszabb esetben
• Beszúrás: O(1)
• Törlés: O(1)

Feladat

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Betesz

kivesz

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Fontos:

• Üres a sorunk?
• Már csak egy elem maradt
• Minden más esetben…

​

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Mi ezzel a probléma?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Előbb vagy utóbb kicsúszunk a tömbből…

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

​

​

• Hogyan lehet egy sort vektorban megvalósítani?

Feladat

Feladat

​

​

• Adjuk meg a sor megvalósítását két verem felhasználásával! Elemezzük a sor műveleteinek a végrehajtási idejét!

​

Feladat

​

​

• Adjuk meg a sor megvalósítását két verem felhasználásával! Elemezzük a sor műveleteinek a végrehajtási idejét!

​

Enqueue(x)

S1.Push(x)

​

Deque

If (S2 is empty)

While(S1 is not empty)

S2.Push(S1.pop)

Return S2.pop

O(1)

O(n)

Feladat

Feladat

​

​

• Adjuk meg a verem megvalósítását két sor felhasználásával. Elemezzük a verem műveleteinek végrehajtási idejét!

​

Feladat

​

​

Push (x)

While (Q1 is not empty)

Temp =Q1.deque

Q2.enque = Temp

Q1.enque

While (Q2 is not empty)

Temp =Q2.deque

Q1.enque = Temp

Pop()

Return Q1.deque

1

1

1

2

2

1

1.

2.

3.

4.

5.

O(2n) = O(n)

O(1)

Prioritási Sor

Prioritási sor

​

​

Absztrakt adatszerkezet, melyben az elemeket prioritásuk szerint tároljuk

​

Három műveletet támogat:

• insert: beszúr egy elemet
• pop: kiveszi a legkisebb prioritású elemet
• min: a legkisebb prioritású elemet adja vissza (pl. int-ek esetén minimumot)

​

Prioritási sor

​

​

Legyen n a PriSor mérete.

Egy standard implementációban:

– Min/Max: O(1)

– Beszúrás: O(log n)

– Törlés: O(log n)

​

Feladat

Feladat

​

​

Feladat Adott a 3, 6, 10, 8, 1, 9, 7 számsorozat, melyeket ebben a sorrendben tárolunk el.

​

Adjuk meg milyen sorrendben vehetjük ki az elemeket:

• verem
• sor
• és prioritási sor adatszerkezet esetén

​

Feladat

​

​

Megoldás:

Verem: Mivel egy LIFO adatszerkezetről van szó, így a legkésőbb berakott elem kerül ki legelőször. A sorrend tehát megfordul: 7, 9, 1, 8, 10, 6, 3

​

Sor: ez egy FIFO adatszerkezet, tehát az jön ki először, amit legelőször tettünk be. A sorrend megmarad: 3, 6, 10, 8, 1, 9, 7

​

Prioritási sor: az elemek rendezésre kerülnek az adatszerkezetben, tehát a sorrend: 1, 3, 6, 7, 8, 9, 10.

Feladat

Feladat

​

​

Hogyan tudjuk megállapítani egy listáról, hogy van e benne kör?

​

​

​

Feladat

​

​

Hogyan tudjuk megállapítani egy listáról, hogy van e benne kör?

​

​

​

Kupac

Feladat

​

​

A kupac (heap) egy hatékony megvalósítása a prioritási sor absztrakt adatszerkezetnek.

​

A kupac egy bináris fa, amelynek minden csúcsa legalább akkora, mint gyerekei → maximális elem a gyökérben van

​

​

​

Feladat

​

​

A kupac olyan véges elemsokaság, amely rendelkezik az alábbi tulajdonságokkal:

​

• Minden elemnek legfeljebb két rákövetkezője (leszármazottja) lehet. Azaz bináris fának tekinthető.

​

• Minden eleme kisebb (vagy egyenlő) a közvetlen leszármazottjainál.

​

• A kupac balról folytonos, azaz ha nem teljes a fa, akkor csak a legutolsó szintből hiányozhatnak elemek, de azok is csak a szint jobb széléről.

​

​

​

Feladat

​

​

​

​

​

Feladat

​

​

Egy h magasságú kupacnak legalább (ill. legfeljebb) hány eleme van?

​

​

​

Feladat

​

​

Egy h magasságú kupacnak legalább (ill. legfeljebb) hány eleme van?

​

​

​

Feladat

​

​

Hol helyezkedhet el a legkisebb elem a maximum-kupacban, ha minden elem különböző?

​

​

​

Feladat

​

​

Maximum-kupac-e a 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 sorozat?

​

​

​

Feladat

​

​

Maximum-kupac-e a 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 sorozat?

​

​

​

Kitekintő

​

​

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - ÚJ ALGORITMUSOK

Link http://www.informatom.hu/sze/01/LGB_SZ001/Cormen-Lieserson-Rivest-Stein.-.Uj.algoritmusok.pdf

​

​

​