Adatszerkezetek és algoritmusok Gyakorlati segédlet gazdasági informatikusok részére
Készítette: Szeghalmy Szilvia
Tartalomjegyzék 1. Bevezetés ........................................................................................................................... 3 2. Rövid összefoglaló a C nyelv elemeiről .............................................................................. 3 2.1. Típusok......................................................................................................................... 3 2.2. Konstans ...................................................................................................................... 4 2.3. Nevesített konstans ..................................................................................................... 4 2.4. Változók ....................................................................................................................... 5 2.5. Értékadó utasítás ......................................................................................................... 5 2.6. Kifejezés ....................................................................................................................... 5 2.7. Elágaztató utasítás....................................................................................................... 6 2.8. Ciklusszervező utasítások ............................................................................................ 6 2.9. Vezérlő utasítások ....................................................................................................... 7 2.10. Beolvasás és kiíratás ................................................................................................ 7 3. Adatszerkezetek ................................................................................................................. 9 3.1. Tömb, mátrix ............................................................................................................... 9 3.2. Halmaz ....................................................................................................................... 11 3.3. Multihalmaz ............................................................................................................... 13 3.4. Ritkamátrix ................................................................................................................ 14 3.5. Sor .............................................................................................................................. 16 3.6. Verem ........................................................................................................................ 18 3.7. Egyirányban láncolt lista............................................................................................ 19 3.8. Kétirányban láncolt lista ............................................................................................ 21 3.1. Bináris fa .................................................................................................................... 24 3.2. Bináris kereső fa ........................................................................................................ 24 3.3. Általános fa ................................................................................................................ 24 3.4. Gráf ............................................................................................................................ 24 4. Feladatok és megoldásaik ................................................................................................ 27 4.1. Témakör: Változók, Típusok, Konstans...................................................................... 27 4.2. Témakör: Kifejezés .................................................................................................... 28 4.3. Témakör: Elágaztató utasítás .................................................................................... 29 4.4. Témakör: Ciklusszervező utasítások.......................................................................... 31 4.5. Témakör: Tömb, mátrix ............................................................................................. 32 4.6. Témakör: halmaz, multihalmaz ................................................................................. 33 4.7. Témakör: Ritkamátrix ................................................................................................ 34 5. Gyakorló feladatok megoldások nélkül ............................................................................ 35
1.
Bevezetés
Jelen anyag célja az otthoni gyakorlás elősegítése. A jegyzet nem lektorált, tehát hibákat tartalmazhat, és minden bizonnyal tartalmaz is. Használata tehát csak kellő körültekintéssel javasolt! A hibákat a
[email protected] címre lehet jelezni. A jegyzet első része a C nyelv bemutatására szolgál, olyan mértékben, amennyire azt a gyakorlati anyag megköveteli. A jegyzet másik részében az órai anyaghoz kapcsolódó feladatok találhatók megoldásokkal együtt. Egy harmadik részben pedig további ötletek vannak gyakorláshoz. A jegyzetben használt jelölések Szintaktikai leírásban szereplő jelölések: | alternatíva (vagy ez, vagy az) a|b [] a []-ben lévő rész opcionális (nem kötelező) *+… a zárójelben lévő elem tetszőleges számú A programozási eszközök ismertetésénél a felső sorban az általános eset szerepel, alatta pedig egy konkrét példa. típus változónév; int x;
Egyéb jelölések … tetszőleges kódrészletet jelöl a forráskódban … // leírás …
2.
a három sor helyére a leírásnak megfelelő kódot kell írni
Rövid összefoglaló a C nyelv elemeiről
Ez a rész a C nyelv eszközeit tárgyalja a teljesség igénye nélkül. A gyakorlatok során gyakran használt programozási eszközök kerülnek bemutatásra.
2.1. Típusok A típusokat tartományukkal, műveleteikkel, és reprezentációjukkal adjuk meg. Számunkra ebből az első kettő lesz lényeges.
aritmetikai típusok: Típus int float double char
Tartomány egész számok valós számok dupla pontos valós számok karakterek[0-255] – ASCII kód
Műveletek aritmetikai, logikai aritmetikai, logikai aritmetikai, logikai aritmetikai, logikai
származtatott típusok: tömb, függvény, mutató, struktúra Típusok közti átjárás: Az aritmetikai típusok közül vannak olyanok, melyeknél az egyik típus magába foglalja a másikat. Ilyen például a double - float, vagy a double - int, float - int, int - char, stb. párosítás. A bővebb tartomány irányában szabadon mozoghatunk, információ veszteség nélkül. Egy egész értéket információveszteség nélkül lehet egy valós típusú változóban tárolni. Fordított helyzetben viszont a valós szám egész része kerül csak tárolásra. A 3.8 egészként tárolva 3 lesz. Tehát nem kerekítés, hanem vágás történik. Az aritmetikai műveleteknél, ha a két operandus típusa eltérő, a művelet elvégzése előtt, a bővebb tartomány irányába konvertálódik a másik operandus értéke.
2.2. Konstans A konstansok érték és típus részből állnak. A konstansok értékét az alakjuk definiálja. Az adott típusú konstans, a típus tartományából veheti fel az értékét. Példák: 2 2.4 2.4f ’k’ ”alma”
//int típusú konstans //double típusú konstans //float típusú konstans //karakter típusú konstans //konstans karakterlánc
2.3. Nevesített konstans Olyan konstans, amely névvel ellátott, és ezzel a névvel tudunk hivatkozni az értéké re a program szövegében. const típus változónév = kezdőérték; const int N = 4;
C-ben jellemző, hogy makrót használunk a konstans definiálására. Ezt a program elején a main függvényen kívül tehetjük meg. #define MIT MIRE
4
Eredményeként a program szövegében előforduló MIT karaktersorozat minden előfordulását MIRE karaktersorozatra cseréli az előfordító. A példában N minden előfordulása 4-re cserélő.
2.4. Változók A változóknak van értéke, attribútumai (számunkra ez a típus), címe, és neve. A név betűvel kezdődik, és betűvel vagy számjeggyel folytatódhat. A C-ben betűnek számítanak az angol abc kis és nagybetűi, és a _, $ jelek. A változóra a nevével hivatkozhatunk a program szövegében. A cím az a memóriaterület, amelyen a változó értéke elhelyezkedik. Az érték pedig a változó típusához tartozó tartomány egy eleme. típus változónév[=kezdőérték][, változónév2 [= kezdőérték2]]… char c; //c nevű karakter típusú változó int x, y=6; //x és y egész típusú változók int t[5] //t nevű 5 elemű egészekből álló tömb létrehozása
2.5. Értékadó utasítás Változó = kifejezés; A bal oldalon mindig változó áll, a jobb oldalon tetszőleges kifejezés állhat. Az értékadás során a kifejezés kiértékelődik (értéke meghatározásra kerül), és ez az érték kerül a baloldali változóba. int x = x = z =
x, y=3, z, k; 5; y+5*(2+5); k = 5;
//x új értéke 5 lesz. //x új értéke 38 lesz //k értéke 5 lesz, z értéke szintén z = (k=5)
2.6. Kifejezés A kifejezések operandusokból, és operátorokból, valamint zárójelekből épülnek fel. Az operandus lehet konstans, nevesített konstans, változó, vagy függvényhívás. Operátorok A C egyszerűsített precedencia táblázata a következő: ( ) [] → ! ++ -← * / % → + → < > <= >= → == != → && → || → = += -= *= /= %= ←
5
A táblázat felső sorában lévő műveleti jelek kötnek legerősebben (vagyis a kiértékelés során ezek hajtódnak végre először), és soronként gyengülnek. Az azonos sorban lévő operátorok kiértékelése a nyíl által mutatott sorrendben történik. () [] ! ++ --
Precedencia felülírása (matematikában megszokott zárójelezés) és függvényhívás jele Tömb operátor. Logikai operátor: tagadás. Növeli, illetve csökkenti az operandus értékét. Kifejezésben a prefix és postfix alak mást eredményezhet. k = i++; //jelentése: k=i; majd i=i+1; k = ++i;//jelentése: i=i+1; majd k=i;
* / + - Matematikában megszokott jelentéssel. % Maradékos osztás. Negatív számokra ne használjuk. < > <= >= == != Hasonlító operátorok. Jelentésük rendre: kisebb, nagyobb, kisebb egyenlő, nagyobb egyenlő, egyenlő, nem egyenlő. A hasonlító operátorok a op b értéke 1, ha a op b teljesül, különben 0. Ahol op valamelyik fenti jel. && || Logikai és illetve vagy operátorok. Rövidzár: csak addig értékeli ki a kifejezést, amíg el nem dől, hogy 0, vagy 1 az érték. = += -= *= /= %= Értékadó operátorok. Az értékadás bal oldalán változónak kell szerepelni. Jobb oldalon tetszőleges kifejezés állhat. Az x op= y művelet jelentése azonos az x = x op (y) kifejezéssel, ahol op az egyenlőségjel előtt álló jelek egyike.
2.7. Elágaztató utasítás if (kif) utasitas1; [else utasitas2;]
Kiértékelődik a kif kifejezés, ha az értéke nullától eltérő, akkor lefut az utasítás1, különben, ha van else ág, akkor lefut az utasítás2.
2.8. Ciklusszervező utasítások Elöltesztelő ciklus: while(kif) utasitas;
6
Működése: kiértékelődik a kif kifejezés, ha nullától eltérő, akkor lefutnak a ciklus belsejében lévő utasítások(ciklusmag). Ez a két lépés addig ismétlődik, amíg a kifejezés értéke eltér nullától. Hátultesztelő ciklus: do utasitas; while(kif);
Hasonló az előzőhöz, viszont itt a ciklusmag első körben mindig lefut, és csak utána jön a kifejezés kiértékelése. Összetett ciklus: for([kif1]; [kif2]; [kif3]) utasitas;
Működése: 1. lépés: A kif1, ha meg van adva, egyetlen egyszer értékelődik ki, amikor program végrehajtása a ciklusfejet eléri. Általában a ciklusváltozó kezdőértékének beállítására használatos. 2. lépés: A kif2, az ismétlődésre vonatkozó feltétel. Ez fut le másodszor. Ha a kif2 értéke nullától eltérő lefut a ciklusmag, és utána lefut a kif3, ami általában egy léptető utasítás. A második lépés ismétlődik, amíg a feltétel nullától eltérő.
2.9. Vezérlő utasítások continue;
A ciklus belsejében kiadva átugorja a ciklusmagban lévő további sorokat, és a feltétel vizsgálattól folytatódik a program. break;
Ciklus belsejében kiadva kilép a ciklusból. return;
Alprogrambol való kilépésre szolgál. Alprogramról később.
2.10.
Beolvasás és kiíratás
A IO műveletek nem képezik a C nyelv részét. De rendelkezésre állnak előre megírt függvények. Ezek közül órán a scanf, és printf függvények kerülnek elő. scanf(formátum_sztring [,valtozo]…); printf(formátum_sztring [,valtozo]…);
7
A formátum sztring, attól függ, milyen típusú, és hány változót kell bekérni illetve kiíratni. int x, z; float y; char karakter; scanf(”%d”, &x); //1 egész szám beolvasása x változóba scanf(”%d%d”, &x, &z); //1-1 egész szám beolvasása x-be és z-be scanf(”%f”, &y); //valós szám beolvasása y-ba scanf(”%c”, &karakter); //1 karakter beolvasása a karakter változóba printf(”%d”, x); //x értékének kiíratása printf(”%d %f”, x, y); //egy valós és egy egész szám kiíratása szóközzel printf(”%f”, y); //valós szám kiíratása printf(”%c”, karakter); //karakter kiíratása printf(”Ezt a szöveget írja ki és x értékét%d”, x);
8
3.
Adatszerkezetek
3.1. Tömb, mátrix Létrehozás Meg kell adni az elemek típusát, a tömb nevét, és minden dimenzióhoz az elemszámot. Egy N dimenziós tömb létrehozása általánosan, ahol az elemszám helyén ko nstans, és nevesített konstans állhat. (A félkövér zárójelben lévő rész elhagyható, a többi *+ itt a szintaktika része!) típus név[elemszám1][elemszám2]…[elemszámN][=kezdőérték] Példák: 5 elemű, t nevű, valós számokból álló 1D-s tömb létrehozása: float t[5];
2 elemű z nevű egészekből álló 1D-s tömb 2, 5, 7 kezdőértékkel: int z[3]={2, 5, 7}; int z[]={2, 5, 7}; //ennél a megoldásnál az elemszámot a fordító „beírja”
2x3-es m nevű egészekből álló 2D-s tömb: int m[2][3];
10x15x30-as 3 dimenziós egészekből álló tömb létrehozása: int tomb3D[10][15][30];
Megj.: C-ben a több dimenziós tömb olyan 1 dimenziós tömb, melynek minden eleme 1 dimenziós tömb. Elérés A tömb elemeinek elérése dimenziónként egy indexszel történik. Az index minden indextartomány esetén *0, Elemszám-1+ zárt intervallumba esik. A fenti t tömb első, második, harmadik, negyedik, és ötödik elemének elérése rendre: t[0], t[1], t[2], t[3], t[4]
A fenti z tömb 5-ös értékű elemének elérése: z[1]
Az m mátrix első sorában lévő elemeinek elérése: m[0][0], m[0][1], m[0][2]
Az m mátrix második sorában lévő elemeinek elérése: m[1][0], m[1][1], m[1][2]
Bejárás A tömb minden elemét fel kell dolgozni. A bejárás jellemzően for ciklussal történik, ahol a ciklusváltozó az aktuális elem indexeként szerepel. A fenti t tömb bejárása: int i; for(i = 0; i<5; ++i) t[i];//az elem feldolgozása feladatfüggő. Itt semmi sem történik vele.
A fenti m mátrix bejárása sorfolytonos módon (ez azt jelenti, hogy az egy sorban lévő elemek egymás után kerülnek feldolgozásra): int i, j; for(i = 0; i<2; ++i) for(j = 0; j<3; ++j) //az oszlop index változik gyorsabban m[i][j];
A fenti m mátrix bejárása oszlopfolytonos módon (ez azt jelenti, hogy az egy oszlopban lévő elemek egymás után kerülnek feldolgozásra): int i, j; for(j = 0; j<3; ++j) for(i = 0; i<2; ++i) //a sor indexe változik gyorsabban m[i][j];
Keresések 1d-s tömbben Az algoritmusok működését lásd: http://shrek.unideb.hu/~pech/asz/Keresesek.pptx Teljes keresés Legyen adva egy N elemű t tömb és legyen K a keresett elem. A függvény a keresett elem indexével tér vissza, ha az szerepel a tömbben, különben -1-el. int keres(int t[],int N, int K){ int i; for( i = 0; i
Lineáris keresés Legyen adva egy N elemű t rendezett tömb és legyen K a keresett elem. A függvény a keresett elem indexével tér vissza, ha az szerepel a tömbben, különben -1-el. Tf.: növekvő rendezettség áll fenn. int keres(int t[],int N, int K){ int i; for( i = 0; i
Bináris keresés Legyen adva egy N elemű t rendezett tömb és legyen K a keresett elem. A függvény a keresett elem indexével tér vissza, ha az szerepel a tömbben, különben -1-el. Tf.: növekvő rendezettség áll fenn. int keres(int t[],int N, int K){ int ah = 0, fh = N, k = (ah+fh)/2; for( ;ah<=fh; k = (ah+fh)/2){ if(t[k] == K) return k;
10
if(t[k]< K) ah = k+1; else fh = k-1; } return -1; }
3.2. Halmaz A matematikai halmazfogalom megjelenítése adatszerkezet szintjén. Homogén és véges. Ábrázolása általában folytonosan történik a karakterisztikus függvény megadásával. Ehhez definiálni kell egy alaphalmazt, rögzített elemsorrenddel. A halmaz elemeit az alaphalmaz elemeinek számával egyező hosszúságú 0-1 sorozat adja meg. A sorozatban 0 jelzi, hogy az alaphalmaz azonos pozícióján lévő elem nincs a halmazban, 1 hogy benne van. A továbbiakban az alaphalmaz az első N nemnegatív egész szám, növekvő sorrend szerint rögzítve. Ekkor a halmazban a [0, N-1+ zárt intervallumbeli értékek szerepelhetnek. Az érthetőség kedvéjért a műveletek egészeket tartalmazó tömbbel kerülnek bemutatásra, a valóságban azonban 1 elem tárolására 1 bitet szokás használni. Ez a megoldás, azért kényelmes, mert minden halmazelem, a tárolásra használt tömb azonos indexével esik egybe, tehát ha a halmazban egy x elem szerepel, akkor a tömb x. eleme 1-es értékű lesz, különben 0. Megj.: Amennyiben a halmaz lehetséges elemei nem felelnek meg ennek a követelménynek, akkor adjunk meg kölcsönösen egyértelmű leképezést az alaphalmaz, és a [0, N-1] intervallum közt.
Létrehozás Pl.: Legyen a tárolandó halmaz ,1, 4, 2, 5-, és N = 10. //A tárolandó halmazelemek értékével azonos indexen áll 1-es, különben 0 int halmaz[] = {0,1,1,0,1,1,0,0,0,0};
A halmazműveletek tárgyalása előtt lássunk két alapvető utasítást. Tf.: x lehetséges halmazelem. (Az alaphalmaz része.) Egy halmaz x elemmel való bővítéséhez, az tömb x. elemét kell 1-re állítani. halmaz[x] = 1;
Az x elem törléséhez pedig a tömb x. elemét 0-ra kell állítani. halmaz[x] = 0;
Eleme Az alábbi függvény 1-et ad vissza, ha x eleme a halmaznak, különben 0-át. int eleme(int halmaz[N], int x){ //azt is le kell ellenőrizni, hogy x beleesik-e a [0, N-1]-be!
11
return x>=0 && x
Unió Két halmaz uniója a karakterisztikus függvényük közti (logikai) vagy művelettel számítható. Tf. hogy N>=M: int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0; for(i = 0; i<M; ++i) eredmeny[i] = halmaz[i] || halmaz2[i]; for( ; i
Metszet Tf. hogy N>=M: Két halmaz metszete a karakterisztikus függvényük közti (logikai) és művelettel számítható. int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0; for(i = 0; i<M; ++i) eredmeny[i] = halmaz[i] && halmaz2[i]; for( ; i
Különbség Tf. hogy N>=M. Halmaz-halmaz2 az alábbi függvénnyel írható le: int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0; for(i = 0; i<M; ++i) eredmeny[i] = halmaz[i] && !halmaz2[i]; for( ; i
Komplementer A halmaz komplementere a halmaz karakterisztikus függvényének bitenkénti negálásával valósítható meg. int halmaz(int halmaz[N]){ int i = 0; for(i = 0; i
12
3.3. Multihalmaz Ábrázolása a halmazéhoz hasonló. A multihalmaz elemeit az alaphalmaz elemeinek számával egyező hosszúságú egész szám sorozat adja meg. Egy adott pozíción szereplő érték azt adja meg, hogy az elem hányszor szerepel a halmazban. A műveleteknek sajnálatos módon többféle definíciójuk is létezik. Létrehozás Pl.: Legyen a tárolandó multihalmaz ,1, 1, 4, 2, 5, 5, 5, 5-, és N = 10. //A tárolandó halmazelemek értékével azonos indexen áll 1-es, különben 0 int halmaz[] = {0,2,1,0,1,4,0,0,0,0};
A multihalmaz műveleteinek tárgyalása előtt lássunk két alapvető utasítást. Tf.: x lehetséges halmazelem. (Az alaphalmaz része.) Egy multihalmaz x elemmel való bővítéséhez, az tömb x. elemét kell 1-el növelni. ++halmaz[x];
Az x elem törléséhez pedig a tömb x. elemét 1-el csökkenteni, ha x eleme a halmaznak. if(halmaz[x]>0) --halmaz[x];
Eleme Az alábbi függvény 1-et ad vissza, ha x eleme a halmaznak, különben 0-át. int eleme(int halmaz[N], int x){ //azt is le kell ellenőrizni, hogy x beleesik-e a [0, N-1]-be! return x>=0 && x
Unió Két halmaz uniója a karakterisztikus függvényük közti összeadás művelettel számítható. Tf. hogy N>=M: int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0; for(i = 0; i<M; ++i) eredmeny[i] = halmaz[i] + halmaz2[i]; for( ; i
Megj.: Más definíció szerint halmaz[i] + halmaz2[i] helyett: max(halmaz[i], halmaz2[i]) szerepel. Metszet Tf. hogy N>=M: Két halmaz metszete a karakterisztikus függvényük közti min művelettel számítható. int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0;
13
for(i = 0; i<M; ++i) eredmeny[i] = min(halmaz[i],halmaz2[i]); for( ; i
Különbség Tf. hogy N>=M. Halmaz-halmaz2 az alábbi függvénnyel írható le: int halmaz(int halmaz[N], int halmaz2[M], int eredmeny[N]){ int i = 0; for(i = 0; i<M; ++i){ eredmeny[i] = halmaz[i] - halmaz2[i]; if(eredmeny[i]<0) eredmeny[i] = 0; } for( ; i
3.4. Ritkamátrix Olyan mátrix melyben egy elem nagyságrendekkel többször szerepel, mint a többi. Ezt az elemet gyakori elemnek nevezzük. A gyakori elem általában a 0. A cél az elemek helytakarékosabb módon való tárolása. Háromsoros reprezentáció NxM-es mátrix háromsoros reprezentációja 3db K elemű vektorral történik (Sor, Oszlop, Érték), ahol K a nem gyakori elemek darabszáma. A mátrix (sor v. oszlopfolytonos) bejárása közben talált nemgyakori elemek sora, oszlopa, és értéke a Sor, Oszlop és Érték vektor következő szabad helyére kerül bejegyzésre. Legyen a kiinduló mátrix:
Sor Oszlop
0 2
0 3
1 0
1 2
1 4
2 0
2 2
Érték
2
1
2
1
5
1
4
Négysoros reprezentációnál az alapmátrix kiegészül egy mutató vektorral, mely (sorfolytonos esetben) az alapmátrixban azonos oszlopban lévő elemeket láncolja össze, ezzel elősegítve az elemek oszlopfolytonos feldolgozását. 14
Sor Oszlop Érték
0 2 2
Mutató 3
0 3 1
1 0 2
1 2 1
1 4 5
2 0 1
2 2 4
-1
5
6
-1
-1
-1
Felépítése (sorfolytonos) A gy a gyakori elem. K a nem gyakori elemek száma. void felepit(int t[N][M], int sor[K], int oszlop[K], int ertek[K], int mutato[K], int gy){ //3 soros int i, j, p = 0; for(i = 0; i
Elem elérése A gy a gyakori elem. Az alapmátrix s. sorának, és o. oszlopban lévő elem értékét adja vissza. void eler(int sor[K], int oszlop[K], ertek[K], int s, int o){ for(int i=0; i
Sorfolytonos leképezés esetén sor, oszlopfolytonos esetén oszlop szerinti lineáris keresés is elegendő teljes keresés helyett: i
15
3.5. Sor put(érték) get()
beteszi az értéket a sor végére kivesz egy értéke a sor elejéről
Az elemek a bekerülés sorrendjével egyező sorrendben kerülnek ki a sorból. Folytonos tárolás esetén, a sor elemei tömbben kerülnek tárolásra. Ez azt jelenti, hogy bár a sor dinamikus adatszerkezet, valójában a tömb előre rögzített mérete behatárolja a sor elemszámát. Fix sor A sor első eleme mindig a tömb első helyén van. Get műveletnél minden elem egyel előrébb kerül. const int N = 50; //A példában legfeljebb 50 elem lehet a sorban. int sor[N]; //a sor elemeinek tárolására. // fix sornál csak a vég mutatót szükséges tárolni int v=-1; int get(){ int i, tmp = sor[0]; if (v == -1) printf(”Nincs elem a sorban!”); else{ //a törlés eggyel balra csúsztatja az elemeket for(i = 0; i< v; ++i) sor[i] = sor[i+1]; --v; } return tmp; } void put(int x){ if(v+1 == N) printf(”A sor megtelt!”); else sor[++v] = x; }
Vándorló sor Sem a sor eleje, sem a vége nincs rögzítve a tömbben. Get műveletnél az sor elejét jelző mutató értéke növekszik egyel, elemmozgatás nem történik. Put műveletnél a sor végére kerül be az elem. Ha ott már nincs hely, akkor a sor összes elemét balra visszük annyival, hogy a sor eleje a tömb elejére(tömb 0. pozíciójára) kerüljön, majd ez után kerül az elem beszúrásra. int sor[N];
16
//a sor elemeinek tárolására
// vándorló sornál eleje, és vége mutatót is szükséges használni. int e =0, v=-1; //a törlés nem csúsztatja az elemeket int get(){ int i; if (v == e-1){ printf("Hiba: a sor üres!\n"); return -1; } ++e; return sor[e-1]; } void put(int x){ int i; if(e == 0 && (v+1) == N){ printf("Hiba: a sor megtelt!\n"); return; } //a beszúrás csúsztatja vissza az elemeket a tömb elejére, //ha már nincs hely a tömb végén else if( v+1 == N){ for(i = e; i< N; ++i) sor[i-e] = sor[i]; v -= e; e = 0; } sor[++v] = x; }
Ciklikus sor Sem a sor eleje, sem a vége nincs rögzítve a tömbben. Get műveletnél a sor elejét jelző mutató értéke egyel nő, put műveletnél a végét jelző mutató nő egyel (modulo maximális elemszám). A modulo biztosítja, hogy a mutató ne menjen az indexhatáron kívülre. Eredményeként, ha a valamelyik mutató eléri a tömb végét, akkor 0-tól fog tovább növekedni. int sor[N]; //a sor elemeinek tárolására //ciklikus sornál eleje, és vége mutatót is szükséges használni. int e =0, v=-1; //a törlés nem csúsztatja az elemeket int get(){ int tmp; if ((v==-1) || (v==e)){ printf("Hiba: a sor üres!\n"); return -1; } tmp = sor[e]; e=++e%N; return tmp; }
17
//és a beszúrás sem csúsztat void put(int x){ if((e == 0 && v+1==N) || (v!=-1 && v+1 == e)){ printf("Hiba: a sor megtelt!\n"); return; } v = ++v%N; sor[v] = x;
Legyen a sor 5 elemű tömbben tárolva, valamint legyen adott x=2, és y=3 egész típusú változók. A műveletek az alábbi változásokat okozzák a sorban. A sor vége félkövérrel jelölve, a sor eleje piros színnel. Művelet x, y értéke Fix sor Vándorló sor Ciklikus sor put(3) 2, 3 3_ _ __ 3_ _ __ 3_ _ __ put(5) 2, 3 35___ 35___ 35___ put(2+x) 2, 3 354__ 354__ 354__ x = get() 3, 3 54___ _54__ _54__ get() 3, 3 4_ _ __ _ _ 4__ _ _ 4__ get() 3, 3 _ _ _ __ _ _ _ __ _ _ _ __ put(1) 3, 3 1_ _ __ _ _ _ 1_ _ _ _ 1_ put(y-3) 3, 3 10___ ___10 ___10 put(x*y) 3, 3 109__ 1 0 9 _ _ 9__10 (vándorolt) put(2) 3, 3 1092_ 1092_ 92_10 put(get()+2) z=get() 3, 3 092__ _092_ 92__0 put(z+2) 0923_ _0923 923_0 y = get() 3, 0 923__ __923 923__
3.6. Verem push(érték) pop()
beteszi az értéket a verem tetejére. kivesz egy eleme a verem tetejéről.
Az elemek a bekerülés sorrendjéhez képest fordított sorrendben kerülnek ki a veremből.
18
3.7. Egyirányban láncolt lista Az adatelemek szétszórtan helyezkednek el a memóriában. Minden adatelem tartalmaz egy mutató típusú tagot is, ami a következő elemre memóriabeli helyét tartalmazza (a következő elemre mutat). Ha nincs következő elem a mutató értéke NULL. Az összetett elem leírására struktúrával történik. A typedef a megadott típust ELEM-re nevezi. typedef struct elem{ int adat; struct elem *kov; } ELEM;
Létrehozás Mivel dinamikus adatszerkezetről van szó üres listát hozunk létre. Tehát a lista feje jelenleg nem mutat érvényes elemre. ELEM *fej = NULL;
Bővítés A bővítéshez az elemnek megfelelő méretű helyet kell foglalni a memóriába, majd beszúrni az elemet a láncba. Elem létrehozása: ELEM* ujelem(int adat){ /*az uj elemnek lefoglaljuk a helyet*/ ELEM *uj = (ELEM*)malloc(sizeof(ELEM)); uj->adat = adat; /*ertek beirasa*/ uj->kov = NULL; /*ezzel sok bajt megspórolhatunk*/ return uj; }
Elem beszúrása a lista elejére: ELEM* beszur_elore(ELEM *fej, int adat){ ELEM *uj = ujelem(adat); /*az uj elem mutasson a lista elso elemere*/ uj->kov = fej; /*az uj elemmel terunk vissza, hogy mostantol ez legyen a fej*/ return uj; }
Elem beszúrása a lista végére: ELEM* beszur_vegere(ELEM *fej, int adat){ ELEM *tmp, *uj = ujelem(adat); /*Ha az új elem függvényben nem állítottuk be, itt kell*/ //uj->kov = NULL; /*ha ures volt a lista az uj elem lesz a fej*/ if(fej == NULL) return uj; /*kulonben elmegyunk a lista vegere*/ for(tmp = fej; tmp->kov; tmp = tmp->kov); /*az uj elemet az utolso moge fuzzuk*/ tmp->kov = uj;
19
return fej; }
Elem beszúrása adott elem után: ELEM* beszur_adott_elem_utan(ELEM *fej, int hova, int mit){ ELEM *tmp, *uj = ujelem(mit); uj->kov = NULL; /*megkeressuk az adat erteku elemet*/ for(tmp = fej; tmp && tmp->adat != hova; tmp = tmp->kov); /*ha a for ciklus azert ert veget, mert megtalaltuk az elemet*/ if(tmp != NULL){ /*akkor befuzzuk az elemet a tmp utani helyre*/ /*eloszor az uj elem mutatojat allitjuk be!*/ uj->kov = tmp->kov; /*utana a tmp kovetkezojet beallitjuk az uj elemre*/ tmp->kov = uj; } return fej; }
Törlés Megadott elem törlése ELEM *torol(ELEM *fej, int mit){ ELEM *tmp, *elozo = NULL; /*megkeressuk a mit erteku elemet (a tmp-be lesz a vegen)*/ for(tmp = fej; tmp && tmp->adat != mit; tmp = tmp->kov) elozo = tmp; /*nem talaltuk a torlendo elemet*/ if(tmp == NULL) return fej; /*a fejet fogjuk torolni, ezert a fej a fej kovetkezoje lesz*/ if(elozo == NULL) fej = fej->kov; /*kulonben, a torlendo elem kovetkezoje a torlendo kovetkezoje lesz*/ else elozo->kov = tmp->kov; free(tmp); /*felszabaditjuk az elem helyet a memoriaban*/ return fej; } /*egesz lista torlese*/ void felszabadit(ELEM *fej){ ELEM *tmp; for(; fej; fej = tmp){ /*el kell menteni a kov. elem mutatojat.*/ tmp = fej->kov; /*mert ez utan a sor utan a fej->kov mar nem ervenyes hivatkozas*/ free(fej); } return NULL; }
20
Csere Meg kell keresni a fejel adott listában az adott elemet (keres függvény lentebb), és az adatrészét felülírni! ELEM* mmit = keres(fej, mit); if(mmit) //ha megtaláltuk mmit->adat = mire;
Bejárás A lista végigjárásával. void bejar(ELEM *fej){ for(; fej; fej = fej->kov) feldolgoz(fej->adat); }
Keresés Keressük a fejel adott listában a mit értékű elemet. Ha nem szerepel NULL-al, ha szerepel, akkor az adott elem címével térünk vissza. ELEM *keres(ELEM *fej, int mit){ for( ; fej && fej->adat != mit; fej = fej->kov); return fej; }
Példák a fenti függvények hívására a főfüggvényből: int main(){ ELEM *fej = NULL, *keresett; fej = beszur_vegere(fej, 2); fej = beszur_elore(fej, 5); fej = beszur_vegere(fej, 1); fej = beszur_adott_elem_utan(fej, 2, 8); fej = beszur_adott_elem_utan(fej, 1, 9); fej = torol(fej, 5); /*A keresés eredményét nem írjuk vissza a fejbe! Elveszne a lista keresett elem előtti része*/ keresett = keres(fej, 2); fej = felszabadit(fej); return 0; }
3.8. Kétirányban láncolt lista Az adatelemek szétszórtan helyezkednek el a memóriában. Minden adatelem tartalmaz két mutató típusú tagot is. Az egyik a megelőző, a másik a rákövetkező elemre mutat, amennyiben az létezik. Különben értékük NULL. Az összetett elem leírására struktúrával történik. A typedef a megadott típust KELEM-re nevezi. Az egyszerűség kedvéjért a lista fejére, és a lista végére mutató változók a példában globális változóként vannak deklarálva. typedef struct kelem{
21
int adat; struct kelem *kov, *elozo; } KELEM;
Létrehozás //Tároljuk globális változóban a lista fej, és végmutatóját. KELEM *fej = NULL, *veg = NULL;
Bővítás Elem létrehozása: KELEM* ujelem(int adat){ /*az uj elemnek lefoglaljuk a helyet*/ KELEM *uj = (KELEM*)malloc(sizeof(KELEM)); /*ertek beirasa*/ uj->adat = adat; uj->elozo = NULL; uj->kov = NULL; return uj; }
Beszúrás a lista elejére: void beszur_elore(int adat){ KELEM *uj = ujelem(adat); /*Ha ures volt a lista, a beszurt elem lesz a lista feje es vege is*/ if(!fej) { fej = veg = uj; return; } /*kulonben a fej ele fuzzuk az uj-at*/ fej->elozo = uj; /*az uj elem mutasson a lista elso elemere*/ uj->kov = fej; /*ha az elem lefoglalasnal nem tettuk meg itt kell*/ //uj->elozo = NULL; /*az uj elemmel lesz a fej*/ fej = uj; }
Beszúrás a lista végére: void beszur_vegere(int adat){ KELEM *tmp, *uj; //ha ures a lista if(!fej){ beszur_elore(adat); return; } uj = ujelem(adat); //uj->kov = NULL; /*ha az ujelem fv-ben nem tettuk meg*/ /*a list utolso eleme lesz az uj megelozo eleme*/ uj->elozo = veg;
22
/*a lista eddigi utolso elemenek kovetkezoje lesz az uj*/ veg->kov = uj; /*a lista vege pedig az uj elem lesz*/ veg = uj; }
Beszúrás adott elem után: void beszur_adott_elem_utan(int hova, int mit){ KELEM*tmp, *uj; /*megkeressuk az adat erteku elemet/ for(tmp = fej; tmp && tmp->adat != hova; tmp = tmp->kov); /*nem talaltuk meg az elemet, ezert kilepunk*/ if(tmp == NULL) return; /*ha a lista vegere kell beszurni meghivjuk azt a fuggvenyt*/ if(tmp == veg){ beszur_vegere(mit); return; } /*kulonben az uj elemet letrehozzuk*/ uj = ujelem(mit); /*befuzzuk az elemet a tmp utani helyre*/ uj->kov = tmp->kov; uj->elozo = tmp; /*a tmp utani elemet elozojet az uj-ra allitjuk*/ (tmp->kov)->elozo = uj; /*utana a tmp kovetkezojet beallitjuk a NULL-ra*/ tmp->kov = uj; }
Törlés void torol(int mit){ KELEM *tmp; /*megkeressuk a mit erteku elemet (a tmp-be lesz a vegen)*/ for(tmp = fej; tmp && tmp->adat != mit; tmp = tmp->kov); /*nem talaltuk a torlendo elemet*/ if(tmp == NULL) return; /*a lista egyetlen letezo elemet toroljuk*/ if(fej == veg){ //fej->adat == mit && veg->adat == mit veg = fej = NULL; return; } /*a fejet kell torolni, ezert a fej a fej kovetkezoje lesz*/ if(tmp == fej){ fej = fej->kov; fej->elozo = NULL;
23
} /*a veget kell torolni, ezert a veg a veg elozoje lesz*/ else if(tmp == veg){ veg = veg->elozo; veg->kov = NULL; } /*kulonben, a torlendo elem kovetkezoje a torlendo kovetkezoje lesz*/ else { (tmp->elozo)->kov = tmp->kov; (tmp->kov)->elozo = tmp->elozo; } /*felszabaditjuk a torlendo elemnek lefoglalt memoriat*/ free(tmp); }
Példa a függvények hívására a main függvényből: int main(){ beszur_elore(4); beszur_vegere(2); beszur_vegere(24); beszur_adott_elem_utan(2, 9); torol(2); }
A többi műveletet az egyirányban láncolt listáéval analóg módon történik.
3.1. Bináris fa A honlapon: Bináris fa (pdf)
3.2. Bináris kereső fa A honlapon: Keresőfa (pdf, és pptx)
3.3. Általános fa A jegyzetedben.
3.4. Gráf A matematika gráf fogalma megjelenése adatszerkezet szintjén. A gráf reprezentálásának elterjedt módja a szomszédsági (kapcsolat) mátrixszal való leírás. Legyen adott egy N csúcsból álló gráf. Ekkor az azt leíró mátrix N sort, és N oszlopot fog tartalmazni. A gráf csúcsait feleltessük meg *0, N-1+ zárt intervallumban lévő egész számoknak kölcsönösen egyértelmű módon. A mátrix i. sorának, és j. oszlopának metszéspontjában 1-es áll, ha i-ből j-be vezet, és, különben 0. Ezzel egy bitmátrixot kapunk.
24
csúcs
0
1
2
3
4
0
0
0
1
0
0
1
0
0
1
1
0
2
1
0
0
0
0
3
0
1
0
0
1
4
1
0
1
0
0
Ha a gráf éleihez súlyokat rendeltünk, akkor 1-es helyett, az adott súlyt szerepeltetjük a mátrixban. Ilyenkor, ha 0-s súly is előfordulhat a gráfban, akkor az él hiányát végtelennel szokás jelölni. csúcs
0
1
2
0
2
1
7
2
4
2
4
3 4
3
1 9
3 0
Műveletek kapcsolatmátrixszal való reprezentáláskor. Létrehozás Az N elemhez tartozó kapcsolatmátrixot: int M[N][N]; Bejegyezzük a mátrixba a kapcsolatokat.
Bővítés Él beszúrása i. csúcsból j. csúcsba. M[i][j] = 1;
Súlyozott gráfnál, w súlyú él hozzáadása i-ből j-be. M[i][j] = w;
Törlés i csúcsból j csúcsba vezető él törlése: M[i][j] = 0;
Súlyozott esetben az él hiányát jelző speciális érték. Csere A kapcsolatmátrixot nem érinti. Bejárás Keresés: a szokásos keresések nem léteznek. Bejárással oldjuk meg. Szélességi bejárás A bejáráshoz során nyílt, és zárt halmazokba pakoljuk az elemeket. A nyílt halmazt sor adatszerkezetként kezeljük! A gráf tetszőleges csúcspontjából kiindulhatunk. (Ha az adott 25
csúcsból nem érünk el minden elemet, a bejárás újraindul egy másik, még nem bejárt csúcstól.) 1. A kezdő elemet betesszük a nyíltak közé. 2. Ameddig a sor nem üres Vegyük ki a sor első elemét X-be. X feldolgozása. Terjesszük ki X-et. Tegyük X-et a zárt halmazba. Kiterjesztés Vegyük sorra X szomszédjait. Amennyiben egy szomszéd nem X és nem szerepel sem a nyílt sem a zárt halmazban, akkor tegyük bele a nyílt halmazba. Az algoritmus során tárolható, hogy melyik elemet honnan, és hány lépésben értük el . Elem(Szülő, lépésszám vagy költség) szerkezettel, ahol a szülő elem azt jelzi, hogy honnan értük el az adott elemet, a lépésszám pedig a kiindulópont és az elem közti lépések számát jelenti. Sima bejárásnál ezt elhagyhatjuk kereső algoritmusoknál lesz szerepe. Mivel a célunk csak az elemek bejárása, ha egy elem szerepel a zártak vagy a nyíltak közt, azt a kiterjesztés során nem kell újra felvenni a nyíltak közé. Induljunk ki a 3-as csúcsból!
Nyílt 3(-, 0)
Zárt -
1(3, 1), 4(3, 1) 4(3, 1), 2(1, 2)
3(-, 0) 1(3, 1)
2(1, 2), 0(4, 2)
4(3, 1)
0(4, 2)
2(1, 2)
-
0(4, 2)
26
Megjegyzés
A 3-as már szerepel a zártak közt, ezért nem kell újra felvenni. A 2(4, 2)-őt nem kell felvenni, mert a 2-es szerepel a nyíltban. A 0(4,2)-őt nem kell újra felvenni, mert a 0 szerepel a nyíltban.
Mélységi bejárás Az egyetlen változás, hogy sor helyett a nyílt halmazt verem adatszerkezetként kezeljük. Nyílt Zárt Megjegyzés 3(-, 0) 1(3, 1), 4(3, 1) 3(-, 0) 2(1, 2), 4(3, 1)
1(3, 1)
0(2, 3), 4(3, 1) 4(3, 1)
2(1, 2) 0(2, 3)
-
4(3, 1)
A 3-as már szerepel a zártak közt, ezért nem kell újra felvenni. A 0-ásból csak a 2-es érhető el, de az már szerepel a zártak közt. A 4-esből csak olyan elem érhető el, ami szerepel a zártban.
Ha a fenti bejárásokat át akarjuk alakítani úgy, hogy egy elem megkeresésére szolgáljon, akkor vagy az elem feldolgozásánál, vagy a kiterjesztésnél vizsgáljuk meg, hogy az adott elem, a keresett elem-e, és ha igen, visszatérünk az adott elemmel. Ha a nyílt halmaz kiürül az elem megtalálása előtt, akkor az elem nem szerepel a gráfban. Ha egy elemhez vezető legjobb utat akarjuk megkeresni, akkor a kiterjesztés részt változtatjuk. Vegyük sorra X szomszédjait. Amennyiben egy szomszéd nem X és nem szerepel sem a nyílt sem a zárt halmazban, vagy ott nagyobb költséggel szerepel, akkor tegyük bele a nyílt halmazba, a rosszabb költségűt pedig vegyük ki.
4.
Feladatok és megoldásaik
4.1. Témakör: Változók, Típusok, Konstans Feladat: Add meg a következő leírásoknak megfelelő deklarációkat! karakter típusú változó valós típusú változó karakter típusú változó k kezdőértékkel két egész típusú változó, az első értéke legyen három. 5 elemű, karakterekből álló tömb Megoldások A megoldásoknál adott változónevek természetesen szabadon választhatók. char c; // c helyett persze más betű is szerepelhet double d; char c2 = ’k’; int x = 3, y; char tomb[5];
27
Feladat: Mi lesz az adott sorban szereplő változó értéke? A számozott sorok külön feladatot képeznek, a korábbi sorok hatását ne vedd figyelembe! int x = 4; float y; 1. x; 2. y; 3. x = 3.2; 4. y = x; 5. y = 4*3.2; 6. x = y; 7. x = 12/5; 8. y = 12/5; 9. x = 12.0/5.0; 10. y = 12.0/5.0; 11. x = 4.9;
Megoldások 1. 4 2. határozatlan, mert nincs kezdőérték megadva 3. 3, mert x egész típusú változó, ezért a tizedesjegyeket levágja. 4. 3, mert x értéke 3 volt, a float bővebb az int-nél, vagyis itt nem gond az eltérő típus. 5. 12.8 6. 12 7. 2, mert egészeket osztunk 8. 2, mert egészeket osztunk (12; 5 az két egész szám) 9. 2, mert x egész típusú 10. 2.4, mert valós számokat osztunk, és y is valós, így tárolásra is kerül 11. 4, mert vágás történik, nem kerekítés
4.2. Témakör: Kifejezés Feladat: Add meg a sorokban lévő kifejezések értékét! Tekintsd úgy a sorokat, mint egy program részletet! (Tehát ha a értékét az első sorban felülírtuk, akkor a 3. sorban már az a értéke 3.)
1. 2. 3. 4. 5. 6. 7.
28
int a, b; double lf; a; a = 5; b = 3.2; lf = a+b; a > 3 && (a != 5 || b == 3.2); (a || b) && (a
Megoldások
1 2 3 4 5
6
7
Részkifejezés a a=5
érték 5 5
típus int int
b = 3.2 lf = a + b a>3 a != 5 b == 3.2 a != 5 || b == 3.2 a > 3 && (a != 5 || b == 3.2) a || b a
3 8 1 (igaz) 0 (hamis) 1 (igaz) 1 (igaz) 1 (igaz) 1 1 1 0 1 6 1.5 -0.5
int (vágás) float (bővítés) int int int int int int int int int int int double(bővítés) double(bővítés)
4.3. Témakör: Elágaztató utasítás Feladat: Adj meg a következő leírásokhoz elágaztató utasításokat (int x, y;)! 1. ha x pozitív szám, adj hozzá egyet. 2. ha x pozitív szám, és kettővel osztható, akkor vonj ki belőle egyet 3. ha x nem negatív, akkor vonj le belőle hármat 4. ha x négy és 14 között van, a határokat is beleértve, akkor legyen nulla 5. ha x nincs négy és 14 közt, a határokat is beleértve, akkor legyen nulla 6. nullázd ki x, és y közül a kisebbet, ha egyenlők, ne tegyél semmit. 7. vonjunk le x-ből 3-at, ha ez nagyobb, mint y, akkor legyen y értéke -1 8. ha x páratlan növeld eggyel az értékét. Ha 3-mal is osztható adj hozzá még ötöt hozzá ötöt. Ha x páros legyen az értéke 0. Megoldások Több helyes megoldás is létezik, egy-egy megoldás áll itt. 1. 2. 3. 4. 5. 6.
29
if(x>0) ++x; if(x>0 && !(x%2)) --x; //!(x%2) kifejezés ua. mint x%2 == 0 if(x>=0) x-=3; //x-=3 kifejezés ua. mint x = x-3 if(4<=x && x<=14) x = 0; if( !(4<=x && x<=14)) x = 0; if(x
else if(y<x) y = 0; 7. if(x-3>y) y = -1; 8. if(x%2){ //x mod 2 nem nulla, tehát x páratlan ++x; if(!(x%3)) x +=5; }else x = 0;
Feladat: Mi lesz a t tömbben az alábbi kódrészletek végrehajtása után? 1. példa int i = 1, a = 3, b = 6, t[4]={0, 3, -4, 9}; if(t[i] == a) t[i+1] = b;
2. példa int t[]={1,4,12}; if(t[0] > t[1]) t[1] = t[0]; else t[2] /= t[1];
3. példa int i, a = 4, b = 6, t[]={1,4,-12,4,6}; for(i = 0; i<4; ++i) if(t[i+1] == a) t[i] = 0; else t[i] = b;
Megoldások 1. t elemei: 0, 3, 6, 9 mert: t[i] == a kifejezésbe i értékét helyettesítve t[1] == 3. t[1] értéket behelyettesítve 3 == 3, tehát végrehajtódik a t[i+1] = b. Ebbe i és b értékét behelyettesítve t[2] = 6. 2. t elemei: 1, 4, 3 mert t[0] > t[1] a tömb elemeit behelyettesítve 1>4, ami hamis. A else hajtódik végre. t[2] /= t[1] átírva: t[2] = t[2] / t[1]. Ami t[2] = 12/4. 3. i i<4 és következménye t*i+1+ == a és következménye 0 1 ciklusmag lefut t[1] == 4, t[0] = 0 1 1 ciklusmag lefut t[2] == 4, t[1] = b 30
ágban lévő kifejezés
t elemei 0, 4, -12, 5, 6 0, 6, -12, 4, 6
2 3 4
1 ciklusmag lefut 1 ciklusmag lefut 0 ciklusmag nem fut le
t[3] == 4, t[2] = 0 t[4] == 4, t[3] = b -
0, 6, 0, 4, 6 0, 6, 0, 6, 6 0, 6, 0, 6, 6
4.4. Témakör: Ciklusszervező utasítások Feladat: Hányszor fut le a ciklusmag (++x), az alábbi kódrészleteknél (int x=1, i=1;)? A feladatok egymástól függetlenek! 4. for(i = 0; i<5; ++i) ++x; 5. for(i = 0; i>=-5; --i) ++x; 6. for(i =0; i<3; --i) ++x; 7. for(; i<4; ++i) ++x; 8. for( ; i==x; ++i) ++x; 9. for( i=0; 1; ++i) ++x; 10. for( i=7; i>x; --i) ++x; 11. for( ; ; ) ++x; 12. for( ; 0; ) ++x; 13. for(i =0, x=0; i==x && i<5; ++i, ++x);
Megoldások 1. 5, mert i a következő értékekre fut ,0,1,2,3,42. 6, mert i a következő értékekre fut ,0,-1,-2,-3,-4, -5} 3. végtelen mert i<3 kezdetben igaz, és i-t csak csökken 4. 3, mert i a következő értékekre fut ,1,2,3-, mivel i kezdőértéke 1 (deklaráció) 5. végtelen, mert i, és x azonos értékről indul, és azonosan növekednek 6. végtelen, mert az 1 feltételként mindig igaz 7. 3, mert i, és x értékei lépésenként: 8. i: 7, 6, 5, 4 9. x: 1, 2, 3, 4 10. tovább már nem kell néznünk, mert i>x feltétel negyedik esetben már hamis. 11. végtelen, mert nincs ismétlésre vonatkozó információ a ciklusfejben. 12. 0, mert a feltétel egyből hamis. 13. 5, mert ez ugyan az, mint a következő kód: x=0; for(i=0; i<5; ++i){ ++x; if(i!=x) break; //soha sem hajtódik végre, x==i mindig igaz }
Feladat: Adj meg a következő leírásokhoz for ciklus fejet. Feltételezd, hogy int t[N] tömb létezik, és egy ciklusváltozónak használható i deklarálva van (int i;)! 1. Egyesével végigmegy az N elemű t tömb elemein. 2. Kettesével végigmegy a tömb elemein. 31
3. 4. 5. 6.
Hármasával végigmegy a tömb elemein hátulról előre. A tömb 2. elemétől indul a tömb végéig. Az tömb 5. elemétől indulva bejárja a 5 egymás utáni elemet. A tömb elejétől addig megy, amíg két egymás mellett álló azonos elemet nem talál.
Megoldások 1. 2. 3. 4. 5. 6.
for(i for(i for(i for(i for(i for(i
= = = = = =
0; i
=0; i-=3) //N-1. a tömb utolsó eleme! 1; i
4.5. Témakör: Tömb, mátrix 1. 2. 3. 4.
Számolja ki egy N elemű, egészekből álló tömb elemeinek összegét! Számolja ki egy N elemű, egészekből álló tömb elemeinek átlagát! Számolja meg hány pozitív szám áll egy N elemű, valós tömbben! Számolja ki két N dimenziós vektor belső szorzatát. (Mindkét vektor egy N elemű tömbbel van reprezentálva.) 5. Határozza meg egy egészekből álló tömb legnagyobb elemének helyét! 6. Határozza meg egy NxM-es mátrix legnagyobb elemét! Megoldások 1. int osszeg(int t[N]){ int i, sum = 0; //kezdőérték adás ne maradjon le! for(i = 0; i
2. double atlag(int t[N]){ int i, sum = 0; for(i = 0; i
3. int pozitiv(double t[N]){ int i, count = 0; for(i = 0; i0) ++count; return count; }
4. double szorzat(double v[N], double v2[N]
32
int i; double s = 0; for(i = 0; i
5. int maximumhely(int t[N]){ int i, maxh = 0; for(i = 1; i
6. int maximum(int t[N][M]){ int i,j, max = t[0][0]; for(i = 0; i
4.6. Témakör: halmaz, multihalmaz Minden feladatnál feltételezzük, hogy az alaphalmaz egész számokból álló *0-N-1] intervallum. 1. Add meg a ,0, 3, 5, 2- halmaz 6 hosszú karakterisztikus függvényét. 2. Add meg a ,0, 0, 3, 3, 3, 4- halmaz 6 hosszúságú karakterisztikus függvényét. 3. Mi az eredeti halmaz, ha a karakterisztikus függvénye: 0010110? 4. Mi az eredeti multihalmaz, ha a karakterisztikus függvénye: 3,3,0,0,4,1,2 5. Egészítsd ki az alábbi kódot, úgy, hogy E a következő halmazművelet eredményét tartalmazza: A (B C) void AuBmC(int A[N], int B[N], int C[N], int E[N]){ int i; for( i = 0; _______ ; ++i) E[i] = __________________; }
6. Egészítsd ki az alábbi kódot, úgy, hogy R a következő halmazművelet eredményét tartalmazza: (B \ C) void AuBmC(int A[N], int B[N], int C[N], int R[N]){ int k; for( k = 0; k
33
Megoldások 1. 1 0 1 1 0 1 2. 2, 0, 0, 3, 1, 0 3. {2, 4, 5} 4. {0, 0, 0, 1, 1, 1, 4, 4, 4, 4, 5, 6, 6} 5. i
4.7. Témakör: Ritkamátrix 1. Adott a következő 3 soros reprezentáció. Mi volt az eredeti mátrix, ha tudjuk, hogy
3x4-es volt, és a gyakori elem 0. Sor 0 Oszlop 0 Érték 4
0 2 6
1 1 5
1 3 2
2 2 2
2. Adott a következő ritkamátrix. Készítse el a 4 soros reprezentációját, ha a gyakori
elem a 0!
Megoldás 1.
2. Sor
34
0
0
1
1
1
2
2
Oszlop 0 Érték 2 Mutató 2
2 6 4
0 1 -1
1 3 -1
2 1 5
2 2 -1
4 1 -1
5.
Gyakorló feladatok megoldások nélkül
Írasd ki az 50 alatti pozitív egész számok négyzetét! Írasd ki az 50 alatti pozitív egész számok köbét! Írj programot az n faktoriális kiszámítására! Írj programot egy n elemű tömbben tárolt minta szórásnégyzetének meghatározására! (az egyes elemek átlagtól való eltérésének négyzetösszege) Keresd meg egy tömbben a legnagyobb páratlan elemet! Keresd meg egy tömbben a legkisebb páros indexű elemet! Keresd meg egy tömbben a 3. legnagyobb elemet! Feltételezzük minden elemből csak egy van. Keresd meg egy mátrixban a legnagyobb elemet! Keresd meg egy mátrixban azt a sort, melyben az elemek összege maximális! Keresd meg egy mátrixban azt az oszlopot, melyben az elemek összege minimális! Határozd meg a mátrixban lévő 4-el osztható elem átlagát! Számold meg oszloponként hány olyan elem van, amely 0-nál nagyobb! Legyen adva egy nullákból és egyesekből álló mátrix. Van–e egy sorban 2 egyforma érték egymás után? Van–e egy oszlopban 2 egyforma érték egymás után? Álljanak egy tömbben egyetlen szóközzel elválasztott szavak. Hányszor szerepelnek az egyes betűk a tömbben? Hány szó van a tömbben? Hány ’b’-vel kezdődő szó van a tömbben? Szerepel-e a tömbben a „azt” szó? Írj fel egy tetszőleges mátrixot, amelyben a gyakori elem az 5-ös! Készítsd el a 3 és 4 soros reprezentációját! Adott a következő 3 soros reprezentáció. volt, és a gyakori elem 0. Sor 0 Oszlop 0 Érték 4
Mi volt az eredeti mátrix, ha tudjuk, hogy 4x6-os 0 4 6
1 3 5
1 5 2
3 3 2
3 5 5
Gyakorló feladatok egyirányban láncolt listához: Írassa ki az egyirányban láncolt lista minden második elemét! Írassa ki az egyirányban láncolt lista páros elemeit! Számolja ki az listaelemek összegét! Számolja ki a listaelemek átlagát! Keressen meg egy adott k számot a listában! (Teljes keresés) Keressen meg egy adott k számot egy rendezett listában! (Lineáris keresés)
Számolja meg hány 5-ös érték van a listában! Ellenőrizze van-e két azonos érték a listában! Írjon függvényt, mely x értékű elemek értékét y-ra cseréli! Írjon olyan függvényt, mely a lista első elemének törlésére szolgál! Írjon olyan függvényt, mely a lista utolsó elemének törlésére szolgál! Rajzolja fel, milyen mutatókat, és milyen sorrendben kell átállítania, ha egy 9, 10, 13, 15-ös listában a 13-as elé szúr be egy 3-as elemet! Tegye fel, hogy van egy rendezett listája! Írjon függvényt, mely beszúr egy új elemet a megfelelő helyre. Az 10., 11. feladatnál készített függvények segítségével valósítsa meg a sor, és a verem egyirányban láncolt listával való reprezentációját! Írjon olyan függvényt, mely egy adott elem elé szúr be elemet! Írassa ki a lista elemeket fordított sorrendben! Gyakorló feladatok kétirányban láncolt listához: Minden, ami az egyirányú listánál is szerepel itt is jó gyakorlásnak! Írassa ki a lista elemeket fordított sorrendben! Rajzolja le, milyen mutatókat milyen sorrendben állítana át, ha az elejére szúr be egy elemet! Rajzolja le, milyen mutatókat milyen sorrendben állítana át, ha a végére szúr be egy elemet! Rajzolja le, milyen mutatókat milyen sorrendben állítana át, ha egy közbenső elem elé szúr be egy elemet! Rajzolja le, milyen mutatókat milyen sorrendben állítana át, ha egy közbenső elem után szúr be egy elemet! Keressen meg az első k értékű számot a listában! (Teljes keresés) Keressen meg az utolsó k értékű számot egy rendezett listában! (Lineáris keresés) Tételezze fel, hogy betűket tartalmaz a lista! Ellenőrizze le, hogy palindroma -e a szó (pl.:abba, apa, görög) Tegye fel, hogy van egy rendezett listája! Írjon függvényt, mely beszúr egy új elemet a megfelelő helyre. Van egy t N elemű tömb. Hozzon létre listát, mely azokat az elemeket tartalma zza, mely szerepel t-ben, és annyi az értéke, ahányszor az adott szám szerepel t-ben. (Segítség: végig kell menni a tömbben, az adott értékű elemet keresni a listában. Ha benne volt, akkor növelni kell a listaelem értékét, ha hiányzott be kell szúrni! Valósítsa meg a sor, és a verem két irányba láncolt listával való reprezentációját!
36
