Írjunk egy programot, amelyik egy „double”-ökből álló halmaz típust hoz létre. A halmaz a következőket kell tudja (ezek a megírandó függvények):
- Be lehessen tenni egy elemet a halmazba. (Ha már benne van, nem történik semmi.)
- Ki lehessen venni egy elemet a halmazból.
- Le lehessen kérdezni, egy elem benne van-e a halmazban.
A halmazban lévő elemek száma lehessen tetszőlegesen nagy!
Megoldás
Az utóbbi kitétel miatt dinamikus memóriát használunk. A halmaz elemeit egy dinamikus tömbben jegyezzük meg; mivel a lefoglalt memóriaterületre csak egy pointerünk van, ezért magunknak kell az éppen aktuális méretet (az elemszámot) nyilvántartani. Egy adott halmazhoz egy konkrét elemszám tartozik; a két elválaszthatatlan adat természetesen egy struktúrába kerül:
typedef struct Halmaz {
int db;
double *adat;
} Halmaz;
Ha létrehozunk egy halmaz struktúrát, akkor az memóriaszemetet fog tartalmazni, mind a db,
mind az adat mezőben. Ezért egy halmazt az első használat előtt inicializálni kell.
Hogy ne szivárogjon a memória, az utolsó használat után a dinamikusan foglalt területet fel is kell
szabadítani. Ezért a fenti három függvényen kívül még kettőt írunk, amelyeknek a feladatai ezek lesznek.
A függvények, amelyek valamely halmazon dolgoznak, megváltoztathatják a struktúra tartalmát. Pl. a
memóriaterület más helyre kerülhet, vagy a darabszám nőhet. Ezért a függvényeknek nem a struktúrát,
vagyis annak másolatát, hanem a struktúrára mutató pointert kell átvegyenek. A betesz
és kivesz függvényeknél ez mindenképpen így van, de a kényelem kedvéért érdemes az
összeset így megírni. Akkor nem kell majd fejben tartani, melyik függvény vár halmazt, és melyik
halmazra mutató pointert. Azok a függvények, amelyek pedig nem változtatják meg a struktúrát (pl. egy
halmaz nem változik meg azáltal, hogy ellenőrizzük, tartalmaz-e egy elemet), a halmazra mutató
pointert konstans pointerként veszik át. Így a fordító ellenőrizni tudja, nem írtunk-e azokba
véletlenül olyan kódot, amely megváltoztatná azt.
A halmazba új számot betenni és számot abból kivenni sajnos költséges művelet. A dinamikusan foglalt
tömböt átméretezni nem lehet, mivel lehet hogy előtte, utána másra használt, foglalt memória van.
Ezért átméretezés esetén új memóriaterületet kell foglalni, és az elemeket átmásolni. A másolás után
pedig a régi memóriaterület felszabadítható, végül pedig a halmaz struktúrában található pointer
az új területre állítható át. (A szabványos realloc() függvény egyébként ugyanezt csinálja.)
#include <stdio.h>
#include <stdlib.h>
typedef struct Halmaz {
int db;
double *adat;
} Halmaz;
/* inicializalatlan strukturat hoz alapallapotba */
void halmaz_init(Halmaz *h) {
h->db=0;
h->adat=NULL;
}
/* halmazt felszabadit az utolso hasznalat utan */
void halmaz_felszabadit(Halmaz *h) {
free(h->adat);
}
/* igazzal ter vissza, ha benne van az adott elem */
int halmaz_benne_van_e(Halmaz const *h, double mi) {
int i;
for (i=0; i<h->db; ++i)
if (h->adat[i]==mi)
return 1; /* ha valahol megtalaljuk, igaz */
return 0; /* ha sehol nem talaltuk, hamis */
}
void halmaz_betesz(Halmaz *h, double mit) {
double *uj;
int i;
/* ha mar benne van, nem kell semmit csinalni */
if (halmaz_benne_van_e(h, mit))
return;
/* atmasoljuk a regi adatokat eggyel nagyobb helyre */
uj=(double*) malloc((h->db+1)*sizeof(double));
for (i=0; i<h->db; ++i)
uj[i]=h->adat[i];
uj[h->db]=mit; /* vegere az uj */
free(h->adat); /* a regi mar nem kell */
h->adat=uj; /* atallitjuk a pointert az ujra */
h->db++; /* eggyel nott a darabszam */
}
void halmaz_kivesz(Halmaz *h, double mit) {
double *uj;
int i, j;
/* ha nincs benne, nincs dolgunk */
if (!halmaz_benne_van_e(h, mit))
return;
/* uj memoriaterulet, eggyel kisebb */
uj=(double*) malloc((h->db-1)*sizeof(double));
j=0;
for (i=0; i<h->db; ++i)
if (h->adat[i]!=mit)
uj[j++]=h->adat[i];
free(h->adat);
h->adat=uj;
h->db--; /* eggyel csokken a darabszam */
}
/* kilistazza egy halmaz tartalmat */
void halmaz_lista(Halmaz const *h) {
int i;
for (i=0; i<h->db; ++i)
printf("%g ", h->adat[i]);
printf("\n");
}
int main() {
Halmaz h;
halmaz_init(&h);
halmaz_betesz(&h, 3.14);
halmaz_betesz(&h, 2.0);
halmaz_betesz(&h, 3.14);
halmaz_lista(&h);
halmaz_betesz(&h, 6.1);
halmaz_lista(&h);
halmaz_kivesz(&h, 3.14);
halmaz_lista(&h);
halmaz_felszabadit(&h);
return 0;
}
A fenti megoldásban kihasználjuk, hogy free(NULL) a szabvány
szerint elfogadott. Azonban egyes régebbi fordítók esetén ebből gond lehet.
Ilyenkor a if (ptr!=NULL) free(ptr); formát érdemes használni.
Miután a main() függvény a 6.1-es számot betette a halmazba,
így néz ki a program memóriaképe:
A veremben a h struktúra van, amely az egész számot és a pointert
tartalmazza; a pointer pedig a dinamikusan foglalható területre mutat, oda, ahol
a malloc() hívás helyet talált a három double méretű
memóriaterületnek.
Írjuk át a programot úgy, hogy a halmazt létrehozó függvények ne egy meglévő, inicializálatlan halmaz struktúrán dolgozzanak, hanem azt is dinamikusan foglalják, és a címével térjenek vissza. Erősen különböztessük meg az új halmazt létrehozó és a meglévő halmazt módosító függvényeket! Az előbbiek visszatérnek egy pointerrel, az utóbbiak várnak egy pointert a módosítandó halmazra. A függvények használata legyen ilyen:
Halmaz *h; h=halmaz_uj(); halmaz_betesz(h, 3.14); halmaz_betesz(h, 6.1); halmaz_lista(h); halmaz_kivesz(h, 3.14); halmaz_lista(h); halmaz_felszabadit(h);
Így a halmazokat kényelmesen adogathatjuk át a függvények között, nem szűnnek meg amiatt, mert
lokális változók lennének. Figyeljük meg, hogy ez a szintaktikára nézve is jótékony hatással van:
mivel h itt eleve már pointer, sehol nem kell az & címképző
operátort használni.
Vegyük észre: ez nagyon hasonló ahhoz, ahogyan az fopen() és a többi
fájlos függvény működik. Vagyis ez nem idegen a C logikájától.
Megoldás
Ilyenkor a memóriaképünk ilyen:
A main()-ben lokális változó csak egy pointer; a kupacon van a struktúra és a tömb is.
A különbség csak a létrehozó és a felszabadító függvényekben van. A létrehozáskor
malloc()-oljuk a struktúrát is, és emiatt természetesen a felszabadításnál
free()-zni kell azt is:
Halmaz *halmaz_init() {
Halmaz *ph;
ph = (Halmaz*) malloc(sizeof(Halmaz));
ph->adat = NULL;
ph->db = 0;
return ph;
}
void halmaz_felszab(Halmaz *ph) {
free(ph->adat);
free(ph);
}
