Programozás I. C nyelv
4. előadás Vezérlési szerkezetek Veszprémi Egyetem Heckl István,
[email protected]
1
Vezérlési szerkezetek • Típusai strukturált programozásban: – szekvencia (egymás utániság) – szelekció (feltétel) – iteráció (ciklus)
2
Szekvencia • Több elemi utasítás egymás utáni sorozata, amelyeket a megjelenés sorrendjében hajtunk végre – az elemi utasításokat ';' zárja le
3
Blokk utasítás • Blokk utasítás: elemi utasításokat fog egybe { elemi utasítás 1; elemi utasítás 2; … } • Használhat: – feltételeknél – ciklusnál – függvénynél – egyéb: osztály deklaráció
4
Példa #include <stdio.h> int main() { char nev[50]; printf("Please provide your name:"); scanf("%s", nev); printf("Thank you your name is %s", nev); return 0; }
5
Szelekció • A végrehajtás elágazik: egy feltétel alapján egy utasítás blokk vagy végrehajtódik vagy nem • Típusai: – if – if else – switch case
6
Szelekció • Szintaxis: if (kifejezés) utasítás 1// lehet blokk utasítás is [else // az else ág opcionális utasítás 2] • Kiértékelés: – kifejezés egy logikai kifejezés • számok is tekinthetőek logikai értéknek – ha a kifejezés nem 0 (igaz), akkor utasítás 1 – ha 0 (hamis), akkor utasítás 2 hajtódik végre 7
Szelekció • Ha Utasítás 1 blokk utasítás akkor a zárójelek kitétele kötelező – mindig rakjuk ki a zárójeleket, mert ezzel későbbi hibákat előzhetünk meg – ha mégse akarunk zárójeleket rakni, akkor a feltételt és utasítás 1-t rakjuk egy sorba • elkerüljük, hogy '{', '}' használata nélkül akarjuk bővíteni utasítás 1-t • nem látjuk, hogy a feltétel igaz volt-e nyomkövetés alatt 8
Szelekció • Egyenrangú megvalósítások: if (temp<0) printf("Ma fagy van\n"); if (temp<0) printf("Ma fagy van\n"); if (temp<0) { printf("Ma fagy van\n"); }
9
Szelekció • Veszélye: if (temp<0) printf("Ma fagy van\n"); printf("Ez nagyon hideg."); /* ez nem az if-hez tartozik, a felteteltol fuggetlenul mindig vegrehajtodik */ • Helyesen: if (temp<0) { printf("Ma fagy van\n"); printf("Ez nagyon hideg."); }
10
Szelekció • Egy függvényben tetszőleges számú feltétel lehet • Ha mindig kirakjuk '{', '}' jeleket és szabályosan tördeljük a fájlt, akkor a végrehajtás menete több feltétel jelenléte mellett is egyértelmű
11
#include <stdio.h> void main(){ double a, b; int z; printf("A oldal:"); if(scanf("%lf", &a) == 0) { printf("hibas bemenet"); } else { printf("B oldal:"); if(scanf("%lf", &b) == 0) printf("hibás bemenet"); else{ printf("terulet=%lf\n", a*b); } } }
12
Szelekció • Ha nem raktuk ki a '{', '}' jeleket, akkor a feltételek értelmezésében bizonytalanság lehet – egy else mindig a legközelebb, ugyanazon szinten lévő if-hez tartozik • nem a tördelés számít – kapcsos zárójeleket használva egyértelműsíthetjük a helyzetet
13
Szelekció • Példa 1: if(n > 0) if(a > b) z = a; else z=b;
// else a belso if-hez
• Példa 2: if(n > 0) { if(a > b) { z = a; } } else { z=b; }
// else a kulso if-hez 14
Többszörös elágazás • Többszörös elágazás készíthető több if-else utasításból – az else ág pontosan egy if-t tartalmaz • egy sorba szokás írnia az "else if" -t – ez valójában nem külön elágazás típus – ekkor csak az utolsó else ágban szokás kirakni a '{', '}' jeleket – az "else if" mind azonos tördelési szinten vannak
15
Többszörös elágazás • Szintaxis: if (kifejezés 1) { utasítás 1 } else if (kifejezés 2) { utasítás 2 … } [else utasítás n] • Utasítás n csak akkor hajtódik végre, ha egyik feltétel sem teljesült
16
Példa if (result >= 75) printf("Passed: Grade A\n"); else if (result >= 60) printf("Passed: Grade B\n"); else if (result >= 45) printf("Passed: Grade C\n"); else printf("Failed\n");
17
// a tobbszoros elagazas hagyomanyos formaban if (result >= 75) { printf("Passed: Grade A\n"); } else { if (result >= 60) { printf("Passed: Grade B\n"); } else { if (result >= 45) { printf("Passed: Grade C\n"); } else { printf("Failed\n"); } } }
18
Példa // van hogy a jobb olvashatosagert erdemes bonyolultabb kodot irni // plusz feltetelek if (result<=45) printf("1-es \n"); if ((result>45) && (result<=60)) printf("2-es \n"); if ((result>61) && (result<=70)) printf("3-as \n"); if ((result>71) && (result<=80)) printf("4-es \n"); if ((result>81) printf("5-os \n"); 19
switch szerkezet • Többszörös elágazás char, short vagy int típusú kifejezés alapján • Szintaxis: switch (kifejezés) { case const1: utasítás; break; case const2: utasítás; break; … [default: utasítás] }
20
switch szerkezet • Mind a kifejezés, mind constk, egész típusúak • Ha a kifejezés értéke egyenlő constk-al, akkor ide ugrik a végrehajtás – az utasítások addig hajtódnak végre, míg ki nem érünk a switch blokkjából vagy break kulcsszóval nem találkozunk • break hatására kilépünk a switch blokkjából • Ha egyik case sem teljesül, akkor a default-ra ugrunk, ha létezik
21
Példa • Leírás: – a és b két egész szám – i karakterben lévő műveletet akarjuk végrehajtani rajtuk (+, - , *, /) – az eredményt a c egész típusú változóba rakjuk
22
int i='-', a=2, b=3, c; switch(i){ case '+': c = a + b; break; case '-': c = a - b; break; case '*': c = a * b; break; case '/': c = a / b; /* a break elhagyasa itt logikai hiba */ default: printf("\nWrong operator\n"); }
23
// hónap és nap alapján kiszámolni, hogy hányadik nap az évben int napokszama=0, nap = 2, honap = 3; // March 2nd switch (honap) { case 12: napokszama += 30; case 11: napokszama += 31; case 10: napokszama += 30; case 9: napokszama += 31; case 8: napokszama += 31; case 7: napokszama += 30; case 6: napokszama += 31; case 5: napokszama += 30; case 4: napokszama += 31; case 3: napokszama += 28; case 2: napokszama += 31; //nincs break } napokszama += nap; // 61 24
Iteráció • definíció: utasításokat többszöri ismétlése • Fajtái: – for ciklus (számlálós) – while ciklus (elől tesztelős) – do-while ciklus (hátul tesztelős)
25
for ciklus • Szintaxis: for([kifejezés1];[kifejezés2];[kifejezés3]) utasítás • • 1. 2.
Az utasítás általában blokk utasítás Végrehajtás: Kifejezés1-et kiértékelése egyszer a legelején Kifejezés2 kiértékelése minden iteráció előtt • Ha kifejezés2 igaz, akkor utasítás végrehajtása • Ha kifejezés2 hamis, akkor vége 3. Kifejezés3 kiértékelése minden iteráció után 26
for ciklus • Általában: – kifejezés1 adja meg a ciklus változó kezdeti értékét – kifejezés2 hasonlítja össze egy vég értékkel – kifejezés3 lépteti azt • A leggyakoribb feladat a ciklusmag n-szer történő végrehajtása – for (idxI=0; idxI
27
Példa #include <stdio.h> int main() { int i, n, fakt; printf("Kerem az egesz szamot:"); scanf("%d", &n); fakt = 1; for(i = 1; i <= n; i++) { fakt *= i; } printf("A faktorialis: %d\n", fakt); return 0; }
28
for ciklus • Tipikus hiba: A for után van egy pontos vessző – ekkor n-szer végrehajtódik az üres utasítás – ezután 1-szer a ciklus mag for(i = 1; i <= n; i++); fakt *= i;
29
while ciklus •
Szintaxis: while (kifejezés) utasítás
•
Végrehajtás: 1. Kifejezést kiértékelése ha hamis, akkor ciklus vége 2. utasítás végrehajtása 3. ugrás 1-re Nincs ; a while után
•
30
while ciklus • Ami for-ral megoldható, az megoldható while-al is
for (kif1; kif2; kif3) utasitás
kif1; while (kif2) { utasitás kif3; }
31
Példa #include <stdio.h> int main() { int i, n, fakt; printf("Kerem az egesz szamot:"); scanf("%d", &n); fakt = 1; i=1; while(i<=n) { fakt *= i; i++; } printf("A faktorialis: %d\n", fakt); return 0; }
32
Példa • Szám ismételt bekérése: while (scanf("%lf", &a) == 0) { flushall(); printf("Hibas adat, kerem a valos erteket:"); }
33
do-while ciklus • Szintaxis: do utasítás while(kifejezés); • Abban különbözik a while-tól, hogy az utasítás legalább egyszer végrehajtódik • Van ';' a while után
34
do-while ciklus • Ami for-ral megoldható, az megoldható do-while-al is – a három cilklus fajta egymásba átírható
for (kif1; kif2; kif3) utasitás
kif1; if (kif2) { do { utasitás kif3; } while (kif2) ; } 35
Egyszerű menü #include <stdio.h> void fv1() {} void fv2() {} void main(){ char c; do{ printf("\n1. fv1"); printf("\n2. fv2"); printf("\n3. kilepes\n"); scanf("%c", &c); switch(c){ case '1': fv1(); break; case '2': fv2(); } flushall(); // insert it if program doesn't halt at scanf } while(c!='3'); }
36
#include <stdio.h> void main() { int n,i,f; char c; do { printf("Kerek egy termeszetes szamot:"); while( scanf("%d",&n)==0 || n<0) { flushall(); printf("Hibas input,kerek egy uj szamot:"); } f=1; for(i=2;i<=n;f*=i++); printf("%d faktorialisa:%d.\n",n,f); do { printf("Van tovabbi adat?(i/n):"); flushall(); scanf("%c",&c); } while( !(c=='i' || c=='n') ); } while(c=='i'); } 37
break • Szintaxis: break; • Hatására a program kilép a switch, for, while vagy dowhile blokkjából – csak a legbelső blokkból ugrunk ki – if -re nem alkalmazható • Ciklusoknál is alkalmazzák if-el együtt a ciklusból való kilépésre – minden feltételt be lehetne építeni a ciklus megállási feltételébe – van, hogy if-break -el egyszerűbb szerkezetet kapunk 38
continue • Szintaxis: continue; • Hatására a program: – while és do-while ciklusnál a megállási feltétel kiértékeléséhez ugrik – for ciklusnál kiértékelődik a megállási feltétel, ha az igaz, akkor a léptetés és utána még egyszer a megállási feltétel • Segítségével néha egyszerűbb szerkezetet lehet elérni • Kerüljük a break és a continue gyakori használatát
39
#include <stdio.h> #include <string.h> void main() { // looking for a girl whose maiden name is Tailor char c, s[100]; while (1) { flushall(); printf("\nsex (m/f): "); scanf("%c", &c); if (c=='m') continue; printf("\nmaiden name: "); scanf("%s", s); if (!strcmp(s,"Tailor")) break; } printf("Tailor has been found\n"); }
40
goto • Szintaxis: – goto cimke; – label: • ugyanolyan label, mint switch-nél • Soha ne használjuk, mert sérti a strukturált programozás elvét
41
Programozás I. C nyelv 5. előadás Bekérési és kiírási függvények, tömbök, véletlen számok Veszprémi Egyetem Heckl István,
[email protected]
1
Bekérési és kiírási függvények • A C nyelv magja nem rendelkezik adatbeviteli és –kiviteli (I/O) utasításokkal • Ezek a feladatot könyvtári függvényekkel megvalósítottak
2
Bekérési és kiírási függvények csoportjai • Stream IO: magas színtű, bufferelt függvények – stdio.h – pl.: printf, scanf – a bufferelés miatt a kimenet késhet • Alacsony szintű IO: nem bufferelt függvények – io.h • Konzol és port IO: közvetlenül érik el a konzolt illetve a portokat – conio.h • Egy programban lehetőleg csak az egyik csoportot használjuk – leggyakrabban: stream io
3
Stream IO • Definíció stream: adatfolyam, amelyből az adatok szekvenciálisan olvashatóak illetve írhatóak
4
Stream • Az stdio streamjei buffereltek – buffer: ideiglenes tár – az adatok először a bufferbe kerülnek és onnan egyszerre továbbítódnak • a buffer ürítése paranccsal is megvalósítható – a buffer használata meggyorsítja az IO műveleteket – nyomkövetés során lehet, hogy nem látjuk rögtön az eredményt • Stream használata: – megnyítás – írás / olvasás – bezárás
5
Stream • Gyakran használt streamek: – stdin: alapértelmezésben a billentyűzet – stdout: alapértelmezésben a monitor – stderr: alapértelmezésben a monitor • A program induláskor automatikusan megnyitja az előbbi streameket – az előbbi streamek impliciten használtak, léteznek olyan függvények, amelyek csak rájuk vonatkoznak • az általános függvények bármely streamre használhatóak • A streamek FILE* típusúak 6
printf, scanf • A printf, scanf függvényeket korábban tanultuk • Változataik: – int sprintf(char* out, const char* format [, argument] ... ); • a kimenet az out karakter tömbbe kerül – int sscanf(const char* in, const char* format [, argument ] ... ); • az in karakter tömbből olvassuk az adatokat
7
getchar • Egy karaktert olvas be, ha ez sikeres volt, akkor a beolvasott karakter ascii kódját kapjuk meg • Deklaráció: int getchar(); • EOF (End Of File) egy speciális érték (-1), amely az adatbevitelt végét jelenti – windows: ctrl+z – linux: ctrl+d • A karaktert a bufferben keresi a függvény – ha talál, akkor kiolvassa és megállás nélkül megy tovább – ha nem talál: akkor a billentyűzetről tölti fel a buffert • enter zárja le a feltöltést
8
putchar • Deklaráció: int putchar(int ch); • A megadott ch karaktert kiírja a képernyőre – stream IO függvény • Sikeres működés esetén a ch karakter kódját kapjuk meg visszatérési értékként
9
Példa #include <stdio.h> void main() { int c; while((c=getchar()) !=EOF) { //flushall(); printf("CORE"); putchar(c); } } • Input: 123 [enter] ctrl+z • Output: CORE1CORE2CORE3
10
Példa • Enter lenyomásáig soronként írja vissza a begépelt karaktereket: – kilépés: egy üres sorba ctrl+z • Ha használjuk a flushall függvényt, akkor a soroknak csak az első betűje kerül kiírásra
11
gets • Deklaráció: char* gets(char* sptr); • A gets egy sort enter lenyomásáig olvas, majd a karaktert az sptr mutató által kijelölt helyre másolja • A sztringben az új sor ('\n') karakter '\0'(EOS) karakterrel helyettesítődik • A gets visszatérési értéke sikeres olvasás esetén a megadott puffer cím, ill. NULL, ha hiba lép fel • scanf nem alkalmas sor beolvasására, mert a szóközt és a tabulátort a sztring végének tekinti
12
puts • Deklaráció: int puts(char* sptr); • sptr sztringet kiírja a képernyőre – stream IO függvény • A sztring után enter kerül • A sikeres kiíratást egy nem negatív számmal jelzi, ellenkező esetben EOF
13
Példaprogram #include <stdio.h> void main() { char str[80]; puts("sztring beolvasasa:"); gets(str); puts(str); }
14
flushall • Deklaráció: int flushall(); • Visszaadja a nyitott streamek számát • Az olvasási buffereket kitörli – az adatok elvesznek • Az írási buffereket kiírja a cél eszközre és törli a buffert
15
Konzol függvények • int cprintf(const char* format [, argument] ... ); • int cscanf(const char* format [, argument] ... ); • char* cgets(char* buffer); • int cputs (const char* string); – sort ír a képernyőre – sztring a kiírandó ('\0'karakterrel lezárt) karaktersorozat • int putch(int c); – putch egy karaktert ír a képernyőre – c a kiírandó karakter
16
Konzol függvények • int getch(void); – a függvény a beolvasott karaktert adja vissza – a beolvasott karakter nem jelenik meg a képernyőn • int getche(void); – a függvény a beolvasott karaktert adja vissza – a beolvasott karakter megjelenik a képernyőn
17
Példa #include <stdio.h> #include
void main() { cprintf("press any key to continue:\n"); char a = getch(); cprintf("the read character is: %c\n", a); cprintf("yes or no (y/n): "); a = getche(); cprintf("\n"); } 18
Tömbök, sztringek • Definíció: olyan objektumok halmaza, amelyek azonos típusúak és a memóriában folytonosan helyezkednek el – jelenleg a statikus tömböket tárgyaljuk, a dinamikus tömböket a mutatókkal együtt vesszük • A tömb elemeinek típusa a void és a függvénytípus kivételével tetszőleges típus lehet – objektum tömbök helyett mutató tömböket szokás használni • Elemek elérése: tömbNév[index]
19
Egydimenziós tömbök • Egydimenziós tömbök deklarálása: – típus tömbnév[méret]; – az elemek indexelése 0-tól (méret-1)-ig történik – méret egy konstans kifejezés • C-ben nincs index ellenőrzés, a fordító nem érzékeli hibának a tömb[-5] hivatkozást, de futás közben fellép a hiba
20
Példaprogram • Példa: 5 elemet tartalmazó egész tömb, melynek elemeit az indexek négyzetével töltjük fel: int a[5]; • A tömb elemeinek egymás után történő elérésére általában a for ciklust használjuk, melynek változója a tömb indexe: int i; for (i=0; i<5; i++) { a[i]=i*i; } 21
Egydimenziós tömbök inicializálása • A C nyelv lehetővé teszi, hogy a tömböket definálásuk során konstans értékekkel inicializáljuk • Értékadás: - típus tömbnév [méret]={vesszővel tagolt konstansok} • Példák vektorok inicializására: int a[10]={1,2,3,4,5,6,7,8,9,10}; char szo[8]={'a','l','m','a'}; float szamak[]= {12.3f, 23.4f, 34.5f, 45.6f};
• Ha méretnél több elemet adunk, fordítási hibaüzenetet kapunk – kevesebb elemet adhatunk meg 22
Egydimenziós tömbök inicializálása • Ha nincs inicáló lista, akkor az elemek határozatlanok – ha van, akkor a nem megadott értékek 0-k • Inicializálás esetén a tömb méret elhagyható, az a kezdőértékek számából meghatározható – jól használható ez a megoldás, ha a tömb elemeit fordításonként változtatjuk – több dimenziós tömböknél az első dimenzióméret hagyható el
23
Léptetés tömbelemekre #include <stdio.h> int main() { int x[]={0,1,2,3}; int a, i = 1; a = x[i]; // a=1 a = x[i++]; // a=1, i=2 a = x[++i]; // a=3, i=3 a = x[i]++; // a=3, x=[0,1,2,4] a = --x[--i]; // a=1, i=2, x=[0,1,1,4] a = x[--x[--i]]++; // a=0, i=1, x=[1,0,1,4] return 0; } 24
A többdimenziós tömbök • Többdimenziós tömbök deklarálása: típus tömbnév[méret 1] [méret 2]…[méret n]; • Kétdimenziós tömbök deklarálása: típus tömbnév[méret 1] [méret2]; • A kétdimenziós tömb egy mátrixxal írható le – méret 1: a tömb sorainak száma – méret 2: a tömb oszlopainak száma • A statikus kétdimenziós tömbök sorfolytonosan tárolódnak – a memóriában az első sor után közvetlenül következik a második, harmadik, ... 25
Többdimenziós tömbök inicálása • A sorfolytonosság hangsúlyozása: int matrix [3] [5] = {4,26,90,14,11, 13,30,70,63,9, 7,87,60,19,12}; • A sorok hangsúlyozása: int matrix [3] [5] = {{4,26}, {13,30,70,63,9}, {7,87,60,19,12}}; – anélkül adhatjuk meg a második sor kezdő értékeit, hogy az első sor minden elemére megtettük volna
26
Példa • Keressük meg egy mátrix elemeiből a maximálisát és minimálisát – kétdimenziós tömb bejárása kettős for ciklussal egyszerűen megoldható – valójában egyszeres for ciklust is használhatunk a sorfolytonosság miatt
27
Példaprogram • Legkisebb és legnagyobb elem kiválasztása: const int row = 3, col = 2; int matrix[row][col]={4, 5, -56, 78, 4, 3}; int emax = matrix[0][0], emin = matrix[0][0]; int i,j; for (i = 0; i < row; i++) for (j = 0; j < col; j++) { if (matrix[i][j] > emax) emax = matrix[i][j]; if (matrix[i][j] < emin) emin = matrix[i][j]; }
28
Példaprogram • Mátrix nevű 2 dimenziós tömb tartalmának kiíratása mátrixos alakban – a belső (j) ciklus kiírja a sorokat a külső (i) a sorok között lépked for (i=0; i
29
Sztringek • A c nyelv nem ismeri a sztring alap típust, az karaktertömbbel van megvalósítva – nincs értékadás sztringek között • Sztring: olyan karaktertömb, amelyben a karakterek sorozatát egy 0 értékű karakter zárja – 0-nak is kell hely a karaktertömbben • Sztring létrehozása: – char a[]="abc"; • a[0]='a', a[1]='b', a[2]='c', a[3]=0 (nem '0') – char* b="abc"; • a sztring konstansok adott memória területen helyezkednek el, b felveszi "abc" kezdőcímét
30
Sztringek – a vezérlő karakterek egy karakteren tárolódnak • példa: char c[]="c:\\a.txt"; • Sztring beolvasása: char a[80]; printf("a="); scanf("a=%s", a); // nincs & a elott, mert 'a' mutato • Sztring tömb: char nyar1[][10] = {"Junius", "Julius", "Augusztus"}; – a karaktertömb nem minden eleme inicializált
31
Véletlen számok generálása • Az itt következő függvények gyakran máshogy vannak megvalósítva a különféle C változatok alatt • int rand(); – ál véletlen számot ad vissza 0 és RAND_max(215 –1) között • a visszatérési értéket egy képlet alapján számolják • több futatás ugyanazt a sorozatot adja, ha a képlet belső paramétere ugyanaz – stdlib.h-ban van deklarálva
32
Véletlen számok generálása • void srand(unsigned int seed); – a rand() által képlet paraméterét állítja be – stdlib.h-ban van deklarálva • long int time(time_t *timer); – 1970 január 1 óta eltelt másodpercek számát adja vissza – a paraméter által mutatott helyre eltárolja ezt az értéket – NULL esetén nincs tárolás – time.h-ban van deklarálva – mivel ez minden futásnál más ez hozza be a véletlent 33 a rendszerbe
Véletlen számok kiíratása 0-99- ig #include <stdio.h> #include <stdlib.h> #include int main(void) { srand( (unsigned)time( NULL ) ); printf("%d\n",rand()%100); printf("%d\n",rand()%100); printf("%d\n",rand()%100); printf("%d\n",rand()%100); return 0; }
34
Véletlen számok intervallumának meghatározása • A véletlen szám előállítási feladat általános megfogalmazása: állítsunk elő véletlen számot [min, max] intervallumban prec tizedes jegy pontossággal – zárt intervallum • Lépésenkénti levezetés: – rand() [0, 215-1] – rand()%a [0, a-1] – rand()%a+b [b, a-1+b] – (rand()%(a*10c))/10c+b [b, a-10-c+b] • c = prec, b = min, a = max + 10-prec - min 35
#include <stdio.h> #include <stdlib.h> #include #include <math.h> int main(void) { // the sum of four random numbers in the [2.123, 5.123] // intervalum with 1 digits precision int prec=1, big; double min=2.123, max=5.123; double a, b=min, c=prec, sum, tomb[4]; big=(int)pow(10, c); a = max + 1./ big - min; srand((unsigned)time(NULL)); tomb[0]=fmod(rand(), (a*big))/big+b; // eg.: 2.123, 2.923, 5.123 tomb[1]=fmod(rand(), (a*big))/big+b; tomb[2]=fmod(rand(), (a*big))/big+b; tomb[3]=fmod(rand(), (a*big))/big+b; sum = tomb[0]+tomb[1]+tomb[2]+tomb[3]; printf("The sum of the four random number: %.2lf\n", sum); return 0; }
36
Programozás I. C nyelv
6. előadás Függvények Veszprémi Egyetem Heckl István, [email protected]
1
Bevezetés • definíció: részprogram, amely utasítások egy sorozatából áll – függvény inputja: a függvény paraméterek – függvény outputja: visszatérési érték • Használat: – ismétlődő feladatok végrehajtása – a program szegmentálása
2
Függvények • A C nyelv függvényei megfelelnek: – a Fortran szubrutinjainak illetve függvényeinek – vagy a Pascal eljárásainak illetve függvényinek • A C nyelv alapvető szervezési egysége a függvény – a függvények azonos hierarchia szinten állnak – függvényben függvényt nem lehet létrehozni – a program maga is egy függvény (main)
3
Függvények • A függvény jó absztrakciós eszköz a programok tervezésénél (top-down stratégia) – a kiindulási feladatot részfeladatokra bontjuk, a részfeladatokat függvényekkel valósítjuk meg – a main függvény meghívja a részfeladatokat megvalósító függvényeket – a részfeladatokat tovább bonthatjuk • ökölszabály: egy függvény egy oldal
4
Függvény megírása • Egy függvény, amely egy argumentumot fogad el, megszorozza kettővel, majd visszaadja az eredményt int multByTwo(int x) { int retval; retval = x * 2; return retval; }
5
Függvény használata
• Végrehajtási sorrend: a1, a2, b1, b2, b3, a3, a4, a5 – a3 a legyen egyenlő művelet • Valójában printf is függvény – egy függvény tekinthető függvénynek, vagy elemi utasításnak
6
Függvény definíció [tárolási osztály] [típus] függvényNév([formális parméter lista]) // függvény fej { utasítás1; // függvény törzs utasítás2; ... }
7
Tárolási osztályok • extern (alapértelmezett): a függvény más fájlokból is elérhető • static: a függvény csak abban a fájlban érhető el, amiben definiálták – jelentés változóknál: a változó csak a program elején inicializálódik (újrainicializálás nem törli a változó értékét)
8
Static lokális függvényváltozó #include <stdio.h> #include <math.h> void cube(int para) { static int count = 1; printf("Call #%d the cube is: %lf\n", count++, pow(para, 3)); } void main() { for (int idxI=0; idxI<4; idxI++) cube(idxI); } 9
Static lokális függvényváltozó • Output static változó esetén: Call #1the cube is: 0 Call #2 the cube is: 1 Call #3 the cube is: 8 Call #4 the cube is: 27 • Output nem static változó esetén: Call #1the cube is: 0 Call #1 the cube is: 1 Call #1 the cube is: 8 Call #1 the cube is: 27 10
Visszatérési érték • A függvény fejben a visszatérési érték típusát kell megadni • return utasítás utáni kifejezésben a visszatérési értéket kell megadni – a kifejezés és a visszatérési érték típusának illeszkednie kell (implicit típuskonverzió lehetséges)
11
Visszatérési érték • A visszatérési érték típusa lehet: – primitív adattípus – mutató – void (a return után nincs kifejezés) – referencia (c++) • Ha több értéket szeretnénk visszaadni, akkor használjunk: – rekord visszatérési értéket – címszerinti paraméter átadást
12
Paraméterek • A függvény inputjai • A zárójelek használata akkor is kötelező, ha nincs paraméter • definíció: típus1 név1, típus2 név2, ... – a paraméterek típusait egyenként kell megadni • Függvény definíciónál formális, függvény hívásnál aktuális paraméter listáról beszélünk
13
Paraméterek • Paraméterátadás: érték szerint – a paraméter értéke a stack-be másolódik – a függvény a másolaton dolgozik – a paraméter változása a függvényben nem változtatja meg a külső értéket • Paraméter egyeztetés: – a függvény paramétereket sorrendjük alapján azonosítjuk • az n. formális paraméter veszi fel az n. aktuális paraméter értékét – ha a formális és aktuális paraméter típusa nem 14 egyezik, akkor implicit típuskonverzió jön létre
Példa void demo(int oldal, int terulet, int kerulet) { printf("oldal: %d, terulet: %d, kerulet: %d\n", oldal, terulet, kerulet); } void main() { int oldal = 6, area = 15; demo(oldal, area, 28.12); /* a fuggvényhívásnál és a fuggvényfejben a változo neveknek nem kell megegyezni */ // kerulet: 28, a tipuskonverzio miatt 15 }
Paraméterek • Paraméterátadás: cím szerint – cím szerinti értékátadás mutató érték szerinti átadásával valósítható meg • a formális paraméter listában mutatót kell definiálni '*'-al • az aktuális paraméter listában mutatót kell létrehozni, általában '&'-el • a függvényben a mutatott értékre kell hivatkozni '*'al – a mutatóval az eredeti változó memória címére hivatkozunk, így amikor módosítjuk, az eredeti változót módosítjuk 16
#include <stdio.h> void proba(int ertek, int* cim) { // hasznalatkor indirekcio operator ertek = 13; *cim = 12; } void main() { int korte = 6, alma = 5; proba(korte, &alma); // hivasnal cimkepzo operator printf("korte: %d, alma:%d\n", korte, alma); } • Output: korte: 6, alma: 12 17
Példa
18
Függvények változói • Paraméterek • Saját lokális változók – auto, register minden hívásnál újra felépül – static egyszer épül fel, értéke megmarad • Globális változók – sértik a strukturált programozás elvét – függvényeken kívül definiáltak
19
Deklaráció • A függvény feje ;-vel a végén: [tárolási osztály] [típus] függvényNév([formális parméter lista]); – prototípusnak is hívják – a formális paramétereknek csak a típusát kötelező megadni deklaráció esetén – definíció: a függvény feje és teste • Használat előtt a függvényt deklarálni vagy definiálni kell – a definíció egyúttal deklaráció is • Ha csak definíció létezne, akkor két egymást hívó függvényt nem lehetne írni • Hibalehetőség: a definíció változtatásakor a deklarációt 20 nem változtatjuk
Deklaráció double variancia() { double a = szoras(); return a*a; } double szoras() { … return result; } • hibaüzenet: undefined symbol szoras • megoldás: – felcserélni a két függvény sorrendjét – a fájl elejére másolni: double szoras();
21
Függvényhívás • függvényNév([aktuális paraméter lista]) – a paraméterek számának és típusának a függvény definíciójánál és a hívási helyen egyezni kell • c++-ban létezik default paraméter • '...' = elipsis, változó paraméterszám • A függvény indításakor az utasításmutató a stack-ben tárolódik – a függvény befejezése után az utasításmutató kiolvasódik a stack-ből – a program következő utasítással folytatódik 22
Függvényhívás • Nyomkövetés: – step into: belép a függvénybe, F11 – step over: a függvényt mint egy utasítás hajtja végre, F10 – step out: kilép a függvényből, shift+F11 • Ha a függvény visszatérési értéke nem void, akkor a függvényhívás általában: változóNév = függvényNév([argumentum lista]); – változóNév és a visszatérési érték típusának illeszkednie kell 23
Verem (stack) elv fv1típus fv1(fv1par){ … } fv2típus fv2(fv2par){ fv1(…); } void main(){ fv2(…); … }
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
main elindul utasítás fv2(…) Visszatérési cím verembe Paraméterek fv2-höz verembe fv2 elindul utasítás f1(…) Visszatérési cím verembe Paraméterek fv1-hez verembe fv1 lefut fv1 paraméterek megsemmisülnek fv1 visszatérési értéke veremből fv2 folytatódik fv2 paraméterek megsemmisülnek fv2 visszatérési értéke veremből 24 main folytatódik
Több forrás fájl • Miért használunk több forrás fájlt? – a logikailag összetartozó függvények kerülnek egy fájlba – több ember dolgozik a programon – gyorsítsuk a fordítást
25
Több forrás fájl • Előfeldolgozó: (precompile) nev1.c, header1.h, header2.h, ... → nev1full.c nev2.c, header5.h, header6.h, ... → nev2full.c • Fordítás: (compile) nev1full.c → nev1.obj nev2full.c → nev2.obj • Szerkesztés: (link) nev1.obj, nev2.obj → projektNev.exe
26
IDE • Integrált fejlesztői környezet (Integrated development enviroment) • Szövegszerkesztő, fordító és linker együtt • Projekt fájl tartalmazza: – a fordítandó forrás fájlok nevei – a fordítási opciókat
27
Header file • Egy fájl összes deklarációját érdemes egy header fájlban összegyűjteni • Ha egy fájl egy header fájl beinkludálásával kezd, akkor később hivatkozhat az összes abban deklarált függvényre • Példa: #include "c1.h" – ” ” esetén az aktuális könyvtárban keresik először c1.h-t, utána rendszerkönyvtárban – <> esetén csak rendszerkönyvtárban 28
Előfeldolgozási direktívák • #include "c1.h" – bemásolja c1.h-t • #define token1 token2 – ahol az token1 előfordul a forrásban helyettesíti token2-el – nincs ; a sor végén • #define azonosító(a1,…an) kifejezés – paraméteres makró hívás • #undef azonosító – megszűnik a define hatása
29
Feltételes fordítás • #if állandó_kifejezés – ha kifejezés igaz, akkor a következő részt lefordítja • #ifdef azonosító – ha van ilyen azonosító, akkor a következő részt lefordítja • #ifndef token1 – ha token1 nincs definiálva, akkor a következő részt lefordítja • #elif állandó_kifejezés – else-if megfelelője • #else • #endif – előfeldolgozói feltétel lezárása
30
Header file felépítés • Fájl név: c1.h #ifned C1_H #define C1_H deklaráció1; deklaráció2; ... #endif • Megszünteti az egymásra hivatkozó header fájlok okozta hibát (already defined…)
31
Az extern kulcsszó • Segítségével a globális változókat láthatóvá tehetjük más fájlokban is • A definiálás helyén – ne használjuk az extern kulcsszót – adjunk kezdő értéket • Egyéb fájlokban – használjuk az extern kulcsszót – ne adjunk kezdő értéket
32
Rekurzív függvények • definíció: önmagát meghívó függvény • Kölcsönös rekurzió: a() hívja b()-t, b() hívja a()-t • Megállási feltétel nélkül a rekurzió stack overflow error-t okoz • Általános felépítés: int fv(int n){ // ... kód if (megállási feltétel) return 1; // ... kód a = fv(n-1); // rekurzió // ... kód } 33
Rekurzív függvények #include <stdio.h> int faktor(int para) { int result; // f.para.1 if (para<=1) return 1; // f.para.2 temp = faktor(para-1); // f.para.3 result = para * temp; // f.para.4 return result; //f.para.5 } void main() { int res; // m1 res = faktor(3); // m2 printf("faktor(3)=%d\n", res); // m3 }
34
Rekurzív függvények • Végrehajtási sorrend: m1, f.3.1, f.3.2, f.2.1, f.2.1, f.1.1, f.1.2, f.2.3, f.2.4, f.2.5, f.3.3, f.3.4, f.3.5, m2, m3 • Az egyes hívásokat különböző függvényekként képzeljük • Az utolsó szinten már háromszor hívtuk meg a faktor függvényt, de még egyik hívás se zárult le – amikor faktor(1) lefutott faktor(2) folytatódik faktor(1) eredményének másolásával, f.2.3 – ha nehezen tudjuk elképzelni a program futását, akkor tekintsük először faktor(1) futását, aztán faktor(2)-t, ... – nyomkövetéssel ellenőrizzük milyen sorrendben hajtódnak végre a program sorok 35
Programozás I. C-nyelv
7. előadás Sztringek és sztringműveletek Veszprémi Egyetem Heckl István, [email protected]
1
Sztringek • definíció: olyan karaktersorozat, amelynek a hossza speciálisan meghatározott – pascal: egy karakter tömb 0-s indexű eleme tárolja a sztring méretét – C: egy karaktertömbben egy 0-t tartalmazó elem jelöli a sztring végét • A C nyelv nem rendelkezik beépített sztring típussal – a sztring egy elemi típusból, karakterekből áll • Egydimenziós karaktertömböket használunk sztringek tárolására 2
Sztringek tárolása • A C nyelv így tárolja a "C-nyelv" sztringet:
• A sztring jellemzői: – hossza: 7 • a 0 értéket nem számoljuk a hosszhoz – szükséges tömb méret: 8 • helyet kell foglalni a 0 értéknek is • n hosszú sztringnek n+1 nagyságú tömb kell – az utolsó karakter indexe: 6 – 0 indexe: 7
3
Sztringek inicializálása karaktertömbbel char st1[10]={'A', 'L', 'M', 'A', '\0' }; char st2[] = {'A', 'L', 'M', 'A', 0 }; • Az st1 sztring számára 10 byte helyet foglal a fordító és az első 5 byte-ba bemásolja a megadott karaktereket – a második 5 byte nem használt – ügyelni kell, hogy az utolsó karakter a 0 legyen • Az st2 pontosa annyi byte hosszú lesz, ahány karaktert megadunk az inicializációs listában – a 0 értéket kétféleképpen is megadhatjuk
4
Sztringek inicializálása sztringliterállal char st1[10]="Alma"; char st2[]="Alma"; • Előny: – áttekinthetőbb – a fordító helyezi el a sztringeket lezáró 0 bájtot • Visual C 7.0-ban a sztring literálok maximális mérete 2 kByte
5
Karaktermutató inicializálása char const *ps = "Gamma"; • A fordító az inicializáló sztringet eltárolja a sztringliterálok számára fenntartott területen, a sztring kezdőcímével inicializálja a létrejövő ps mutatót • A sztring karakterei akkor se módosíthatóak, ha nem használjuk a const típusmódosítót • A ps értéke a későbbiekben megváltoztatható ps="iota"; // "iota" string literal – mutató értékadása történik, a ps felveszi az új sztring konstanscímét – tömb szintaktikánál ez nem működik 6
Sztring literálok összefűzése • Szintaxis: "string1" "string2" – a fenti kifejezés ekvivalens "string1string2"-el – a két sztring között lehet több whitespace is – vezérlő karakter értelmezése a részsztring végén befejeződik • Példák: char str[] = "This is " "a test"; char str[] = "This is " "a nice test"; // line concatenation could have been used char s1[] = "\01" "23"; 7 char s2[] = "\0123"; //s1 !=s2
Hivatkozás a sztring karaktereire • Történhet: – tömb szintaktikával (gyakoribb) – mutató szintaktikával (később vesszük) • Példa: char st1[10]="Alma"; printf("a masodik betu: %c\n", st[1]); printf("a harmadik betu: %c\n", *(st+2)); st1[4]='k'; st1[5]=0; // don't forget printf("az uj string: %s", st1); // Almak 8
Tipikus hibák • Lezáratlan sztring: char s[] = {'a', 'b', 'c'}; printf("%s", s); • Értékadás karaktertömbök között: char st1[]="haho", st2[]="bruhaha"; st2=st1; • Címképző operátor használata scanf-nél: char s[222]; scanf("%s", &s);
9
Sztringműveletek • Mivel sztring alaptípus nem létezik, azt kezelő operátorok sem definiáltak (értékadás, összehasonlítás, stb.) • A sztring kezelés a string.h deklarációs állomány függvényeivel megvalósítható
10
Sztringműveletek Főbb műveletek sztring beolvasása sztring kiírása értékadás hozzáfűzés hossz lekérdezése sztringek összehasonlítása
Függvény sscanf, gets sprintf, puts strcpy strcat strlen strcmp
11
gets függvény • Szintaxis: char* gets(char* buffer); • Egy sort olvas be a szabványos inputról, majd azt az argumentumban megadott buffer mutató által kijelölt területre másolja • Az új sor (\n) karakter a (\0) (EOS) karakterrel helyettesítődik • A visszatérési értéke sikeres olvasás esetén a megadott puffer címe, hiba esetén NULL • scanf nem alkalmas sor beolvasására, mert a szóközt és a tabulátort a sztring végének tekinti 12
puts függvény • Szintaxis: int puts(const char* string); • Az argumentumban megadott sztringet a szabványos kimenetre írja – scanf-el lehet kiírni olyan sztringet, amely whitespacet tartalmaz • A sztring megjelenését automatikusan a '\n' (új sor) karakter kiíratása követi • A függvény egy nem negatív szám visszaadásával jelzi a string sikeres kiíratását
13
Példa #include <stdio.h> void main(void) { char line[81]; // buffer big enough printf("Input a string: "); gets(line); printf("The line entered was: "); puts(line); } • Output: Input a string: Hello Nagykanizsa! The line entered was: Hello Nagykanizsa!
14
sprintf, sscanf • Szintaxis: – int sprintf(char* out, const char* format [, argument] ...); • a kimenet az out karakter tömbbe kerül – int sscanf(const char* in, const char* format [, argument ] ...); • az in karakter tömbből olvassuk az adatokat
15
Példa az sscanf és a sprintf függvényekre #include <stdio.h> void main() { char adat[3][16]={"16.64","3.7344","2333.23"}; double e; int i; for(i=0;i<3;i++) { sscanf(adat[i],"%lf",&e); e+=0.5; sprintf(adat[i],"%ld",(long)e); } for(i=0;i<3;i++) printf("%d.\t %s\n",i,adat[i]); } 16
strcpy függvény • Szintaxis: char* strcpy(char* dest,const char* src); • Az src sztring karaktereit másolja az dest sztringbe a lezáró EOS ('\0') karakterrel együtt • A felülírt sztringre mutató pointerrel tér vissza
17
strcat függvény • Szintaxis: char* strcat(char* dest, const char* src); • Az dest sztringhez fűzi az src sztringet, és az összefűzött sztringre mutató pointerrel tér vissza – normál működés során dest és a visszatérési érték megegyezik
18
Példa #include <string.h> #include <stdio.h> void main() { char string[80]; strcpy(string, "Hello world from "); strcat(string, "strcpy "); strcat(string, "and "); strcat(string, "strcat!"); printf("String = %s\n", string); }
• Output: String = Hello world from strcpy and strcat! 19
strchr függvény • Szintaxis: char* strchr(const char* str1, int c); • Megkeresi a c változóban tárolt karakter első előfordulási helyét az str1 sztringben, és az erre mutató pointerrel tér vissza • A NULL jelzi, hogy a karakter nincs benne a sztringben
20
strrchr függvény • Szintaxis: char* strrchr(const char* str1, int c); • Megkeresi a c változóban tárolt karakter utolsó előfordulási helyét az str1 sztringben, és az erre mutató pointerrel tér vissza • A NULL jelzi, hogy a karakter nincs benne a sztringben
21
#include <string.h> #include <stdio.h> void main(void) { int ch = 'e'; char string[] = "Hello Melo!"; char *pdest; int result; printf("String to be searched: %s\n", string); printf("Search char: %c\n", ch); pdest = strchr(string, ch); result = pdest - string; if(pdest != NULL) printf("First %c found at position %d\n\n", ch, result); // result 1 else printf("%c not found\n"); pdest = strchr(string+result+1, ch); // second occurance }
22
strdup függvény • Szintaxis: char* strdup(const char* str); • Memóriát foglal és ide másolja az str sztringet • A visszatérési érték a másolatra mutató pointer illetve NULL ha nem sikerült a helyfoglalás • A lefoglalt memóriát fel kell szabadítani – free() függvény, lásd később
23
strlen függvény • Szintaxis: size_t strlen(const char* str); • A sztring hosszát adja meg a sztringet záró EOS karakter nélkül • stddef.h gyakran használt típusukat definiál – lásd typedef parancs – size_t megfelel unsigned int-nek • változó méretének típusa – ptrdiff_t megfelel signed int-nek • mutatók különbségének típusa 24
strlwr függvény és strupr függvény • Szintaxis: char* strlwr(char* str); – az str sztring angol nagybetűit kicsire cseréli – az eredeti tartalom elveszik – a visszatérési érték str • Szintaxis: char* strupr(char* str); – az str sztring angol kisbetűit nagyra cseréli – az eredeti tartalom elveszik – a visszatérési érték str
25
#include <string.h> #include <stdio.h> #include <malloc.h> void main(void) { char string[100] = "The String to End All Strings!"; char *copy1, *copy2; copy1 = _strlwr(_strdup(string)); copy2 = _strupr(_strdup(string)); printf("Mixed: %s\n", string); printf("Lower: %s\n", copy1); printf("Upper: %s\n", copy2); printf("The length is: %d\n", strlen(string)); free(copy1); free(copy2); }
• Output: Mixed: The Lower: the Upper: THE The length
String to End All Strings! string to end all strings! STRING TO END ALL STRINGS! is: 30
26
strset függvény • Szintaxis: char* strset(char* str, int c); • A függvény a c -ben tárolt karakterrel feltölti a sztring minden karakterét • A visszatérési érték az str-re mutató pointer • Hibalehetőség: ha str korábban nem inicializált, vagyis nincs 0 lezáró karakter, akkor futás közben memória hiba léphet fel
27
Példa #include <string.h> #include <stdio.h> void main(void) { char string[] = "Fill the string with " "something"; printf("Before: %s\n", string); strset(string, '*'); printf("After: %s\n", string); }
• Output: Before: Fill the string with something After: ******************************
28
strcmp függvény • Szintaxis: int strcmp(const char* str1, const char* str2); • Két sztringet hasonlít össze lexikorgafikusan – az összehasonlítás alapja az ascii kód – a rövidebb szavak vannak előbb • A visszatérési érték: – negatív, ha az str1<str2 – nulla, ha str1==str2 – pozitív, ha az str1>str2 • Az stricmp függvény két sztringet hasonlít össze az angol kis/nagybetűk megkülönböztetése nélkül 29
strrev függvény • Szintaxis: char* strrev(char* str); • Az strrev függvény megfordítja az str sztringet az EOS karaktert a helyén hagyja • A visszatérési érték a megfordított str sztringre mutató pointer – a fordítás helyben történik, így str és a visszatérési érték megegyezik – a visszatérési értéket fel lehet használni, hogy összefűzzünk több függvényt
30
Példa #include <string.h> #include <stdio.h> #include <malloc.h> void main(void) { char string[100], *copy; int result; printf("Input a string and I will tell you if it is a palindrome:\n"); gets(string); result = stricmp(string, copy=_strrev(_strdup(string))); 31
if(result == 0) printf("The string \"%s\" is a palindrome\n\n", string); else printf("The string \"%s\" is not a palindrome\n\n", string); free(copy); }
• Output: Input a string and I will tell you if it is a palindrome: Able was I ere I saw Elba The string "Able was I ere I saw Elba" is a palindrome 32
strspn függvény • Szintaxis: size_t strspn(const char* s1,const char* s2); • A függvény az s1 sztring első olyan karakterének pozíciójával tér vissza amely az s2 sztringben nem található – megadja a leghosszabb olyan s1 prefix hosszát, amelynek karakterei s2 beliek
33
strcspn függvény • Szintaxis: size_t strcspn(const char* s1,const char* s2); • A függvény az s1 sztring első olyan karakterének pozíciójával tér vissza amely az s2 sztringben megtalálható – megadja a leghosszabb olyan s1 prefix hosszát, amelynek karakterei nem s2 beliek
34
#include <string.h> #include <stdio.h> void main(void) { char string[] = "cabbage"; int result; result = strspn(string, "abc"); printf("The portion of '%s' containing only a, b, or c is %d bytes long\n", string, result); result = strcspn(string, "bge"); printf("The portion of '%s' not containing b, g, or e is %d bytes long\n", string, result); }
• Output: The portion of 'cabbage' containing only a, b, or c is 5 bytes long The portion of 'cabbage' not containing b, g, or e is 2 bytes long
35
strstr függvény • Szintaxis: char* strstr(const char* str1,const char* str2); • Az str2 sztring első előfordulási helyét keresi az str1 sztringben, a visszatérési érték az erre a helyre mutató pointer • Ha az str2 nem található az str1-ben NULL értékkel tér vissza
36
#include <string.h> #include <stdio.h> void main() { char str[] = "s t"; char string[] = "It is the 3d milenia"; char *pdest; int result; printf("String to be searched: %s\n", string); pdest = strstr(string, str); result = pdest - string; if(pdest != NULL) printf("'%s' found at position %d\n\n", str, result); else printf("'%s' not found\n", str); }
• Output: String to be searched: It is the 3d milenia 's t' found at position 5
37
strtok függvény • definíció token: nyelvi elem – pl.: szavak a mondatokban • Szintaxis: char* strtok(char* str1,const char* str2); • A függvény az str2 sztringben megadott karaktereket elválasztójeleknek tekintve többszöri hívással feldarabolja az str1 sztringet • Minden visszatérési érték egy-egy tokenre mutató pointer, vagy NULL ha nem darabolható tovább • Minden hívás egy 0 értéket tesz egy token után – str1 elveszik 38
strtok függvény • Az első hívás visszaadja az első tokent, módosítja str1-t és egy belső változóban tárolja azt • A második hívástól kezdve NULL-t kell írni az első paraméter helyére – ekkor a függvény a belső változóból dolgozik – több szöveg párhuzamos elemzése hibát okoz
39
#include <string.h> #include <stdio.h> void main(void) { char* token; char string[] = "A string\tof ,,tokens\nand some more tokens"; char seps[] = " ,\t\n"; printf("Separators: ' ', ',', '\\t', '\\n'"); printf("\n%s\n\nTokens:\n", string); token = strtok(string, seps); // first token while(token != NULL) { printf(" %s\n", token); token = strtok(NULL, seps); /*other tokens*/ } }
40
Output: Separators: ' ', ',', '\t', '\n' A string of ,,tokens and some more tokens Tokens: A string of tokens and some more tokens
41
strncpy függvény • Szintaxis: char* strncpy(const char* str1, const char* str2, size_t maxn); • Ez a függvény a str2 sztringből maximum maxn karaktert másol a str1 sztringbe, az EOS karakter nélkül
42
Példa #include <string.h> #include <stdio.h> void main(void) { char string[100] = "Cats are nice usually"; printf("Before: %s\n", string); strncpy(string, "Dogs", 4); strncpy(string + 9, "mean", 4); printf("After: %s\n", string); }
• Output: Before: Cats are nice usually After: Dogs are mean usually 43
strncat függvény • Szintaxis: char* strncat(const char* str1, const char* str2, size_t maxn); • A függvény az str2 sztringből maxn db karaktert fűz az str1 sztring végéhez
44
Példa #include <string.h> #include <stdio.h> void main(void) { char string[80] = "This is the initial string!"; char suffix[] = " extra text to add to the string..."; printf("Before: %s\n", string); strncat(string, suffix, 19); printf("After: %s\n", string); }
• Output: Before: This is the initial string! After: This is the initial string! extra text to add
45
strnset függvény • Szintaxis: char* strnset(char* s, int ch, size_t n); • A ch változóban tárolt karakterrel tölti fel az s sztring első n darab karakterét • A visszatérési érték az s -re mutató pointer
46
Példa #include <string.h> #include <stdio.h> void main(void) { char string[15] = "This is a test"; printf("Before: %s\n", string); strnset(string, '*', 4); printf("After: %s\n", string); }
• Output: Before: This is a test After: **** is a test
47
string, mint függvény paraméter, és mint visszatérési érték #include <string.h> #include <malloc.h> #include <stdio.h> char* code(char* text, char* orig, char* replaced) { char* result = strdup(text), *pFound; int len = strlen(text), pos; for (int idxI=0; idxI
void main() { char orig[]="original", c1[]="ig", c2[]="uk", *coded, *decoded; // c1 and c2 should be a full alphabet printf("The original string: %s\n", orig); coded = code(orig, c1, c2); // i->u, g->k printf("The coded string: %s\n", coded); decoded = code(coded, c2, c1); // u->i, k->g printf("The decoded string: %s\n", decoded); free(coded); free(decoded); }
• Output: The original string: original The coded string: orukunal The decoded string: original
49
ctype függvények • Lásd: isalnum, isascii, isupper, ...
50
Programozás I. C-nyelv
8.előadás Mutatók Veszprémi Egyetem Heckl István, [email protected]
1
Mutatók • definíció: mutató (pointer) egy olyan változó, amely más objektumok címét tárolja • A mutató operátora: * – mutató deklaráció – índirekció: a mutatott érték • Egy mutató hossza 4 bájt (4GB címezhető) • Speciális érték: NULL – logikailag hamisat jelent • Példa: int* mutato=NULL; 2
Mutató deklaráció • [tárolási osztály] mutatottTípus* pNev1=NULL; • [tárolási osztály] mutatottTípus *pNev1 =NULL, *pNev1 =NULL, nev3; • A *-t általában a típushoz illesztjük – szintaktikailag helyes: int* a; int * b; int *c; int (*d); – deklarációnál minden mutató változó előtt szerepelni kell a *-nak • ha egy sorban csak egy változót deklarálunk akkor a típushoz szokás illeszteni a *-t • ha többet, akkor a változóhoz • A mutató változókat általában nevűkben is megjelöljük 3 • A mutatókat mindig inicializáljuk
Címképző operátor • A címképző operátor az utána szereplő változó címét adja vissza – segítségével értéket adhatunk egy mutatónak • Egy változó címét egy mutatóban tárolhatjuk • Ezután a változót kétféleképen érhetjük: – a változó nevén keresztül – mutatón keresztül (egy változóra több mutató is mutathat) • Példa: int *mutato, idxI=7; mutato = &idxI; printf("value of the pointer:%p", mutato);4
A mutató és mutatott változó értéke • A mutató is változó, értékére ugyanúgy a nevével hivatkozunk, mint egyéb változóknál – a mutató értéke egy memória cím • Általában a mutatott értéket akarjuk használni és nem a mutató értékét • A mutató által mutatott értékre az índirekció operátorával hivatkozunk, *-t írunk a mutató neve elé – először a mutató értéke olvasódik ki – azután rögtön a mutatott érték
5
A mutató és mutatott változó értéke int idxI=7, *pointer=&idxI; printf("&pointer=%#x, pointer=%#x, *pointer=%d\n", &pointer, pointer, *pointer); • Output: &pointer=0x12fec8, pointer=0x12fed4, *pointer=7
6
A mutatók veszélyei • A mutatókat használhatjuk arra, hogy egy változót többféleképen elérjünk – ha a mutató nem egy létező változóra mutat és úgy próbáljuk használni, akkor futási hibát kapunk • Védekezés: ha egy mutatót nem használunk, vagy az általa mutatott változó megszűnik, akkor a mutató értékét állítsuk NULL-ra – a mutató használata előtt ellenőrizzük, hogy értéke NULL-e if (p) *p=32;
7
#include <stdio.h> void main() { int x=7, y=3; int *pX=&x, *pY=&y;//mutato valtozik printf("x=%d *pX=%d\n", x, *pX); x=12; printf("x=%d *pX=%d\n", x, *pX); *pX=1; // mutatott ertek valtozik printf("x=%d *pX=%d\n", x, *pX); pY=pX; // mutato valtozik printf("y=%d *pY=%d\n", y, *pY); } • Output: x=7 *pX=7 x=1 *pX=1
x=12 *pX=12 y=3 *pY=1
8
Címszerinti paraméterátadás lépéseinek demonstrálása a main függvényben #include <stdio.h> void fg(int* pX) { *pX=4; } void main() { int x=7; fg(&x); int* pX=&x; // függvényhívás *pX=4; // függvényen belüli értékváltoztatás pX=NULL; // kilépés a függvényből printf("x=%d", x); // a megváltozott érték }
9
Többszörös índirekció • Mivel a mutató is változó, van címe, így azt tárolni tudjuk egy mutatóban • Mutatóra mutató mutatók deklarálása ugyanúgy történik, mint az egyszerű mutatók deklarálása: – mutatottTípus* ppNev1; • habár a mutatott típus nyelvtani egységnek számít nem szabad zárójelbe rakni – példa: int** ppNev1; • Az índirekció mélysége növelhető
10
Példa #include <stdio.h> void main(){ double x; double* p; double** pp; x=7; p=&x; pp=&p; printf("x+*p+**pp=%lf\n", x+*p+**pp); } • Output: x=21
11
typedef • A typedef paranccsal egy típust új névvel láthatunk el – nem hoz létre változót • Lehet lokális vagy globális hatókörű – a parancs helyétől a hatókör végéig használható • Szintaxis: typedef tipusNev ujTipusNev; • Példa: typedef int egesz; void main() { egesz a=12; } 12
typedef • typedef-el egyszerűsíthetjük a pointer deklarációkat • Példa: typedef char* cptr; /* karakterre mutató pointer */ typedef cptr* cpptr; /* cptr típusú változóra mutató pointer */ cpptr myArray;
13
Mutató aritmetika Művelet:
Eredmény:
pointer + int
pointer
pointer - int
pointer
pointer - pointer
int
• p+1, a p+2, stb. címek az adott objektum után elhelyezkedő első, második, stb. objektumok címét adják – nem pedig az adott címet növelik egy bájtnyival – az eredmény típusa p1 típusából adódik • p1-p2 megadja, hogy a két cím között hány objektum helyezkedik el – p1 és p2 típusának egyeznie kell
14
Dinamikus változók • definíció: olyan változó, amely tárolásához szükséges helyet futás közben foglaljuk le és egy mutatón keresztül érjük el – általában nagyméretű változók (tömbök, rekordok) esetében használjuk – futási időben derül ki, hogy mekkora tömbre van szükség, vagy hogy az adott rekordra szüksége van-e egyáltalán • Ha már nincs szükségünk a lefoglalt területre, azt fel kell szabadítani és a mutatóját le kell nullázni
15
Dinamikus változók • Terület lefoglalása: – használjuk a malloc.h vagy stdlib.h header fájlt – szintaxis: void* malloc(int területByteban); – tömbnél területszámolás: sizeof(típus)*tömbMéret – a visszatérési értéket konvertálni kell a megfelelő mutató típusra – ellenőrizzük, hogy sikerült-e a helyfoglalás • Terület felszabadítása: – free(p); p=NULL; – hiányában hibát nem kapunk, de fel nem szabadított 16 területet másra nem használhatjuk
Példa #include <stdio.h> #include <malloc.h> #include <stdlib.h> void main() { int x=7, y=3; int *p; p = (int*)malloc(sizeof(int)); if (p==NULL) exit(-1); *p=x+y; printf(" Az összeg: %d\n",*p); free(p); }
17
Mutatók és tömbök kapcsolata • Statikus tömb: mérete konstans kifejezéssel adott, vagyis már fordítási időben ismert – az eddig használt tömb • Dinamikus tömb: mérete futási időben dől el, külön eljárással kell számára helyet foglalni • Egy mutató dinamikus tömbként is használható – valójában a tömbműveletek vannak mutató műveletekre visszavezetve – tömb és mutató között szoros a kapcsolat, de nem ekvivalensek – szintaktikailag nincs különbség azon mutató között, amely egy objektumra és amelyik egy tömbre mutat
18
Mutatók és tömbök kapcsolata • Definiáljunk egy 10 elemű egész vektort: int a[10]; • 'a' egy konstans mutatónak tekinthető • Az a[4] kifejezés ekvivalens az *(a+4) -el – a[0] = *a – az összeadás mutató aritmetikával történik
19
Mutatók és tömbök kapcsolata #include <stdio.h> #include <stdlib.h> void main() { const int n=4; int stomb[n], *dtomb=NULL, idxI; dtomb = (int*)malloc(sizeof(int)*n); for (idxI=0; idxI
Különbségek a statikus és dinamikus tömbök között • A statikus tömb mérete ismert, a dinamikusé nem int a[10]; int *b=a; // sizeof(a) = 40 // sizeof(b) = 4 // size of a pointer • A címképző operátort alkalmazva statikus tömbre ugyanazt a címet kapjuk, mint a tömb címe, dinamikus tömbre alkalmazva más címet kapunk – a statikus tömb címe egy pointer, ami dinamikus tömbként használható – a dinamikus tömb címe a dinamikus tömböt reprezentáló pointernek a címe // a == &a == b != &b
21
Különbségek a statikus és dinamikus tömbök között • A statikus tömb címe nem változhat, a dinamikusé igen char *dp="dinamikus", sp[]="statikus"; // sp="uj"; // error dp="uj"; // ok – a dp mutató értéke módosul, ezután az "uj" sztring konstans címére fog mutatni (nem az eredeti dp által mutatott memória tartam íródik felül)
22
Különbségek a statikus és dinamikus tömbök között • Egy dimenziós tömb esetén még nem mutatkozik a különbség a statikus és dinamikus tömb szerkezete között – mindkét esetben ugyanúgy hivatkozunk az elemekre és a memóriában történő elhelyezkedés is hasonló • int** dinamikus; és int statikus[2][3]; két teljesen különböző típus, habár mindkét típust használhatjuk mátrixként – "dinamikus" egy pointer, ami egy pointerre mutat, ami int-re mutat – "statikus" egy 2*3 dimenziós, sorfolytonosan tárolt, egész elemeket tartalmazó mátrix 23
24
// ket dimenzios dinamikus matrix #include <stdio.h> #include <malloc.h> void main() { int** p; int idxI, sorok=2, oszlopok=3; p = (int**)malloc(sizeof(int*)*sorok); for (idxI=0; idxI<sorok; idxI++) p[idxI]= (int*)malloc(sizeof(int)* oszlopok); // use matrix p for (idxI=0; idxI<sorok; idxI++) free(p[idxI]); free(p); p = NULL; }
25
Statikus tömbök indexelése • Deklaráció: int arrayName[max1][max2]…[maxn]; • Hivatkozás egy elemre: arrayName[ss1][ss2]…[ssn] • Ekvivalens az alábbi kifejezéssel: *((arrayName) + (ss1* max2 * max3...*maxn) + (ss2 * max3...*maxn) + ... + (ssn-1*maxn) + (ssn)) – max1 nem része a fenti képletnek • Példa: int a[4][6]; a[3][5] = *(a+3*6+5)
26
Dinamikus tömbök indexelése • Hivatkozás egy elemre: arrayName[ss1][ss2]…[ssn] • Ekvivalens az alábbi kifejezéssel: *(...*(*(arrayName+ss1)+ss2)...+ssn) • Példa: a[3][5] = *(*(a+3) +5)
27
Statikus tömb mint függvényparaméter • int arrayName[max1][max2]…[maxn]; típusú tömb átadható mint: – int arrayName[max1][max2]…[maxn] – int (*arrayName)[max2]…[maxn] – int arrayName[][max2]…[maxn] – int* • hívásnál explicit (int*) típuskonverzió kell • a tömb indexet nekünk kell kiszámítani • A paraméter átadás (a tömb szempontjából) cím szerint történik – a módosult tömb érték a visszatérés után is 28 megmarad
Dinamikus tömb mint függvényparaméter • int*** array; típusú dinamikus tömb csak int*** típusként adható át – az egyes dimenziók maximális értékeit külön paraméterben szokás átadni
29
Tömb mint visszatérési érték • Mutató visszatérési érték megengedett, ami tekinthető dinamikus tömbnek • Statikus tömbök visszaadása nem megengedett – mutató egy statikus tömbre visszaadható
30
Függvények és pointerek kapcsolata • Egy függvény név zárójel nélkül használva, az adott függvényre mutató pointerre konvertálódik – függvény neveket használhatunk paraméterként • típus ellenőrzés itt is végrehajtódik: a visszatérési értéknek és a paraméterek típusainak egyeznie kell – az alábbi kifejezések ekvivalensek • k=strcmp("almafa", "fa"); • k=(*strcmp)("almafa", "fa"); • k=(**strcmp)("almafa", "fa"); 31
#include <stdio.h> void work(int number, long (*function)(int)) { printf("%d", (*function)(number)); } long inc4(int a) { return a+4;} long dec4(int a) { return a-4;} void main() { int k=3; if (k>0) work(12, inc4); else work(4, dec4); }
• Output: 16
32
Konstans mutató és mutatott érték • A const kulcsszó elhelyezkedhet a csillag előtt és után – típus const *a; // a mutatott érték konstans • ekvivalens kifejezés: const típus *a; • *a=7, a[6]=2; // hiba – típus* const a=initValue; // a mutató értéke konstans • a=NULL; // hiba • az inicializáció kötelező – típus const * const a = &b; // a mutatott érték és a mutató is konstans • Függvény deklaráláskor használjuk a const kulcsszót, ha 33 a program logikája indokolja
Mutatók elnevezése • A különböző funkciókat ellátó mutatókat nevükben is különböztessük meg: – mutató mint alias: idxIAlias – mutató mint dinamikus objektum: pVariableName • pl: struct ember *pKovacs; – mutató mint dinamikus tömb: variableNameAr • pl: int* fizetesekAr; – mutató mint link: variableName • egy adatszerkezet (lista, fa) egyik eleméből a másikba mutat • pl: struct faElem *jobb; 34
Egyéb memória kezelő utasítások • void* calloc(int numOfElem, int sizeOfElem); – lefoglal területet és 0-al inicializálja azt – int *p = (int*) calloc(20, sizeof(int)); • void* memcpy(void* dest, void* src, int bajtSize); – memóriában másol – használd a memory.h-t • void* memset(void* dest, char c, int size); – a memórába írja a c karaktert size-szor 35
Univerzális mutató • void* p; // bármilyen típusra mutathat – kivéve const, volatile változóra • Használat előtt a megfelelő típusúra kell konvertálni • Példa: void main() { void* pv; int *pint, i; pv = &i; pint = (int*)pv; } 36
Trükkös mutatók • double (*p2multi)[3]; – mutató egy három elemű tömbre – tömbindexelés operátorának nagyobb a precedenciája, mint az indírekció operátorának – felfogható két dimenziós tömbként is • double* p2multi[3]; – három elemű tömb mutatókból
37
Trükkös mutatók • long* var(long, long); – egy long-ra mutató pointert visszaadó függvény – a függvényhívás operátorának nagyobb a precedenciája, mint az indirekcíóénak • long (*var)(long, long); – mutató egy függvényre, amely long-t ad vissza és két long paramétere van • int (*var[5])(int, int); – 5 elemű pointer tömb, a pointerek int-t visszaadó és 2 int-t fogadó függvényekre mutatnak – függvény tömb nem létezik 38
Trükkös mutatók • double (*var())[3]; – egy függvény visszaad egy pointert egy 3 elemű double tömbre – statikus tömb visszaadása nem lehetséges • typedef void (*PVFN)(); – egy mutató egy void-t visszaadó függvényre
39
Trükkös mutatók • unsigned int *(* const *name[5][10]) (void); – 5*10-es statikus pointer tömb, a pointerek konstans pointerekre mutatnak, amelyek olyan függvényekre mutatnak, amelyek unsigned int*-t adnak vissza • char *(*(*var)())[10]; – var egy pointer egy olyan függvényre, amely egy 10 elemű tömbre mutató pointert ad vissza, ahol az elemek char-ra mutató pointerek
40
Trükkös mutatók int t[]={1,2,3,4}, *p=t, n=1, k; k=p[n]; k=n[p]; /* correct and equivalent with the previous line */
41
Programozás I. C nyelv 9. előadás Struktúra, union, enum, bit mezők Veszprémi Egyetem Heckl István, [email protected]
1
Bevezetés • definíció struktúra: több tetszőleges típusú objektum együttese – hívják rekordnak is • A struktúrát alkotó objektumok elnevezése: – mező – adattag • Struktúra változó létrehozása két lépésben: – típus definíció – változó deklaráció
2
Struktúra típus definíció • Szintaxis: struct struktúraNév { típus1 adatTag1; típus2 adatTag2; ... }; • Az új típus neve struct struktúraNév – C++ -ban struktúraNév is típusnév • Pontos vessző zárja le a struktúra deklarációt • Lehet lokális vagy globális hatókörű – a parancs helyétől a hatókör végéig használható
3
Példa // Konyvtárkezelő program struktúrája: struct book { char nev[20]; /* a szerzo neve */ char* cim; /* a mu címe */ int ev; /* a kiadás éve */ float ar; /* a konyv ara */ };
4
Struktúra változó definiálása • Szintaxis: struct struktúraNév változóNév; • Ugyanúgy történik, mint minden egyéb változó definiálás – struct a típusnév része • A struktúra változó definiálása egyúttal adagtagjainak definiálását is jelenti – memória foglalódik le számukra • Példa: struct book macska, gyerek, *cprogP; cprogP=(struct book*)malloc(sizeof(struct book)); 5
Struktúra változó definiálása • A struktúra típus és változó deklaráció összevonható, de nem ajánlott – a struktúra neve el is hagyható • Példa: struct struktúraNév { típus1 adatTag1; típus2 adatTag2; ... } változóNév;
6
Típus definíció struktúrára • Struktúra definiálásra gyakran használják a typedef utasítást – ezután már csak egyetlen azonosítót kell használni változó definiáláskor typedef struct book bookType; // new type bookType virusok; // new variable • A struktúra deklaráció és a typedef egy utasítással is megoldható, így egy azonosítóval kevesebb kell typedef struct book {//book can be omitted int ev; ... 7 } bookType;
Struktúra típus deklaráció • A struktúra definíció egyben deklaráció is • Deklarációkor csak a struktúra típus nevét adjuk meg • Egymásra hivatkozó struktúra definíciók miatt van rá szükség • Szintaxis: struct struktúraTipus; • Példa: struct kutya; struct ember; struct ember { int ID; struct kutyaja* blokki;}; struct kutya { char nev[50]; struct ember* tulaj;};
8
Tagkijelölő operátor • A struktúra adattagjaira a tagkijelölő operátorral '.' hivatkozhatunk • Szintaxis: struktúraVáltozóNév.adatTagNév • Példa: macska.ar=2000; int currentEv=macska.ev; strcpy(macska.nev, "Kedvenceink");
9
Tagkijelölő operátor • Struktúra pointerek adattagjainak elérése: – az indirekció és a tagkijelölő operátor együttes használatával • a tagkijelölő operátornak nagyobb a precedenciája – a -> operátorral • valójában ez csak egy rövidítése az előző módszernek • Példa: (*cprogP).ev = 1998; ps->ar = 24.95; 10
Egymásba ágyazott struktúrák és tömbök • Egy struktúra tartalmazhat tömböket és struktúrákat is – adott adattag eléréséhez több tagkijelölő operátor is kellhet • Egy struktúra tartalmazhat mutatókat más struktúrákra (mutató link) – struct book-nak lehet struct book* adattagja • a könyvek felfűzhetőek egy listába – dinamikus struktúrákkal tetszőleges adatszerkezet megvalósítható, pl.: családfa • elképzelhető, hogy nincsen közvetlen mutató minden struktúrára, hanem egy struktúra mutató linkekből álló úton keresztül érhető el 11 • példa: anyai nagyapa = anyám apja
struct personalItems { struct book noteBook; char usualLogin[100]; char usualPassword[100]; }; void main() { struct personalItems myItems; myItems.noteBook.ar=123; myItems.usualLogin[1]='a'; // [] precedenciaja nagyobb, de a kiértékelés balról jobbra halad bookType books[10]; // rekord tömb books[2].ar=34; } 12
struct kocsi; // struktúra típus deklaráció struct szemely { int id; char nev[200]; int szuletesiIdo; struct szemely *apa, *anya, *gyerek; struct kocsi *sajatK, *szolgalatiK; }; struct kocsi { int id; char tipus[200]; int gyartasiIdo; struct szemely *tulaj, *hasznalo; struct kocsi* pot; 13 };
Helyes kifejezések struct szemely oktato, osztaly[60]; oktato.nev[0] // H oktato.sajatK->gyartasiIdo // 1005 oktato.szolgalatiK->tulaj->nev // VE osztaly[1].apa->apa // gyerek 1 nagyapaja osztaly[5].gyerek->apa // gyerek 5 apja osztaly[7].sajatK->pot->gyartasiIdo osztaly[7].sajatK->pot->tulaj->apa->nev[0]
14
Struktúra függvényparaméter és visszatérési érték • A struktúra függvényparaméter érték szerint adódik át – mutató mező esetén csak a mutató értéke másolódik a mutatott érték nem • két mutató hivatkozik ugyanarra az objektumra • mutató tekinthető dinamikus tömbnek – statikus tömb mező esetén a tömb érték szerint másolódik • statikus tömb paraméter cím szerint másolódik • A struktúra visszatérési érték engedélyezett – szemben a tömbökkel, ahol csak tömbre mutató pointer engedélyezett 15
#include <stdio.h> #include <stdlib.h> typedef struct { char nev[20]; // static char* cim; // dinamic int ev; float ar; } bookType; bookType readBookType(); void printBookType(bookType rec); void main() { bookType virus; virus = readBookType(); printBookType(virus); free(virus.cim); virus.cim=NULL; }
16
bookType readBookType() { bookType rec; printf("Kerem a konyv adatait!\n"); printf("Szerzo:"); gets(rec.nev); rec.cim = (char*)malloc(sizeof(char)*40); printf("Cim:"); gets(rec.cim); printf("Kiadas eve:"); scanf("%d", &rec.ev); //. prefereniája nagyobb a mint az &-e printf("Ar (Ft):"); scanf("%f", &rec.ar); return rec; } 17
void printBookType(bookType rec) { /* Az adotok kiírása: */ printf("\nA konyv adatai\n"); printf("Szerzo:%s\n", rec.nev); printf("Cim:%s\n", rec.cim); printf("Kiadas eve:%4d\n", rec.ev); printf("Ar:%5.2f Ft\n", rec.ar); }
18
Statikus és dinamikus tömb típusú mezők viselkedés paraméter átadáskor void test(bookType rec) { rec.nev[0]='X'; rec.cim[0]='W'; }
19
Struktúra iniciálás • A változó deklaráció után {} között fel kell sorolni az egyes adattagok kezdeti értékeit sorrendben – a lista végéről lemaradt értékek 0-t kapnak • statikus tömb esetén az elemek lesznek 0-k – ha nincs iniciáló lista, akkor az értékek határozatlanok • Példa: struct book noteBook = {"Bevezetes a virusvedelembe", "James Smith", 1999, 2000}; • Struktúra típus deklarálásánál csak a const static egész változókat lehet inicializálni 20
Összetett adattípus iniciálása • Ha az összetett adattípus tartalmaz más összetett adattípust, akkor az iniciálás történhet – strukturálatlanul: • csak egy {} párt használunk • felsoroljuk először az első adattag vagy első elem kezdeti értékét vagy értékeit, aztán a másodikét, stb. – ne felejtsük el, hogy a struktúrák mélyen egymásba épülhetnek – ha az adatszerkezetet fának képzeljük el, akkor fa levelei az egyszerű adattípusok, amelyeknek a mélységi bejárás szerinti sorrendjükben 21 adunk értéket
Összetett adattípus iniciálása – strukturáltan: • minden összetett adattípus kezdeti értékeit {}-el fogjuk közre • jobban érthető • lehetőség van arra, hogy bármely összetett adatot csak részben adjunk meg – {} kell hogy tartalmazzon egy értéket – a többi 0 lesz • egyszerű adattípus kezdeti értéke köré is tehetünk {}-t – vegyes: a felső szinteken strukturáltan adjuk meg az, de például egy statikus mátrixot sorfolytonosan 22 adnunk meg
Példa struct B {int x; int y;}; struct A { struct B myB; struct B myBB; }; struct A myA = {44, 67, 85,}; // coma causes no error struct A myAA = { {44, 67}, {85}};
23
Példa struct B {int z[2]; int y;}; struct A { struct B ar[3]; struct B* point; struct B elem; }; struct A myA = { { {{0, 1}, 200}, {{2, 3}, 100}, {{4, 5}, 500} }, {0}, // {} around primitive type {{66}, 700} };
24
Példa typedef struct { int n1, n2, n3; } triplet; triplet nlist[2][3] = { { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }, // R1 { {9, 8, 7}, {6, 5, 4}, {3, 2, 1} } // R2 }; // OK • A fordító az első { után nlist[0]-nak, akar értéket adni, a második után nlist[0][0]-nak, a harmadik után nlist[0][0].n1-nek • A fordító az első } után tudja, hogy nlist[0][0]-nak az iniciálása kész, a negyedik után, hogy nlist[0]-é kész, az utolsó után, hogy nlist-é kész
25
Példa triplet nlist[2][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, // R1 {9, 8, 7}, {6, 5, 4}, {3, 2, 1} // R2 }; // ERROR • A fordító az első { után nlist[0]-nak, akar értéket adni strukturálatlanul – az első 3 értéknek van kezdeti értéke a többi 0 lesz • A fordító az első } után tudja, hogy nlist[0][0]-nak az iniciálása kész • Ezután nlist[1]-nek, akar értéket adni strukturálatlanul – az első 3 értéknek van kezdeti értéke a többi 0 lesz • Ezután nlist[2]-nek, akar értéket adni, de a mátrix 26 csak két sorból áll, ezért hiba lép fel
Struktúrák használata • Struktúrák mozgatását kerüljük, a struktúrák sorrendjét egy struktúra mutatókat tartalmazó tömbbel tartsuk számon – struktúrák mozgatása, felcserélése, új elem beszúrása, paraméter átadása rengeteg memória művelettel jár • a gyakorlatban használt struktúrák általában nagyok • egy mutató csak 4 bájtos
27
Struktúrák használata 2. lépés
Rekord 1
Rekord 2
Rekord 3
1. lépés
Rekord 4
3. lépés
Rekord 1
structType rekordok[4]; rekordok[3].id=122477133; // hivatkozás
28
Struktúrák használata p1
p2
p3
p4
Rekord 1 Rekord 2 Rekord 3 Rekord 4
structType* rekordpk[4]; for (int idxI=0; idxI<4; idxI++) rekordpk[idxI]=(structType*)malloc(size of(structType)); // helyfoglalás 29 rekordpk[1]->adatTag1=12;
Az union típus • definíció: olyan összetett típus, amelyben a különböző típusú adattagok ugyanazon a memória területen helyezkednek el • Az adattagok felülírják egymást, egyszerre csak egy adattagban lehet helyes érték – kivétel: amikor a union-t arra használjuk, hogy egy egész változót bájtonként érjünk el • Szintaktikája teljesen megegyezik a struct szintaktikájával, csak a union kulcsszót kell használni • union használata nagy memóriaigényű programoknál képzelhető el 30
Az union mérete • Definíció szerint az union mérete legalább a legnagyobb adattípusának a mérete – ha van benne int akkor 4-e osztható – ha van benne double akkor 8-e osztható – ha van benne egy 3 méretű struktúra, nem biztos, hogy osztható 3-al
31
#include <stdio.h> #include <string.h> union utipus { int a; double b; char c[8]; }; void printUnion(union utipus var) { printf("int value=%d\n", var.a); printf("double value=%lg\n", var.b); printf("char[8] value=%s\n\n", var.c); } void main() { union utipus v; v.a=123; printUnion(v); v.b=-12.87; printUnion(v); strcpy(v.c, "haho"); printUnion(v); }
32
Példa kimenet int value=123 double value=-9.5596e+061 char[8] vallue=< int value=-1546188227 double value=-12.87 char[8] vallue== ||úp:> int value=1869111656 double value=-12.8691 char[8] vallue=haho
33
Bit mező • Definíció: olyan egész típusú változó, amely kevesebb bitből áll, mint az alapvető egész típusok • Csak struct, union, class (lásd c++) típusoknak lehet bit mezője • A bit mezők valójában egész típusokban tárolódnak – leggyakrabban: unsigned int – több bitmező is tárolódhat egy egész típusban • az implementáció fordítóként különbözhet
34
Helyfoglalás bit mezők számára visual C 7.0-ban • Egy bit mező pontosan egy egész típusban van • Ha a következő egész típus hossza más, akkor helyet foglal az új alaptípusnak – akkor is ha volt már olyan egész típus és még van benne hely
35
Bit mező • Szintaxis: alapIntTipus név:hossz; – a hossz egy konstans kifejezés – a név kimaradhat, a névtelen bit mezőt nem tudjuk elérni – a 0 hosszú névtelen bit mező hatására a következő bit mező számára már új egész típus lesz foglalva • Példa: struct MyBitField { unsigned int a:1; unsigned int b:0; // anonym bit field unsigned int b:14; };
36
Bit mezők használata • A bit mezők egészekként viselkednek – az érték készletűket a hossz és az előjelesség szabja meg – ha nagyobb értéket rendelünk hozzá egy bit mezőhöz, mint az tárolni tud, akkor csak az utolsó bit lesz figyelembe véve • a szomszédos bit mezők nem íródnak át
37
Bit mezők korlátai • Nem értelmezhető bit mezőre: – tömb – mutató – referencia • A bit mező nem típus, így nem lehet – függvény paraméter – függvény visszatérési érték
38
#include <stdio.h> struct Date { unsigned int nWeekDay : 3; // 0..7 (3 bits) unsigned int nMonthDay : 6; // 0..31 (6 bits) unsigned int : 0; // Force alignment to int next boundary unsigned int nMonth : 5; // 0..12 (5 bits) unsigned int nYear : 12; // 0..4096 (12 bits) }; union IntByByte { unsigned int byte1:8; unsigned int byte12:16; unsigned int byte123:24; unsigned int byte1234:12; // unsigned int byte1234:80; // error: unsigned int is smallerthan 80 bits }; // Date.nYear fg() {return 0;} // error: bit field is not a type 39
void main() { Date myDate; myDate.nWeekDay=4; myDate.nMonthDay=14; myDate.nMonth=11; myDate.nYear=2005; // unsigned int a = &myDate.nMonth; // error: & can not be used for bitfield unsigned int currentDay = myDate.nWeekDay; // bit field regarded as integer int size=sizeof myDate; // try to delete the anonym bit field myDate.nWeekDay=10; // overflow, the first 3 bit is considered, neighbouring fields are not affected IntByByte myInt; myInt.byte1234=4; myInt.byte1234=257; myInt.byte1234=65538; myInt.byte1234=0xa001b506; printf("byte1=%#x, byte12=%#x, byte123=%#x, byte1234=%#x\n", myInt.byte1, myInt.byte12, myInt.byte123, myInt.byte1234); 40 }
Az enum típus • Szintaxis: enum typeName = { value1 [=int1], value2 [=int2], ... valuen [=intn] }; • definíció: a felhasználó által létrehozott típus, amelynek az értékkészlete felsorolással adott – az egyes enum értékek sztringek • nem használunk idézőjeleket • nem kezdődhetnek számmal 41
Az enum típus • Az egyes enum értékekhez int értékek kapcsolódnak • Az int értékek hozzárendelése történhet – a felhasználó által – automatikusan: eggyel nagyobb int érték, mint az előző • az első enum érték automatikus int értéke 0 • Több enum érték is felveheti ugyanazt az int értéket • A #define előfeldolgozó direktívát lehet vele kiváltani – van hatóköre – a fordító értelmezi 42
Az enum típus • Az enum típus szintaxisa hasonlít a struktúra szintaxisához – gyakran hoznak rá typedef-t – lehet névtelen enum típust létrehozni, ha rögtön • létrehozunk egy változot • typedef-ben használjuk
43
enum változó létrehozása • Az enum típusú változó mindenhol használható, ahol egy int is használható – példa: értékadás jobb oldalán, tömb indexben, ... • enum változó értékadása történhet: – enum értékkel – int értékkel, amennyiben használunk explicit típuskonverizót
44
#include <stdio.h> // write out the enum value of the days // try to set the hungarian numbering convention enum Day { sunday, // =7 monday, // =1 tuesday, wednesday, thursday, friday, saturday }; void main() { enum Day today; // enum can be omitted in c++ int a; today = monday; today = (enum Day)3; // explicit cast required in c++ a = today; a = friday; printf("The enum codes of the days.\n"); printf("sunday:%d, monday:%d, tuesday:%d, wednesday:%d, thursday:%d, friday:%d, saturday:%d\n", sunday, monday, tuesday, wednesday, thursday, friday, saturday); 45 }
Programozás I. C nyelv 10. előadás Fájlkezelés Veszprémi Egyetem Heckl István, [email protected] 1
Bevezetés • Definíció fájl: adatok szervezési egysége • Fájlok tulajdonságai: – név – elérési út – méret – atributumok: meglétük rendszer függőek • csak olvasható: mivel a programoknak van jogosultsága módosítani ezt a jellemzőt, elvileg megtehetik, hogy először törlik a tulajdonságot, módosítanak, majd visszaállítják • rejtett • könyvtár
2
Bevezetés • archív: – fájl módosítás állítja be – archiválás törli – dátumok: meglétük rendszer függőek • létrehozás • utolsó módosítás • utolsó hozzáférés
3
Fájl típusok • Szöveges: – csak ASCII karaktereket tartalmaznak • a vezérlő karaktereket is beleértve • a vezérlő karakterek kiértékelésre kerülnek – általában olvasható információt tartalmaznak – az állomány végét a (EOF) vezérlő karakter jelöli • Binárisan: – a fájlt bájtonként értelmezzük – bármilyen értékű bájtot tartalmazhat – például: kép, program, zene – néhány rendszer csak szöveg fájlokat tud küldeni • létezik konverzió binárisról szövegesre
4
Fájl kezelő függvények csoportjai • Fájl művelet név alapján • Stream IO: magas színtű, bufferelt függvények – FILE* a fájl azonosító – stdio.h – a bufferelés miatt a kimenet késhet • Alacsony szintű IO: nem bufferelt függvények – int a fájl azonosító – io.h • Egy programban lehetőleg csak az egyik csoportot használjuk – általában: stream io
5
_access • Szintaxis: int _access(const char* fullName, int mode); • Visszatérési érték: – -1, ha a fájl nem létezik vagy nem rendelkezik mode joggal – 0 ha a fájl rendelkezik mode joggal • Szükséges header fájl: io.h • mode értékek: – – – –
0 2 4 6
létezik-e a fájl írható-e a fájl olvasható-e a fájl (mindig olvasható) írható és olvasható-e fájl
6
_chmod • Szintaxis: int _chmod(const char* fullName, int pmode); • fullName fájlra beállítja a pmode jogosultságot • Visszatérési érték -1 ha a fájl nem létezik • mode értékek: (sys/stat.h -ban definiáltak) – _S_IWRITE írható-e a fájl – _S_IREAD olvasható-e a fájl (mindig olvasható) – _S_IREAD | _S_IWRITE írható és olvasható-e fájl • Szükséges header fájl: io.h
7
_fullpath • Szintaxis: char* _fullpath(char* absPath, const char* relPath, size_t maxLength); • Megadja relPath-hoz tartozó abszolút utat absPathban – absPath maximális mérete maxLength – ha absPath == NULL, akkor malloc-al foglalódik számára hely • a felhasználó feladata a buffer felszabadítása – feltételezzük, hogy a relPath-hoz tartozó bázis könyvtár a program könyvtára • használható a ".." szülő könyvtár jel • Szükséges header fájl: stdlib.h
8
_fullpath • A visszatérési érték normál működés során az abszolút útvonal buffere, hiba esetén NULL • Példa: #include <stdio.h> #include <stdlib.h> void main() { char full[255], part[255]; while(1) { printf("Enter partial path or ENTER to quit: "); gets(part); if(part[0] == 0) break; if(_fullpath(full, part, 255) != NULL) printf("Full path is: %s\n", full); else printf("Invalid path\n"); }}
9
_makepath • Szintaxis: void _makepath(char* path, const char* drive, const char* dir, const char* fname, const char* ext); • Egy teljes fájl nevet alkot annak komponenseiből – ha egy komponens hiányzik, akkor az nem lesz része a teljes fájl névnek – a függvény intelligens, például, ha ext nem tartalmaz pontot, akkor azt automatikusan kirakja • A teljes név hossza nem szabad hogy meghaladja az stdlib.h-ban definiált _MAX_PATH-t – lehet, hogy az operációs rendszer korlátja kisebb • Szükséges header fájl: stdlib.h 10
_splitpath • Szintaxis: void _splitpath(const char* path, char* drive, char* dir, char* fname, char* ext); • Egy teljes fájl nevet szétbont annak komponenseire • A komponensek maximális hosszai az stdlib.h-ban definiáltak – _MAX_DRIVE – _MAX_DIR – _MAX_FNAME – _MAX_EXT 11
#include <stdlib.h> #include <stdio.h> void main() { char path_buffer[_MAX_PATH]; char drive[_MAX_DRIVE]; char dir[_MAX_DIR]; char fname[_MAX_FNAME]; char ext[_MAX_EXT]; _makepath(path_buffer, "c", "\\sample\\crt\\", "makepath", "c"); printf("Path created with _makepath: %s\n\n", path_buffer); _splitpath(path_buffer, drive, dir, fname, ext); printf("Path extracted with _splitpath:\n"); printf(" Drive: %s\n", drive); // c: printf(" Dir: %s\n", dir); // \sample\crt\ printf(" Filename: %s\n", fname); // makepath printf(" Ext: %s\n", ext); // .c } 12
_mktemp • Szintaxis: char* _mktemp(char* format); • Egyedi fájlnevet hoz létre, amit általában ideiglenes fájl nevének használunk – format kinézete: baseXXXXXX • base: egy tetszőleges sztring • XXXXXX: helyfoglalás 6 darab karakter számára • A függvény hívása átírja format XXXXXX részét – az első karakter: egy kis betű (a-z) • az első olyan, amelyet formatba beírva olyan sztringet kapunk, hogy ilyen nevű fájl nem létezik – maradék 5 karakter: számjegyekből álló azonosító, amely minden futásra más és más
13
_mktemp • A visszatérési érték format címe vagy NULL, ha már nem sikerült új egyedi fájlnevet létrehozni – 26 egyedi fájl nevet lehet létrehozni egy base-el egy futás alatt • Szükséges header fájl: io.h
14
#include #include <string.h> #include <stdio.h> void main(void) { char *templ = "fnXXXXXX", *result; const int trial=30, length=20; char names[trial][length]; int i; FILE *fp; for(i = 0; i < 30; i++) { strcpy(names[i], templ); result = _mktemp(names[i]); if(result == NULL) printf("Problem creating the template\n"); else if((fp = fopen(result, "w")) != NULL) { printf("Unique filename is %s\n", result); fclose(fp); } else printf("Cannot open %s\n", result); } } 15
remove • Szintaxis: int remove(const char* fn); int _unlink(const char* fn); • Letörli az fn fájlt • Visszatérési érték 0, ha sikeres a törlés • Szükséges header fájl: stdio.h • Példa: #include <stdio.h> void main() { if( remove( "remove.obj" ) == -1 ) perror( "Could not delete 'REMOVE.OBJ'" ); else printf( "Deleted 'REMOVE.OBJ'\n" ); }
16
rename • Szintaxis: int rename(const char* oldname, const char* newname); • Átnevezi oldname fájlt newname-re • Visszatérési érték 0, ha sikeres az átnevezés • Hibakódok: – EACCES: newname már létezik – ENOENT: oldname nem létezik – EINVAL: nem szabályos karakterek a fájlnévben • Szükséges header fájl: stdio.h
17
struct __stat64 • Struktúra, amelyben fájl információkat tárolunk • Szükséges header fájl: sys/types.h, amelyet sys/stat.h követ • Nem minden mezőnek van minden esetben értelme • Az időpontokat 1970-3000 között tudja ábrázolni • Az idő mezőket a _ctime64 függvénnyel konvertálhatjuk sztringé • Mezők: – st_atime: utolsó hozzáférés ideje – st_ctime: létrehozás ideje – st_mtime: módosítás ideje – st_size: fájl méret
18
struct __stat64 – st_mode: bitmask • _S_IFDIR ha könyvtárról van szó • _S_IFREG ha fájlról van szó – st_dev, st_rdev: a fájlt tároló lemez azonosítója – st_gid: (unix) csoport tulajdonos azonosító – st_uid: (unix) felhasználó tulajdonos azonosító – st_ino: (unix) inode-k száma – st_nlink
19
_stat64 • Szintaxis: int _stat64(const char* file, struct __stat64* buffer); • Információkat kér le file-ról, amit buffer-ben tárol • A visszatérési érték 0 ha sikeres volt az információ kérés, -1 egyébként
20
#include #include <sys/types.h> #include <sys/stat.h> #include <stdio.h> void main() { struct __stat64 buf; int result; result = _stat64("myTry.cpp", &buf); if(result != 0) perror("Problem getting information"); else { printf("File size : %ld\n", buf.st_size); printf("Drive : %c:\n", buf.st_dev + 'A'); printf("Time modified : %s", _ctime64(&buf.st_mtime)); } } 21
Példa #include <sys/stat.h> #include #include <stdio.h> void main() { int oldmask; /* Create read-only files: */ oldmask = _umask(_S_IWRITE); printf("Oldmask = 0x%.4x\n", oldmask); }
22
Stream típus • FILE (az stdio.h file deklarálja) – typedef-fel definiált struktúra • fájlnév • helye a tárolón • hozzáférés módja • mutató, hogy hol tartunk benne • stb. – mindig a típus mutatóját használjuk
23
Fájl IO műveletek • A konzolra vonatkozó io műveleteknek vannak fájlokra vonatkozó párjai – általában a függvénynév kap 'f' prefixet – van egy új FILE* paraméter – az egyéb eltéréseket külön kihangsúlyozzuk • int fprintf(FILE* f, const char *format [, argument] ... ); • int sscanf(const char* in, const char* format [, argument ] ... ); • char* fgets(char* buf, int max, FILE* f) – legfeljebb max-1 karaktert olvas be 24
Fájl IO műveletek • int fputs(char* buf, FILE* f) • int fflush(FILE* f); – f bufferét üríti – visszatérés érték 0, ha sikerült kiüríteni a buffert, hiba esetén EOF • int feof(FILE* f); – ellenőrzi, hogy vége van-e a fájlnak • int ferror(FILE* f); – ellenőrzi, hogy történt-e hiba (például fread-nél)
25
fopen • Szintaxis: FILE* fopen(const char* fn, const char* m) • fn fájlt próbálja megnyitni m nyitási módot használva – használat előtt a fáljokat meg kell nyitni • Visszatérési érték: a fájlt reprezentáló pointer – hiba esetén NULL • Példa: FILE *f; f = fopen("autoexec.bat", "r");
26
Fájl megnyitási módok "r" létező fájl olvasása "w" nem létező fájl írás (ha létezik megsemmisül) "a" hozzáfűzés, EOF megmarad (ha nem létezik a fájl, akkor létrejön) "r+" létező fájl írás/olvasás "w+" nem létező fájl írás/olvasás (ha létezik a fájl megsemmisül) "a+" létező írás/olvasás hozzáfűzés, EOF eltűnik (ha nem létezik a fájl, létrejön) • Az előbbi nyitási módok szöveg fájlokra vonatkoztak, bináris fájlok esetén használjunk "b" postfixet 27
freopen • Szintaxis: FILE* freopen(const char* fn, const char* m, FILE* old) • old -t átírányítja fn-re • bezárja old-t • megnyítja fn-t • hozzárendeli a fájl mutatót old-hoz • Visszatérési érték: – hiba esetén NULL – egyébként old 28
Fájl bezárás • Ha egy fájlt nem használunk tovább, akkor be kell zárni, hogy más is használhassa – az egyszerre nyitva lévő fájlok száma korlátozott (512) – az alacsony szinten nyitva lévő fájlok száma is korlátozott • Szintaxis: int fclose(FILE* f) – visszatérési érték 0, ha sikerült, hiba esetén EOF – buffert ürít és bezárja a fájlt • Szintaxis: int fcloseall() – minden fájlt (streamet) bezár (kivéve: stdin, stdout, stderr) – visszatérési érték a bezárt fájlok száma
29
setvbuf • Szintaxis: int setvbuf(FILE* f, char* buf, int mode, size_t size); • Felülírja az automatikus buffer használatot, f számára buf-t fogja buffernek használni – buf mérete size*2/2, size ∈ [2, 32768] – a parancsot közvetlenül a fájl megnyitása után kell kiadni • Visszatérési érték: 0 siker esetén • Lehetséges mode értékek: – _IOFBF, _IOLBF: buffer használat a paraméterek szerint • ha buf NULL, akkor automatikusan foglalódik hely30 – _IONBF: nincs buffer használat
Példa #include <stdio.h> #include <stdlib.h> void main() { FILE* tf; int i, a; double sum, adat; // Az adatok.txt file létrehozása és feltöltése sorokkal tf=fopen("adatok.txt", "w+"); if (tf==NULL) { fprintf(stderr, "sikertelen file-nyitasi kisarlet!\n"); exit(-1); } for(i=0; i<10; i++) fprintf(tf, "%4d, %10.8f\n", i, i*3.14159265); fflush(tf); 31 fclose(tf);
/* az adatok.txt file tartalmának visszaolvasása*/ if(!(tf = fopen("adatok.txt" , "r+"))) { fprintf(stderr, "Sikertelen file-nyitasi kisarlet!\n"); exit(-1); } sum = i = 0; while (!feof(tf)) { fscanf(tf, "%d,%lf\n" , &a, &adat); sum += adat; i++; printf("%d. sor feldolgozasa megtortent!\n", a); } fclose(tf); printf("A %d db. szam atlaga: %10.8f\n", i, sum/i); }
32
fgetc • Szintaxis: – függvény változat: int fgetc(FILE* f) – makró változat: int getc(FILE* f) • Egy karaktert olvas be a fájlból • Visszatérési érték: a beolvasott karakter kódja, hiba esetén EOF • Példa: int c; FILE* f; c = getc(stdin); c = fgetc(f); 33
fputc • Szintaxis: – függvény változat: int fgetc(FILE* f) – makró változat: int getc(FILE* f) • Egy karaktert ír a fájlba • Visszatérési érték: a kiírt karakter, hiba esetén EOF • Példa: int c; FILE *f; putc(c, stdout); putc(c, f);
34
Példa #include <stdio.h> #include void main(){ int c; FILE* f; f = fopen("adat.dat", "r"); if(!f) printf("Fajl megnyitasi hiba"); else{ while((c=getc(f)) != EOF) putchar(isupper(c) ? tolower(c) : c); if(fclose(f) == EOF) printf("Fajl bezarasi hiba"); } }
35
ungetc • Szintaxis: int ungetc(int c, FILE* stream); • Visszarak egy karaktert az olvasási strembe – valójában a karakter a bufferbe kerül vissza, így elveszhet annak űrítésekor • Visszatérési érték: siker esetén c • Több egymás utáni ungetc hívást nem szabad használni • Hasznos, ha két mező nincs egymástól elválasztva
36
#include <stdio.h> #include void main(void) { int ch, result = 0; printf("Enter an integer: "); while(((ch = getchar()) != EOF) && isdigit(ch)) result = result * 10 + ch - '0'; /* Use digit. */ if(ch != EOF) ungetc(ch, stdin); /* Put nondigit back. */ printf("Number = %d\nNext character in stream = '%c'\n", result, getchar()); }
• Input: 123a • Output: Enter an integer: Number = 123 Next character in stream = 'a' 37
Objektumok írása, olvasása • Szintaxis: size_t fread(const void* buf, size_t size, size_t num, FILE* f) – beolvas num darab size méretű objektumot f-ből és buf-ban tárolja • buf megfelelő típusú tömb – visszatérési érték: a beolvasott elemek száma • kevesebb lehet, mint num, ha olvasás közben hiba történt • Szintaxis: size_t fwrite(const void* buf, size_t size, size_t num, FILE* f) – Kiír f-be num darab size méretű struktúrát buf-ból 38 – Visszatérési érték: a kiírt elemek száma
fseek • Szintaxis: int fseek(FILE* f, long n, int orig) • A f aktuális pozíció mutatóját lehet mozgatni n bájtal orig-tól kiindulva – n lehet negatív is – a buffer törlődhet • Visszatérési érték 0, ha sikerült • Lehetséges orig értékek: – SEEK_CUR aktuális pozíció – SEEK_END fájl vége – SEEK_SET fájl eleje • void rewind(FILE* f); 39 – megfelel (void)fseek(f, 0L, SEEK_SET) -nak
ftell • Szintaxis: long ftell(FILE* f); • Megadja f aktuális pozíció mutatóját – append esetén a függvény a következő olvasás helyét adja meg • írás csak a fájl végén fog történni • fájl megnyitása után az olvasás mutató a fájl elejére mutat • írás hatására az olvasás mutató is változik, a fájl végére ugrik • Lásd még: fgetpos, fsetpos 40
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { char nev[30]; int kor; } RECORD; void main() { FILE* bf; size_t cnt; RECORD rt[11], re; long pos; /* A 0. es a 10. elem feltoltese */ strcpy(rt[0].nev, "AT&T Bell Lab."); rt[0].kor = 25; strcpy(rt[10].nev, "Intel Lab."); rt[10].kor = 35; /* rekordtomb kiirasa binaris file-ba */ bf = fopen("ADAT.DAT", "w+b");
41
if (bf==NULL) { fprintf(stderr, "Sikertelen file-nyitas!\n"); exit(-1); } pos = ftell(bf); cnt = fwrite(rt, sizeof(RECORD), 11, bf); pos = ftell(bf); /* Visszapozicionalas a file elejere */ rewind(bf); /* A 0. rekord visszaolvasasa */ cnt = fread(&re,sizeof(RECORD),1, bf); if (cnt!=1) { fprintf(stderr, "File olvasasi hiba!\n"); exit(-1); } /* pozicionalas a 10. rekordra */ fseek(bf, 10 * sizeof(RECORD), SEEK_SET); /* Az 10. rekord visszaolvasasa */ cnt = fread(&re, sizeof(RECORD), 1, bf); fclose(bf); }
42
tmpfile • Szintaxis: FILE* tmpfile(void); • Létrehoz egy ideiglenes fájlt a gyökér könyvtárban • Az ideiglenes fájlok törlődnek: – bezáráskor – a program befejezésekor (ha nem történt hiba) – _rmtmp() függvény hívásakor • Használjuk a _tempnam vagy _tmpnam függvényeket, hogy megadjunk egy könyvtárat az ideiglenes fájloknak
43
Alacsony szintű IO műveletek • Lásd: _open, _create, _sopen, _close, _commit, _dup, _eof, _lseek, _tell, _read, _write, _chsize, _fstat, _locking, _pipe, ...
44
_umask • Szintaxis: int _umask(int pmode); • Beállítja a _creat, _open, _sopen függvényekhez tartozó alapértelmezett jogosultság maszkot állítja be • A maszkban beállított egyes bit azt jelzi, hogy a kapcsolódó tulajdonság nem (!) engedélyezett • A visszatérési érték a korábbi maszk értéke • A fájl csak lezárás után kapja meg a jogosultságot • pmode értékek: (sys/stat.h -ban definiáltak) – _S_IWRITE írható-e a fájl – _S_IREAD olvasható-e a fájl (mindig olvasható) – _S_IREAD | _S_IWRITE írható és olvasható-e fájl 45 • Szükséges header fájl: sys/stat.h, io.h
Programozás I. C-nyelv
11. előadás Láncolt listák, verem, sor Veszprémi Egyetem Heckl István, [email protected]
1
Bevezetés • Adattípusok fajtái: – egyszerű adattípusok: char, int, float, ... – összetett adattípusok: tömb, struktúra, union, osztály • tartalmazhatnak egyszerű és összetett adattípusokat is – felhasználói adatszerkezetek: láncolt lista, fa, verem, sor, ... • Felhasználói adatszerkezetek típusai: – általánosan ismertek • csak a hasznos adatok különböznek • példa: bináris keresőfa, ciklikus lista 2 – egyedi: például P-gráf reprezentáció
Bevezetés • A felhasználói adatszerkezetek jellemzői általában: – dinamikus struktúrákból állnak – a struktúrákat mutatók kötik össze – legalább egy struktúrának a címét tároljuk változóban – valamilyen valós rendszernek a számítógépes reprezentációi • lásd a személy, kocsi struktúra példát • A felhasználói adatszerkezetek egyszerű esetben mutatók nélkül is megvalósíthatóak – egy verem elkészíthető egy tömb és egy egész változó segítségével 3
struct kocsi; // struktúra típus deklaráció struct szemely { int id; char nev[200]; int szuletesiIdo; struct szemely *apa, *anya, *gyerek; struct kocsi *sajatK, *szolgalatiK; }; struct kocsi { int id; char tipus[200]; int gyartasiIdo; struct szemely *tulaj, *hasznalo; struct kocsi* pot; };
4
gy er e ap k a
id: 12 nev: "Eva" szuletesiIdo: 1980
szolgalatiK
pot
id: 225 nev: "Jaguar" gyartasiIdo: 2000
ha na sz
a ap k e er gy
an y gy a er ek
id: 35 nev: "Lali" szuletesiIdo: 1977
id: 15 nev: "Volvo" gyartasiIdo: 1960
tulaj sajatK
ha sz na lo
id: 02 nev: "Feri" szuletesiIdo: 1947
lo
id: 86 nev: "Adam" szuletesiIdo: 2000
tulaj sajatK
id: 72 nev: "Honda" gyartasiIdo: 2005 5
Bevezetés • Definíció: láncolt lista: dinamikus rekordok egy olyan halmaza, amelyek mutatók segítségével kapcsolódnak és folytonos láncot alkotnak • A mutató típusa megegyezik az őt tároló rekord típusával • Az utolsó elem NULL mutatót tartalmaz • A lista a tömbnél rugalmasabb, de karbantartása nehezebb A
*
A
*
A
*
NULL
6
A láncolt lista típusai • Láncoltság szerint: – egyszeresen láncolt – kétszeresen láncolt • Ciklikusság szerint: – ciklikus – nem ciklikus • Rendezettség szerint: – rendezett – nem rendezett • A fenti három tulajdonság egymástól független NULL
NULL
7
A lista mint típus • A lista a felhasználói adatszerkezetek közül a legalapvetőbb • A listán alapvó adatszerkezetek általában: – sor – verem • A listának általában csak az elejét, végét, aktuális elemét ismerjük • Listát reprezentálhat: – mutató az első elemre – őrszem: listaelem típusú struktúra, amely nem tartalmaz hasznos adatot – struktúra: tartalmazhatja az eleje, vége, aktuális elem 8 mutatókat és az elemszámot
Lista műveletek • Elem keresés – kulcs alapján • Elem kiíratás • Elem beszúrás – adott elem után, kulcs szerint növekvő sorrendbe, utolsó helyre • Elem törlés • Lista kiírás • Lista törlés • Lista rendezése • Méret meghatározás • Elemek cseréje
9
Listaelem definíciója struct le{ struct le* next; // kötelező struct le* prev; int key; dataType1 var1; dataType2 var2; ... }; • A kulcs általában a felhasználói adat része – pl.: személyi szám vagy más egyedi adat • Néha a next mutatón kívül csak egy mutató van a lista 10 elem rekordban, amely egy adat rekordra mutat
A lista implementálása • A lista implementációja sokféle lehet, különbözhet a: – lista szerkezet (ciklikus, rendezett, ...) – lista elem típus – lista változó típus – megvalósított függvények (API) • Implementálás: – válaszd ki a lista szerkezetét – dönts a lista elem és a lista típusról – válaszd ki a megvalósítandó függvényeket – függvény implementálásakor rajzold le az összes lehetséges esetet ! 11
Listák C++ -ban • A C++ lehetőséget ad sablonok használatára – segítségükkel olyan listák (vagy más felhasználói adatszerkezetek) készíthetőek, amelyekben a hasznos adat típusa sablon paraméter • Az STL (standard template library) definiálja a list<elementType> típust, amelyhez meg vannak írva a listát kezelő függvények
12
Példa • Készítsünk egy egyszeresen láncolt, rendezett, nem ciklikus listát • A lista elem struktúra tárolja az adattagokat • Egy lista elem mutató reprezentálja a listát • Valósítsuk meg a következő függvényeket: – beszúrás – törlés – keresés
13
Példa #include <stdio.h> #include <malloc.h> typedef struct le { int id; char name[100]; struct le* next; } listElem; listElem* createListElem() { // use pointer return type to avoid record copy listElem* result=(listElem*)malloc(sizeof(listElem)); printf("\nProvide name for new elem:"); scanf("%s", result->name); printf("Provide id for new elem:"); scanf("%i", &result->id); return result; }
14
Magyarázat • Egy lista elemet ugyanúgy hozzunk létre, mint bármilyen más rekordot • Az elem már létrejön a függvényhívás hatására, de még nem lesz része a listának • A visszatérési érték listElem* típusú, mert listElem esetén egy felesleges rekordmásolás lépne fel • Ne felejtsük el, hogy a dinamikusan lefoglalt területet fel is kell szabadítani
15
void displayListElem(listElem* myList) { printf("\nlistElem name: %s\n", myList->name); printf("listElem id: %i\n", myList->id); } void deleteList(listElem* myList) { listElem *act, *prev; act = myList; // 1 while (act) { // 2 prev = act; // 3 act = act->next; free(prev); // 4 } } void main() { listElem *myList=NULL, *found=NULL; myList = createListElem(); displayListElem(myList); deleteList(myList); }
16
Magyarázat • A megírt függvényeket teszteljük le alaposan – készítsünk megfelelő main függvényt • Az aktuális elem mutató változtatása után (act = act->next;) mindig ellenőrizni kell, hogy annak értéke NULL-e • Egy listát úgy szabadítunk fel, hogy minden elemét felszabadítjuk
17
A lista törlés head
1 2 head
3 head
4 head
A
*
A
*
A
*
NULL
act act == NULL A
*
prev A
*
A
*
NULL
act *
prev A
A
A
*
A
*
NULL
*
A
*
NULL
act *
A
4 prev
act 18
void listList(listElem* myList) { listElem *act=myList; // 1 printf("\nListing the elments:"); while (act) { // 2 displayListElem(act); // 3 act = act->next; // 4 } } listElem* search(listElem* myList, int searchID) { listElem *act=myList; // 1 while (1) { // returns the pointer of the if (!act) // 2 // record with the given ID return NULL; if (act->id == searchID) // 3 return act; act = act->next; // 4 } return NULL; // function never reach this point }
19
Magyarázat • Egy listában tetszőleges mező alapján kereshetünk • Ha a kulcsmező nem egyedi, akkor vagy megkeressük az összes searchID kulcsú elemet vagy csak az elsőt • Tesztelésnél legyünk alaposak – próbáljunk keresni: • üres listában • egy elemű listában • hosszú listában – a keresett elem legyen: • első • utolsó • közbenső • nincs a listában
20
A listában keresés
21
A lista kiírása
22
void insert(listElem** myListP, listElem* myElem) { listElem *act, *prev; if (*myListP==NULL) { // a1 no list exists *myListP=myElem; myElem->next=NULL; // a2 return; } act = *myListP; // b1 if (act->id > myElem->id) { // insert before the first element myElem->next = *myListP; *myListP = myElem; // b2 return; }
23
while (1) { prev = act; act = act->next; // c1 if (act==NULL) { // c2 insert at the end prev->next = myElem; myElem->next = NULL; // c3 return; } if (act->id > myElem->id) { // insert between two elements prev->next = myElem; myElem->next = act; // d1 return; } } return; // program doesn't reach this point }
24
Magyarázat • Ebbe a típusú listába való illesztéskor 4 különböző eset van • Minden esetet le kell rajzolni és alaposan tesztelni • Mivel beszúráskor a lista feje is megváltozhat, ezért azt cím szerint adjuk át – mutató átadása cím szerint kétszeres índirekcióval történik
25
Elem beszúrása head
NULL
a1 head
A
*
NULL
a2 head
A
*
NULL
A
*
NULL
b1 head
b2 A
* 26
Elem beszúrása
27
Elem beszúrása
28
listElem* delElement(listElem* myList, int searchID) { listElem* act=myList, *prev, *temp; if (!act) return NULL; // a1 there is no list if (act->id == searchID) { // b1 the first element temp = act->next; // is to be deleted free(act); return temp; // b2 } while (1) { prev = act; // c1 act = act->next; if (!act) return myList; // c2 elem not found if (act->id == searchID) { prev->next = act->next; // c3 free(act); // not the first element is to be return myList; // deleted } } return NULL; // function never comes to here 29 }
Magyarázat • A lista fej itt is változhat, most az új fejet visszatérési értéként adjuk vissza • A b és c esetnél nem számít, hogy a törlendő elem után van-e még elem
30
Elem törlése
31
Elem törlése head
A
*
*
A
*
NULL
*
A
*
NULL
*
NULL
A
c1 prev
c2 head
act
act && act->id != searchID A
*
A
c1 prev
c2 head
act
act && act->id == searchID A
*
A
*
A
c3 prev
act
32
void main() { // try the previous functions // sorted, single linked list listElem *myList=NULL, *found=NULL; // parameter passing of a pointer according to address insert(&myList, createListElem()); insert(&myList, createListElem()); insert(&myList, createListElem()); listList(myList); // myList can change so it is the return value myList=delElement(myList, 4); printf("list after deleting element with id 4\n"); listList(myList); found=search(myList, 7); if (found) { printf("\n7 found in record:"); displayListElem(found); } deleteList(myList); myList=NULL; }
33
Oda-vissza láncolt lista
NULL
NULL
Oda-vissza láncolt listába való beszúrás
34
Oda-vissza láncolt listából való törlés
35
Ciklikus lista
Ciklikus listába való beszúrás
36
A ciklikus listából való törlés
37
Verem • Definíció: olyan felhasználói adatszerkezet, amelyből mindig csak a legkésőbb betett adatot lehet kivenni – LIFO: last in first out – stack record 163 • API: – int pop(element*); record 74 • a visszatérési érték jelzi, hogy sikeres volt-e a művelet – int push(element*); – int Empty(); – int Full();
record 26 record 103
38
Verem • Megvalósítható egy láncolt listával: – pop = a lista végén lévő elem visszaadása és törlése a listából – push = elem beszúrása a lista végére • STL megfelelője a stack<elemTípus> • Használat: – mélység szerinti fabejárás – paraméterek átadása függvényeknek
39
Sor • Definíció: olyan felhasználói adatszerkezet, amelyből mindig csak a legkorábban betett adatot lehet kivenni – FIFO: first in first out – queue • API: ugyanaz mint a veremnél
40
Sor • Megvalósítható egy láncolt listával: – pop = a lista elején lévő elem visszaadása és törlése a listából – push = elem beszúrása a lista végére • STL megfelelője a queue<elemTípus> • Használat: – szélesség szerinti fabejárás – processzor biztosítása az egyes alkalmazásoknak
41
Programozás I. C nyelv 12. előadás Bináris fa, bináris kereső fa, kupac, időkezelő függvények Veszprémi Egyetem Heckl István, [email protected]
1
Fogalmak • Fa: összefüggő, körmentes gráf, azaz bármely két csúcsa között pontosan egy út van • Bináris fa: olyan fa, amelynek csúcspontjaiból maximum 2 részfa nyílik • A fát tekintjük irányítottnak, ekkor az élek a szülőktől a gyerekek felé mutatnak
2
Fogalmak • Szülő: egy csomópont megelőző csomópontja – a gyökeret kivéve valamennyi csomópontnak van szülője • Ős: egy csomópont szülője és a gyökér által meghatározott út valamely csomópontja • Gyerek: az adott csomópontot közvetlenül követő elem – bináris fáknál megkülönböztethetünk bal, illetve jobb oldali gyerekeket – a gyerekek egymásnak testvérei • Leszármazott: azon csomópontok halmaza, amelyek irányított úton elérhetőek az adott csomópontból 3
Fogalmak • • • •
Mélység / magasság: a fa leghosszabb útjának hossza Gyökér: az a csomópont, amelynek nincs őse Levél: olyan csomópont, amelynek nincs gyereke Szintszám: a fa gyökeréhez a 0 szintszám tartozik, a további csomópontokhoz pedig mindig 1 -gyel nagyobb szintszám, mint a szülő szintszáma
4
Példa • • • • •
Szülő: 7 Ős: {2,7} Bal gyerek: 1 Jobb gyerek: 5 Leszármazottak: {1, 5}
• • • •
Levelek: {1, 5, 8, 3} 2. szint: {4, 9} Gyökér: 2 Mélység: 4 5
Bináris fák bejárása • Fajtái: – preorder – inorder – postorder • A bejárások rekurzívak és az aktuális elem feldolgozásának helyét jelölik
6
Bináris fák bejárása • Preorder bejárás: - a gyökér feldolgozása - a bal részfa preorder bejárása - a jobb részfa preorder bejárása - eredmény: 1, 2, 4, 5, 3, 6, 7 Step 1 Step 3 Step 2 1
2
4
3
5
6
7
7
Bináris fák bejárása • Inorder bejárás: – a bal részfa inorder bejárása – a gyökér feldolgozása – a jobb részfa inorder bejárása – eredmény: 4, 2, 5, 1, 6, 3, 7 – bináris keresőfákból növekvő sorrendben olvassa ki Step 2 az értékeket Step 3
Step 1 1
2
4
3
5
8
6
7
Bináris fák bejárása • Postorder bejárás: – a bal részfa postorder bejárása – a jobb részfa postorder bejárása – a gyökér feldolgozása – eredmény: 4, 5, 2, 6, 7, 3, 1 – matematikai kifejezések kiértékelésekor használják Step 3 Step 2 Step 1 1
2
4
3
5
9
6
7
Bináris keresőfa • Bináris keresőfa (bst - binary search tree): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal oldali leszármazottak kulcs értékei nem nagyobbak, mint az aktuális elem kulcs értéke, a jobb oldali leszármazottak kulcsértékei pedig nagyobbak • Bináris keresőfa felépítése: – új elem bekérése – indulás a gyökértől – ha az új elem kulcsa nem nagyobb, mint az aktuális elem kulcsa, akkor balra egyébként jobbra megyünk – ha adott irányba nincs elem, akkor oda beszúrjuk az új elemet 10
• Elemek: 12, 23, 8, 25, 10, 18
11
Bináris keresőfa • A bináris keresőfa előnye a listával szemben, hogy egy elem gyorsabban megtalálható – a fa mélysége általában kisebb, mint a lista hossza • Adott kulcsú elem keresése: – indulás a gyökértől – ha a keresett elem és az aktuális elem kulcsa: • megegyezik, akkor végeztünk • ha az előbbi kisebb, akkor jobbra megyünk • ha az előbbi nagyobb, akkor balra megyünk • A fa felépítése függ az elemek sorrendjétől • Ha az elemek beszúrása sorrendben történik, akkor a fa 12 lánccá degenerálódik (legrosszabb eset)
Bináris keresőfa adatszerkezet megvalósítása • Implementálás: – döntsd el, hogy van-e szülő mutató – válaszd ki a tárolni kívánt adatokat • külön struktúrában tároljuk vagy nem? – határozd meg a kulcs elemet – döntsd el, hogy reprezentálod a fát: mutató, sentinel, osztály – válaszd ki a megvalósítandó függvényeket • függvény implementálásakor rajzold le az összes lehetséges esetet • beszélő neveket használj 13
#include <stdio.h> #include <stdlib.h> struct node { int key; struct node *less, *bigger; int data1; }; void printNode(struct node* cs) { printf("[key:%d, data1: %d]", cs->key, cs->data1); } void createNode(struct node* act) { // filling up the node with data printf("Creating a new node\n"); printf("key:"); scanf("%d", &act->key); printf("data1:"); scanf("%d", &act->data1); } 14
Magyarázat • struct node: fa csomópont típusának a meghatározása – nincs külön struktúra az adatoknak • printNode: egy csomópont kiírása • createNode: csomópont adatainak a bekérése – paraméter átadás cím szerint, hogy ne kelljen pluszban rekordot másolni
15
void printTree(struct node* cs) { if (!cs) return; if(cs->less) printTree(cs->less); printNode(cs); if(cs->bigger) printTree(cs->bigger); } void freeTree(struct node* cs) { if (!cs) return; if(cs->less) freeTree(cs->less); if(cs->bigger) freeTree(cs->bigger); free(cs); }
16
Magyarázat • A fa listázása inorder sorrendben történik, mert így kapjuk meg az elemeket növekvő sorrendben – először kilistázzuk rekurzívan az adott csomópontnál kisebb elemeket – az adott csomópontot – majd az adott csomópontnál nagyobb elemeket • A fa törlése postorder sorrendben történik, egy elemet akkor törölhetünk, ha mindkét részfáját már töröltük – egy elem törlése után már nem hivatkozhatunk a less és bigger adattagjaira 17
struct node* searchNode(struct node* root, int key) { if (!root) return NULL; struct node* act = root; while (act) { if (act->key==key) return act; if (key<=act->key) act = act->less; else act = act->bigger; } return NULL; } struct node* smallestNode(struct node* act) { // return the smallest element in subtree rooting at act if (!act) return NULL; if (!act->less) return act; return smallestNode(act->less); 18 }
Magyarázat • searchNode adott kulcsú elemet keres meg • smallestNode a részfa legkisebb elemét keresi meg – rekurzív – a jobb szélső gyerek a legkisebb, a balszélső a legnagyobb • Mindét függvény a keresőfa tulajdonságot használja ki
19
smallest of 31
search: 25 1
12
root
12
2 (25>12) er gg bi
bi gg er
23
23
1
le
gg er
20
31
er gg bi
le ss
3 (25>23) bi
ss
start
20
31 2
le
ss
le ss
4 (25<31)
25
le ss
ss le
24
25
3
24 20
struct node** linkAddressToInsert(struct node* act, int key) { // return the address of the less or bigger pointer of the node to where key // have to be inserted if (key<=act->key) { if (act->less) return linkAddressToInsert(act->less, key); else return &act->less; } else { if (act->bigger) return linkAddressToInsert(act->bigger, key); else return &act->bigger; } } 21
void insertNode(struct node** root, struct node* cs) { struct node* act = *root, *newNode, **linkAdress; newNode = (struct node*)malloc(sizeof(struct node)); *newNode=*cs; newNode->less=NULL; newNode->bigger=NULL; if (*root==NULL) { *root=newNode; return; } linkAdress=linkAddressToInsert(*root, cs->key); *linkAdress=newNode; }
22
Magyarázat • linkAddressToInsert: – a beszúrás szabályai szerint megkeresi azt a csomópontot, amely az adott kulcsú elem szülője lesz – visszaadja a less illetve bigger mutatók közül a megfelelőnek a címét – ha csak a szülőnek adjuk vissza a címét, akkor utána még vizsgálni kell, hogy melyik mutatója megfelelő • insertNode két esetet vizsgál: – még nem létezik a fa: a gyökeret módosítani kell – már létezik a fa: meg kell keresni az új elem szülőjét – létezik nem rekurzív változat is 23
insert 18 **root
12 bi gg
NULL
er
23 bi
le
gg
ss
*linkAddress
er
20 NULL
31 le
ss
NULL
NULL
25 le
ss
18
NULL
24 NULL
NULL
24
void insertNode(struct node** root, struct node* cs) { // non-recursive struct node* act = *root, *newNode; newNode = (struct node*)malloc(sizeof(struct node)); *newNode=*cs; newNode->less=NULL; newNode->bigger=NULL; if (*root==NULL) { *root=newNode; return; } while (1) { if (newNode->key<=act->key) { if (act->less == NULL) { act->less = newNode; return; } else act = act->less; } else { if (act->bigger == NULL) { act->bigger = newNode; return; } else act = act->bigger; } } // while end }
25
struct node** linkAddressTo(struct node* root, struct node* child) { // address of the less or bigger pointer of the parent of 'child' // this is the address of the link pointing to child if (!root || !child || child==root) return NULL; struct node* act = root; int key=child->key; while (act) { if (act->less==child) return &act->less; // return according to address if (act->bigger==child) return &act->bigger; if (key<=act->key) act = act->less; else act = act->bigger; } return NULL; }
26
Magyarázat • Adott elem szülőjének a less illetve bigger mutató közül a megfelelőnek a címét adja vissza – ha csomópontokban lenne parent mutató, akkor erre a függvényre nem lenne szükség
27
void deleteNode(struct node** root, int key) { struct node *del, **linkAddressToDel, *newChild, *sub, **linkAddressToSub; if (*root==NULL) return; // no tree del=searchNode(*root, key); if (!del) return; // key not found linkAddressToDel=linkAddressTo(*root, del); if (del->less==NULL || del->bigger==NULL) {// 0,1 child if (del->less==NULL && del->bigger==NULL) newChild=NULL; // 0 child else if (del->less==NULL) newChild=del->bigger; // 1 child else newChild=del->less; // 1 child if (linkAddressToDel) *linkAddressToDel=newChild; else *root=newChild; free(del); return; 28 }
// 2 children sub=smallestNode(del->bigger); linkAddressToSub=linkAddressTo(*root, sub); if (linkAddressToDel) *linkAddressToDel=sub; else *root=sub; sub->less=del->less; sub->bigger=del->bigger; *linkAddressToSub=NULL; free(del); }
29
Magyarázat • Csomópont törlésnél két eset van, a törlendő csomópontnak (del): – 0 vagy 1 gyereke van – 2 gyereke van • Mindkét esetben vizsgálni kell, hogy a gyökeret töröljüke, ha igen akkor módosítani kell
30
Magyarázat • Két gyerekű csomópont törlésekor a keresőfa tulajdonság megőrzése érdekében del helyére át kell mozgatni a kulcs szerinti szomszédját sub-t – lehetséges sub értékek: • smallestNode(del->bigger): a jobb oldali részfa legkisebb eleme • biggestNode(del->smaller): a bal oldali részfa legnagyobb eleme – sub-nak 0 vagy 1 gyereke van
31
delete 24 **root
12
er gg bi
bi gg
NULL
er
s
er
le s
le
gg
ss le
24
NULL
s
25
*linkAddressToDel
NULL
NULL
s
le
ss
NULL
le s
NULL
31 le s
20
er gg bi
bi
ss
23
*del NULL
32
b ig g
er
ss
er le
le
ss
gg
ss
bi
le ss
le
er
er
gg
b ig g
bi
33
le
ss
ge
r
er
b ig
ss
gg
le
bi
ss
er le
ss
gg
le
bi
s les
34
void main() { struct node *root=NULL, newNode, node1={12, 0, 0, 12}, node2={23, 0, 0, 20}, node3={20, 0, 0, 7}, node4={31, 0, 0, 9}, node5={25, 0, 0, -1}, node6={24, 0, 0, 2}; // createNode(&newNode); insertNode(&root, &newNode); insertNode(&root, &node1); insertNode(&root, &node2); insertNode(&root, &node3); insertNode(&root, &node4); insertNode(&root, &node5); insertNode(&root, &node6); printf("\nOrdered node list: "); printTree(root); if (searchNode(root, 25)) printf("\n25 is found in the tree\n"); deleteNode(&root, 23); printf("\nOrdered node list after deleting 23: "); printTree(root); freeTree(root); 35 }
Kupac (heap) • Definíció: teljes fa: olyan fa, amelynek a szintjei jobbról balra folytonosan vannak feltöltve • Max-kupac: olyan teljes bináris fa, amelynek minden csúcsára igaz, hogy a gyerekek kulcsértékei nem nagyobbak, mint a szülők kulcsértékei – a gyökér a legnagyobb kulcsú • Elsőbbségi sornak is hívják
36
Kupac megvalósítása • Történhet: – felhasználói adatszerkezetként az előbbi példához hasonlóan – tömbként • általában ha kupac rendezést valósítjuk meg és csak a kulcs a hasznos adat • minden bináris fa tárolható tömbként – nem bővíthető dinamikusan
37
Bináris fa reprezentálása tömbbel • A tárolás szabályai: – a fa gyökerét a tömb első eleme tárolja – a k csomópont bal gyereke a tömb [2*k+1], jobb gyereke pedig a [2*k+2] helyet foglalja el – a d mélységű bináris fa tárolásához 2^d elemet tartalmazó tömbre van szükség • annál hatékonyabb, minél teljesebb a fa
38
void exchange(int* a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; } void downheap(int* a, int size, int parent) { // the children of a[v] are already heaps // the root a[v] may violate the heap property // modify the tree to force the heap property int left=2*parent+1, right=2*parent+2, maxChild=left; if (left>=size) return; // a[v] has no children if (right<size && a[right]>a[left]) maxChild=right; // if there are two children and the right is bigger, then it will be maxChild if (a[parent]>=a[maxChild]) return; // it is a heap else { exchange(a, parent, maxChild); // force heap property at the top downheap(a, size, maxChild); // force heap property in the changed subtree } 39 }
Magyarárzat • downheap: egy bináris fát kupaccá alakit, amennyiben a gyökér bal és jobb oldali gyereke eredetileg már kupac – ha a gyökérre nem érvényes a kupac tulajdonság, akkor fel kell cserélni a nagyobb értékű gyerekkel és a meg kell hívni újra a függvényt a módosult részfára – létezik nem rekurzív algoritmus is – magyarul felszívárog-nak hívják a függvényt, mert a maximumot hozza a gyökerébe
40
24 42
heap
31
25
26 5
20
downheap
42 31 25
26 24
20
5 41
void buildheap(int a[], int n) { // first create the basic heaps (they have 2 or elements) // when v==n/4-1, we regard such a tree whose two subtrees are already heaps // the new root may violate the heap property for (int v=n/2-1; v>=0; v--) downheap(a, n, v); } void heapsort(int* a, int n) { buildheap(a, n); while (n>1) { n--; exchange(a, 0, n); // put the biggest of the current heap into its final place in the array // put the most right leaf at the top of the heap downheap(a, n, 0); // force the heap property on the decread heap } 42 }
Magyarázat • buildheap: először kicsi aztán egyre nagyobb kupacokat hoz létre, addig míg minden csomópont része nem lesz a kupacnak – egy különálló csomópont kupacnak tekinthető – két kupacból egy új közös gyökér és a downheap segítségével lehet nagyobb kupacot létrehozni
43
44
24 0
42
26 31
25
3
4
5
6
24 42 26 25 31 20 5
downheap 0
31
26 24
2
5
20 42
25
1
20
1
2
3
4
5
6
42 31 26 25 24 20 5 5 45
Magyarázat • heapsort: maxremove segítségével meghatározzuk először a legnagyobb elemet, aztán a maradék kupacból a legnagyobbat, stb. – maxremove nincs külön megírva • törli a gyökeret • berakja helyére a legalsó szint levelei közül a jobb szélsőt • meghívja az új gyökérre downheap-t
46
42 0
31
2
3
4
5
6
42 31 26 25 24 20 5
26 24
25
1
5
20 5
0
31
26 24
25
3
4
5
6
5 31 26 25 24 20 5
downheap 0
25
26 24
2
20
31
5
1
20
1
2
3
4
5
6
31 25 26 5 24 20 5 47
void printArray(int* array, int size) { int idxI=0; printf("["); for (;idxI<size;idxI++) printf("%d ", array[idxI]); printf("]"); } void main() { int a[]={15, 23, 48, 6, 89, 54, 2, 12}; int size = sizeof (a) / sizeof( int); printArray(a, size); heapsort(a, size); printArray(a, size); }
48
Egyéb fa típusú adatszerkezetek • Kiegyenlített fa: olyan bináris keresőfa, amely biztosítja, hogy ne legyenek benne aránytalanul hosszú ágak – a hatékonyság a mélységétől függ • Binomiális kupac: olyan kupac, amely támogatja kupacok egyesítését • Bxy-fa: – levelek azonos szinten vannak – az elemek rendezettek – egy csúcsnak x-y eleme lehet • S-fa: olyan kiegyenlített bináris kereső fa amelyben a gyakran használt elemek vannak elől 49 – így azok gyorsan elérhetőek
Az időkezelés header fájlai • Az idő és a dátum kezeléséhez a következő deklarációs állományokat kell beépíteni a programunkba: – #include – #include <sys\timeb.h>
50
asctime függvény • 26 karakteres sztringben adja vissza a *tblock struktúrában tárolt dátumot és időt • Példa: char *asctime(const struct tm *tblock) Sun Jun 19 04:08:30 1994\n\0
51
clock függvény • clock_t clock(void); • Processzor idő lekérdezése – visszatérési értéke a program indulása óta eltelt processzor idő belső egységben – ANSI C kompatibilis • A függvény segítségével két esemény közötti intervallum határozható meg – Ha az időértéket másodpercben kívánjuk megkapni, a visszaadott értéket el kell osztani a CLK_TCK konstanssal 52
ctime függvény • char *ctime(const time_t *time) • A dátumot és az időt sztringgé alakítja , és a 26 karakteres sztringre mutató pointerrel tér vissza • *time paraméter értéke a time függvény hívásával állítható be – ANSI C kompatibilis
53
Példa
#include void main() { time_t now; now=time((time_t *)NULL); printf(”It’s %.24s”,ctime(&now)); }
54
difftime függvény • A függvény a megadott két time_t típusú időpont különbségét határozza meg másodpercekben • double difftime(time_t time2,time_t timer);
55
ftime függvény • Az aktuális időpontot és dátumot a timeb típusú struktúrába tölti • a timeb struktúra szerkezete : struct timeb{ long time;/*1970.1.1 éjfél óta eltelt idő(mp)*/ short millitm;/*a másodpercek törtrésze (ms)*/ short timezone;/*a helyi és a GMT idő eltérése (mp)*/ short dstflag;/*0 ha nincs nyári időszámítás*/ 56
};
gmtime függvény • Az aktuális dátumot és az időpontot Greenwich-i idővé (GMT) konvertálja és egy struct tm típusú struktúrába tölti • time feltöltését a time hívásával végezhetjük • A tm struktúra definíciója a time.h include file-ban található • Visszatérési értéke a struktúrára mutató pointer • DOS specifikus • struct tm *gmtime(const time_t *timer);
57
localtime függvény • A helyi time_t típusú dátumot és az ídőpontot egy struct tm típusú struktúrába tölti • struct tm *localtime(const time_t *timer);
58
A tm struktúra szerkezete: struct tm{ int tm_sec;/*másodperc*/ int tm_min;/*perc*/ int tm_hour;/*óra (0-23)*/ int tm_mday;/*hónap napja (0- 31)*/ int tm_mon;/*hó (0-11)*/ int tm_year;/*év (a naptári év- 1900)*/ int tm_wday;/*a hét napja (0-6 ;vasárnap=0)*/ int tm_yday;/*az év napja (0-365)*/ int tm_isdst;/*0 ha nincs nyári időszámítás*/ }; 59
mktime függvény • Kitölti a tm struktúra hiányzó adattagjait és time_t formátumúra alakítja a struktúrában tárolt időt és dátumot • time_t mktime(struct tm *t);
60
stime függvény • A rendszeridőt és a dátumot állítja be • A tp pointer mutat az idő értékére, amely 1970.január 1. 00:00:00 óra(GMT) óta eltelt időt tartalmazza másodpercekben • int *stime(time_t *tp);
61
time függvény • Az aktuális időt kérdezi le • Visszatérési értékként és a nem NULL timer paraméterrel kijelölt objektumban megadja az aktuális időt (1970. Január 1. 00:00:00 óra GMT óta eltelt idő másodpercekben • ANSI C és UNIX kompatibilis
62
Példa #include void main() { int j,it,eltelt,s; for(j=0;j<2;j++) { it[j].s=ido_sec(&it[j]); } int eltelt=it[1].s-it[0].s; }
63
tzsed függvény • a TZ környezeti változó értéke alapján beállítja a daylight, timezone és tzname globális változókat • Szökő napok?
64