Kihagyás

Flexibilis tömb

Flexibilis, avagy változó hosszúságú tömbök

Az eddig megismert C tömbökkel az a baj, hogy a méretüket fordítási időben meg kell adni. A feldolgozott adatok mennyisége, mérete viszont nem mindig ismert előre, így előfordulhat, hogy a tömb számára kevés helyet foglaltunk, de az is, hogy feleslegesen sokat.

A \(C^{99}\) szabvány már ismeri a változó-hosszúságú tömb fogalmát, amikor is a tömb deklarációjában méretként egy futásidőben kiértékelhető egész kifejezést is megadhatunk:

1
2
3
4
void func(int n) {
    int tomb[n];
    ...
}

Ez viszont a memória verem területén fog létrejönni, ami nem igazán erre a célra lett kitalálva, így ezeknek a tömböknek a használhatósága korlátozott. Ráadásul a \(C^{11}\) szabvány bizonyos implementációkra felmentést ad az ilyen tömbök kezelése alól.

A megoldás: tömb helyett pointert deklarálunk, és ha tudjuk a kívánt méretet, memóriát már a megfelelő számú elemnek foglalunk. Vagyis dinamikusan foglalunk helyet a tömbünk elemeinek, azaz dinamikus tömböt használunk. Mivel a pointert tömbként kezelhetjük, a program kódjában ez semmilyen más változást nem eredményez.

Azaz a 

1
2
3
4
5
6
7
8
int tomb[MAX];
...
n = ...

...
for(i=0; i<n; ++i) {
    tomb[i]=i;
}

kódban használt tömb helyett annak dinamikusan foglalunk memóriát és pointerrel hivatkozunk rá, illetve az egyes elemekre:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int *tomb;
...
n = ...
tomb=malloc(n*sizeof(int));
...
for(i=0; i<n; ++i) {
    tomb[i]=i;
}
free(tomb);
...

Danger

Ne feledjük, a dinamikusan foglalt memória felszabadításáról azonban mindig gondoskodnia kell a programnak!

A hatékonyabb memóriakezelés ellenére a dinamikus tömb méretét még így is előre, legkésőbb a tömb létrehozásakor ismernünk kell. Erre is van megoldás: a C nyelvben a void *realloc(void *ptr, size_t size); függvény segítségével, amely az első paraméter által mutatott tömb méretét módosítja a második paraméterben adott méretre (amennyiben ez sikerül).

Ennek segítségével meg tudunk valósítani egy egyszerű flexibilis tömböt, aminek a méretét nem kell előre megadnunk:

1
2
3
4
5
6
7
8
int *tomb = NULL, int n = 0;
...
while(...) {
    tomb = realloc(tomb, (++n)*sizeof(int));
    ...
}
free(tomb);
...

Flexibilis tömb, mint absztrakt adattípus

Algoritmusok tervezésekor gyakran előfordul, hogy tömbbökkel kell dolgozni, de az adatok darabszáma csak az algoritmus futása közben válik ismertté, esetleg a futás során még változhat is. Ez utóbbi esetet a megismert tömb adattípus nem tudja kezelni. Egy ilyen típus értékkészlete \(\bigcup_{n=1}^{\infty}T_n\), ahol \(T_n\) az \(E\) elemtípusból és \(I_n=\{0\dots n-1\}\) indextípusból képzett tömb típus. Ha az ilyen sorozatokon a következő műveleteket értelmezzük, akkor egy (absztrakt) adattípushoz jutunk, amit flexibilis tömb típusnak nevezünk. Jelöljük ezt a flexibilis tömb típust a továbbiakban \(FT\)-vel, és legyen \(I=\{0\dots\infty\}\).

