Programozás alapjai C nyelv 5. gyakorlat. Írjunk ki fordítva! Írjunk ki fordítva! (3)

Tömbök

Programozás alapjai C nyelv 5. gyakorlat

• Azonos típusú adatok tárolására. • Index mindig nullától indul, és csak egész típusú (char is egész) lehet. Pl: m[2][3] int alma[8]; float m[3][4]; m[0][0] m[0][3] alma[0] alma[7] m[2][0]

Szeberényi Imre BME IIT

<[email protected]>

Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

-1Programozás alapjai I. (C nyelv, gyakorlat)

Tömbök (2)

© BME-IIT Sz.I.

2005.10.17.

-2-

Írjunk ki fordítva !

• Értékkészlet - elemek értékkészletéből • Konstansok - elemek konstansaiból • Művelethalmaz

Feladat: Olvassunk be 10 valós számot a standard inputról és írjuk ki azokat a beolvasással ellentétes sorrendben!

– indexelés (hivatkozás egy elemére) – hivatkozhatunk a címére, így átadhatjuk fv. paraméterként (azaz leírjuk a nevét) tömb neve == tömb címe

– más művelete nincs !!!


© BME-IIT Sz.I.

2005.10.17.

-3-


Írjunk ki fordítva! (2)

© BME-IIT Sz.I.

2005.10.17.

-4-

Írjunk ki fordítva! (3) #include <stdio.h> int main() { float tomb[10]; int i;

Vázlat: Tárolni kell ⇒ tömb for i, 0 to 9 olvas(i) for i, 9 to 0 kiir(i)

for (i = 0; i < 10; i++) scanf(”%f”, &tomb[i]);

}

for (i = 9; i >= 0; i--) printf(”%f ”, tomb[i]); return 0;

Nem trükközünk a for ciklusban, mert így mindenkinek sokkal olvashatóbb!! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

-5-


© BME-IIT Sz.I.

2005.10.17.

-6-

1

Tömbök (3)

Tömbök (4)

Többdimenziós tömbök, for, register

Jellemző fordulat:

int tomb3d[100][100][100]; … { int i,j; register int k; … for (i = 0; i < 100; i++) for (j = 0; j < 100; j++) for (k = 0; k < 100; k++) { … tomb3d[i][j][k]++; … } }

int tomb[100]; int i, n = sizeof(tomb)/sizeof(int); … for (i = 0; i < n; tomb[i++] = 0) ;

k-ra 1000000-szor hivatkozunk. Hogy gyors legyen a kód, CPU regiszterbe kérjük Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

-7-

2005.10.17.

• a tömb méretét a fordító határozza meg; ha változtatunk, elég 1 helyen • inicializáljuk a tömböt a for léptető részében, így üres a ciklusmag Programozás alapjai I. (C nyelv, gyakorlat)

Tömbök (5)

© BME-IIT Sz.I.

2005.10.17.

-8-

Összefoglalás

Kezdeti értékadás tömböknek - elemkonstansok felsorolása:

• A tömbök

char sztring[] = ”hello”; int primek[] = {2,3,5,7,11,13};

– ugyanolyan típusú alapelemből sokat egy egységként tekintünk

• a tömb méretét a fordító határozza meg felsorolt elemkonstansok alapján • ilyenkor nagyon fontos a

• Pl. karakter tömbök, sztring-konstansok

– indexelés: 0-tól tömbméret-1-ig, csak egésszel – többdimenziós tömbök – fizikai tömbméret: sizeof(tombváltozó) – logikai tömbméret (elemek száma):

sizeof(primek)/sizeof(int);

fordulat az elemszám (logikai méret) megahtározásához

sizeof(tombváltozó)/sizeof(elemtípus)

Mekkora a sztring tömb? 6 karakteres a ’\0’ miatt. Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

-9-

Felsorolás v. enumeráció


2005.10.17.

- 10 -

• Értékkészlet – a névvel megadott értékek halmaza • Konstansok – a névvel megadott értékek halmaza + egészek halmaza • Művelethalmaz

felsorolás_spec: enum felsorolás_tip_azonopc { felsorolás_lista }

