Információs Technológia

Információs Technológia A C programozási nyelv elemei, rendező algoritmusok

Fodor Attila Pannon Egyetem Műszaki Informatikai Kar Villamosmérnöki és Információs Rendszerek Tanszék [email protected]

2010. november 25.

Kommunikáció a program és az operációs rendszer között

Program elindítása

Operációs rendszer fő feladatai

File kezelés Tárgazdálkodás Felhasználói felület Perifériák kezelés Erőforrásokkal való gazdálkodás Ütemezés Hálózatkezelés Programok és állományok védelme

Fodor Attila (Pannon Egyetem)

Információs technológia

2010. november 25.

2 / 40



Program indítása, leállítása menete

Programot tartalmazó állomány megkeresése a háttértárolón Programkód betöltése a háttértárból a memóriába Környezet átadásához a meghatározott memóriaterület lefoglalása, feltöltése Program neve Elérési út Paraméterek

Vezérlés átadása a betöltött program meghatározott címére Program futtatása... Program visszatérési érték átadása az operációs rendszernek Program által használt memória felszabadítása



2010. november 25.

3 / 40



Paraméterek átadása a programnak

Program meghívása programneve param1 param2 param3 \eleresi\ut\programneve param1 param2 param3

Program kódja C nyelvben int main(int argc, char* argv[]) { ... return 0; }



2010. november 25.

4 / 40



A main függvény változatai

ANSI szabvány által megengedett void main( void ); int main( void ); int main( int argc[ , char *argv[ ] [, char *envp[ ] ] ] );

Microsoft specifikus: int wmain( ); int wmain( int argc[ , wchar_t *argv[ ] [, wchar_t *envp[ ] ] ] );

Paraméterek argc - Parancssor-argumentumok száma argv - Karaktersorozatokat tartalmazó tömböt címző mutató A 0. paraméter a program neve envp - Felhasználói környezetben lévő változók



2010. november 25.

5 / 40



A main függvény változatai

ANSI szabvány által megengedett void main( void ); int main( void ); int main( int argc[ , char *argv[ ] [, char *envp[ ] ] ] );

Microsoft specifikus: int wmain( ); //int main( int argc, char *argv[ ], char *envp[ ] ) int main(int argc, char* argv[]) { ... return 0; }



2010. november 25.

6 / 40



Paraméterek és környezeti változók feldolgozása

int main( int argc, char *argv[ ], char *envp[ ] ) { int i; for(i=0; i<argc; i++) { printf("%d. parameter: %s\n", i, argv[i]); ... \\paraméterek feldolgozása } while (envp[i+1] != NULL) { printf("%d. körny. változó: %s\n", i, envp[i]); ... \\környezeti változók feldolgozása i++; } ... return 0; }



2010. november 25.

7 / 40



Paraméterek és környezeti változók feldolgozása (példa)

J:\FOA\Egyetem\Inf_tech\Orai_peldak\Inftech_lista\Debug\Inftech_lista.exe aaaa bbb c

0. parameter: J:\FOA\Egyetem\Inf_tech\Orai_peldak\Inftech_lista\Debug\Inftech_lista. 1. parameter: aaaa 2. parameter: bbb 3. parameter: ccc 4. korny. valtozo: ComSpec=C:\windows\system32\cmd.exe 5. korny. valtozo: DFSTRACINGON=FALSE 6. korny. valtozo: FARLANG=English 7. korny. valtozo: FP_NO_HOST_CHECK=NO 8. korny. valtozo: HOMEDRIVE=C: 9. korny. valtozo: HOMEPATH=\Users\fodora 10. korny. valtozo: INCLUDE=C:\Program Files\Microsoft Visual Studio .NET 2003\SDK\v 11. korny. valtozo: KMP_DUPLICATE_LIB_OK=TRUE 12. korny. valtozo: LIB=C:\Program Files\Microsoft Visual Studio .NET 2003\SDK\v1.1\ 13. korny. valtozo: LOCALAPPDATA=C:\Users\fodora\AppData\Local 14. korny. valtozo: LOGONSERVER=\\CHARON 15. korny. valtozo: MKL_SERIAL=YES 16. korny. valtozo: NIDAQmxSwitchDir=C:\Program Files\National Instruments\NI-DAQ\Sw 17. korny. valtozo: NIIVIPATH=C:\Program Files\IVI\ ... 42. korny. valtozo: VXIPNPPATH=C:\Program Files\IVI Foundation\VISA\ 43. korny. valtozo: windir=C:\windows Fodor Attila (Pannon Egyetem)


