OAF Gregorics Tibor : Memória használat C++ szemmel (munkafüzet) 1

OAF

Gregorics Tibor : Memória használat – C++ szemmel (munkafüzet)

1

Számábrázolás Számok bináris alakja A számítógépek memóriájában a számokat bináris alakban (kettes számrendszerben) ábrázoljuk. A bináris alakban felírt szám egy számjegye 0 vagy 1 értékű lehet. Ezt hívjuk bitnek. A számjegy értéke a pozíciójától, a helyiértékétől függ. A kettes számrendszer helyiértékei a kettő hatványai. Egy természetes szám bináris alakjának számjegyeit helyiérték szerint növekvő sorrendben egy kettővel való osztogatásos módszerrel lehet előállítani. Az osztásoknál keletkezett maradék a soron következő számjegy, az osztás eredménye pedig a következő osztás osztandója. Az osztogatás addig tart, amíg az osztandó nem nulla. Példa: Adjuk meg a 183(10) bináris alakját! 183 : 2 = 91 maradt: 1 91 : 2 = 45 maradt: 1 45 : 2 = 22 maradt: 1 22 : 2 = 11 maradt: 0 11 : 2 = 5 maradt: 1 5 : 2 = 2 maradt: 1 2 : 2 = 1 maradt: 0 1 : 2 = 0 maradt: 1 Tehát 183(10) = 10110111(2) = 1*27 + 0*26 + 1*25 + 1*24 + 0*23 + 1*22 + 1*21 + 1*20 Egy törtszám bináris alakjának számjegyeit helyiérték szerint csökkenő sorrendben egy kettővel való szorzásos módszerrel lehet előállítani. A szorzat egész része a soron következő számjegy, törtrésze a következő szorzás szorzandója. A módszer addig tart, amíg a szorzandó nem nulla, de előfordulhat, hogy ez nem következik be, mert a kettes számrendszerben felírt szám egy végtelen kettedes tört lesz. Példa: Adjuk meg a 0.8125(10) bináris alakját! 0.8125 * 2 = 1.6250 egészrész: 1 törtrész: 0.625 0.625 * 2 = 1.250 egészrész: 1 törtrész: 0.25 0.25 * 2 = 0.50 egészrész: 0 törtrész: 0.5 0.5 * 2 = 1.0 egészrész: 1 törtrész: 0 Tehát 0.75(10) = 0.1101(2) = 1*1/2 + 1*1/4 + 0*1/8 + 1*1/16 Példa: Adjuk meg a 0.1(10) bináris alakját! 0.1 * 2 = 0.2 egészrész: 0 törtrész: 0.2 0.2 * 2 = 0.4 egészrész: 0 törtrész: 0.4 0.4 * 2 = 0.8 egészrész: 0 törtrész: 0.8 0.8 * 2 = 1.6 egészrész: 1 törtrész: 0.6 0.6 * 2 = 1.2 egészrész: 1 törtrész: 0.2 0.2 * 2 = 0.4 egészrész: 0 törtrész: 0.4 0.4 * 2 = 0.8 egészrész: 0 törtrész: 0.8 … Tehát 0.1(10) = 0.00011… (2) (végtelen szakaszos tört)

OAF


2