sz1 = zold; s1 = 0;

© BME-IIT Sz.I.

Felsorolás v. enumeráció (2)

Elsősorban absztrakciós eszköz. Olyan egyedi típus, melynek értékkészlete a névvel megadott értékek halmaza.

enum szinek { piros, zold, tok = 13, makk; } sz1, k23, kartya_szin; enum szinek s1 = makk;


{ 0, 1, 13, 14 }

– egészekre vonatkozó műveletek

k23 = 2; ??? © BME-IIT Sz.I.

2005.10.17.

- 11 -


© BME-IIT Sz.I.

2005.10.17.

- 12 -

2

„ly” számláló

„ly” számláló (vázlat)

• Készítsünk algoritmust és C programot, ami megszámolja a standard bemeneten fájl végéig érkező szövegben az „ly” sorozatotokat!

sz = 0 while olvas(ch) begin ha ch = ‘y’, akkor az előzmények alapján növeljük a számlálót (sz) end

– Az „lly” sorozat kettőnek számít! – Egyéb változat pl: „llly” esetén nem írjuk elő, hogy mit kell csinálni. – Első változatban csak kisbetűket figyelünk.


© BME-IIT Sz.I.

2005.10.17.

(olvas(ch) beolvassa a következő karaktert és hamis fv.értékkel jelzi, ha fájl vége van) - 13 -

Az előzmények

Hogyan emlékezhetünk az előzményekre? – Kóddal, azaz „hol jár a program?”. – Adattal, vagyis egy változóban tároljuk.

2005.10.17.

- 15 -

„ly” számláló programja

© BME-IIT Sz.I.

- 14 -

2005.10.17.


© BME-IIT Sz.I.

2005.10.17.

- 16 -

Állapot fogalma

#include <stdio.h> #define olvas(c) (c = getchar()) != EOF main() { Logikailag karakter, int sz = 0, ch; akkor miért int? while (olvas(ch)) { if (ch == ’l’) if (olvas(ch)) if (ch == ’y’) sz += 1; else if ((ch == ’l’) && olvas(ch)) if (ch == ’y’) sz += 2; } printf(”ly-ok szama: %d\n”, sz); } Programozás alapjai I. (C nyelv, gyakorlat)

2005.10.17.

Még nem jött „l” betű. sz = 0 while olvas(ch) begin Jött „l” betű. if ch == ’l’ if olvas(ch) begin Két „l” betű jött if ch == ’y’ sz = sz + 1 else if ch == ’l’ and olvas(ch) if ch == ’y’ sz = sz + 2 end end kiír(sz)

– Volt-e „l” betű ? – Ha volt, akkor hány „l” betű volt ?

© BME-IIT Sz.I.

© BME-IIT Sz.I.

„ly” számláló algoritmusa

Mik azok az előzmények?



• 3 állapot van – nem jött „l” (alap) – jött „l” (l_jott) – „ll” jött (ll_jott)

• Az állapottól és a következő karaktertől függ a tevékenység és az új állapot. • Az állapotinformáció is tárolható adatként. Állapotgép - 17 -


© BME-IIT Sz.I.

2005.10.17.

- 18 -

3

„ly” számláló állapottere

„ly” számláló állapottáblával

„l” egyéb

alap

l_jott

„y” / +1 egyéb

„l”

„y” / +2 egyéb Programozás alapjai I. (C nyelv, gyakorlat)

ll_jott © BME-IIT Sz.I.

2005.10.17.

- 19 -

egyéb

alap

l_jott

alap

alap

l_jott

ll_jott alap/+1 alap

ll_jott

ll_jott alap/+2 alap

© BME-IIT Sz.I.

2005.10.17.

- 20 -

#include <stdio.h> #define olvas(c) (c = getchar()) != EOF void main() { int sz = 0, ch; enum { alap, l_jott, ll_jott} all = alap; while (olvas(ch)) {

sz = 0 all = alap while olvas(ch) sz_növelés_és_állapot_váltás(ch, all) kiír(sz)

2005.10.17.


„ly” számláló állapotgéppel

Vázlat:

© BME-IIT Sz.I.

„y”

