Programozás alapjai II. (7. ea) C++

Programozás alapjai II. (7. ea) C++ Kiegészítő anyag: speciális adatszerkezetek Szeberényi Imre BME IIT

<[email protected]>

M Ű E GY E T E M 1 7 82 C++ programozási nyelv

© BME-IIT Sz.I.

2016.04.05.

- 1-

Speciális adatszerkezetek • A helyes adatábrázolás választása, a helyes adatszerkezet megtalálása igen fontos tervezési és implementációs kérdés. • Ügyetlen tárolással teljesen tönkretehetjük az amúgy gondos tervezés eredményét is. • Különböző szempontokat kell figyelembe venni: – modell, sebesség, méret

C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 2-

Tömbök • •

Ha a méret és a dimenziószám ismert, nincs gond. Ha a dimenziószám változik, akkor nem oldható meg nyelvi eszközzel – – – –

tárolás sor-, vagy oszlopfolytonosan memóriaterület dinamikus foglalása kiszámítandó az elem címe az indexkifejezés alapján (legutolsó index fut a leggyorsabban) C-ben az index 0-tól n-1-ig megy, de nem minden nyelven van így.


2016.04.05.

- 3-

Tömbök/2 I-1,0,0

i j

I-1,J-1,0

0,0,0

I-1,0,K-1 0,0,K-1

k 0,J-1,K-1

0,J-1,0 M[I][J][K] méretű 3D mátrix[i][j][k] elemének címe= J*K*i+K*j+k+bázis C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 4-

N dimenziós tömb • Legyen Li egy N dimenziós tömb i. dimenziójának minimális indexe, Ui pedig a maximális indexe. A tömb i1, i2, i3, i4, ..in indexű elemének címe: S2*S3*... *Sn*(i1-L1) + S3*...Sn*(i2-L2) + ... + (in-Ln) + bázis • ahol: Si = Ui – Li + 1


2016.04.05.

- 5-

Nagyméretű ritka tömbök • Nagyméretű ritka (sok azonos elem) mátrixok tárolásánál fontos lehet a helytakarékos megoldás. • Ha a nem nulla elemek száma ismert, akkor statikus táblákkal viszonylag egyszerű a megoldás • Az adat mellett tároljuk a sor- és oszlopindexet is.


2016.04.05.

- 6-

Nagyméretű ritka tömbök/2 0

1 12

2

3 14

4

0 1 2 26 40 3 4 17 31 5 9 85

Sor: Érték:

4 0 2 5 17 12 26 9 0 1 2 3


OszlElső: 0

1

4

4 0 2 5 31 14 40 85 4 5 6 7

8

5

7

2016.04.05.

8

- 7-

Nagyméretű ritka tömbök/3 0 0 1 2 3 4 17 5

1 12

2

26

3 14

4

OszlElso:

40

Sor: 4 Ertek: 17

31 9

0

1

0 2 5 12 26 9

4

5

7

8

4 0 2 6 31 14 40 85

85

int elem(int i, int j) { // pl: 2,3 for (k = OszlElso[j]; k < OszlElso[j+1]; k++) if (Sor[k] == i) return(Ertek[k]); return(0); } C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 8-

Nagyméretű ritka tömb listával • Statikus tábla helyett körkörösen láncolt ortogonális lista. (fésű) • Minden listaelemben tárolni kell az elem indexét, és az adatot. • A nulla, vagy más ismétlődő adatot nem tároljuk. • Minden sorhoz és oszlophoz van egy fej (strázsa), amit a speciális index jelöl.


2016.04.05.

- 9-

Nagyméretű tömb ortogonális listával 0 0

0 1

1 0

1 1 8

0 3

0 4

2 3 9

2 0 3 0

0 2

3 1 4


2016.04.05.

- 10 -

Sorok és vermek • Sor: FIFO (First-In-First-Out) • Verem: LIFO (Last-In-First-Out) Ez a k ép most nem jeleníthető meg.

– megvalósítás tömbbel, vagy listával


2016.04.05.

- 11 -

Sorok felhasználása • Természetes eszköz a várakozó sorok megvalósításához. • Természetes eszköz a puffereléshez (termelő-fogyasztó sebességkülönbség kiegyenlítése)


2016.04.05.

- 12 -

Verem felhasználása • Viselkedés miatt (dinamikusan növekszik ill. csökken, LIFO) • Tipikus megvalósítása az eljáráshívásnak és a paraméterátadásnak. • Rekurzió megvalósításának segédeszköze. • Lokális változók tárolása. • Postfix kifejezések kiértékelése. • Visszalépéses (backtrack) algoritmusok segédeszköze. C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 13 -

Hash függvény • Egy fix hosszúságú kivonatot készít, ami jellemző az adatra. h = H(z). • tulajdonságai: – egyirányú – h-hoz nehéz találni olyan z ≠ z'-t amire h=H(z') – H-hoz nehéz találni olyan z ≠ z'-t amire H(z)=H(z')

• Felhasználása: Index leképezése egy véges tartományra. (pl. indexelés stringgel) C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 14 -

Hash tábla • Olyan tároló, amelyben hash függvény segítségével tárolunk. • A tárolás alapját képező kulcsot (sokszor magát a tárolandó adatot) hash függvény segítségével kivonatoljuk. Az így kapott érték alapján tárolunk, de felkészülünk az esetleges ütközésekre is. • Példa H-ra:


