Dinamikus adatszerkezetek tutorial

Írta: Olasz Ákos (iLikeBigTits) / B415

Kiegészítette: Csöndes László

Bevezető

Buktál prog 1-ből? :))) Vagy csak végre meg akarod érteni mi fán terem néhány gusztustalan dinamikus adatszerkezet pl. láncolt lista vagy legjobb barátja, a bináris fa? Mert jó ember vagyok:) s mert sztem tul sokan állnak ezek miatt bukásra, gondoltam leírom amit ebből a részből tudni érdemes egy vizsgán.

Egy igengagyi memóriamodell és pointerek

Kezdjük először ezzel, hogy rálátást kapj a memória modelljéről. Ez a továbbiakban sokat fog segíteni a listák megértésében. Képzeld el a memóriát, mint 1 kockás füzet lapját. Számozzunk be sorra minden kockát, és hivatkozzunk rájuk a sorszámuk alapján. Minden változónk amit használunk ebben az indexelt térben van valahol, s elfoglalhat több kockát (bájtot) is. Pl ('char' tipusú változó 1 byte, 'int' általában 4-et, stb.). Memóriához sokféleképpen juthatunk.

Statikus változók

Ezeket a programunk memóriafoglalás nélkül használhatja. Jegyezzük meg: nekik is van memóriacímük.

%CODE{"cpp"}% int a,b; float f; char c; / FONTOS! a pointer is statikus változó, értéke pedig egy memóriacím lehet. Később látni fogjuk. */ %ENDCODE%

S a többi. Ezeket közvetlenül nem a memóriacímük alapján használjuk a programban, hanem csak hivatkozunk rájuk a nevük alapján. Ha a címük kell (hányadik indexű byte-on kezdődnek) akkor használhatjuk az elé írt '&' operátort.

Dinamikus memóriafoglalás, pointerek

Ilyenkor az operációs rendszert kérjük meg arra, hogy adjon egy olyan memóriacímet, amit szabadon használhatunk. Miután memóriát kértünk, az értéket el is tároljuk, ezekre valók a pointerek, amik maguk is statikus változók, memóriacímek tárolására szolgálnak. Méretük 32 bites rendszereken (pl. Windows 98, Linux stb.) 4 byte (mindig ugyanannyi, mint egy 'int' tipus mérete, s hasonló műveleteket végezhetünk velük).

%CODE{"cpp"}% int *a; char *b; %ENDCODE%

Deklarálásukkor még nem mutatnak sehová, vagy érvénytelen helyre.

Ha azonban helyes címet adunk neki, akkor használhatóak: %CODE{"cpp"}% int x; int px = &x; // itt a 'px' az 'x' változó címét veszi fel. Ilyen komment nincs C89-ben, csak / */. Ne használjátok prog1-en!

int *mp = (int *) malloc ( sizeof(int)*5 ); /* itt kértünk egy olyan memóriaterületet, ahol elfér 5 int. Ennek a címét kapjuk vissza. */

int *pp = ∓ / igen, a pointerre mutató pointer... Értéke egy olyan memóriacím, ahol elfér egy pointer. / %ENDCODE%

Látjuk tehát, hogy a pointerek tulajdonképpen számokat tárolnak (memóriacímeket). Lehet használni tehát az 'int'-ekkel használatos műveleteket.

Egész pontosan pointerekhez hozzá lehet adni (vagy kivonni) inteket (vagy intekhez ptr-eket). Összeszorozni vagy összeadni két pointert például már nem lehet (compiler error). Viszont pl. van <, >, == stb.

%CODE{"cpp"}% int x= ... ; mp = mp + x; / FONTOS! az mp-ben tárolt memóriacím nem x-szel fog növekedni, hanem x * sizeof(*mp)-vel, azaz a mutatott típus méretével. /

mp++; / a pointer tipusa int *, tehát az érték sizeof(int)-tel fog növekedni. Hasznos, ha egy dinamikus tömbben a következő elemre akarunk mutatni. */

char d= ... ; d++; / a következő karakterre fog mutatni /

d--; / ugyanez, csak visszafelé */ %ENDCODE%

A pointerek értékeit (mi van azon a címen, amire mutat) az elé írt '*' operátorral kaphatjuk meg.

%CODE{"cpp"}% int a=2006 , b; int *p=&a; // ilyenkor 'p' mutat 'a'-ra int b=(*p); // 'b' = a 'p' által mutatott címen lévő érték (2006). (*p)=26; // a 'p' által mutatott címre beírunk 26-ot. %ENDCODE%