A gráf szemléletesebb, a táblázatból viszont nehezebb kihagyni átmenetet.

„l”



állapot „l”

- 21 -



© BME-IIT Sz.I.

2005.10.17.

- 22 -

Állapotgép előnyei

switch (all) { case alap: if (ch == ’l’) all = l_jott; break; case l_jott: if (ch == ’l’) all = ll_jott; else { all = alap; if (ch == ’y’) sz += 1; } break; case ll_jott: if (ch != ’l’) { all = alap; if (ch == ’y’) sz += 2; } } } /* end while */ printf(”ly-ok szama: %d\n”, sz);

• Könnyebb átlátni, megérteni. • Könnyebb módosítani. • Mechanikus optimalizálási módszerekkel a felesleges állapotok könnyen kiszűrhetők. • Mechanikus a kódolása. • Az egész program táblázatok kitöltéséből áll.

} Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

- 23 -


© BME-IIT Sz.I.

2005.10.17.

- 24 -

4

Megoldás általánosítása

Állapot- és tevékenységtábla

A beolvasott karaktertől és az állapottól függően két feladatunk van:

tev.tábla

• új állapot meghatározása • tevékenység elvégzése

input

Három fajta beolvasott karakterünk és 3 állapotunk van, azaz 3x3 adat határozza meg a következő állapotot, és a tevékenységet. Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

- 25 -

alap l_jott ll_jott

y

egyéb

l_jott / +0 ll_jott / +0 ll_jott / +0

alap / +0 alap / +1 alap / +2

alap / +0 alap / +0 alap / +0


© BME-IIT Sz.I.

2005.10.17.

- 27 -

2005.10.17.

- 26 -


© BME-IIT Sz.I.

2005.10.17.

- 28 -

Megvalósítási kérdések

sz = 0; all = alap; while beolv(ch) begin tip = ch_típusa; sz = sz + tev_tab[all][tip]; all = all_tab[all][tip]; end;

© BME-IIT Sz.I.

© BME-IIT Sz.I.

Ötlet: • Tegyük bele a tevékenységeket és az új állapotot is egy-egy táblázatba. Ebből egyszerű indexeléssel elérhető a köv. állapot ill. a tevékenység.

Táblázatvezérelt program



Táblázatvezérelt program

betű típus l

új állapot

áll.tábla

Állapot- és tevékenységtábla(2) álapot / típus

állapot

tevékenység

• Hogyan töltjük fel a táblázatokat? – elemenként – kezdeti értékadással

• Hogyan állapítjuk meg a ch típusát? – elemi utasításokkal – újabb tömbbel

2005.10.17.

- 29 -


© BME-IIT Sz.I.

2005.10.17.

- 30 -

5

„ly” számláló táblázatai

„ly” számláló táblázattal

typedef enum{ alap, l_jott, ll_jott} all_t; typedef enum{l_betu,y_betu,egyeb_betu} betu_t; int all_tab[3][3] = { l_jott, alap, alap, ll_jott, alap, alap, ll_jott, alap, alap }; int tev_tab[3][3] = { 0, 0, 0, 0, 1, 0, 0, 2, 0 };


© BME-IIT Sz.I.

2005.10.17.

- 31 -

void main() { int sz = 0, ch; betu_t tip; all_t all = alap; while (olvas(ch)) { switch (ch) { case 'l': tip = l_betu; break; case 'y': tip = y_betu; break; default : tip = egyeb_betu; } sz += tev_tab[all][tip]; all = all_tab[all][tip]; } printf("ly-ok szama: %d\n", sz); } Programozás alapjai I. (C nyelv, gyakorlat)

A típus is táblázattal

© BME-IIT Sz.I.

2005.10.17.

tip_tab['l'] = l_betu; tip_tab['y'] = y_betu; while (olvas(ch)) { tip = tip_tab[ch]; sz += tev_tab[all][tip]; all = all_tab[all][tip]; } printf("ly-ok szama: %d\n", sz); } - 33 -


float-ra mutató pointer


© BME-IIT Sz.I.

© BME-IIT Sz.I.

2005.10.17.

- 34 -

Indirekció