Természetes számok ábrázolása A számítógépeken a 8 bit (1 bájt) többszörösein történik az ábrázolás, hiszen csak a bájt a memória legkisebb címezhető egysége. A természetes számok ábrázolásánál egyszerűen kettes számrendszerbe váltjuk át a számot. Egyetlen kérdés az, hogy rendelkezésre áll-e elegendő bit, a számjegyek ábrázolására. Ha nem, túlcsordulásról beszélünk. Ilyenkor az eredeti szám értéke hibásan rögzül. Egész számok ábrázolása Az egész számok ábrázolása abban tér el a természetes számokétól, hogy a szám abszolút értéke mellett az előjelét is ábrázolni kell. Az abszolút értéket bináris alakban ábrázoljuk, az előjelet pedig egyetlen biten. Történetileg többféle ábrázolás is kialakult. Egyenes kód: A számokat s biten ábrázoljuk úgy, hogy az első biten a szám előjelét (0 - pozitív, 1 negatív), utána pedig a szám abszolút értékének bináris alakját. Az ábrázolható számok -2s-1 +1 és 2s-1–1 közé kell, hogy essenek, ellenkező esetben túlcsordulás lép fel. Az ábrázolás hátránya, hogy a nullát két különböző kód is jelzi (00000000 illetve 10000000), továbbá az, hogy két szám összegét a számok előjelétől függő módszerekkel lehet kiszámolni. Egyes komplemens kód vagy inverz kód: A számokat s biten ábrázoljuk úgy, hogy az abszolút értékének bináris alakja nullával kezdődjön. Az ábrázolható számok -2s-1+1 és 2s-1–1 közé kell, hogy essenek, ellenkező esetben túlcsordulás lép fel. A pozitív egész számot ezzel a bináris alakkal kódoljuk, a negatív egész szám esetén az abszolút érték 0-val kezdődő bináris alakját komplementáljuk. (Ilyenkor az első bit 1-es lesz, amely jelzi, hogy a szám negatív.) Az ábrázolás hátránya, hogy a nullát két különböző kód is jelzi (00000000 illetve 11111111), továbbá az, hogy két szám összeadásakor keletkező túlcsordulás bitet (legmagasabb helyiértéken keletkező átvitel) hozzá kell adni az eredményhez, ha a helyes eredményt akarjuk megkapni (feltéve, hogy az eredmény is ábrázolható s biten). Kettes komplemens kód: Az egész számok általánosan elterjedt kódolása. A számokat s biten ábrázoljuk úgy, hogy az abszolút értékének bináris alakja nullával kezdődjön. Az ábrázolható számok -2s-1 és 2s-1–1 közé kell, hogy essenek, ellenkező esetben túlcsordulás lép fel. A pozitív egész számot ezzel a bináris alakkal kódoljuk, a negatív egész szám esetén a szám abszolút értékének bináris alakját komplementáljuk és hozzáadunk egyet. (Az első bit jelzi, hogy a szám pozitív-e vagy negatív: 0 - pozitív, 1 - negatív.) 1. Példa. Adjuk meg a +12 egész szám kettes komplemens kódját 4 bájton! i) 12(10) = 00000000 00000000 00000000 00001100(2)

OAF


3

2. Példa. Adjuk meg a -12 egész szám kettes komplemens kódját! i) 12(10) = 00000000 00000000 00000000 00001100(2) ii) Vegyük a bináris alak komplementerét! 11111111 11111111 11111111 11110011 iii) Adjunk hozzá binárisan 1-et! 11111111 11111111 11111111 11110100 Többletes kód: A számokhoz, mielőtt binárisan ábrázoljuk őket, hozzáadunk egy rögzített értéket (eltolás), és az így kapott számnak vesszük a bináris alakját. Az eltolás mértékét úgy állapítjuk meg, hogy az ábrázolni kívánt számok az eltolás után ne legyenek negatívak. Például ha s biten kívánjuk a számainkat ábrázolni, akkor az eltolás lehet a 2s-1. Ekkor ennek bináris alakja (100…00) jelenti a nullát és az ábrázolható számok -2s-1 és 2s-1–1 közé esnek. (Az első bit most is a szám előjelét jelzi, de 1 – pozitív és 0 - negatív.) Ha az eltolásnak a 2s-1–1-et választjuk, akkor a nulla kódja 01111111 lesz, az ábrázolható számok -2s-1+1 és 2s-1 közé esnek. Elsősorban számok nagyság szerinti összehasonlításához, számok összegének és különbségének kiszámolásához alkalmas ábrázolás. Fixpontos számábrázolás Valós számok ábrázolása úgy, hogy rögzített számú biten lehet külön a szám egészrészét és külön a törtrészét ábrázolni. Az előjel ábrázolására alkalmazhatók az egész számok ábrázolásánál bemutatott módszerek BCD számábrázolás A binárisan kódolt decimális számokat tízes számrendszerben ábrázoljuk, de a számjegyeket binárisan kódoljuk, többnyire egy számjegyet félbájton. Külön félbájt szolgál az előjel jelzésére. Ez a forma kevésbé alkalmas a számok közötti műveletek elvégzésére. Lebegőpontos számábrázolás Valós számok IEEE 754 szabvány szerinti (4 illetve 8 bájtos) lebegőpontos ábrázolásánál a számokat ((-2)*b+1)*m*2k alakban írjuk fel, ahol b az előjel (0 - pozitív, 1 - negatív), az m a mantissza (1 m<2), a k pedig a karakterisztika. Maga a kód a valós szám előjelbitjéből (1 bit), utána s biten (az s 8 illetve 11 bit) a karakterisztika 2s-1–1 eltolású többletes kódjából (ekkor 2s-1+1 k 2s-1), végül a mantissza bináris alakjának törtrészéből (23 illetve 52 biten) áll. Példa: Adjuk meg a -12.25 valós szám lebegőpontos kódját 1+11+52 biten! i. Negatív szám, ezért az előjel bit 0 lesz: b = 0 ii. A szám abszolút értékének bináris alakja: 12.25(10) = 1100.01(2) iii. Normalizáljuk az így kapott számot 1 és 2 közé: 1100.01(2) = 1.10001(2) *23 iv. Ábrázoljuk a karakterisztikát többletes kódban 11 biten: 3+210 –1 (10) = 10000000010(2) v. Állítsuk össze a kódot: 1 10000000010 10001000000000000000 … 00000000