Mivel alapvetően tömbökről van szó, így azokat a műveleteket, amiket a sima tömb megvalósít, meg kell valósítani a flexibilis tömbnek is, de azokon kívül rendelkeznie kell olyan műveletekkel, amik a létrehozását, megszüntetését, méret módosítását lehetővé teszik. Mivel a sima tömb alapvetően nem tartja nyilván önmagáról a méretet, de a flexibilis tömb esetében ezt azért tudni kell, erről is gondoskodni kell a típus leírása során. Így a típust leíró absztrakt műveletek a következőek lesznek:

Művelet megnevezése Művelet leírása
Kiolvas(\(\rightarrow\) A:FT; \(\rightarrow\) i:I; \(\leftarrow\) x:E) Az A sorozat i. komponensének kiolvasása az x változóba, ha A legalább i+1 elemet tartalmaz.
Módosít(\(\leftrightarrow\) A:FT; \(\rightarrow\) i:I; \(\rightarrow\) y:E) Az Asorozat i. komponensének módosítása y értékre, ha Alegalább i+1 elemet tartalmaz.
Felső(\(\rightarrow\) A:FT): I Az A elemszámának lekérdezése.
Értékadás(\(\leftarrow\) A:FT; \(\rightarrow\) X:FT) Értékadó művelet. Az Aváltozó felveszi az X, FT típusú kifejezés értékét.
Létesít(\(\leftrightarrow\) A:FT; \(\rightarrow\) n:I) n elemű flexibilis tömböt létesít.
Megszüntet(\(\leftrightarrow\) A:FT ) Törli az Aflexibilis tömbhöz foglalt memóriát.
Növel(\(\leftrightarrow\) A:FT; \(\rightarrow\) d:I) Az Afelső határát a d értékkel növeli.
Csökkent(\(\leftrightarrow\) A:FT; \(\rightarrow\) d:I) Az Afelső határát a d értékkel csökkenti.

Flexibilis tömb, mint virtuális C adattípus

Mivel a flexibilis tömb esetében valahogy nyilván kell tartanunk annak méretét, így érdemes egy struktúrát definiálni, amelyben a tömbre mutató pointert és a tömb méretét összekapcsoljuk:

1
2
3
4
typedef struct FT {
        E *tomb;                    /* tömb */
        I meret;  /* a tömb aktuális mérete */
} FT;
Flexibilis tömb egyszerű megvalósítás

Mivel az egyes műveletek a flexibilis tömb esetén nem adhatóak meg egyetlen C utasítással (hiszen nincs ennek sem konkrét megvalósítása a C nyelven), így készítsünk egy alap implemtációt ezekre. Hasonlóan a halmazokhoz, itt is emeljük ki az absztrakt leírását a műveleteknek egy header állományba (legyen ez most ftomb_simple_t.h )!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#ifndef FTOMB_SIMPLE_H
#define FTOMB_SIMPLE_H

typedef ???          elem_t;         /* a tömb elemtípusa */
typedef unsigned int index_t;
typedef struct flex_tomb_t {
        elem_t *tomb;                             /* tömb */
        index_t hatar;             /* aktuális indexhatár */
} flex_tomb_t;

/* A műveletek deklarációja:                              */
void kiolvas(flex_tomb_t a, index_t i, elem_t *x);
void modosit(flex_tomb_t a, index_t i, elem_t x);
index_t felso(flex_tomb_t a);
void letesit(flex_tomb_t *a, index_t n);
void megszuntet(flex_tomb_t *a);
void novel(flex_tomb_t *a, index_t d);
void csokkent(flex_tomb_t *a, index_t d);

#endif // FTOMB_SIMPLE_H

A tömb elemtípusát értelemszerűen úgy kell megadni, hogy az a felhasználási igényünknek megfelelő legyen majd.

Valósítsuk meg ezeket a műveleteket egy c állományban:

 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
#include <stdlib.h>
#include "ftomb_simple_t.h"

void kiolvas(flex_tomb_t a, index_t i, elem_t *x) {
    if (i < a.hatar) {
        *x = a.tomb[i];
    }
}

