Mutatók és címek (ism.) Programozás alapjai C nyelv 8. gyakorlat. Indirekció (ism) Néhány dolog érthetőbb (ism.) Változók a memóriában

Mutatók és címek (ism.)

Programozás alapjai C nyelv 8. gyakorlat

• 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.

Szeberényi Imre BME IIT

<[email protected]>

int i, *ip; float f, *fp; Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

-1-

Indirekció (ism)

i cime int *ip; float *fp; ip = &i

Memória

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

© BME-IIT Sz.I.


© BME-IIT Sz.I.

2005.11.07.

-2-

• 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 ?

float f;

13

float-ra mutató pointer

ip = &i; fp = &f;

Néhány dolog érthetőbb (ism.)

*ip = 13;

int i;

int-re mutató pointer

2005.11.07.

-3-

Dinamikus adatszerkezet


© BME-IIT Sz.I.

2005.11.07.

-4-

Változók a memóriában int i;

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

float f; int *ip; float *fp; Halom (heap)


© BME-IIT Sz.I.

2005.11.07.

-5-


© BME-IIT Sz.I.

2005.11.07.

-6-

1

malloc() hatása

Allokált terület használata

int i;

int i;

float f;

float f;

int *ip;

int *ip;

float *fp;

cím

cím

float *fp;

fp = malloc(sizeof(float));

fp = malloc(sizeof(float));

3.14

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

© BME-IIT Sz.I.

2005.11.07.

-7-


malloc() standard függvény

© BME-IIT Sz.I.

2005.11.07.

-8-

2005.11.07.

- 10 -

Ujabb malloc

<stdlib.h> void *malloc(size_t size); void free(void *p);

int i; float f; int *ip;

• 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.

cím

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

3.14

Nincs ellenőrzés ! Programozás alapjai I. (C nyelv, gyakorlat)

© BME-IIT Sz.I.

2005.11.07.

-9-


Elveszett !!! Van megoldás ?

Önhivatkozó struktúra struct elem { int i; struct elem *kov; } e, *p;

• 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.

© BME-IIT Sz.I.

Miért kell a zárójel? - 11 -

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


p->i = 12; Szemléletesebb

© BME-IIT Sz.I.

2005.11.07.

- 12 -

2

Lánc kialakítása

Láncolt adatszerkezet

typedef struct elem { int i; struct elem *kov; } elem_t;

KEZD

ADAT KOV

ADAT KOV

ADAT KOV

ADAT KOV

elem_t *kezd; kezd = malloc(sizeof(elem_t)); kezd->i = 35;

ADAT KOV

35

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

88

ADAT KOV

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

2005.11.07.

ADAT KOV

ADAT KOV

ADAT KOV

NULL © BME-IIT Sz.I.

- 13 -


Duplán láncolt adatszerkezet KEZD1

ADAT KOV

ADAT KOV

© BME-IIT Sz.I.

2005.11.07.

- 14 -

Rendezve építés

ADAT KOV

KEZD

15 KOV

2 KOV

32 KOV

634 KOV

NULL ADAT KOV

ADAT KOV

ADAT KOV

NULL

ADAT KOV

8 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 15 -

Feladat 1

© BME-IIT Sz.I.

© BME-IIT Sz.I.

2005.11.07.

- 16 -

Vázlat (adatszerkezet)

• 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)


2005.11.07.

typedef struct lanc_str { int i; struct lanc_str *kov; } lanc_elem, *lanc_poi; pointer típus struktúra típus

- 17 -


© BME-IIT Sz.I.

2005.11.07.

- 18 -

3

Vázlat (algoritmus)

KEZD

I KOV

I KOV

I KOV

I KOV


I KOV

I KOV

kezdo = NULL while olvas(i) kezdo = lancol(kezdo, i) kiir(kezdo)

I KOV

(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.)

I KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 19 -


Függvény spec. - beolvas

2005.11.07.

- 20 -

Függvény spec. - lancol

int olvas(int *i);