OAF


4

Adatábrázolás Karakterek ábrázolása Egy adott karakterkészlet elemeit, karaktereit megsorszámozunk 0-val kezdődően, és ezeket a sorszámokat tároljuk binárisan kódolva a megfelelő karakter helyett. Az egyik legegyszerűbb az ASCII karakterkészket, amelyik 256 különböző karaktert tartalmaz. A 0 és 255 közötti sorszámok bináris kódja egy bájton ábrázolható. Az UTF-8 változó hosszú kódolással ábrázolja a karaktereket (magába foglalja és 1 bájton ábrázolja az ASCII karaktereket, de például az ékezetes betűk sorszámai 2 bájton kódolódnak) Logikai érték ábrázolása Habár a logikai érték tárolására egyetlen bit is elég lenne, de mivel a legkisebb címezhető egység a bájt, ezért egy bájtot foglal el. A nulla értékű (csupa nulla bit) bájt a hamis értéket, minden más az igaz értéket reprezentálja. Struktúra ábrázolása Egy struktúra mezői közvetlenül egymás után foglalnak helyet a memóriában. Az első elem címe egyben a struktúra címe is. Például egy -5 egész számot és egy hamis logikai értéket magába foglaló struktúra esetén a memória egymást követő 5 bájtján, először 4 bájton a -5 kettes komplemens kódja, majd egy csupa nulla bitből álló bájt jelenik meg. (struct valami{ int n; bool l}) Tömb ábrázolása Egy tömb elemei közvetlenül egymás után, sorban helyezkednek el a memóriában. Az első elem címe egyben a tömb címe is. Például négy egész számot tartalmazó [0, 1, -5, 3] tömb esetében a memória egymás utáni 16 bájtján fog elhelyezkedni a négy egész szám kettes komplemens kódja. (int v[] = {0, 1, -5, 3}) A több dimenziós tömb felfogható eggyel kevesebb dimenziós tömbök tömbjeként. Például a mátrix felfogható, mint sorainak tömbje (ez a sor-folytonos szemlélet), vagy oszlopainak tömbje (ez az oszlop-folytonos szemlélet). Sor-folytonos szemlélet esetén a mátrixok sorait közvetlenül egymás után tároljuk, a sorok tárolására pedig a korábban elmondottak érvényesek. Karakterlánc ábrázolása A karakterlánc egy változtatható hosszúságú karaktersorozat. A karakterek kódját sorban egymás után tároljuk el. A sorozat hosszát vagy egy külön számláló (ez többnyire a lánc előtt tárolt egész szám, ami a karakterlánc kezdetét jelző címen található) vagy a lánc végén utolsó utáni karakterként elhelyezett speciális karakter (’\0’) jelzi.

OAF


Pointerváltozó és közvetett hivatkozás Változó

int i = -2

Pointer

int *p

Közvetett hivatkozás int i; int *p = &i; *p = 3;

Referencia változó

int i = -2; int &r = i;

5

OAF


Tömbök és pointerek Automatikus helyfoglalású tömb

int v[] = {0, 1, -5, 3}

v == &v == &v[0] v[0] == *v

Pointer és tömb

int *p; p = v;

*(p+2) = -3; p[2] = 12; *(v+2) = -5;

6

OAF


Dinamikus helyfoglalás

int *p;

p = new int;

*p = -2;

delete p;

Dinamikus helyfoglalású tömb

int* v;

v = new int[4];

for(int i=0; i<4; ++i) v[i] = i;

delete[] v;

7

OAF


8

Feladat Rendezzük növekvő sorrendbe egy mátrix sorait a sorösszegek alapján! Használjunk buborékrendezést!

