Programozás alapjai C nyelv 8. gyakorlat. Mutatók és címek (ism.) Indirekció (ism)

Programozás alapjai C nyelv 8. gyakorlat Szeberényi Imre BME IIT

<[email protected]>

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

© BME-IIT Sz.I.

2005.11.07.

-1-

Mutatók és címek (ism.) • 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 i, *ip; float f, *fp;

int-re mutató pointer float-ra mutató pointer


© BME-IIT Sz.I.

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

-2-

Indirekció (ism) *ip = 13;

int i;

float f;

13 i cime int *ip;

float *fp; ip = &i

Memória


© BME-IIT Sz.I.

2005.11.07.

-3-

1

Néhány dolog érthetőbb (ism.) • Scanf-nél az & jelentése ? • Miért nincs tömbök között értékadás. (t1 = t2) ? • Tömb, mint fv. paraméter. • Miért nem hibás az if ( ”alma” == ”alma”) utasítás, de mégsem működik ? • Miért hibás a .... case ”alma”: utasítás ?


© BME-IIT Sz.I.

2005.11.07.

-4-

Dinamikus adatszerkezet • Az adatok száma nem ismert előre. • Nem tudunk vagy nem akarunk feleslegesen helyet foglalni az adatoknak. • A feladat dinamikusan változhat.


© BME-IIT Sz.I.

2005.11.07.

-5-

Változók a memóriában int i; float f; int *ip; float *fp; Halom (heap)


© BME-IIT Sz.I.

2005.11.07.

-6-

2

malloc() hatása int i; float f; int *ip; float *fp;

cím

fp = malloc(sizeof(float));


© BME-IIT Sz.I.

2005.11.07.

-7-

Allokált terület használata int i; float f; int *ip; float *fp; fp = malloc(sizeof(float));

cím 3.14

*fp = 3.14 Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

-8-

malloc() standard függvény <stdlib.h> void *malloc(size_t size); void free(void *p);

• A malloc lefoglal a dinamikus területen egy, a paramétereként kapott méretű területet. • Visszaadja a lefoglalt terület kezdőcímét, hiba eseten NULL-t. • A free felszabadítja a lefoglalt területet. Nincs ellenőrzés ! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

-9-

3

Ujabb malloc int i; float f; int *ip; cím

float *fp; fp = malloc(sizeof(float));


3.14

© BME-IIT Sz.I.

2005.11.07.

- 10 -

Elveszett !!! Van megoldás ? • Minden dinamikus változóhoz saját pointer kell, egyébként nem érhető el az adat! • Mégis kell tudni előre az adatok számát? • Hol van itt az ígért rugalmasság? • Miért nem tárolhatom a pointert együtt az adattal? • LÁNCOLT szerkezet! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 11 -

Önhivatkozó struktúra struct elem { int i; struct elem *kov; } e, *p; Miért kell a zárójel?

e.i = 8; p = &e; (*p).i = 12;


p->i = 12; Szemléletesebb

© BME-IIT Sz.I.

2005.11.07.

- 12 -

4

Lánc kialakítása typedef struct elem { int i; struct elem *kov; } elem_t; elem_t *kezd; kezd = malloc(sizeof(elem_t)); kezd->i = 35;

35

kezd->kov = malloc(sizeof(elem_t));

88

kezd->kov->i = 88; Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 13 -

Láncolt adatszerkezet

KEZD

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 14 -

Duplán láncolt adatszerkezet KEZD1

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

NULL ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 15 -

5

Rendezve építés

KEZD

15 KOV

2 KOV

32 KOV

634 KOV

NULL 8 KOV


© BME-IIT Sz.I.

2005.11.07.

- 16 -

Feladat 1 • Olvassunk be a standard inputról fájl végéig egész számokat, és írjuk ki azokat fordított sorrendben! A nem számjegy karaktereket tekintsük elválasztónak és dobjuk el! • Tárolnunk kell, mert az utolsó adatot kell először kiírni. • Mivel az input adatok számát előre nem ismerjük, dinamikus adatszerkezetet kell használnunk! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 17 -

