A tétel (record) tétel: különböző típusú adatokat csoportosít, ezeket egyetlen adatként kezeli, de hozzáférhetünk az elemeihez is A tétel elemei mezők. Például tétel: személy elemei: név, lakcím, születési dátum kétféle tételtípus: • rögzített tételtípus személy:
név
cím
születési dátum
• változó tételtípus diák:
név
ösztöndíj évfolyam ösztöndíj (igen) összege
diák:
név
évfolyam ösztöndíj ((nem)
A mezőket az azonosítójukon keresztül érhetjük el: tételazonosító.mezőazonosító
1
Műveletek a tételek szintjén: • értékadás • mezőkiválasztás A tétel absztrakt adattípus Specifikáció: elemek:
véges számú, nem rendezett, nem homogén adathalmaz, minden adat típusa egyénenként meghatározott szerkezet: azonosító minden elemnek (kölcsönös megfeleltetés) műveletek: értékadás egy mezőnek mező értékének lekérdezése értékadás tételek között Legyen R egy tétel típusú azonosító, id egy mező azonosítója (R-ben). Értékadás egy mezőnek: bemenet: R tétel id mezője, v azonosító v. konstans, eredmény: R előfeltétel: v típusa azonos id típusával utófeltétel: az R tétel id mezőjének új értéke v lesz C-ben: R.id = v, Pascalban: R.id := v 2
Mező értékének lekérdezése: bemenet: R tétel id mezője, eredmény: v előfeltétel: v típusa azonos id típusával utófeltétel: v értéke az R tétel id mezőjének értéke lesz C-ben: v = R.id, Pascalban: v := R.id Értékadás tételek között: bemenet: R2 tétel, eredmény: R1 tétel előfeltétel: R1, R2 azonos típusúak utófeltétel: R1 felveszi R2 értékét C-ben: R1 = R2, Pascalban: R1 := R2 Tételek C-ben és Pascalban C-ben Pascalban struct tétel{ típus_1 mezőlista_1; típus_2 mezőlista_2; ... típus_n mezőlista_n; } változólista;
type tétel=record mezőlista_1: típus_1; mezőlista_2: típus_2; ... mezőlista_n: típus_n; end;
struct tétel változólista;
3
var
változólista: tétel;
C++-ban egyéb lehetőségek: struct vektor{ int* e; int d; void init(int* e0, int d0); void torol() {delete [] e;} void negyzet(); void kiir(); }; void vektor::init(int* e0, int d0); { d=d0; e = new int [d]; for (int i=0; i
Az objektumelvű programozásban újabb lehetőségek: osztályok, objektumok — átveszik a tétel szerepét Tömbök (array) tömb: azonos típusú elemek halmaz, a memóriában folytonosan helyezkednek el felhasználás: tömbazonosító, indexelés leggyakoribbak: egydimenziós tömb (vektor): [első..utolsó] ...
A 6
első
6
6
6
első+1 első+2
hivatkozás: A[i] kétdimenziós tömb (mátrix) A ... i
A[i, j]
6
utolsó−1 utolsó
... ...
j sorok, oszlopok hivatkozás: A[i, j] vagy A[i][j] 5
Ábrázolásmódok deklaráció (példák): Pascalban: var változó : array[elsőindex..utolsóindex] of típus; var változó : array[elsőindex1..utolsóindex1, elsőindex2..utolsóindex2] of típus; var v: var m:
array[1..20] of integer; array[1..10,1..15] of real;
v[12], m[2,6] C++-ban típus változó[méret]; nullával kezdődő index típus[méret] változó; típus változó[méret] = konstanslista; típus[méret] változó = konstanslista; int a[5] int a[5]={1,2,3,4,5} int a[]={1,2,3,4,5} 5 elemű tömb, hivatkozások: a[0], . . . a[4] double b[6][5] int c[3][2]={1,2,3,4,5,6} 30, illetve 6 elemű tömbök, hivatkozások pl.: b[0][4], c[2][1] 6
helyfoglalás Pascalban statikus C-ben: malloc, calloc, free függvények a stdlib.h-ból int sz[6]; statikus helyfoglalás float *fp fp = (float*)malloc(5*sizeof(float)), dinamikus helyfoglalás fp[2] hivatkozás a 2. elemre free(fp) C++-ban: new és delete operátorok int * c = new int[10]; delete [] c;
7
#include<stdio.h> #include<stdlib.h>
// malloc miatt
main(){ int a[10], c[]={0,1,2,3,4,5,6,7,8,9}, *p;
for (int i=0; i<10;i++) a[i]=c[i]*c[i]; for (i=0; i<10;i++) printf("%5d", a[i]); printf("\n"); for (p=a; p-a<10;p++) printf("%5d", *p); printf("\n\n"); int
b[5][5];
for (i=0; i<5;i++) for (int j=0; j<5;j++) b[i][j]=i+j; 8
for (i=0; i<5;i++) { for (j=0; j<5;j++) printf("%5d", b[i][j]); printf("\n"); }; printf("\n"); // egydimenzios tomb dinamikusan int n, *x; printf("n="); scanf("%d",&n); x=(int*)malloc(n*sizeof(int)); for (i=0; i
9
// ketdimenzios tomb dinamikusan int m; int **y; printf("m="); scanf("%d",&m); printf("n="); scanf("%d",&n); y=(int**)malloc(m*sizeof(int*)); for (i=0; i<m;i++) y[i]=(int*)malloc(n*sizeof(int)); for (i=0; i<m;i++) for (j=0; j
Tömbök megfeleltetési függvényei (Array Mapping Functions) 10 soros 20 oszlopos mátrix esetében: típus A[10][20] a0,0 ... a0,19 6
6
0
a1,0 ... a1,19 6
19 20
6
39
... ai,j ...
a9,0 ... a9,19
6
k = 20i + j
6
180
6
199
Legyen A n-dimenziós tömb: felső indexhatárok: s1, s2, . . . sn alsó indexhatár mindenhol 0 (azaz típus A[s1][s2] . . . [sn ]) Aktuális index: [i1][i2] . . . [in ]. Mennyi k (az Ai1 ,i2 ,...,in elem sorszáma)?
k=
n X j=1
δj ij ,
ha j = n 1, n Y ahol δj = sk ha 1 ≤ j < n. k=j+1
Ha címet szeretnénk: cím(Ai1 ,i2 ,...,in ) = A + sizeof(típus)
n X j=1
11
δj ij
A cím kiszámítása C++-ban, ha a típust T -vel jelöljük: unsigned int product = 1; T* address = A; for (int j = n; j >= 1; --j){ address += product * ij ; product *= sj ; } A tömbök paraméterei Az A tömb címe legyen a, elemei mérete h, a dimenzió n, alsó indexhatárai: e1, e2, . . . en felső indexhatárai: u1, u2, . . . un , aktuális indexek: i1, i2, . . . in. egydimenziós tömb: indexhatárok: e, u cím(Ai ) = cím(Ae ) + h(i − e) = (a − he) + hi = c0 + c1 i, ahol c1 = h, c0 = a − c1e kétdimenziós tömb: indexhatárok: e1, e2, u1, u2 cím(Aij ) = cím(Ae1 e2 ) + h(i − e1)(u2 − e2 + 1) + h(j − e2) = c0 + c1 i + c2j, ahol c2 = h, c1 = (u2 − e2 + 1)c2, c0 = a − c1 e1 − c2e2
12
n-dimenziós tömb: indexhatárok: e1, e2, . . . en; u1, u2, . . . un cím(Ai1 ,i2 ,...,in ) = c0 + c1 i1 + c2i2 + . . . + cn in cn = h ... ck−1 = (uk − ek + 1)ck , ahol 1 < k ≤ n ... c0 = a − c1e1 − c2 e2 − . . . − cn en Sajátos tömbök Háromszögű mátrix Legyen a következő mátrix: a11 0 0 . . . 0 a a 21 22 0 . . . 0 A = a31 a32 a33 . . . 0 ... ... ... ... ... an1 an2 an3 . . . ann Kezdőcím: a, elemméret h:
cím(aij ) = a + 1 + 2 + 3 + . . . + (i − 1) h + (j − 1)h hi(i − 1) = a+ + (j − 1)h 2 = c0 + c1i(i − 1) + c2j 13
ahol c2 c2 = h, c1 = , c0 = a − h. 2 Ritka tömbök A nem nulla elemeket őrizzük csak meg: (i, j, aij ) Háromsoros ábrázolás
1 ≤ i ≤ m, 1 ≤ j ≤ n
Eredeti mátrix: a11 a12 a13 a14 a15 a16 a17 0 0 4 0 0 5 0 a21 a22 a23 a24 a25 a26 a27 = 0 1 0 0 0 7 0 a31 a32 a33 a34 a35 a36 a37 0 0 0 0 0 8 9 Háromsoros ábrázolás: sor oszlop érték
= (1,1,2,2,3,3) = (3,6,2,6,6,7) = (4,5,1,7,8,9)
i j aij
14
A ritka tömb leképezése Leképez 1. k := 0 2. for i := 1 to m m a sorok száma do for j := 1 to n n az oszlopok száma 3. 4. if aij 6= 0 then k := k + 1 5. 6. sork := i 7. oszlopk := j 8. ertekk := aij 9. return k, sor, oszlop, ertek Adott indexű elem lekérdezése Adott a három vektor, és k értéke (mindegyik vektor ennyi elemű): Keres(i, j) k a vektorok elemszáma 1. for p := 1 to k 2. do if (sorp = i) és (oszlopp = j) 3. then return ertekp 4. if (sorp > i) 5. then return 0 6. return 0
15
Négysoros ábrázolás Mint előbb, csak még van egy negyedik vektor is, a mutató. Példa. a11 a12 a13 a14 a15 a16 a17 0 0 4 0 0 5 0 a21 a22 a23 a24 a25 a26 a27 = 0 1 0 0 0 7 0 a31 a32 a33 a34 a35 a36 a37 0 0 0 0 0 8 9 sor oszlop érték mutató
= = = =
(1,1,2,2,3,3) (3,6,2,6,6,7) (4,5,1,7,8,9) (0,4,0,5,0,0)
i j aij
A 4 a második elem a mutatóban, azt jelenti, hogy a háromsoros ábrázolásban a 2. index (1. sor, 6. oszlop: 5) egy olyan oszlopban (6.) levő elemet őriz, amely oszlopban még van nemnulla elem (a 7 a 2. sor 6. oszlopában), ennek az indexe szerepel itt, a 4 (negyedik helyen szerepel a háromsoros ábrázolásban).
16
Ritka m´atrixok ,,´abr´azol´asa”
17
#include <stdio.h> #include <stdlib.h> // dinamikusan helyet foglal egy matrixnak int ** lefoglal(int rows, int cols){ int i; int **m=(int**)malloc(rows*sizeof(int*)); for (i=0; i
// helyet foglal az m matrixnak // helyet foglal az x matrixnak
for (i=0; i<10;i++) for (j=0; j<=10;j++)m[i][j]=i*j; listaz(m,rows, cols); printf("\n"); x=m; listaz(x,rows, cols); return 0; }
// m erteket kap
// kilistazza az m matrixot // m-et x-be masolja // kilistazza az x matrixot