void modosit(flex_tomb_t a, index_t i, elem_t x) {
    if (i < a.hatar) {
        a.tomb[i] = x;
    }
}

index_t felso(flex_tomb_t a) {
    return a.hatar;
}
void letesit(flex_tomb_t *a, index_t n) {
    a->hatar = n;
    a->tomb = (elem_t*) ((n) ? malloc(n * sizeof(elem_t)) : NULL);
}

void megszuntet(flex_tomb_t *a) {
    free(a->tomb);         /* A free() függvény jól kezeli a NULL értéket */
    a->tomb = NULL;
    a->hatar = 0;
}

void novel(flex_tomb_t *a, index_t d) {
    a->tomb = (elem_t*)realloc(a->tomb, (a->hatar += d) * sizeof(elem_t));
}

void csokkent(flex_tomb_t *a, index_t d) {
    a->tomb = (elem_t*)realloc(a->tomb, (a->hatar -= d) * sizeof(elem_t));
}

Ha a tömbünk egyszerű flexibilis tömb, akkor igazából ezek a műveletek nem is bonyolultak. Mivel a tömb mérete, mint információ elérhető, így azt használjuk is ki arra, hogy a műveletek csak akkor próbálják a memóriát írni, olvasni, ha a kérések ezekre a műveletekre a megadott határon belül vannak. Így elkerülhetünk számos futási hibát.

Flexibilis tömb elegáns megvalósítás

Az egyszerű megvalósításával a flexibilis tömbnek az a baj, hogy a tömb újraallokálása sokszor nehézkes, főleg a méret növekedésével elképzelhető, hogy a program nem tud egyben akkora memóriát kihasítani a tömbnek a realloc által, amennyire szükség lehet. Éppen ezért (tanulva a halmaz megvalósításból), valósítsuk meg úgy a flexibilis tömbünket, hogy az kisebb (adott mérettel rendelkező) dinamikus tömbök sorozatából álljon. Így a tömb elemei bár a memóriában nem lesznek feltétlenül egymás mellett, viszont nagy valószínűséggel nem okoz majd gondot újabb és újabb memóriaszeletek allokálása.

A megoldásunkban karban kell tartanunk egy laptérképet, ami tulajdonképpen a kis tömbökre mutató pointereket tartalmazza, illetve külön memóriát kell foglalni a kis tömböknek:

kep

Egy konkrét elem elérésekor itt is kiindulhatunk abból, hogy az adott elem sorszámának és a kis tömbök méretének hányadosa megadja, melyik kis tömbben van az adott elem, a maradék pedig megadja ezen tömbön belüli indexét az elemnek.

Definiáljuk a flexibilis tömbünk utasításait az ftomb.h headerben:

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

#define L ???                                 /* lapméret */

typedef ???          elem_t;         /* a tömb elemtípusa */
typedef unsigned int index_t;
typedef elem_t *lap_t;
typedef lap_t  *lapterkep_t;
typedef struct flex_tomb_t {
        lapterkep_t lt;                      /* laptérkép */
        index_t     hatar;         /* aktuális indexhatár */
} flex_tomb_t;

/* A műveletek deklarációja:                              */
void kiolvas(flex_tomb_t a, index_t i, elem_t *x);
void modosit(flex_tomb_t a, index_t i, elem_t x);
index_t felso(flex_tomb_t a);
void letesit(flex_tomb_t *a, index_t n);
void megszuntet(flex_tomb_t *a);
void novel(flex_tomb_t *a, index_t d);
void csokkent(flex_tomb_t *a, index_t d);

#endif // FTOMB_H