• Minden változó és függvény memóriában levő helye (címe) képezhető. (pl: &valtozo) • Ez a cím ún. pointerben vagy mutatóban tárolható. • A pointer egy olyan típus, amelynek az értékkészlete cím, és mindig egy meghatározott típusú objektumra mutat. int-re mutató pointer

- 32 -

void main() { int sz = 0, ch; betu_t tip; all_t all = alap;

Mutatók és címek

int i, *ip; float f, *fp;

2005.10.17.

„ly” számláló tip. táblával

• A betűtípus meghatározása is lehetséges tömbbel. Gyakori, hogy a karakter osztályozó függvényeket is /isxxx()/ így valósítják meg. • Ha az enum definícioját megváltoztatjuk, akkor kihasználhatjuk egyeb_betu==0. Így egyszerűbb a betu_tip globális a tömb feltöltése: typedef enum{egyeb_betu, l_betu, y_betu} betu_t; betu_t tip_tab[256]; /* ebben minden 0 */ • Ez a változtatás sajnos a táblázatok feltöltését is érinti, hiszen megváltozott az index sorrend. Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

ip = &i; fp = &f; 2005.10.17.

float f;

13 i cime int *ip;

float *fp; ip = &i

- 35 -

*ip = 13;

int i;

Memória


© BME-IIT Sz.I.

2005.10.17.

- 36 -

6

Mire jó ?

Pointer típus jellemzői

• Bonyolultabban írjuk le az i =13-at?

• Értékkészlet - adott objektum címe • Konstansok - NULL (0) • Művelethalmaz:

– Lehet egy cél, de nem ez az igazi ok.

• Hardver közeli megoldások. – Olvasható assembly. – Memóriába ágyazott I/O.

– értékadás – indirekció – címaritmetika – relációk

• Dinamikus memóriakezelés. – Nagyon fontos.

• Változó paraméter hiányának kiváltása. – Legalább ennyire fontos. Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

- 37 -

Címaritmetika

© BME-IIT Sz.I.

- 38 -

Már nem létezik float *fp, ft[10]; for (fp = &ft[0]; fp < &ft[10]; *fp++ = 0);

Eggyel való növelés a következő objektum címzését eredményezi. (p = p + 1, p += 1, p++) Programozás alapjai I. (C nyelv, gyakorlat)

2005.10.17.

int *ip, t[10]; for (ip = &t[0]; ip < &t[10]; *ip++ = 0);

p = p + i * sizeof(obj) p = p - i * sizeof(obj) p = (p - p) / sizeof(obj)

p p i

© BME-IIT Sz.I.

Címaritmetika példák

• C nyelv egyik jellegzetessége, és a gépközeli jelleget erősíti. Jelöljük i-vel az egész értéket, p-vel a pointert: p+i p-i p-p


2005.10.17.

Az ip++ ill. az fp++ elemről-elemre lép. Pont akkorát lép, amekkora az adott elem (int ill. float) mérete. - 39 -


© BME-IIT Sz.I.

2005.10.17.

- 40 -

A prioritásra, kötési szabályra és a sorrendre ügyelni!!!

Címaritmetika példák (2)

int *ip, i, t[10]; int *ip, t[10]; *(t+2) = 12;

≡

ip = t; *ip++ = 23; *++ip = 23; (*ip)++;

t[2] = 12;

A tömb azonosítója a 0. elem címét jelenti.

t[i] ≡ *(t+i) &t[i] ≡ t+i

/* Vigyázat a kiértékelés sorrendjét nem * határozza meg a prioritás */ *ip++ = *ip++; /* nem definiált működés !! */ t[i++] = i++; /* nem definiált működés !! */ *i = *ip+++*ip;/* ravasz, de nem jó */

ip = &t[10] ip – t == 10 Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.10.17.

/* mi a fő- és mellékhatás? */ /* hova ír ? */ /* ez mit növel ? */

- 41 -


© BME-IIT Sz.I.

2005.10.17.

- 42 -

7

Programozás alapjai C nyelv 5. gyakorlat. Írjunk ki fordítva! Írjunk ki fordítva! (3)

Recommend Documents