2010. november 25.

8 / 40



Paraméterek és környezeti változók feldolgozása (példa) Inftech_lista.exe aaaa bbb ccc

0. parameter: Inftech_lista.exe 1. parameter: aaaa 2. parameter: bbb 3. parameter: ccc 4. korny. valtozo: ComSpec=C:\windows\system32\cmd.exe 5. korny. valtozo: DFSTRACINGON=FALSE 6. korny. valtozo: FARLANG=English 7. korny. valtozo: FP_NO_HOST_CHECK=NO 8. korny. valtozo: HOMEDRIVE=C: 9. korny. valtozo: HOMEPATH=\Users\fodora 10. korny. valtozo: INCLUDE=C:\Program Files\Microsoft Visual Studio .NET 2003\SDK\v 11. korny. valtozo: KMP_DUPLICATE_LIB_OK=TRUE 12. korny. valtozo: LIB=C:\Program Files\Microsoft Visual Studio .NET 2003\SDK\v1.1\ 13. korny. valtozo: LOCALAPPDATA=C:\Users\fodora\AppData\Local 14. korny. valtozo: LOGONSERVER=\\CHARON 15. korny. valtozo: MKL_SERIAL=YES 16. korny. valtozo: NIDAQmxSwitchDir=C:\Program Files\National Instruments\NI-DAQ\Sw 17. korny. valtozo: NIIVIPATH=C:\Program Files\IVI\ ... 42. korny. valtozo: VXIPNPPATH=C:\Program Files\IVI Foundation\VISA\ 43. korny. valtozo: windir=C:\windows Fodor Attila (Pannon Egyetem)


2010. november 25.

9 / 40

C programozási nyelv

Goto

Goto

Nehezen átlátható Strukturált programozás elveivel ellentétes Minden olyan probléma, amely goto-val van megoldva megoldható struktúráltan is (Bizonyos esetekben a goto alkalmazása egyszerűbb megoldást eredményezne) Néha azonban megkerülése felesleges (Például: többszörösen egymásba ágyazott ciklusok) A cégek Coding Standard-jai általában tiltják!!!



2010. november 25.

10 / 40


Goto

Goto alkalmazása

Függvényen belüli (lokális) C nyelv által támogatott goto cimke_neve HELYETTE: break continue

Függvényen kívül (globális) C nyelv által támogatott setjmp, longjmp TILOS !!! Ha mégis, akkor különösen indokolt esetben !!!



2010. november 25.

11 / 40


Goto

Goto (példa) #include <stdio.h> int main() { int i, j; for ( i = 0; i < 10; i++ ) { printf( "Kulso ciklus i = %d\n", i ); for ( j = 0; j < 2; j++ ) { printf( " Belso ciklus j = %d\n", j ); if ( i == 3 ) goto stop; } } /* Ezt nem irja ki... */ printf( "Ciklus vege i = %d\n", i ); stop: printf( "stop cimkere ugras i = %d\n", i ); }



2010. november 25.

12 / 40


Typedef

Typedef Olyan azonosítot definiál, amely későbbiekben saját típusnévként használható Így létrehozott típusok megnevezése: typedef nevek Valóságban nem vezet be új típust, csupán szinonímát hoz létre Létrehozása: Deklarátorban szereplő névhez hozzárendel egy típusnevet typedef int egeszszam, *egeszmutato; typedef struct { double x, y, r; } kor;