Vázlat (adatszerkezet) typedef struct lanc_str { int i; struct lanc_str *kov; } lanc_elem, *lanc_poi; pointer típus struktúra típus


© BME-IIT Sz.I.

2005.11.07.

- 18 -

6

Vázlat (algoritmus)

KEZD

I KOV

I KOV

I KOV

I KOV

I KOV

I KOV

I KOV

I KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 19 -

Vázlat (algoritmus) kezdo = NULL while olvas(i) kezdo = lancol(kezdo, i) kiir(kezdo) (olvas(i) beolvassa a következő egész értéket és hamis fv.értékkel jelzi, ha fájl vége volt. A nem számjegy karaktereket elválasztónak tekinti és eldobja.) Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 20 -

Függvény spec. - beolvas int olvas(int *i); – Int értékű függvény, beolvassa a következő egészet a standard inputról. A nem számjegy karaktereket eldobja. – bemenet: • standard input

– kimenet: • függvényérték: hamis (0), ha fájl vége volt • az olvasott egész (változó paraméter hiányában címet kell átadni) Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 21 -

7

Függvény spec. - lancol lanc_poi lancol(lanc_poi p, int i); – A paraméterként kapott lánc elejére felvesz egy új elemet, amelybe az integer paraméterként kapott értéket teszi. – bemenet: • lánc elejére mutató pointer. NULL, ha üres • felveendő érték

– kimenet: • függvényérték: lánc elejére mutató pointer, NULL, ha elfogyott a memória Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 22 -

Függvény spec. - kiir void kiir(lanc_poi p); – Void függvény (eljárás) a paraméterként kapott láncot kiírja – bemenet: • lánc elejére mutató pointer. NULL, ha üres

– kimenet: • standard output


© BME-IIT Sz.I.

2005.11.07.

- 23 -

Implementáció - lancol lanc_poi lancol(lanc_poi p, int i) { lanc_poi uj; if (uj = malloc(sizeof(lanc_elem))){ uj->i = i; /* érték beírása */ uj->kov = p; /* befűz az elejére */ } return(uj); } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 24 -

8

Implementáció - kiir void kiir(lanc_poi p) { while (p != NULL) { printf(”%6d”, p->i); /* érték kiírása */ p = p->kov; /* következőre */ } }


© BME-IIT Sz.I.

2005.11.07.

- 25 -

Implementáció - beolvas int olvas(int *i) { int r ;

}

while ((r = scanf(”%d”, i)) == 0) scanf(”%*c”); return(r != EOF); csillag jelentése a formátumlistán


© BME-IIT Sz.I.

2005.11.07.

- 26 -

Implementáció - program #include <stdio.h> #include <stdlib.h> typedef struct lanc_str { int i; struct lanc_str *kov; } lanc_elem, *lanc_poi; … alprogramok … Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 27 -

9

