Kihagyás

Halmaz

Halmaz típus

A programozásban számtalan formában előfordulhatnak halmazok és halmazokkal végzett műveletek. A lényege ennek a típusnak, hogy adott egy univerzum (U), ami tartalmazza a potenciális elemeit a halmaznak (ezeket legtöbbször egész számokkal ábrázoljuk, hisz a lényeg, hogy diszkrét, egymástól jól elkülöníthető elemeket kell definiálnunk). A P(U)értékhalmaz visszaadja az U univerzum összes lehetséges részhalmazainak halmazát. Ez lesz a Halmaz(U) új adattípus értékhalmaza. Azaz egy halmaz pillanatnyi állapotát az határozza meg, hogy az univerzum elemei az adott halmazba beletartoznak-e, vagy sem.

Halmaz, mint absztrakt adattípus

Mivel a halmaznak konkrét megvalósítása nincs C nyelven, így még egyértelműbb az az igény, hogy a halmaz műveleteit absztrakt módon adjuk meg. Azt, hogy ezt utána hogyan valósítjuk meg, mindig az adott probléma fogja meghatározni.

A halmaz adattípustól elvárt műveleteket a következő táblázat foglalja össze:

Művelet megnevezése Művelet leírása
Üresít(← H:Halmaz); A H halmaz elemeit törli. Eredmény egy üres halmaz.
Bővít(↔ H:Halmaz; → x:U); A művelet a H változó értékéhez hozzáveszi az x elemet.
Töröl(↔ H:Halmaz; → x:U); A művelet a H változó értékéből törli az x elemet.
Eleme(→ x:U; → H:Halmaz):bool; A függvényművelet akkor és csak akkor ad igaz értéket, ha x\(\in\) H halmaznak.
Egyesítés(→ H1:Halmaz; → H2:Halmaz; ← H:Halmaz); A művelet eredményeként a H változó értéke a H1 \(\cup\) H2 lesz.
Metszet(→ H1:Halmaz; → H2:Halmaz; ← H:Halmaz); A művelet eredményeként a H változó értéke a H1 \(\cap\) H2 lesz.
Különbség(→H1:Halmaz; → H2:Halmaz; ← H:Halmaz); A művelet eredményeként a \(H\) változó azokat az x \(\in\) H1 elemeket tartalmazza, melyekre x \(\not\in\) H2.
Egyenlő(→ H1:Halmaz; → H2:Halmaz):bool; Az egyenlőség relációs művelet.
Rész(→ H1:Halmaz; → H2:Halmaz):bool; Akkor és csak akkor ad igaz értéket, ha a H1 \(\subseteq\) H2.
Ürese(→ H:Halmaz):bool; Akkor és csak akkor ad igaz értéket, ha H=\(\emptyset\).
Értékadás(← H1:Halmaz; → H2:Halmaz); A művelet hatására a H1 változó felveszi a H2 értékét.

Halmaz, mint virtuális adattípus

Ahogy az már szóba került, nincs a halmaznak konkrét megvalósítása C nyelven. Ellenben számos módszerrel meg tudjuk azt valósítani mégis. Mi kell ehhez? A halmazok reprezentálásánál a kulcsszerep annak a kérdésnek jut, ami megválaszolja az univerzum összes elemére, hogy adott elem része-e az adott halmaznak, vagy sem. Az H U-beli részhalmaz megadható annak karakterisztikus függvényével, ami minden U-beli elemhez 0-át, vagy 1-et rendel, attól függően, hogy az adott elem eleme e a halmaznak, vagy sem. Egy kézenfekvő megoldás a halmazok megadására, hogy egy univerzum méretének megfelelő bool tömbben tároljuk el minden elemre, hogy az eleme, vagy nem az adott halmaznak. Bár ez megoldás lehet, azonban nagyobb halmazok esetében nem gazdaságos megoldás, hiszen egy bool érték eltárolásához legalább egy (de az is lehet, hogy négy) bájt kell, holott az egész információ tartalom 1 biten is elfér.

Ehelyett próbáljuk azt, hogy valamely egész típust felhasználva egyetlen egész típusú változóban tároljuk el több halmazelem karakterisztikus értékét. Például ha adott egy 32 bites int változónk, akkor az alkalmas egy 32 elemű kisebb halmaz reprezentálására, ahol minden egyes bitnek meg van feleltetve az univerzum egy eleme. Például:

kep

vagy

kep

Nyilván a könnyebb kezelhetőség érdekében érdemes a bitek sorrendjében valami rendezettséget találni.

Az egyes biteket ezután a bitműveletek segítségével könnyen el tudjuk érni:

kep

Illetve a további bitműveletekkel, mint a &, | és ~ segíthetik a bitek beállítását, törlését, lekérdezését.

Ha nagyobb halmazokat szeretnénk létrehozni, akkor azt összepakolhatjuk kishalmazokból. Az elemeket sorszámozva az egész osztás segít abban, hogy megtaláljuk, adott elemhez rendelt karakterisztikus értéket melyik kishalmazban találjuk. Ehhez az elem sorszámát kell osztani a kishalmaz méretével (azaz egy kishalmazban tárolható elemek számával). Kishalmazon belül pedig a pozíciót hasonló, csak épp maradékos osztással kapjuk meg:

kep