Változó létrehozása, használata: egeszszam i; egeszmutato p; kor k; k.x = 1.23; Fodor Attila (Pannon Egyetem)


2010. november 25.

13 / 40


Függvénypointer

Függvénypointer

A változókhoz hasonlóan, függvényt is el lehet érni indirekten Alkalmazás oka: Függvény is átadható paraméterként A függvényekre mutató pointerek tömbökbe is szervezhetőek Sokkal rugalmasabb program készíthető Függvényre mutató pointer: int (*fp)(double x); int - visszatérési érték fp - pointer neve x - függvény paramétere (double típus)



2010. november 25.

14 / 40


Függvénypointer

Pointerek fajtái (áttekintés)

char a char *a char **a

- karakter típusú változó - karakter típusú pointer - karakter típusú mutatóra mutató mutató

char *a[] char **a[] char (*a)[]

- karakter típusú pointerek tömbje - karakter típusú mutatóra mutató mutatók tömbje - karakter típusú tömbre mutató pointer

char a() char *a()

- karakter típusú függvény - karakter típusú pointerrel visszatérő függvény

char (*a)() - karakter típusú függvényre mutató pointer char (*a[])() - karakter típusú függvényre mutató pointereket tartalmazó tömb



2010. november 25.

15 / 40

Rendezések

Rendezések (ismétlés)