Figyeljük meg, csak a típus megadása az, ami különbözik ezen a szinten az egyszerűbb megoldástól! Nyilván itt is külön meg kell adni a tömbben tárolt elemek konkrét típusát. Ezen kívül definiálnunk kell a lapterkep_t típust, aminek segítségével a kistömböket tudjuk elérni, illetve maga a flexibilis tömb típus most direkt ezt éri el, és csak közvetve hivatkozhatunk a tömb elemeire. A szintén eltárolt aktuális elemek számából meg tudjuk határozni, hogy konkrétan mennyi kis tömbünk van, felhasználva a kis tömbök méretét is.

A műveletek megvalósítása ezek után:

 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 <stdlib.h>
#include "ftomb_t.h"

void kiolvas(flex_tomb_t a, index_t i, elem_t *x) {
    if (i < a.hatar) {
        *x = a.lt[i / L][i % L];
    }
}

void modosit(flex_tomb_t a, index_t i, elem_t x) {
    if (i < a.hatar) {
        a.lt[i / L][i % L] = x;
    }
}

index_t felso(flex_tomb_t a) {
    return a.hatar;
}
void letesit(flex_tomb_t *a, index_t n) {
    a->hatar = n;
    if (n) {
        int j;
        a->lt = (elem_t**) malloc((1 + ((n - 1) / L)) * sizeof(lap_t));
        for (j = 0; j <= ((n - 1) / L); ++j) {                /* lapok létesítése */
            a->lt[j] = (elem_t*) malloc(L * sizeof(elem_t));
        }
    } else {
        a->lt = NULL;
    }
}

void megszuntet(flex_tomb_t *a) {
    if (a->hatar) {
        int j;
        for (j = 0; j <= ((a->hatar - 1) / L); ++j) {            /* lapok törlése */
            free(a->lt[j]);
        }
        free(a->lt);
        a->lt = NULL;
        a->hatar = 0;
    }
}
void novel(flex_tomb_t *a, index_t d) {
    int j;
    a->lt = (elem_t**) realloc(a->lt,
                            (1 + ((a->hatar + d - 1) / L)) * sizeof(lap_t));
    for (j = ((a->hatar) ? ((a->hatar - 1) / L) + 1 : 0);           /*   új lapok */
                            j <= (a->hatar + d - 1) / L; ++j) {     /* létesítése */
        a->lt[j] = (elem_t*) malloc(L * sizeof(elem_t));
    }
    a->hatar += d;
}

void csokkent(flex_tomb_t *a, index_t d) {
    if (d <= a->hatar) {
        int j;
        for (j = (a->hatar - d - 1) / L + 1; j <= (a->hatar - 1) / L; ++j) {
            free(a->lt[j]);                           /* felesleges lapok törlése */
        }
        a->hatar -= d;
        a->lt = (elem_t**) realloc(a->lt,
                            (1 + ((a->hatar - 1) / L)) * sizeof(lap_t));
    }
}
Példa: rendezés több szempont szerint
  • Problémafelvetés:
    • A beolvasott adatokat rendezzük több szempont szerint is egy egyszerű rendezési algoritmussal és minden rendezés után legyen kiíratás is!
  • Specifikáció:
    • Flexibilis tömbbel dolgozzunk.
    • Az input név-adat párok sorozata, amelynek végét a * név jelzi.
    • Az output a név szerint növekvő, adat szerint növekvő illetve csökkenő sorrendben rendezett három tömb.
  • Algoritmustervezés:
    • A fő algoritmusban csak az elemeket kell beolvasni egy végjelig, majd rendre aktivizálni kell a különböző szempontok szerinti rendezést és ki kell íratni az eredményt.
    • A rendezés a beszúró rendezés lesz.