2016.04.05.

- 15 -

Hash tábla/2 z

Ht:

H

ütközés


2016.04.05.

- 16 -

Hash ütközések feloldása • A bemutatott megoldás logikus lenne, de nem ez a szokásos. • A táblában keresnek egy újabb szabad helyet. Pl. lineáris kereséssel próbálnak a következő elemekből választani. – Hátrány, hogy csoportok alakulnak ki (clustering) – Ezért gyakoribb a többszörös hash használata


2016.04.05.

- 17 -

Lineráis kereséssel int Proba(int s, Key k) { int i = s; do { if (Ht[i] == k) return(i); i = (i + 1) % m; } while (i != s); return(-1); }

Spec. kulcs


int Tarol(Key k) { int h = Hash(k); int i = Proba(h, Ures); if (i < 0) return(0); Ht[i] = k; return(1); } Key Keres(Key k) { int h = Hash(k); int i = Proba(h, k); if (i < 0) return(Ures); return(Ht[i]); } 2016.04.05.

- 18 -

Többszörös hash • A Proba ciklusában d=+1 helyett d = Hash2-t használunk. • Pl: Hash2-ben a θ helyett 1-θ-t használunk. int Proba(int s, Key k) { int i = s; int d = Hash2(k); do { if (Ht[i] == k) return(i); i = (i + d) % m; } while (i != s); return(-1); }


2016.04.05.

- 19 -

Listák • • • • • •

Egyszeresen láncolt Többszörösen láncolt Körkörösen láncolt Rendezett Rendezetlen Fésűs (ortogonális)


2016.04.05.

- 20 -

Duplán láncolt adatszerkezet

KEZD1

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

NULL ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

NIL KEZD2 C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 21 -

Fésűs lista TK KOVTK KOVH NEV,ATL KOVH

TK KOVTK KOVH ????? KOVH

????? KOVH


TK KOVTK KOVH

????? KOVTK KOVH

NEV,ATL KOVH ????? KOVH 2016.04.05.

- 22 -

Fa szerkezetek • Bináris fa k

– Rendezett, 1 db kulcs 2 pointer

• Halom (kupac) – speciális bináris fa – tömbbel is szokás ábrázolni

• N-fa – – – –

N-1 db kulcs, N db pointer ha k < k1 -> p0 ha ki < k < ki+1 -> pi ha kn-1 < k -> pn-1


k1, k2, k3 p0 p1

p2

2016.04.05.

p3

- 23 -

Bináris fa bejárása ism. Ha a fa_nem_üres Akkor kiírjuk_a_bal_részfát kiírjuk_az_elemet kiírjuk_a_jobb_részfát Vege

15 20

6

3 2


31 5

22

2016.04.05.

91

- 24 -

Kupac (heap) ai <= a2i ha i < n/2 ai <= a2i+1 ha i < n/2

a1 a2 a4 a8

a3 a5

a6

a7

a9


2016.04.05.

- 25 -

Süllyeszt ai <= a2i ha i < n/2 ai <= a2i+1 ha i < n/2

a1=10 a2=8 a4 =19 a8 =88

a5 =15 a9 =35


a3 =11 a6 =12

a7 =18

A kisebb ágon haladunk, addig, amíg cserélni tudunk. 2016.04.05.

- 26 -

Rendezés algoritmusa • Készítsünk kupacot – a tetején lesz a legkisebb elem

• Levesszük a legfelsőt és elsüllyesztjük a ∞-t, így újból kupachoz jutunk aminek a tetején a ismét legkisebb elem van.


2016.04.05.

- 27 -

Kérdések • Hogyan készítünk kupacot ? – an/2+1 ... an biztosan kupac, ezért ebben elsüllyesztjük az an/2-t, majd az an/2-1-t, és így tovább.

• Hogyan ábrázoljuk ? – tömbben: elem index = tömb index 1 2 3 4 5 6 7


2016.04.05.

- 28 -

Kérdések (2) • Mit használjunk ∞ helyett? – Legyen ez a tömb legutolsó eleme! Ezzel kicseréljük a legelső elemet így a kupac mérete eggyel csökken, ugyanakkor a maradék továbbra is kupacot alkot. csere legkisebb

maradék kupac C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 29 -

B-tree • B-fa (B-tree) – kiegyensúlyozott – olyan N-fa, amelynek minden csomópontjából legalább N/2 és legfeljebb N ág indul. (gyökér kivételével) – kulcsok száma: k = n-1

k1, k2, k3 p0 p1

p2

p3

• C példa: http://www.iit.bme.hu/~szebi/prog2/bfa.c


2016.04.05.

- 30 -

B-tree példa (N=5) 55

ide jönne, de elérte a maximális számot (N=5-höz max. 4 kulcs tartozik)

20

10,12


30,35,40,50 55

2016.04.05.

- 31 -

B-tree példa/2 új kulcs jött fel kettéhasadt

20, 40

10,12

30,35

50, 55

A levelek azonos szinten maradtak. C++ programozási nyelv © BME-IIT Sz.I.

2016.04.05.

- 32 -

Programozás alapjai II. (7. ea) C++

Recommend Documents