Megoldás A feladat megoldásához szükségünk lesz egy mátrixra, amelyet a szabványos bementről töltünk fel. A rendezéshez először kiszámoljuk a mátrix sorösszegeit, és azokat a sorok indexeivel együtt egy egydimenziós tömbben tároljuk el. A rendezést ugyanis nem közvetlenül a mátrixon hajtjuk végre (a sorok cseréje túl költséges lenne), hanem ezen a sorösszeg-sorindex párokat tartalmazó segédvektoron. A segédvektor elemeit az összegérétkek alapján sorba rendezzük. A rendezés után a segédvektor i-edik eleme azt mutatja majd meg, hogy a rendezett mátrix (amit fizikailag nem kell létrehoznunk) i-edik sora az eredeti mátrix hányadik sorának felel meg. Ez alapján tudjuk a szabványos kimeneten az átrendezett mátrixot megjeleníteni úgy, hogy közben a mátrix a kezdeti tartalmát őrzi. Specifikáció A = (t : Zn×m, v : Párn) Pár = rec(ért: Z, ind: Z) Ef = ( t = t’) Uf = ( t = t’ v’ : Párn i [1..n]: v’[i] = ( j=1..m t[i,j], i)

v = rendezett(v’) )

Absztrakt program Előkészítés: A v tömböt az utófeltételben szereplő v’ értékűre állítja be.

i = 1 .. n v[i].ért := össz(i)

s := össz(i) s := 0

v[i].ért :=i

j = 1 .. m s := s + t[i,j]

Buborékrendezés: A v tömb rendezése „ért” szerint.

i = 2 .. n menet(v, i, k)

menet(v, i, k) k := n

i := k

j:=n .. i v[j].ért < v[j-1].ért csere(j,j-1) k := j

SKIP

OAF


9

Megjelenítés: A t mátrix sorainak megjelenítése összegük szerinti növekedő sorrendben a v tömb segítségével.