A feladat megvalósítása során a rendezésnek a megadása lesz az egyik legfontosabb elem.

  • Problémafelvetés: beszúró rendezés:
    • Rendezzük a tömb elemeit!
  • Specifikáció
    • Az input egy tömb, és a tömb elemtípusán értelmezett rendezési reláció.
    • Az output a megadott reláció alapján rendezett tömb.

  • Algoritmustervezés:

    • A tömböt logikailag egy már rendezett és egy még rendezetlen részre osztjuk, és a rendezetlen rész első elemét beszúrjuk a rendezett elemek közé úgy, hogy azok rendezettek maradjanak.
      kep
      Az algoritmus tehát mindig a már rendezett tömbbe (zöld) szúr be új elemet (kék), amelyet a még rendezés előtt álló elemek (piros) első eleme ad. Így ennek helye felszabadul, és az már a rendezett tömbhöz fog tartozni, ahol a beszúrás során először megkeressük az újonnan beszúrt elem helyét, majd ha az megvan, akkor az elem mögé kerülő adatokat egy hellyel jobbra mozgatjuk, és a felszabadult helyre betesszük a beszúrandó elemet.

  • Algoritmustervezés szerkezeti ábrával:

    kep

Maga a buborék algoritmus a rendezési relációt (azaz azt a függvényt, amely alapján két elemről eldönti, hogy melyik a kisebb) paraméterként kapja. Ezzel lehetőségünk van arra, hogy külön rendezést írva az egyes esetekre, újra és újra felhasználjuk a rendezési algoritmus megvalósítását.

  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
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/* Rendezzük névsorba illetve átlag szerint a hallgatókat!
 * Flexibilis tömbbel történik a megvalósítás, tehát a
 * névsor hosszát nem kell előre megmondani.
 * 1998. Február 16.  Dévényi Károly, devenyi@inf.u-szeged.hu
 * 2006. Augusztus 15.  Gergely Tamás, gertom@inf.u-szeged.hu
 * 2014. Október 15.  Gergely Tamás, gertom@inf.u-szeged.hu
 */

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

#define L 10                                                          /* lapméret */

typedef struct {                                             /* a tömb elemtípusa */
    char nev[21];
    float adat;
} elem_t;

typedef elem_t *lap_t;

typedef lap_t  *lapterkep_t;

typedef unsigned int index_t;

typedef struct flex_tomb_t {
    lapterkep_t lt;                                                  /* laptérkép */
    index_t     hatar;                                     /* aktuális indexhatár */
} flex_tomb_t;

typedef bool (*rend_rel_t)(elem_t, elem_t);

/* A műveletek megvalósítása: */

void kiolvas(flex_tomb_t a, index_t i, elem_t *x) {
    if (i < a.hatar) {
        *x = a.lt[i / L][i % L];
    }
}

void modosit(flex_tomb_t a, index_t i, elem_t x) {
    if (i < a.hatar) {
        a.lt[i / L][i % L] = x;
    }
}

index_t felso(flex_tomb_t a) {
    return a.hatar;
}

void letesit(flex_tomb_t *a, unsigned int n) {
    a->hatar = n;
    if (n) {
        int j;
        a->lt = (elem_t**) malloc((1 + ((n - 1) / L)) * sizeof(lap_t));
        for (j = 0; j <= ((n - 1) / L); ++j) {                /* lapok létesítése */
            a->lt[j] = (elem_t*) malloc(L * sizeof(elem_t));
        }
    } else {
        a->lt = NULL;
    }
}

void megszuntet(flex_tomb_t *a) {
    if (a->hatar) {
        int j;
        for (j = 0; j <= ((a->hatar - 1) / L); ++j) {            /* lapok törlése */
            free(a->lt[j]);
        }
        free(a->lt);
        a->lt = NULL;
        a->hatar = 0;
    }
}

void novel(flex_tomb_t *a, index_t d) {
    int j;
    a->lt = (elem_t**) realloc(a->lt,
                            (1 + ((a->hatar + d - 1) / L)) * sizeof(lap_t));
    for (j = ((a->hatar) ? ((a->hatar - 1) / L) + 1 : 0);           /*   új lapok */
                            j <= (a->hatar + d - 1) / L; ++j) {     /* létesítése */
        a->lt[j] = (elem_t*) malloc(L * sizeof(elem_t));
    }
    a->hatar += d;
}