lanc_poi lancol(lanc_poi p, 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:

– A paraméterként kapott lánc elejére felvesz egy új elemet, amelybe az integer paraméterként kapott értéket teszi. – bemenet:

• standard input

• lánc elejére mutató pointer. NULL, ha üres • felveendő érték

– 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.

© BME-IIT Sz.I.

2005.11.07.

– kimenet: • függvényérték: lánc elejére mutató pointer, NULL, ha elfogyott a memória - 21 -


Függvény spec. - kiir

© BME-IIT Sz.I.

2005.11.07.

- 22 -

Implementáció - lancol lanc_poi lancol(lanc_poi p, int i) { lanc_poi uj;

void kiir(lanc_poi p); – Void függvény (eljárás) a paraméterként kapott láncot kiírja – bemenet:

if (uj = malloc(sizeof(lanc_elem))){ uj->i = i; /* érték beírása */ uj->kov = p; /* befűz az elejére */ } return(uj);

• lánc elejére mutató pointer. NULL, ha üres

– kimenet: • standard output

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

© BME-IIT Sz.I.

2005.11.07.

- 23 -


© BME-IIT Sz.I.

2005.11.07.

- 24 -

4

Implementáció - kiir

Implementáció - beolvas

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

int olvas(int *i) { int r ;


© BME-IIT Sz.I.

2005.11.07.

- 25 -

formátumlistán


Implementáció - program

© BME-IIT Sz.I.

2005.11.07.

- 26 -


#include <stdio.h> #include <stdlib.h>

main() { int n; lanc_poi kezdo = NULL;

typedef struct lanc_str { int i; struct lanc_str *kov; } lanc_elem, *lanc_poi;

while (olvas(&n)) kezdo = lancol(kezdo, n); kiir(kezdo);

Meg kellene vizsgálni, hogy NULL-e!

}

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

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

© BME-IIT Sz.I.

2005.11.07.

- 27 -

Feladat 2


© BME-IIT Sz.I.

2005.11.07.

- 28 -

Megoldási alternatívák

• 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

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

nem számjegy karaktereket tekintsük elválasztónak és dobjuk el!) 12 KOV

• 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.

23 KOV

15 KOV

41 KOV

Nem okos megoldás ! - 29 -


© BME-IIT Sz.I.

2005.11.07.

- 30 -

5

Megoldási alternatívák


• Rendezve építjük a láncot

25 KOV

12 KOV

35 KOV

kezdo = NULL while olvas(i) kezdo = beszur(kezdo, i) kiir(kezdo)

41 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 31 -


Alprogram spec. - beszur

© BME-IIT Sz.I.

2005.11.07.

- 32 -

2005.11.07.

- 34 -

Beszúrás a láncba

lanc_poi beszur(lanc_poi kp, int i);

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.

– 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 -


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

KEZD

12 KOV

25 KOV

35 KOV

© BME-IIT Sz.I.

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

41 KOV

KEZD

12 KOV

25 KOV

35 KOV

41 KOV

NULL

NULL 9 KOV

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

© BME-IIT Sz.I.

2005.11.07.

- 35 -


© BME-IIT Sz.I.

2005.11.07.

- 36 -

6

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

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

12 KOV

KEZD

25 KOV

35 KOV

KEZD

41 KOV

12 KOV

25 KOV

35 KOV

41 KOV

NULL 151 KOV

p = kezd; while (p != NULL && p->i < i) p = p->kov;

NULL


© BME-IIT Sz.I.

2005.11.07.

- 37 -

Lemaradó pointer

KEZD

12 KOV

25 KOV

41 KOV

NULL


© BME-IIT Sz.I.

34 KOV

2005.11.07.

- 39 -

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

- 38 -

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

2005.11.07.

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 -

… 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.!

/* elejére kell */

© BME-IIT Sz.I.

2005.11.07.



© BME-IIT Sz.I.

Implementáció - beszúr

35 KOV

pl = kezd; p = kezd; while (p != NULL && p->i < i) { pl = p; p = p->kov; }


34 KOV

- 41 -


© BME-IIT Sz.I.

2005.11.07.

- 42 -

7

Miért kell figyelni az elejét ?

Láncolt lista strázsával

• 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.

KEZD

????? KOV

25 KOV

35 KOV

41 KOV

NULL

- 43 -


© BME-IIT Sz.I.

2005.11.07.

Implementáció - beszúr2

Implementáció - kiir2

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); }

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 */ } }


© BME-IIT Sz.I.

2005.11.07.

- 45 -

Implementáció - program2

© BME-IIT Sz.I.

2005.11.07.

© BME-IIT Sz.I.

2005.11.07.

- 46 -

Miért kell a lemaradó pointer ?

… 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)


- 44 -

• 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!

- 47 -


© BME-IIT Sz.I.

2005.11.07.

- 48 -

8

Hova kell strázsa?

Beszúrás másolással

• 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.

KEZD

15 25 KOV

12 KOV

15 beszúrása

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.

- 49 -

Implementáció - beszúr3

© BME-IIT Sz.I.

2005.11.07.

- 51 -

2005.11.07.

- 50 -


© BME-IIT Sz.I.

2005.11.07.

- 52 -

Mikor használható ez a trükk ?

… 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 } © BME-IIT Sz.I.

2005.11.07.

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 */ } }

Implementáció - program3


© BME-IIT Sz.I.

Implementáció - kiir3

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)


• 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.

- 53 -


© BME-IIT Sz.I.

2005.11.07.

- 54 -

9

Összefoglalás

Láncolt szerkezet tulajdonságai • Előnyök:

• 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

– 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:

– a következő adat pointerét az előző adat mellett tároljuk


© BME-IIT Sz.I.

2005.11.07.

– 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) - 55 -


© BME-IIT Sz.I.

2005.11.07.

- 56 -

10

Mutatók és címek (ism.) Programozás alapjai C nyelv 8. gyakorlat. Indirekció (ism) Néhány dolog érthetőbb (ism.) Változók a memóriában

Recommend Documents