Implementáció - program main() { int n; lanc_poi kezdo = NULL; while (olvas(&n)) kezdo = lancol(kezdo, n); kiir(kezdo);

Meg kellene vizsgálni, hogy NULL-e!

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

© BME-IIT Sz.I.

2005.11.07.

- 28 -

Feladat 2 • Olvassunk be a standard inputról file végéig egész számokat, és írjuk ki azokat nagyság szerint rendezve! (Az előző feladathoz hasonlóan a nem számjegy karaktereket tekintsük elválasztónak és dobjuk el!)

• Tárolnunk kell a rendezés miatt. • Mivel az input adatok számát előre nem ismerjük, dinamikus adatszerkezetet kell használnunk! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 29 -

Megoldási alternatívák • Láncot építünk és utólag rendezzük. – túl sok pointert kell egyszerre kezelni:

12 KOV

23 KOV

15 KOV

41 KOV

Nem okos megoldás ! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 30 -

10

Megoldási alternatívák • Rendezve építjük a láncot

25 KOV

12 KOV

35 KOV

41 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 31 -

2005.11.07.

- 32 -

Vázlat (algoritmus) kezdo = NULL while olvas(i) kezdo = beszur(kezdo, i) kiir(kezdo)


© BME-IIT Sz.I.

Alprogram spec. - beszur lanc_poi beszur(lanc_poi kp, int i); – A paraméterként kapott láncba beszúr egy új elemet, amelybe az integer paraméterként kapott értéket teszi. – bemenet: • lánc elejére mutató pointer. NULL, ha üres • felveendő érték

– kimenet: • függvényérték: lánc elejére mutató pointer, NULL, ha elfogyott a memória Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 33 -

11

Beszúrás a láncba Három különböző eset van: • Új elem a lánc belsejébe kerül. • Új elem a lánc elejére kerül. • Új elem a lánc végére kerül.


© BME-IIT Sz.I.

2005.11.07.

- 34 -

Beszúrás a lánc belsejébe

KEZD

12 KOV

25 KOV

35 KOV

41 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 35 -

Beszúrás a lánc elejére

KEZD

12 KOV

25 KOV

35 KOV

41 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 36 -

12

Beszúrás a lánc végére

12 KOV

KEZD

25 KOV

35 KOV

151 KOV

41 KOV

NULL


© BME-IIT Sz.I.

2005.11.07.

- 37 -

A megfelelő hely keresése Módosítani kell!

KEZD

12 KOV

25 KOV

35 KOV

41 KOV

NULL p = kezd; while (p != NULL && p->i < i) p = p->kov; Programozás alapjai I. (C nyelv, gyakorlat)

34 KOV

© BME-IIT Sz.I.

2005.11.07.

- 38 -

Lemaradó pointer

KEZD

12 KOV

25 KOV

35 KOV

41 KOV

NULL pl = kezd; p = kezd; while (p != NULL && p->i < i) { pl = p; p = p->kov; } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

34 KOV

2005.11.07.

- 39 -

13

Implementáció - beszúr lanc_poi beszur(lanc_poi kp, int i) { lanc_poi uj, p, pl; uj = malloc(sizeof(lanc_elem)); if (uj == NULL) return(NULL); uj->i = i; p = kp; pl = p; while (p != NULL && p->i < i) { pl = p; /* lemaradó poi. */ p = p->kov; /* futó poi. */ } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 40 -

Implementáció - beszúr if (p == kp) kp = uj; else pl->kov = uj; uj->kov = p; return(kp);

/* elejére kell */ /* nem az elejére */ /* új mögötti rész */

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

© BME-IIT Sz.I.

2005.11.07.

- 41 -

Implementáció - program … alprogramok … main() { Precedencia ! int n; lanc_poi kezdo = NULL; while (olvas(&n)) if ((kezdo = beszur(kezdo, n)) == NULL) printf(”Elfogyott a memória\n), exit(1); kiir(kezdo); } Vessző op.! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 42 -

14

Miért kell figyelni az elejét ? • Külön kezelést igényel, mert a „kezdo” nem dinamikus változó, de a többi pointer igen, azaz: kezdo = valami, de a többi esetben p->kov = valami Ötlet: • Tegyünk a lánc elejére egy kamu elemet!


© BME-IIT Sz.I.

2005.11.07.

- 43 -

Láncolt lista strázsával

KEZD

????? KOV

25 KOV

35 KOV

41 KOV

NULL


© BME-IIT Sz.I.

2005.11.07.

- 44 -

Implementáció - beszúr2 lanc_poi beszur2(lanc_poi kp, int i) { Elöl van strázsa! lanc_poi uj, p, pl; uj = malloc(sizeof(lanc_elem)); if (uj == NULL) return(NULL); uj->i = i; pl = kp; p = kp->kov; while (p != NULL && p->i < i) { pl = p; p = p->kov; Egyszerűbb! } pl->kov = uj; uj->kov = p; return(uj); } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 45 -

15

Implementáció - kiir2 void kiir2(lanc_poi p) { p = p->kov; /* strázsa átlépése */ while (p != NULL) { printf(”%6d”, p->i); /* érték kiírása */ p = p->kov; /* következőre */ } } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 46 -

Implementáció - program2 … alprogramok … main() { int n; lanc_poi kezdo = malloc(sizeof(lanc_elem)); kezdo->kov = NULL; /* strázsa létrehozása */ kezdo nem változik while (olvas(&n)) if (beszur2(kezdo, n) == NULL) printf(”Elfogyott a memória\n), exit(1); kiir2(kezdo); } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 47 -

Miért kell a lemaradó pointer ? • A megtalált elem elé kell beszúrni. Ötlet: • Szúrjuk be mögé az új elemet, és abba tegyük át a régi elemet! • Ezután a régi elembe írhatjuk az új értéket!


© BME-IIT Sz.I.

2005.11.07.

- 48 -

16

Hova kell strázsa? • Az elejére sohasem szúrunk be, mert ha az első elem elé kellene, akkor is az elem mögé vesszük fel az új struktúrát. Az elejére ezért nem kell strázsa. • Csak egy pointert akarunk használni, és nem engedjük meg, hogy az NULL értéket vegyen fel. A lánc végén ezért van strázsa.


© BME-IIT Sz.I.

2005.11.07.

- 49 -

Beszúrás másolással KEZD

12 KOV

15 beszúrása

15 25 KOV

35 KOV

41 KOV

???? KOV

25 KOV

NULL

ne „fussunk le” a láncról Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 50 -

Implementáció - beszúr3 lanc_poi beszur3(lanc_poi p, int i) { lanc_poi uj; uj = malloc(sizeof(lanc_elem)); if (uj == NULL) return(NULL); while (p->kov != NULL && p->i < i) p = p->kov; strázsa hátul van *uj = *p; /* teljes struktúrát másolja */ p->i = i; /* beír a régibe */ p->kov = uj; /* beláncolja az újat */ return(p); } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 51 -

17

Implementáció - kiir3 void kiir3(lanc_poi p) { while (p->kov != NULL) { /* hátul van a str. */ printf(”%6d”, p->i); /* érték kiírása */ p = p->kov; /* következőre */ } }


© BME-IIT Sz.I.

2005.11.07.

- 52 -

Implementáció - program3 … alprogramok … main() { int n; lanc_poi kezdo = malloc(sizeof(lanc_elem)); kezdo->kov = NULL; /* strázsa létrehozása */ kezdo nem változik while (olvas(&n)) if (beszur3(kezdo, n) == NULL) printf(”Elfogyott a memória\n), exit(1); kiir3(kezdo); a str. miatt másik kiíró kell } Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 53 -

Mikor használható ez a trükk ? • Ha az adat nem nagy, ugyanis minden beszúráskor a teljes struktúrát lemásoljuk. Nagy méretű adat esetén (>2-3Kb) ez számottevő idő lehet.


© BME-IIT Sz.I.

2005.11.07.

- 54 -

18

Összefoglalás • Dinamikus területen tetszőleges számú adat hozható létre (malloc). • Minden ilyen adat egy pointeren keresztül érhető el. • Láncolt adatszerkezet ötlete – a következő adat pointerét az előző adat mellett tároljuk


© BME-IIT Sz.I.

2005.11.07.

- 55 -

Láncolt szerkezet tulajdonságai • Előnyök: – elvileg tetszőlegesen sok adat tárolható – nem kell előre meghatározni az adatok számát – rendezés egyszerű, többnyire az építés már rendezetten történik – az adatkapcsolatok jól ábrázolhatók

• Hátrányok: – az adat mellett még egy pointert is tárolni kell – nem érhető el tetszőleges sorrendben az adat – könnyű elszakítani a láncot (hibás kezelés) Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

- 56 -

19

Programozás alapjai C nyelv 8. gyakorlat. Mutatók és címek (ism.) Indirekció (ism)

Recommend Documents