void csokkent(flex_tomb_t *a, index_t d) {
    if (d <= a->hatar) {
        int j;
        for (j = (a->hatar - d - 1) / L + 1; j <= (a->hatar - 1) / L; ++j) {
            free(a->lt[j]);                           /* felesleges lapok törlése */
        }
        a->hatar -= d;
        a->lt = (elem_t**) realloc(a->lt,
                            (1 + ((a->hatar - 1) / L)) * sizeof(lap_t));
    }
}

/* Rendezés */

void beszuro_rendezes(flex_tomb_t t, rend_rel_t kisebb) {
                          /* A kisebb rendezési reláció szerinti helyben rendezés */
    int    i, j;
    elem_t e, f;
    for (i = 1; i < felso(t); ++i) {
        kiolvas(t, i, &e); 
        j = i - 1;

        while (true) {
            if (j < 0) {
                break;
            }
            kiolvas(t, j, &f);
            if (kisebb(f, e)) {
                break;
            }
            modosit(t, ((j--) + 1), f);
        }
        modosit(t, j + 1, e);
    }
} /* beszuro_rendezes */

bool rend_nev_novekvo(elem_t x, elem_t y) {
                                          /* a névsor szerinti rendezési reláció  */
    return strcmp(x.nev, y.nev) <= 0;
}

bool rend_adat_novekvo(elem_t x, elem_t y) {
                                           /* az adat szerinti rendezési reláció  */
    return x.adat <= y.adat;
}

bool rend_adat_csokkeno(elem_t x, elem_t y) {
                                   /* az adat szerint csökkenő rendezési reláció  */
    return x.adat >= y.adat;
}

void kiiras(flex_tomb_t t) {
                                                                      /* Kiíratás */
    elem_t e;
    index_t i;
    for (i = 0; i < felso(t); ++i) {
        kiolvas(t, i, &e);
        printf("%6.2f %s\n", e.adat, e.nev);
    }
}

int main() {
    flex_tomb_t sor;
    elem_t      hallg;                                            /* beolvasáshoz */
    index_t     i;

    letesit(&sor, 0);                             /* a flexibilis tömb létesítése */
                                                                     /* beolvasás */
    printf("Kérem az adatsort, külön sorban név és adat!\n");
    printf("A végét a * jelzi.\n");
    scanf("%20[^\n]%*[^\n]", hallg.nev); getchar(); 
    i = 0;                                          /* az i. helyre fogunk beírni */
    while (strcmp(hallg.nev, "*")) {
        novel(&sor, 1);                             /* a flexibilis tömb bővítése */
        scanf("%f%*[^\n]", &hallg.adat); getchar();
        modosit(sor, i++, hallg);  
        scanf("%20[^\n]%*[^\n]", hallg.nev); getchar(); 
    }

    beszuro_rendezes(sor, rend_nev_novekvo);              /* Rend. névsor szerint */
    printf("Névsor szerint rendezve:\n");
    kiiras(sor);                                                      /* Kiíratás */

    beszuro_rendezes(sor, rend_adat_novekvo);               /* Rend. adat szerint */
    printf("Adat szerint rendezve:\n");
    kiiras(sor);                                                      /* Kiíratás */

    beszuro_rendezes(sor, rend_adat_csokkeno);                   /* Rendezés újra */
    printf("Adat szerint csökkenő sorba rendezve:\n");
    kiiras(sor);                                                      /* Kiíratás */

    megszuntet(&sor);                                /* a flexibilis tömb törlése */
    return 0;
}

Bár a megoldás most egyben tartalmazza a tömb megvalósítást is, ne feledjük, hogy akár használhatnánk azt a megoldást is, hogy a tömb utasításait a fenti módon külön implementáljuk, és magánál a beszúró rendezésnél "csak" include-oljuk az ftomb_t.h-t.

Utolsó frissítés: 2022-11-25 15:25:14