FONTOS! A pointerek tömbként is használhatóak ( a tömbök is memóriacímre mutatnak, konkrétan oda, ahol vannak az elemei tehát ők is pointerek a maguk formájában). Így a fentebb deklarált 'mp' a következőképpen indexelhető: mp[0] ugyanaz, mint *mp vagy (mp-1)[1] (bonyolodik) mutat az első elemre. mp[1] mutat a 2. elemre, ugyanaz, mint *(mp + 1) vagy *(++mp) vagy (mp-1)[2] :) A ++mp-nek van mellékhatása. Ügyelni kell arra, hogy a foglalt memóriatartományok elejére mindig legyen pointer, különben a program memóriát fog szivárogtatni. Egyébként nem érdemes 'kivinni' pointereket memóriaterületekről (mint pl. a (mp-1)[1]), mert a C szabvány nem minden műveletet garantál.

• Megjegyzés*: x86-64-en az int 32 bites, de a pointerek 64 bitesek, ez vidám errorokat

szokott okozni régebbi progrmoknál (itt egyébként épp a long ugyanakkora, mint egy pointer). Garantáltan működő viszont a következő: %CODE{"cpp"}% typedef union { int n; void* p; } int_and_ptr; %ENDCODE%

Mondjuk ilyenre egészen biztosan nem lesz szükségetek még vizsgán sem, de nem árt tudni.

Ennyit a pointerekről és a memóriáról.

Láncolt lista

Mire jó ez? Hát többek között olyan dolgok tárolására, amiből nem tudjuk, hogy mennyit kell eltárolnunk. Máskülönben ha tudnánk, használhatnánk akár sima tömböket is. A továbbiakban mindenhol a következő típusú listát fogjuk használni:

%CODE{"cpp"}% typedef struct _elem { int ertek; struct _elem *kov; } ELEM, pELEM;

pELEM lista, tmp; %ENDCODE%

Ez azt jelenti, hogy a pELEM ugyanaz, mint az ELEM (vagyis egy ELEM-re mutató pointer).

Tehát minden lista->kov tartalmaz egy memóriacímet, ahol a lista következő eleme tárolódik. A lista végén természetesen NULL érték áll.

Láncolt lista bejárása

Egyszerű feladat, nem is foglalkoznék vele sokat.