i = 1 .. n i = 1 .. n Ír(t[v[i].ind][j]

Megoldás C++-ban Az implementációt három változatban készítjük el. A mátrixot és a segédvektort először statikusan lefoglalt tömbökkel másodszor dinamikusan lefoglalt tömbökkel, végül a vector< > sablon segítségével ábrázoljuk. Az első változathoz szükség van a max maximális méretre. A tömbjeinket (mátrixot és a rendezésnél használt segédvektort) ekkora méretűre deklaráljuk. A max×max méretű mátrixnak természetesen csak egy n×m-es részét, a max méretű segédvektornak pedig az első n elemét használjuk. Hátránya ennek a megoldásnak, hogy egyfelől memória pazarlás, másfelől ellenőrizni kell, hogy a tényleges méretek nem nagyobbak-e a max értéknél. A második változatban mind a mátrixot, mind a rendezéshez használt segédvektort dinamikusan foglaljuk le. Ez a megoldás a memória felhasználásában takarékos, de magunknak kell gondoskodni a memória terület lefoglalásáról és felszabadításáról, illetve annak a kivételnek a kezeléséről, amely akkor keletkezik, ha az általunk kért memória foglalás nem sikerül. A harmadik változat hátterében is dinamikus memória foglalás történik, de ezt elrejti előlünk a vector< > típus. További előny, hogy itt nem kell a tömbök paraméterátadásánál külön átadni a tömb aktuális méretét, az bármikor lekérdezhető tulajdonsága a tömbnek. Mindhárom változat main() függvénye tartalmazza az alábbi négy szakaszt, amely a dinamikusan lefoglalt tömbök használatánál kiegészül a tömb felszabadítását végző ötödik szakasszal (ez meghívja a free() függvényt) is: 1. Mátrix létrehozása és feltöltése (meghívja a read() függvényt) A mátrix deklarációja után a read()függvény végzi el a mátrix feltöltését. A második változatban a mátrix deklarációja még csak egy pointert jelez. 2. Segédvektor létrehozása és feltöltése (meghívja a sum() függvényt) A segédvektort a változatnak megfelelően deklaráljuk, majd az absztrakt programban megadott módon feltöltjük. A segédvektor egy elemének kitöltéséhez az absztrakt programban megadott s:=össz(i) függvényt a sum() függvény implementálja. 3. Segédvektor rendezése (meghívja a session() függvényt) Az absztrakt program alapján működik, az abban megadott k:=menet(i) függvényt implementálja a session() függvény. 4. Rendezett mátrix kiírása (meghívja a write() függvényt) A mátrix sorainak a rendezés utáni sorrendjében történő kiírása. Ehhez a segédvektort használjuk hiszen annak i-edik eleme mutatja meg, hogy a rendezett mátrix (amit fizikailag nem hoztunk létre) i-edik sora az eredeti mátrix hányadik sorának felel meg.

OAF


1. Változat #include #include #define max 100 using namespace std; struct Pair { int value; int ind; }; void read(int t[][max], int &n, int &m); int sum(const int x[], const int m); int session(Pair v[], const int n, const int i); void write(const Pair v[], const int t[][max], const int n, const int m); int main() { int t[max][max]; int n, m; // Mátrix beolvasása read(t, n, m); // Előkészítés Pair v[max]; for(int i=0; i> ch; return 0; }

10

OAF


2. Változat #include #include using namespace std; struct Pair { int value; int ind; }; void read(int** &t, int &n, int &m); int sum(const int x[], const int m); int session(Pair v[], const int n, const int i); void write(const Pair v[], int** t, const int n, const int m); void free(int** &t, const int n); int main() { int** t; int n, m; // Mátrix beolvasása read(t, n, m); // Előkészítés try{ Pair* v = new Pair[n]; }catch(std::bad_alloc o){ cout << "Memória foglalási hiba\n"; exit(1); { for(int i=0; i> ch; return 0; }

11

OAF


3. Változat #include #include #include using namespace std; struct Pair { int value; int ind; }; void read(vector > &t); int sum(const vector &x); int session(vector<Pair> &v, const int i); void write(const vector > &t); int main() { vector > t; // Mátrix beolvasása read(t); int n = (int)t.size(); // Előkészítés vector<Pair> v; for(int i=0; i> ch; return 0; }

12

OAF


13

Függvények A read() függvény megvalósításai természetesen eltérnek: az első változat csak feltölti a max×max méretű mátrix n×m-es részét, a második változat lefoglalja az n darab sor számára az m méretű helyeket, a harmadik változat elrejti ezt a memóriafoglalást, erre csak a resize() metódus hívása utal. void read(int t[][max], int &n, int &m) // 1.VÁLTOZAT { cout << "n: "; cin >> n; cout << "m: "; cin >> m; if(n>max || m>max){ cout << ”Hibás méretek!”; char ch; cin >> ch; exit(2); } for(int i=0; i> t[i][j]; } } void read(int** &t, int &n, int &m) // 2. VÁLTOZAT { try{ cout << "n: "; cin >> n; cout << "m: "; cin >> m; t = new int*[n]; for(int i=0; i> t[i][j]; } } }catch(std::bad_alloc o){ cout << "Memória foglalási hiba\n"; char ch; cin >> ch; exit(1); } } void read(vector > &t) // 3. VÁLTOZAT { int n; cout << "n: "; cin >> n; t.resize(n); int m; cout << "m: "; cin >> m; for(int i=0; i> t[i][j]; } } }

OAF


14

A write() függvény a v segédvektor által megadott sorrendben írja ki a mátrix sorait a szabványos kimenetre. Az i-edikként kiírt sor sorszáma a v[i].ind-ben található, ezért az i-edik sor j-edik elemének kiírása a cout << t[v[i].ind][j] utasítással történik. A write() függvény ezért csak a szignatúrájában különbözi a három változatban, de a harmadik változatban a tömbök méretének megadása most is a size() metódussal történik. void write(const Pair v[], const int t[max][], const int n, const int m) { for(int i=0; i &v, vector > &t) { for(int i=0; i<(int)t.size(); ++i){ for(int j=0; j<(int)t[v[i].ind].size(); ++j) cout << t[v[i].ind][j] << "\t"; cout << endl; } } // 3.VÁLTOZAT

A második változat második paramétere nem const, ugyanis nem megengedett const int** változónak egy int** értékül adása, erre pedig a main() függvényből való meghívásnál sor kerül.

A második változatban nekünk kell gondoskodni a lefoglalt terület felszabadításáról. void free(int** &t, const int n) { for(int i=0; i
OAF


15

A sum() és a session() az absztrakt program alapján készült, az első két változatban teljesen azonos. int sum(const int x[], const int m) { int s = 0; for(int j=0; j<m; ++j) s += x[j]; return s; } int session(Pair v[], const int n, const int i) { int k = n-1; for(int j=n-1; j>i-1; --j) if( v[j].value < v[j-1].value ){ Pair c = v[j]; v[j] = v[j-1]; v[j-1] = c; k = j; } return k; }

A harmadik változatban ezeknek a függvényeknek más lesz a szignatúrája. int sum(const vector &x); int session(vector<Pair> &v, const int i);

A függvénytörzsben egyetlen eltérés van: a paraméterként megkapott tömbök méretét nem tartalmazza külön paraméterváltozó (m illetve n), mert azt lekérdezhetjük a size() metódussal ( (int)x.size() illetve (int)v.size()).

OAF Gregorics Tibor : Memória használat C++ szemmel (munkafüzet) 1

Recommend Documents