Könnyen belátható, hogy ezzel a módszerrel minden \(x\) természetes szám egyértelműen meghatározható az \((x/K, x%K)\) számpárral. Egy \(x\) akkor és csak akkor eleme a \(H\) változó által reprezentált halmaznak, ha teljesül, hogy a \(H[x/K]\) kishalmaznak eleme az \((x%K)\), azaz a megfelelő kishalmaz megfelelő bitje 1.
Az univerzum méretét egyértelműen meghatározza a kishalmazt ábrázoló adattípus mérete, illetve az, hogy ilyen kishalmazból mennyit használunk fel.

Mivel a halmazt tényleg megvalósíthatjuk többféleképpen is, érdemes ezt úgy megtenni, hogy igény szerint adott megvalósítás könnyen lecserélhető legyen. Ebben segít nekünk a moduláris programozás lehetősége, illetve az, hogy magát az absztrakt típust leíró függvény deklarációkat a definícióktól külön tudjuk megadni, és használni.

Hozzunk létre egy külön header állományt (legyen a neve most ennek halmaz_t.h), amiben az alábbiakat írjuk:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#ifndef HALMAZ_H
#define HALMAZ_H

#include <stdbool.h>

#define K (8*sizeof(KisHalmaz))
#define M ???
#define H_MAX (M*K)

typedef unsigned long int halmazelem;
typedef halmazelem KisHalmaz;
typedef KisHalmaz Halmaz[M];

void Uresit(Halmaz);
void Bovit(Halmaz, halmazelem);
void Torol(Halmaz, halmazelem);
bool Eleme(Halmaz, halmazelem);
void Egyesites(Halmaz H1, Halmaz H2, Halmaz H);
void Metszet(Halmaz H1, Halmaz H2, Halmaz H);
void Kulonbseg(Halmaz H1, Halmaz H2, Halmaz H);
bool Egyenlo(Halmaz H1, Halmaz H2);
bool Resz(Halmaz H1, Halmaz H2);
bool Urese(Halmaz H);
void Ertekadas(Halmaz H1, Halmaz H2);

#endif // HALMAZ_H

Az M méretet természetesen úgy definiáljuk, ahogy az az adott feladatunk számára szükséges.

Mielőtt tovább haladnánk, nézzük meg alaposabban is a fenti kódot! Az egész kód egy pár makró által keretbe lett foglalva. Minden header esetében vigyázni kell arra, hogy az include-olások által a benne szereplő deklarációk ne duplikálódjanak, mert ebben az esetben a kód nem fordulna le. Egy egyszerű trükkel akadályozza meg minden header állomány a kód többszörös bekerülését a fordításba. Amikor a fordító találkozik a header állomány kódjával, a header nevéből képzett makró létezésének ellenőrzésével vizsgálja, hogy a header már bekerült-e a fordításba. Amennyiben a makró még nem definiált (#ifndef HALMAZ_H) (azaz a fordító először látja a kódot), akkor a makró definiálásra kerül (#define HALMAZ_H). A következő kódokat a fordító figyelembe veszi.

Amikor újra ezen állomány vizsgálatához érkezne a fordító (pl. többszörös include-ok miatt), a makró ellenőrzése jelzi, hogy itt már járt, azok a kódok, amik az #endif utasításig vannak, nem kerülnek be újra a fordításba.

Ha definiálunk emellett egy halmaz_t.c állományt, abban megadhatjuk az egyes függvények implementációját is: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "halmaz_t.h"

void Uresit(Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = 0;
}

void Bovit(Halmaz H, halmazelem x) {
    if(x < H_MAX)
        H[x / K] |=  (1l << (x % K));
}

void Torol(Halmaz H, halmazelem x) {
    if(x < H_MAX)
        H[x / K] &= ~(1l << (x % K));
}

bool Eleme(halmazelem x, Halmaz H) {
    return (x < H_MAX) && (H[x / K] & (1l << (x % K)));
}

void Egyesites(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] | H2[i];
}

void Metszet(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] & H2[i];
}

void Kulonbseg(Halmaz H1, Halmaz H2, Halmaz H) {
    long int i;
    for(i = 0; i < M; ++i)
        H[i] = H1[i] & ~(H2[i]);
}

bool Egyenlo(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; (i < M) && (H1[i] == H2[i]); ++i);
    return i == M;
}

\begin{lstlisting}[firstnumber=47]
bool Resz(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; (i<M) && !(H1[i] & ~(H2[i])); ++i);
    return i == M;
}

bool Urese(Halmaz H) {
    long int i;
    for(i = 0; (i < M) && !(H[i]); ++i);
    return i == M;
}

void Ertekadas(Halmaz H1, Halmaz H2) {
    long int i;
    for(i = 0; i < M; ++i)
        H1[i] = H2[i];
}

Természetesen ha másfajta megvalósítást használnánk, akkor elég csak ezt a c állományt más implementációra cserélni, a headerben kiemelt résznek köszönhetően nem kell a felhasználó kódok implementációját változtatni.

Diszkrét ismétléses vezérlés és a halmazok

Emlékezzünk vissza, hogy a vezérlési módok megismerése során a diszkrét ismétlésnél is kiemeltük, hogy annak nincs C-beli megvalósítása. Azután viszont, hogy az univerzumot reprezentálni tudjuk, lehetőség nyílik arra, hogy a diszkrét ismétléses vezérlést megfogalmazzuk ezekre az esetekre.

Ha megtudjuk adni az univerzum legkisebb és legnagyobb elemeit, az elemeken pedig végig tudunk lépdelni egy megadott rendezés által, akkor a diszkrét ismétléses vezérlés megvalósítható az alábbi módon:

kep

aminek C-beli megvalósítása:

1
2
3
4
5
for(x = U_min; x <= U_max; ++x) {
    if(Eleme(x,H)) {
        M;
    }
}