%CODE{"cpp"}% tmp=lista; while (tmp != NULL) { /* Ide írjuk, amit minden listaelemmel meg szeretnénk csinálni, pl. összeadni az értékeket, vagy összehasonítani őket egy másik értékkel (= keresés); / tmp=tmp->next; // azaz vesszük a következő listaelem címét // és azt használjuk tovább } %ENDCODE%

Műveletek listaelemekkel

Képzeljük el úgy a listát, mintha dobozok lennének az elemei (bagósok kedvéért mondjuk PALL MALL dobozok) és a 'kov' változó egy madzag lenne. Az első doboz ugye a másodikhoz van kötve, a 2. a 3.hoz stb.

Elemcsere

Így látjuk, hogy mondjuk megcserélni annyi két listaelemet, hogy a dobozokat a helyükön hagyjuk, s csupán a madzagokat kötjük át. Természetesen a 2 doboz előtt madzagokat is át kell majd kötnünk, hogy helyes legyen az új sorrend.

	  /-----\	  /-----\			 /-----\	  /-----\
	  |Aprev|---->|  A  |----> ... |Bprev|---->|  B  |----> ...
	  \-----/	  \-----/			 \-----/	  \-----/

A-t és B-t szeretnénk megcserélni. Hát itt van:

%CODE{"cpp"}% Aprev->kov = B; tmp1 = A->kov; A->kov = B->kov; B->kov = tmp1; Bprev->kov = A; %ENDCODE%

Az eredmény:

	  /-----\	  /-----\			 /-----\	  /-----\
	  |Aprev|---->|  B  |----> ... |Bprev|---->|  A  |----> ...
	  \-----/	  \-----/			 \-----/	  \-----/

Listaelem beszúrása (C-t B és A közé)

				/-----\	  /-----\
	... ---->|  A  |---->|  B  |----> ...
				\-----/	  \-----/

Egyszerű: (C az új elem)

%CODE{"cpp"}% A->kov=C; C->kov=B; %ENDCODE%

...és kész.

Listaelem törlése:

Az előző ábrán, kitörölni B-t a következő:

%CODE{"cpp"}%

/ A B-t akarjuk kitörölni. Eltesszük a B utáni elem címét: / ELEM temp=B->kov; /* Most felszabadítjuk a B által foglalt helyet, mert már nincs rá szükség / free(B);

/ És beállítjuk A következő mutatójátt a B utáni elemre */ A->kov=temp; %ENDCODE%

Ilyen egyszerű.

Rendezés

Sokféle képpen végrehajtható, itt egy primitív példa. A módszer, hogy páronként összehasonlítjuk az elemeket, és ha az adott rendezése elv szerint inverzióban állnak, megcseréljük őket. Aztán kezdjük előről az egészet, mindaddig, amíg el nem értük a lista végét úgy, hogy nem kellett cserélni:

%CODE{"cpp"}%

 pELEM rendez(pELEM lista)
 {

pELEM tmp=lista, n=NULL,n1=NULL, prev=NULL;

while ( tmp->kov!=NULL) { // elértük a lista végét? if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere if (prev==NULL) { // ez az elso elem? n1=tmp->kov; // lementjük az egyik végét tmp->kov=tmp->kov->kov; // és cseréljük n1->kov=tmp; lista=n1; /*@@@@ Ez itt nagyon haxos. Én külön változót használnék erre ZH-n.*/ } else { // nem az első elem prev->kov=tmp->kov; // ekkor figyelembe vesszük n1=tmp->kov->kov; // az előző elemet is tmp->kov->kov=tmp; tmp->kov=n1; } prev=NULL; // csere volt, szal kezdjük tmp=lista; // előről az egész vizsgálatot } else { prev=tmp; // nem kell cserélni, így tmp=tmp->kov; // megyünk tovább } } return lista; // visszatérünk a rendezett // lista első elemért mutató // pointerrel

 }

%ENDCODE%

Az algoritmus értelemszerűen kis változtatással átírható csökkenő sorrendre, vagy más tipusu adatok rendezésére.

Jó tanács: Ha elemeket kell rendezni, és nem kifejezetten a rendezés implementálása a feladat akkor próbáljátok meg őket tömbben tárolni és qsort(), vagy ha nem megy, akkor rendezett bináris fában! (ha nincs odaírva, hogy nem lehet könyvtári függvényeket használni, vagy nem lehet qsort-ot használni, akkor lehet).

Ennyit a láncolt listákról.

Fák

Na elérkeztünk az emberek kedvenc témájához. Gondoljuk végig! Egy bináris (de legyen tenáris, kvaternáris vagy kvináris) fa nem más, mint egy olyan láncolt lista, amelyiknek több irányban lehet láncolt következő eleme. Itt is ugyanazon az elvel gondolkodunk, mint a láncolt listánál, ám az algoritmusok bonyolódnak. A fát legtöbbször rekurzívan járjuk be. Miért? Mert szükség van egy olyan módszerre, ami képes arra, hogy egyes pozíciókba vissza tudjon lépni. Például épp serényen járunk be egy fát, amikor rájövünk, hogy vissza kell lépnünk egy szintet. Ekkor jön jól, hogy egy 'return' és máris egy szinttel feljebb vagyunk.

A továbbiakban a fákat a következő típusunak tekintjük.

%CODE{"cpp"}% typedef struct _bifa { int adat; struct _bifa *jobb, *bal; } BIFA, *pBIFA; %ENDCODE%

Fák létrehozása, elemek felvétele

Gyakori feladat (vizsgán, zh-n, máshol ritkán csinál ilyet az ember) hogy vegyünk fel elemeket rendezve egy bináris fába. Hogyan tesszük ezt? A fában ha pl. növekvő sorrendbe szeretnénk az elemeket rakni, akkor egyszerűen bal oldalra rendezzük az aktuális csomóponttól kisebb elemeket, míg jobb oldalra a nagyobbakat.

Elemek felvételére elég egy nemrekurzív függvény is!

Egy példa, számok felvételére szolgáló függvény:

%CODE{"cpp"}%

 // Látjuk, hogy a fára mutató pointer pointere kell, mert ha csak simán a
 // fára mutató pointert adnánk át, akkor arról egy másolatot kapnánk
 // (lévén hogy a pointer is csak 1 statikus változó!)
 // ami értékadáskor nem elég, mert mi az eredeti fát szerenénk

módosítani.

 void felvesz ( pBIFA *bfa, int elem) {

pBIFA fa=*bfa; if (!fa) { // ha üres a fa, akkor felvesszük az első elemét // emiatt kell a BIFA **bfa a fv paraméterlistájában (*bfa)=(pBIFA) malloc (sizeof(BIFA)); (*bfa)->adat=elem; (*bfa)->bal=(*bfa)->jobb=NULL; return; } while ( true ) { // a végetelenségig tudunk menni a fában

if (fa->adat==elem) {return;} // ha az elemet már előzőleg felvettük // kilépünk if (fa->adat > elem) { // ha az új elem kisebb, mint az aktuális // szint eleme

if (fa->bal!=NULL) fa=fa->bal; // ha lehet, elmegyünk balra

else { fa->bal=(pBIFA) malloc (sizeof(BIFA)); fa->bal->adat=elem; fa->bal->bal=fa->bal->jobb=NULL; return; // ha felvettük az elemet, kilépünk } } else // ugyanaz, csak most az uj elem nagyobb, mint az aktuális

if (fa->jobb!=NULL) fa=fa->jobb; else { fa->jobb=(pBIFA) malloc (sizeof(BIFA)); fa->jobb->adat=elem; fa->jobb->jobb=fa->jobb->bal=NULL; return; } }

 }

%ENDCODE%

Kiegészítés: Juj. Hát ilyet tuti nem hoznék össze ZH-n magamtól, respect!

Alternatív fgv:

%CODE{"cpp"}% void felvesz(BIFA* gy, int elem) {

if(gy==NULL) return; /*Nem kell mindig, de szép.*/
if(gy->adat==elem) return; /*Ilyen már van, nem tesszük be még1x.*/
if(gy->adat<elem) /*Az elemünk nagyobb, akkor jobbra kell betenni.*/
{
if(gy->jobb)	  /*Van már jobboldalt valami, rekurzívan elmegyünk oda.*/
{
 felvesz(gy->jobb,elem);
}else{										  /*A jobboldal tök üres.*/
 gy->jobb=(BIFA*)malloc(sizeof(BIFA));/*Csinálunk egy új elemet*/
 gy->jobb->jobb=gy->jobb->bal=NULL;	/*KiNULLázzuk a pointereket*/
 gy->jobb->adat=elem;					  /*Betesszük az adatot*/
 return;										/*Készen vagyunk.*/
}
}else{ /*Az elemünk kisebb, most az előző jön, csak a baloldallal.*/
if(gy->bal)felvesz(gy->bal,elem);
else{
 gy->bal=(BIFA*)malloc(sizeof(BIFA));
 gy->bal->jobb=gy->bal->bal=NULL;
 gy->bal->adat=elem;
 return;
}
} /*Ez a <elem ifnek a vége*/

} %ENDCODE%

ZH-n, vizsgán a rövidített verziót könnyebb leírni:

%CODE{"cpp"}% void felvesz(BIFA* gy, int elem){

if(gy==NULL ||| gy->adat==elem) return; /*A || bal fele ízlés szerint

kihagyható, de ha bent hagyod, biztonságosabb*/

BIFA** a=gy->adat<elem?&gy->jobb:&gy->bal; /*Itt is bejön sajna a duplaptr

hax*/

if(*a)felvesz(*a,elem);else{
*a=(BIFA*)malloc(sizeof(BIFA));
(*a)->bal=(*a)->jobb=NULL;
(*a)->adat=elem;
}

}

%ENDCODE%

Próbáljátok megérteni, nem bemagolni, mert az biztos bukás.

Egyszerű fabejárás, műveletekkel

Tegyük fel, hogy be kell járnunk egy fát, s közben mindenféle dolgot kell tennünk (adatokat összeadni, gyerekeket számolni, funkcionális hazárdokat keresni, vagy biciklizni ).

Erre a rekurzió ad lehetőséget.

Séma a számlálgatós feladatokra

A következő fv megszámolja, hány elemnek van jobb oldali gyermeke!

%CODE{"cpp"}% int gyerekek (pBIFA fa) { int n=0;

if (fa==NULL) return -1; // üres a fa!

if (fa->jobb !=NULL ) { // el lehet menni jobbra

n = n + 1; // a fának van jobb oldali gyereke, így növeljük a // számlálót

n = n + gyerekek(fa->jobb); // megszamoljuk a jobb oldali reszt (n=n+ rövidebb verziója az n+=)

} if (fa->bal !=NULL ) // el lehet menni balra n = n + gyerekek(fa->bal); // megszamoljuk a bal oldali reszt

return n; // visszaterunk az eredmennyel } %ENDCODE%

Mit csináltunk itt? Fontos először is tudnunk, hogy a függvény egyszerre csak az aktuális elemmel törődik, s nem látja annak gyerekeinek gyerekeit. Annyit tud, hogy jobbra és balra el lehet-e menni. Ennyi elég, mert ha egyik irányba el lehet menni, akkor meghívja önmagát azzal az elemmel, ami a kívánt irányban van. Amikor visszatér, az előző függvényhíváshoz tér vissza, s ezzel átadja a lentebb fekvő gyerekek értékeit. Bonyolult.

Erre egy futási példa:

								 (a)
								 / \
							 (b)	(c)
							 /		 \
						 (d)			(e)
							 \
							  (f)

A fenti fv először meghívódik úgy, hogy az (a) pontban vagyunk. Jobb oldalra el is tudunk, tehát növeljük az (a) pontban lévő számlálót (már =1). Meghívjuk a függvényt a jobb oldalra, s most a (c) pontban állunk. Van jobb oldali eleme? Van, növeljük a (c)-beli számlálót. Mivel újra van jobb oldali elem, elmegyünk (e) felé. Mivel itt nincs se jobb, se bal oldali elem, így kilépünk, visszaadunk 0-t (nincs jobb oldali elem!). Ekkor visszaléptünk (c)-be, és az n=n+... sor 0-t ad n-hez, így az marad =1. Ekkor tovább fut a függvény, megnézzük van-e bal oldali elem. Nincs. Ekkor ujra visszatérünk a (c) pontbeli számláló értékével, ami így hozzá adódik az (a) pontbeli számláló értékéhez, ami immáron =2. Most újra az (a) pontban vagyunk, s elmegyünk bal oldali irányba. Látható, hogy itt is ugyanilyen módon fog viselkedni a függvényünk: elmegy egészen (f)-ig, majd visszatér 0-val, innen (d) visszatér 1-el, (b) is visszatér 1-el mert (d) visszatérési értéke hozzáadódott (b) belső számlálójához, majd (b) visszatér ezzel az értékkel, ami hozzáadódik (a) számlálójához, ami így már 3.

Ha fenti bírod követni, akkor nem érted a rekurziót, ülj neki, és ha megvan, akkor gyere vissza. (_Ahhoz hogy megértsd a rekurziót, előbb meg kell értened a rekurziót :D_)

Remélem érthető tehát a bináris fák bejárása. Ha nem a gyerekek számát, hanem mondjuk a fában tárolt adatok összegét kell meghatározni, akkor értelemszerűen azokat kell az n-hez adni, s azzal kell visszatérni. Pl.:

%CODE{"cpp"}% int osszeg (pBIFA fa) { int n; if (fa==NULL) return -1;

n=fa->adat;

if (fa->jobb !=NULL ) n = n + osszeg(fa->jobb); if (fa->bal !=NULL ) n = n + osszeg(fa->bal);

return n; // visszaterunk az eredmennyel } %ENDCODE%

Fa rendezett kiíratása

Jó esetben rendezve vesszük fel az elemeket a fába, így egyszerűen kiírathatjuk őket sorrendben. Hogyan tegyük? Vizsgáljuk meg, hogy a fenti rekurzív függvényünk hogyan működik! Meghívódik egy elemre, majd ha annak van jobb oldali eleme elmegy arra, ha annak van jobb oldali gyereke, akkor megint elmegy arra ....... tehát mindaddig jobbra megy, amíg van arra elem. Ez azt jelenti, hogy ha balról jobbra találhatóak a nagyobb elemek, akkor a fenti függvény pontosan akkor találokzik a legnagyobbal, amikor először nem tud tovább menni jobbra, így érthető, hogy nincs nagyobb elem. Hová tegyük hát a kiíró részt? Csökkenő sorrendben történő kiíratás esetén írassuk ki akkor az elemet, amikor a függvény már bejárta a jobb oldali, nagyobb számokat tartalmazó ágat (mert az aktuális elem értéke mindig kisebb, mint az igy rendezett, töle jobbra lévő elemek!!!) Ezáltal egy elem akkor kerül kiírásra, ha a nála nagyobb elemek már ki lettek írva.

Fontos.

Kezdjük már szeretni a rekúúúrziót ugye?

%CODE{"cpp"}% void kiir(pBIFA fa) { if (fa==NULL) return; if (fa->jobb) kiir(fa->jobb);

printf("%d ",fa->adat);

if (fa->bal) kiir(fa->bal); return; } %ENDCODE%

Általában növekvő sorrendben szokták kérni a kiíratást (=> bal, printf, jobb). Ha megvan a fa==NULL vizsgálat, akkor le lehet spórolni az if(fa->irány)-t.

Máris vége?

Nah asszem ennyi tudással már jól lehet venni a dinamikus memóriás feladatokat. Különös gondot fordítottam arra, hogy az itt hozott példák mind helyesen működjenek, ám így hajnalban már becsúszhattak hibák.

Bukásmentes iv-t mindenkinek! :-)