Buborék rendezés 1. (ismétlés) egesz i, j, minind, tmp, v[], n n = egesz_tomb_merete / egy_elem_merete for(i=n-1; i>1; i-- ) for(j=0; j
Összehasonlítás: N(N − 1)/2 O(n2 ) Mozgatás: 3N(N − 1)/2 O(n2 ) Fodor Attila (Pannon Egyetem)


2010. november 25.

16 / 40

Rendezések


Buborék rendezés 1. (ismétlés)

int i, j, minind, tmp, v[10], n; n=sizeof(v)/sizeof(int); for(i=n-1; i>1; i-- ) for(j=0; j


2010. november 25.

17 / 40

Rendezések


Buborék rendezés 2. (ismétlés) egesz i, j, minind, tmp, v[], n n = egesz_tomb_merete / egy_elem_merete for(i=0; i
Összehasonlítás: N(N − 1)/2 O(n2 ) Mozgatás: 3N(N − 1)/2 O(n2 ) Fodor Attila (Pannon Egyetem)


2010. november 25.

18 / 40

Rendezések


Buborék rendezés 2. (ismétlés)

int i, j, minind, tmp, v[10], n; n=sizeof(v)/sizeof(int); for(i=0; i


2010. november 25.

19 / 40

Rendezések


Minimum kiválasztásos rendezés (ismétlés) egesz i, j, minind, tmp, n egesz v[] n = egesz_tomb_merete / egy_elem_merete for(i=0; i
// csere

Összehasonlítás: N(N − 1)/2 O(n2 ) Mozgatás: 3(N − 1) O(n) Fodor Attila (Pannon Egyetem)


2010. november 25.

20 / 40

Rendezések


Minimum kiválasztásos rendezés (ismétlés)

int i, j, minind, tmp; int v[10], n; n=sizeof(v)/sizeof(int); for(i=0; i
// csere

}



2010. november 25.

21 / 40

Rendezések


Koktél rendezés

Hasonlóan mőködik mint a buborék rendezés Kettő irányból történik a vizsgálat. A legrosszabb eset: is O(n2 ) műveletre Majdnem rendezett lista esetén: körülbelül O(n)



2010. november 25.

22 / 40

Rendezések


Koktél rendezés int bottom = 0; int top = n-1; int swap = TRUE; while (swap == TRUE) { swap = FALSE; for(int i=bottom; ia[i+1]) { swap = TRUE; tmp = a[i]; a[i] = a[i+1]; a[i+1] = tmp; } top--; for(int i=top; i>bottom; i--) if (a[i]
//csere volt

//

top = top-1;

// bottom = bottom+1;


2010. november 25.

23 / 40

Rendezések


Kerti törpe rendezés Megkeresi az első olyan helyet, ahol két egymást követő elem rossz sorrendben van ⇒ megcseréli őket Ha egy ilyen csere után rossz sorrend keletkezik (csak a legutolsó csere előtt lehet) ⇒ ellenőrizni kell int i=1, tmp; while (i
//ha jó a sorrend előre lép


2010. november 25.

24 / 40

Rendezések


Beillesztéses rendezés A soron következő elemnek megkeressük a helyét a tőle balra lévő rendezett részben Ezzel párhuzamosan a nagyobb elemeket rendre eggyel jobbra kell mozgatni int v[10], i, j, y, n; n=sizeof(v)/sizeof(int); for(i=1; i0) && (v[j]>y); j--) { v[j+1] = v[j]; j = j-1; } v[j+1] = y; }

Összehasonlítás: O(n2 ) Mozgatás: O(n2 ) Fodor Attila (Pannon Egyetem)


2010. november 25.

25 / 40

Rendezések

Kupac rendezés (Heap sort)

Kupac adatszerkezet és tulajdonságai

Kupac adatszerkezet Bináris kupac: Egy majdnem teljes bináris fa egy tömbben ábrázolva A tömb mérete = kupac mérete = N

Kupactulajdonsag Kupac tulajdonsag: A kupac minden i, gyökértől különböző eleme eseten: A[Szul.(i)] . A[i] Egy olyan binaris fát képvisel, amelyre igaz, hogy minden csúcs bal es jobb oldali részfájában csak kisebb vagy egyenlő értékek talalhatók. (Ez nem azonos a bináris keresőfa adatszerkezettel!!!)



2010. november 25.

26 / 40

Rendezések


Kupacolás /* TFH i-re nem teljesül a kupactulajdonság */ void kupacol(int i, int tomb[], int meret) { int bal, jobb, legnagyobb, csere; bal = balkupac(i); jobb = jobbkupac(i); if (bal<=meret && tomb[bal]>tomb[i]) legnagyobb = bal; else legnagyobb = i; if (jobb<=meret && tomb[jobb]>tomb[legnagyobb]) legnagyobb = jobb; if (legnagyobb!=i) { csere = tomb[i]; tomb[i] = tomb[legnagyobb]; tomb[legnagyobb] = csere; kupacol(legnagyobb); } }

A rossz helyen levő elemeket lefelé görgeti, mindig a nagyobb gyerek Információs technológia 2010. november 25. 27 / 40 felé


Rendezések


Kupacolás (példa)



2010. november 25.

28 / 40

Rendezések


Kupacolás teljes fára

Kupac építés A fa minden egyes elemére, a levelek feletti elemtől kezdve a gyökérig (bottom-up) void epit(int tomb[], int meret) { int i; for (i=(meret-1)/2; i>0; i--) kupacol(i, tomb, meret); }



2010. november 25.

29 / 40

Rendezések


Kupacolás teljes fára Kupac rendezés a legnagyobb elem a gyökér, az legyen a legutolsó ⇒ az utolsót és az elsőt cseréljük Hatékonyság: O(nlog (n)) void rendez(int tomb[], int hossz) { int i, csere; epit(tomb, hossz); for (i=hossz-1; i>0; i--) { csere = tomb[i]; tomb[i]=tomb[0]; kupacol(0, tomb, hossz); } }



2010. november 25.

30 / 40

Rendezések


Kupacolás (példa)



2010. november 25.

31 / 40

Rendezések

Gyorsrendezés (Quick sort) (Hoare, 1962)

Gyorsrendezés (Quick sort) (Hoare, 1962) Alapelve: 1. felosztjuk az adatokat A[p..r] és A1[p..q] és A2[q..r] szakaszokra úgy, hogy A1<=A2 (NINCS RENDEZVE!!!) 2. Az A1 és A2 résztömböket rendezzük (az 1-es módszer folyamatos ismétlésével) Nincs szükség összefésülésre

Az algoritmus sarokpontja: az 1. felosztó lépés Megvalósítása többféle lehet void gyorsrendez(int tomb[], int also, int felso) { int kozep; if (also

2010. november 25.

32 / 40

Rendezések


Qsort megvalalósítása (csere, kiírás) void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } int choose_pivot(int i,int j ) { return((i+j) /2); } void printlist(int list[],int n) { int i; for(i=0;i


2010. november 25.

33 / 40

Rendezések


Qsort megvalalósítása (rendezés) void quicksort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = choose_pivot(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n; while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j--; if( i < j) swap(&list[i],&list[j]); } swap(&list[m],&list[j]); //2 elem csereje // rekurziv rendezes quicksort(list,m,j-1); quicksort(list,j+1,n); } }



2010. november 25.

34 / 40

Rendezések


Qsort megvalalósítása (meghívása) void main() { const int MAX_ELEMENTS = 10; int list[MAX_ELEMENTS]; int i = 0; // veletlenszamok generalasa for(i = 0; i < MAX_ELEMENTS; i++ ){ list[i] = rand(); } printf("Adatok rednezes elott:\n"); printlist(list,MAX_ELEMENTS); // rendezes quicksort algoritmussal quicksort(list,0,MAX_ELEMENTS-1); printf("Adatok rednezes utan:\n"); printlist(list,MAX_ELEMENTS); }



2010. november 25.

35 / 40

Rendezések


Qsort függvény Quick sort algoritmust használó függvény általános célra Az összehasonlító függvényt paraméterként nekünk kell megadni Prototípusa: void qsort(void *base, size_t num, size_t width, int (*cmp)(void *e1, void *e2)); base: Adatokra mutató pointer num: Adatok száma width: Adat mérete (byte-ban) Utolsó paraméter: Összehasonlító függvényre mutató pointer Például: int compare(int **a, int **b) { return a>b?1:0; }



2010. november 25.

36 / 40

Rendezések


Beépített qsort rendezés alkalmazása #include <stdlib.h> #include <string.h> #include <stdio.h> int compare( const void *arg1, const void *arg2 ); int main( int argc, char **argv ) { int i; /* Eliminate argv[0] from sort: */ argv++; argc--; /* Sort remaining args using Quicksort algorithm: */ qsort( (void *)argv, (size_t)argc, sizeof( char * ), compare ); /* Output sorted list: */ for( i = 0; i < argc; ++i ) printf( " %s", argv[i] ); printf( "\n" ); } int compare( const void *arg1, const void *arg2 ) { /* Compare all of both strings: */ return _stricmp( * ( char** ) arg1, * ( char** ) arg2 ); }



2010. november 25.

37 / 40

Rendezések

Shell rendezés

Shell rendezés

A Shell-módszer nem foglalkozik egyszerre minden elemmel Egyszerre egymástól adott távolságra lévőkkel foglalkozik A rendezés itt is több menetben történik Minden menet elején meghatározunk egy úgynevezett lépésközt, a L-t (adott menetben a vektor egymástól L távolságra lévő elemeit rendezzük) Az induló lépésköz meghatározása úgy történik, hogy a rendezéshez szükséges menetek száma körülbelül log2 N legyen Lépésszám: O(nlog2 n)



2010. november 25.

38 / 40

Rendezések

Shell rendezés

Shell rendezés

egesz t[], L egesz i, j, y L = EGESZ_KONVERZIO( LOG(N)/LOG(2) ) Ciklus amíg L>=1 Ciklus k=L+1-től 2*L-ig Ciklus i=k-tól N-ig L-esével növelve j = i-L y = t[i] Ciklus amíg j>0 és t[j]>y t[j+L] = t[j] j = j-L Ciklus vége t[j+L] = y Ciklus vége Ciklus vége L = Kovetkezo_L(L) Ciklus vége



2010. november 25.

39 / 40

Rendezések

Shell rendezés

További rendezési algoritmusok

Szétosztó rendezés Leszámláló rendezés Radix (számjegyes) rendezés Edény rendezés



2010. november 25.

40 / 40

Információs Technológia

Recommend Documents