Tömbök

Tömbök

Tömb, mint absztrakt adattípus

Algoritmusok tervezésekor gyakran előfordul, hogy adatok sorozatával kell dolgozni, vagy mert az input adatok sorozatot alkotnak, vagy mert a feladat megoldásához kell. Tegyük fel, hogy a sorozat rögzített elemszámú (\(n\)) és mindegyik komponensük egy megadott (elemi vagy összetett) típusból \(E\) való érték. Ekkor tehát egy olyan összetett adathalmazzal van dolgunk, amelynek egy eleme \(A = (a_0, \dots, a_{n-1})\), ahol \(a_{i} \in E, \forall i \in (0, \dots, n-1)\)-re. Ha az ilyen sorozatokon a következő műveleteket értelmezzük, akkor egy (absztrakt) adattípushoz jutunk, amit tömb típusnak nevezünk. Jelöljük ezt a tömb típust \(T\)-vel, amely tömb elemei \(E\) típusú adatok, a \(0, \dots, n-1\) intervallumot pedig jelöljük \(I\)-vel, ezekkel az értékekkel tudunk majd a tömb elemeire hivatkozni!

Művelet megnevezése Művelet leírása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i: I, \(\leftarrow\) x: E) Az A tömb i. értékét kiolvassa és eltárolja az x változóban.
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i: I, \(\rightarrow\) x: E) Az A tömb i. értékét módosítja az x értékkel.
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T) Az A tömb felveszi az X tömb típusú kifejezés értékét.

Tömb, mint virtuális adattípus

Amikor egy tömböt szeretnénk létrehozni, annak deklarációja nagyon hasonlít ahhoz, ahogy adott típusból egyetlen adat deklarációját megadjuk, annyi különbség van, hogy a változó neve kiegészül egy szögletes zárójel párral, ami között megadjuk a tömb méretét, azaz azt az elemszámot, amennyi elemet el szeretnénk tárolni a tömbben. Azaz:

típus változónév[elemszám];

Konkrét példával:

1
2
char ct[t]; //létrehoz egy 5 darab char típusú elem eltárolására szolgáló tömböt
unsigned short int it[20]; //20 elemű unsigned short int tömb

Természetesen a tömb típussal is definiálhatunk új típust:

typedef típus újnév[elemszám];

Például:

1
2
typedef int tomb20[20];
tomb20 t;

Művelet absztrakt szinten Művelet virtuális megvalósítása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i: I, \(\leftarrow\) x: E) x = A[i];
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i: I, \(\rightarrow\) x: E) A[i] = x;
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T) Nincs direkt megvalósítás! Használható a memcpy(), vagy a \(C^{11}\) szabvány után a biztonságosabb memcpy_s() függvény.

Fontos megjegyezni, hogy a C nyelvben az indexelés mindig 0-val kezdődik. Azaz egy int t[20]; deklaráció esetén a tömb elemei a t[0], \(\dots\), t[19] lesznek. Figyelni kell arra, hogy a C-ben nincs indexhatár-ellenőrzés. Ez azt jelenti, hogy a fenti példánál maradva tudunk hivatkozni a t[-1], vagy esetleg t[20] elemekre is, ami lehet, hogy látszólag rögtön nem okoz problémát, de nagyon csúnya futási hibákat eredményezhet amiatt, hogy a memória egy olyan területét érjük el, amin más adat van.

Példa - riadólánc

  • Problémafelvetés: adott valahány ember, akik riadóláncot akarnak alkotni. A közösség minden tagjára meghatározott, hogy kit értesít. Eldöntendő, hogy adott értesítési hozzárendelések valóban riadóláncot alkotnak-e?
  • Specifikáció:
    • A probléma inputja egy n szám, a közösség tagjainak (akiket [0, \(\dots\), n-1] sorszámokkal azonosítunk) száma, valamint egy n elemű számsorozat, melynek i. tagja az i. sorszámú ember által értesítendő személy sorszáma.
    • Az output egy "Igen" vagy "Nem" tetszőleges szövegkörnyezetben.
  • Algoritmustervezés:
    • A riadólánc egy Lanc nevű számsorozattal adható meg, amelynek i. eleme annak az embernek a sorszáma, akit az i-nek értesíteni kell.
    • A Lanc sorozat akkor és csak akkor valódi riadólánc, ha bármelyik elemétől elindulva a Lanc szerinti hozzárendelést követve visszajutunk i-be úgy, hogy közben minden elemet érintettünk.
    • Ezt azonban elég egy tetszőleges elemtől kezdve kipróbálni.
  • Algoritmustervezés szerkezeti ábrával:
    kep

A megvalósítás során azt vizsgáljuk, hogy a kezdő embertől hány emberen keresztül tudunk láncot alkotni. Amikor a lánc körbe ér, a számolás befejeződik. A számolás során elkezdjük a tömb elemeit vizsgálni a következő módon az ELSO indexű embertől kezdve:

  • Megnézzük, hogy jártunk e már az adott embernél (ezt trükkösen onnan fogjuk tudni, hogy miután adott ember adatait feldolgoztuk, az ő tömb értékét N-re állítjuk, azaz egy olyan értékre, akit a valóságban nem tudna értesíteni).
  • Ha még nem jártunk az adott embernél, akkor egész biztos az adott emberhez tartozó bejegyzés N-nél kisebb nemnegatív szám a beolvasás miatt. Ekkor
    • olvassuk ki annak az embernek a sorszámát, akit az aktuális ember értesít, és ezt jegyezzük meg,
    • az aktuális ember által értesítendő ember sorszáma helyett tároljuk el adott embernél az N értéket,
    • növeljük annak a számlálónak az értékét 1-gyel, amiben azt tároljuk, hány embert értesítettünk már,
    • folytassuk annak az embernek a kiértékelésével a folyamatot, akit az aktuális ember értesített volna.
  • Ha a soron következő ember már korábban értesítve volt, akkor a következő esetek lehetnek:
    • Mindenki értesítve van, és az utolsó ember az ELSO-t értesíti. Ez jó, mert akkor a riadólánc zárul, és körbe is ért. Az "Igen" válasszal térhet vissza a programunk.
    • Mindenki értesítve van, de az utolsó nem az ELSO-t értesíti. Ez nem jó, ha nem a dedikált ELSO embernél kezdtük volna a feldolgozást, akkor már hamarabb zárult volna a kör, és az ELSO kimaradt volna a láncból. Ezért itt "Nem" a válasz.
    • Nem lett mindenki értesítve, azaz a számláló kisebb, mint az emberek száma. Ez esetben hamarabb zárult a kör, mint kellett volna. A válasz ebben az esetben is "Nem".

A Beolvasás részt részletesebben ki tudjuk fejteni:

kep

A Beolvasás részben nagyon fontos, hogy minden tömb elemre megadjuk azt az index értéket, ami meghatározza, hogy az adott pozíción levő ember kit értesít. Mivel nincs indexhatár-ellenőrzés, így csakis olyan adatot adghatunk meg, ami a tömböt indexeli. Ha a beolvasás más adatot adna, akkor azt a beolvasást meg kell ismételni. Amikor megvan, hogy az i. ember kit fog értesíteni, hanyadik embert a tömbben, módosítjuk a tömb i. indexű elemét ezzel az értékkel.

 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
/* Adott n számú embert tartalmazó közösség. Eldöntendő,
 *   hogy riadóláncot alkotnak-e?
 * 2006. augusztus 9. Gergely Tamás, gertom@inf.u-szeged.hu
 */

#include <stdio.h>

#define N    8                               /* a sorozat elemeinek száma */
#define ELSO 0                       /* az első vizsgálandó elem sorszáma */

int main () {
    int lanc[N];                               /* a sorozatot tároló tömb */
    int e, i;                                            /* munkaváltozók */
    int kov;                                   /* a következő vizsgálandó */
    int szam;                                                 /* számláló */

    printf("Kérem a %d elemű sorozatot, amelyről ", N);
    printf("eldöntöm, hogy riadólánc-e!\n");

    for (i = 0; i < N; ++i) {                                /* beolvasás */
        printf("%d. kit értesít ? ", i);
        scanf("%d%*[^\n]", &e); getchar();

        while ((e < 0) || (N <= e)) {
            printf("Hibás adat!\nKérem újra: ");
            scanf("%d%*[^\n]", &e); getchar();
        }
        lanc[i] = e;
    }

    kov  = ELSO;                                         /* inicializásás */
    szam = 0;
    do {
        i       = kov;
        kov     = lanc[i];                                 /* továbblépés */
        lanc[i] = N;                         /* jártam már itt bejegyzése */
        ++szam;
    } while (lanc[kov] != N);                          /* jártam már itt? */

    if ((szam == N) && (kov == ELSO)) {
        printf("A számsorozat riadólánc.\n");
    } else {
        printf("A számsorozat nem riadólánc.\n");
    }
    return 0;
}

A megvalósításban rögzítettük a lánc méretét egy N konstanssal, illetve az ELSO elemet, amit most a tömb kezdő indexére állítottunk. A megvalósítás persze lehetővé tenné, hogy ez az ELSO érték bármelyik alkalmas tömbindex legyen, azaz 0 és N-1 között bármely értékre beállíthattuk volna. Figyeljük meg a kódban azokat a sorokat, amelyek a riadóláncot megvalósító tömböt kezelik!

Először is vegyük a deklarációt:

1
int lanc[N];
Itt láthatjuk, hogy a lanc-ban egész értékeket tárolunk, a tömb mérete N. Fontos, hogy deklarációkor a töm mérete konstans mód meghatározható legyen!

A beolvasás részen végig megyünk a tömbön a 0. indextől egészen az N-1 indexig. Általában igaz az, hogy a tömb bejárásokat érdemes egy for ciklussal vezényelni, ahol a tömb indexelésére a ciklus ciklusváltozóját használjuk.

A feldolgozás során mivel legalább az ELSO elemet fel kell dolgozzuk, így itt érdemes egy végfeltételes ciklust használni. Minden ciklusban kiolvassuk a ciklusváltozónak megfelelő tömbelemet, és módosítjuk is azt.

Általános tömb típus, mint absztrakt adattípus

Az eddigiekben a tömbben tárolt elemek típusa egyszerű típus volt, a tömb indexelése egy dimenzión mozgott. Azonban elképzelhető, hogy az adatokat célszerűbb több dimenzióban tárolni. Gondoljunk egy táblázatra, amelynek oszlopai és sorai vannak, az egyes elemeket pedig a sor és oszlop sorszámok segítségével a legegyszerűbb meghatározni.

Éppen ezért, a tömböket definiálhatjuk általános módon is, ahol eltérően az előző definíciótól a tömbben tárolt adatok \(E\) típusa mellett indexek egy sorozatát adjuk meg. Ehhez legyenek \(I_1, \dots, I_k\) tetszőleges sorrendi típusok, ahol az
\(I = I_1 \times \dots \times I_k = \{ (i_1, \dots, i_k) |i_1 \in I_1, \dots, i_k \in I_k \}\)
halmaz, amely az \(I_1 \times \dots \times I_k\) halmazok direktszorzatából áll, megadja az indexek halmazát. Képezhetjük azt a \(T = Tomb( I_1 \times \dots \times I_k, E)\) új típust, amelynek értékhalmaza az \(I\)-ből \(E\)-be való függvények halmaza, azaz: \(\{ A|A : i \rightarrow E \}\). A \(k\)-t a tömb dimenziójának nevezzük.

Nem meglepő módon egy általános tömb esetében hasonló műveletekre számítunk, mint az egyszerű, egy dimenziós esetben, a különbség csupán az indexek megadásában van:

Művelet megnevezése Művelet leírása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\leftarrow\) x: E) Az A tömb (i1, \(\dots\),ik) komponensát kiolvassa és eltárolja az x változóban.
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\rightarrow\) x: E) Az A tömb (i1, \(\dots\),ik)komponensét módosítja az x értékkel.
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T) Az A tömb felveszi az X tömb típusú kifejezés értékét.

Általános tömb típus, mint virtuális adattípus

Könnyen ésszrevehetjük, hogy egy T = Tomb( I1\(\times \dots \times\) Ik, E) típus felfogható úgy, mint egy olyan egyszerű, egy dimenziós T = Tomb( I1 , T1) tömb, amely T1 = Tomb( I2 \(\times \dots \times\) Ik, E) típusú tömböket tárol. Továbbá az sem jelent megkötést, hogy minden egyes Ij intervallum [0 .. Nj] alakú legyen, hiszen bármely [n..m] intervallum elemei egyszerűen transzformálhatóak a [0..(m-n)] intervallumra. Ezek alapján a C nyelven már létre tudunk hozni többdimenziós tömb típust is:
typedef E T[N1][N2] ...[Nk];

Művelet absztrakt szinten Művelet virtuális megvalósítása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\leftarrow\) x: E) x = A[i1]...[ik];
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\rightarrow\) x: E) A[i1]...[ik] = x;
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T) Nincs direkt megvalósítás! Használható a memcpy(), vagy a \(C^{11}\) szabvány után a biztonságosabb memcpy_s() függvény.
Tömb inicializálása

Amikor egy tömböt létrehozunk, akkor lehetőségünk van arra, hogy annak elemeit kezdőértékekkel lássuk el. Például:

1
2
3
4
5
6
7
8
9
int t[][3] = {
    { 1, 2, 3 },  { 4, 5, 6 },  { 7, 8, 9 }
};
int t1[4][3] = {
    { 1, 2, 3 },  { 4, 5, 6 },  { 7, 8, 9 }
};
int t2[][3] = {
    { 1 },  { 4 },  { 7 },  { 9 }
};

A fenti példában a t tömb egy 3*3-as tömb. Bár az első dimenzió mérete nincs megadva, az a kezdőértékek számából kiolvasható. A t2-es tömbnél viszont látjuk, hogy maga a tömb 4*3-as, de látszólag ugyanúgy van inicializálva, mint a t tömb. Ha ezt a 2 dimenziós tömböt egy táblázatnak képzeljük el, akkor ez egy 4 soros, 3 oszlopos táblázat, aminek az utolsó sora a szabvány szerint 0-val inicializálódik. A t3-as tömbnél nem adjuk meg az első dimenzió méretét, ezt az inicializálásból ki tudjuk találni, hogy 4. A nem inicializált elemek itt is 0 értéket vesznek fel.

Ha tehát tömböt kezdőértékkel deklarálunk, akkor az első dimenzió mérete elhagyható, mert az a kezdőértékek számából kiolvasható. De ha kevesebb kezdőértéket adunk meg, mint amekkora tömbre később szükségünk van, akkor ezt a méretet is meg kell adni.

Inicializálás

Ha egy tömböt hiányosan inicializálunk (de inicializálunk), akkor a hiányzó elemeket 0-val (vagy azzal ekvivalens értékkel) tölti fel a fordító. Ha egy tömböt nem inicializálunk (hiányosan sem), az elemei definiálatlanok maradnak, nem kapnak kezdőértéket.

Általános tömb típus, mint fizikai adattípus

A tömbök esetében nagyon fontos látnunk, hogy az egyes elemeket hogyan is tárolja el egy-egy C program, mivel látni fogjuk, hogy ezen ismeret fogja segíteni azt, hogy akár pointerekkel hivatkozzunk egy-egy tömb elemre. A lehetséges gépi megvalósítás vizsgálatánál abból kell kiindulni, hogy a memória lineáris szerkezetű. Tömb típusú változó számára történő helyfoglalás azt jelenti, hogy minden tömbelem, mint változó számára memóriát kell foglalni. Feltehetjük, hogy egy adott tömb változóhoz a tömbelemek számára foglalt tárterület összefüggő mezőt alkot.

A megvalósítás azt jelenti, hogy a lefoglalt memóriaterület kezdőcíme és az i1 , \(\dots\) ik indexkifejezések értékéből kell meghatározni egy adott A tömb A[i1]\(\dots\)[ik] elemének a címét. Gyakorlatilag látható, hogy adott indexre ezt egyértelműen meg kell tudni határozni, így újabb műveletként felvehetjük a tömbökhöz a Cím(A[i1]\(\dots\)[ik]) címfüggvényt is. Ami egyértelmű, hogy a Cím függvény felírható t0 + TCF(i1 , \(\dots\) ik) alakban is, ahol t0 az A változóhoz foglalt memóriamező kezdőcíme, a TCF függvény pedig a tömb típus által meghatározott és tömb-címfüggvénynek nevezzük.

Ahhoz, hogy a tömböket hatékonyan tudjuk kezelni, ennek a TCF függvénynek egyszerűnek, gyorsan számolhatónak kell lennie az t0 + TCF(i1, \(\dots\) ik) értékek függvényében. Egydimenziós esetben adja magát a képlet, ha tudjuk, hogy egy tömbelem mérete c, akkor az i. elem kezdőcíme i*c távolságra lesz a tömb kezdőcímétől (itt kihasználjuk azt is, hogy a tömbök indexelése 0-tól kezdődik).

Ha ezt általánosítani szeretnénk tetszőleges dimenzióra, könnyen megtehetjük, ha ismerjük a tömb paramétereit. Tegyük fel, hogy adott egy E T[N1]\(\dots\)T[Nk]; tömb deklarációnk. Mivel feltehetjük, hogy ez is egy egy dimenziós tömb, amely minden eleme egy tömb, melynek típusa E T[N2]\(\dots\)T[Nk], így felhasználva az előbbi egy dimenziós megoldást kapjuk, hogy T[i1] offszetje (azaz tömbön belüli címe) i1 \(\cdot\)c1, ahol c1 = sizeof(E T[N2]\(\dots\)T[Nk]).

Ennek mintájára már adott T[i1] [i2] offszetje is, ami i1 \(\cdot\)c1 + i2\(\cdot\)sizeof(E T[N3]\(\dots\)T[Nk]).

Általánosan tehát T[i1]\(\dots\) [ik] offszetje i1 \(\cdot\)c1 + \(\dots\) + ik \(\cdot\)ck, ahol \(\forall\) i-re, amire 1 \(\leq\) i < k, arra ci = sizeof(E[N\(_{i+1}\)] \(\dots\)[Nk]) és ck = sizeof(E).

Ha a tömbméretet konstansként adtuk meg, akkor a c1, \(\dots\), ck konstansok fordítási időben kiszámíthatóak. Éppen ezért az eredeti C standard nem is engedi a statikus tömböket csak úgy deklarálni, ha a méretük ismert fordítási időben. Ha a tömbünk méretét változóval adtuk meg, akkor a c\(_1\), \(\dots\), c\(_k\) konstansok kiszámítása futásidőben történik.

Ez tulajdonképpen a tömbelemek index szerinti lexikografikus rendezését adja meg, azaz ha (i1, \(\dots\), ik) \(<_{lex}\) (j1, \(\dots\), jk) akkor és csak akkor teljesül, ha a legkisebb u indexre, amire iu \(\neq\) ju, ott iu < ju.

Kétdimenziós esetben (E T\([\)N\(]\)\([\)M\(]\)) például a lexikografikus rendezés az alábbiak szerint működik. A memóriában a tömb elemek egymás után (egy dimenzióban) kapnak helyet:

kep

Míg logikailag egy 2 dimenziós táblázatot alkotnak:

kep

Nagyon fontos újra és újra kihangsúlyozni, hogy a tömbök használata nagy körültekintést igényel, hiszen a C program végrehajtása közben nincs indexhatár-ellenőrzés. Ha adott egy double m[10][10]; deklaráció, akkor az m[0][10] és az m[1][0] hivatkozások megegyeznek, ráadásul a C mind a kettőt el is fogadja. Ez néha persze jó is, mert így lehetőség van arra, hogy tetszőleges dimenziós tömböt akár egy dimenziósként végigjárjunk, ha a művelet, amit végzünk a tömbelemeken független azok dimenziójától (pl. ilyen lehet az inicializálás, vagy ha egyszerűen össze akarom adni az letárolt értékeket, ...)

Az alábbi kódrészletben a két dimenziós tömböt egyetlen ciklussal inicializáljuk, viszont a kiíratásnál fontos a dimenzió, hiszen szeretnénk, ha megfelelő táblázat alakban látnánk a tömböt:

1
2
3
4
5
6
7
8
int i, j, a[3][3];
for (i = 0; i < 9; ++i)
    a[0][i] = i;
for (i = 0; i < 3; ++i) {
    for(j = 0; j < 3; ++j)
        printf("%d ", a[i][j]);
    printf("\n");
}

Kimenet

1
2
3
0 1 2
3 4 5
6 7 8

Tömb, mint paraméter

Egy függvény paramétere lehet tömb típusú is. Ilyen esetben azonban nem történik teljes értékmásolás, hanem csak a tömb címe (vagyis egy pointer) kerül átadásra, így a tömb elemein végzett bármely módosítás az eredeti tömbön kerül végrehajtásra. Mivel C-ben nincs indexhatár-ellenőrzés, és a paraméterként átadott tömbnek csak a címét kapja meg a függvény, ezért ha a függvény T paramétertípusa E típusú elemekből álló egydimenziós tömb, ennek a pontos méretét a függvény deklarációjában nem kell megadni.

AzE típus méretét viszont pontosan ismerni kell, tehát ha a T többdimenziós tömb típus, azaz E is legalább egydimenziós tömb típus, akkor E minden dimenziójának a méretét pontosan fel kell tüntetni, azaz csak T legelső dimenziójának mérete hagyható el. Például:

1
2
bool ciklikus(int n, int A[]);
int fgv(int tomb[][10][3]);

Példa - riadólánc 2.

  • Problémafelvetés: a Riadólánc algoritmusban a bemenő adatot tároló tömb az algoritmus végrehajtása során módosul. Ez elkerülendő akkor, ha a bemenő adaton más műveletet is kell végeznünk majd a későbbiekben. Készítsünk tehát egy olyan függvényt, amely egy értesítési láncról eldönti, hogy az riadólánc-e (matematikai megfogalmazással: eldönti, hogy a kapott adatok ciklikus permutációt határoznak-e meg) anélkül, hogy a láncot magát megváltoztatná!
  • Specifikáció:
    • A függvény inputja egy n szám, a közösség tagjainak (akiket [0, \(\dots\), n-1] sorszámokkal azonosítunk) száma, valamint egy n elemű tömb, melynek i. tagja az i. sorszámú ember által értesítendő személy sorszáma. A tömb bemenő paraméter, értékét a függvény nem változtathatja meg.
    • Az output a függvény visszatérési értéke, egy logikai igaz érték ha az input ciklikus permutáció, illetve hamis ha nem az.
  • Algoritmustervezés szerkezeti ábrával:
    kep

A megoldásban számoljuk azt, hogy az ELSO elemtől indulva haladunk az értesítési listán, miközben számoljuk az érintett egyedeket. A ciklusunk megállási feltétele, ha az érintett elemek száma eléri a közösségünk méretét, vagy pedig visszatérünk az ELSO elemhez.

Amennyiben mindkét feltétel egyszerre teljesül, a függvény visszatérési értéke igaz (teljes a láncunk és kört alkot), egyébként a visszatérési érték hamis.

 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
/* Adott n számú embert tartalmazó közösség. Eldöntendő,
 *   hogy riadóláncot alkotnak-e?
 *   Ehhez felhasználunk egy függvényt, amely eldönti, hogy
 *   a kapott sorozat ciklikus permutáció-e?
 * 2005. október 13. Gergely Tamás, gertom@inf.u-szeged.hu
 * 2014. október 9. Gergely Tamás, gertom@inf.u-szeged.hu
 */

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

#define N    8                               /* a sorozat elemeinek száma */
#define ELSO 0                       /* az első vizsgálandó elem sorszáma */

bool ciklikus(int n, int perm[]) {                /* A paraméter egy tömb */
    int kov = ELSO, szam = 0;                    /* következő és számláló */
    do {
        kov = perm[kov]; szam++;                           /* továbblépés */
    } while ((kov != ELSO) && (szam != n));
    return (kov == ELSO) && (szam == n);
}

int main () {
    int lanc[N];                               /* a sorozatot tároló tömb */
    int e, i;                                            /* munkaváltozók */

    printf("Kérem a %d elemű sorozatot, amelyről ", N);
    printf("eldöntöm, hogy riadólánc-e!\n");

    for (i = 0; i < N; ++i) {                                /* beolvasás */
        printf("%d. kit értesít ? ", i);
        scanf("%d%*[^\n]", &e); getchar();

        while ((e < 0) || (N <= e)) {
            printf("Hibás adat!\nKérem újra: ");
            scanf("%d%*[^\n]", &e); getchar();
        }
        lanc[i] = e;
    }

    if (ciklikus(N, lanc)) {
        printf("A számsorozat riadólánc.\n");
    } else {
        printf("A számsorozat nem riadólánc.\n");
    }
    return 0;
}

Mivel a tömbünk egy dimenziós, a függvény deklarációjában a perm tömbnek a méretét nem kell meghatározni. A main függvényben definiáljuk a lanc-ot, amelyben eltároljuk, hogy ki kit fog értesíteni. A korábbi megoldáshoz hasonlóan itt is nagyon fontos, hogy a tömbben szereplő adatok megfelelőek legyenek, így mindenki csak olyan elemet értesíthet, aki a "közösség tagja". Azaz egy érvényes tömbelem indexre kell mindenkinek hivatkoznia.

Ha ezzel megvagyunk, a lánc egy tetszőleges elemétől vizsgálhatjuk, hogy az ciklikus-e. A ciklikus függvény hívásakor fontos az, hogy maga a függvény tudja, hogy a lánc milyen méretű, így ezt is átadjuk paraméterben, bár igaz, hogy ebben az esetben talán ez egy felesleges lépésnek hat, mivel a tömb méretét meghatározó konstans globálisan elérhető. A második paraméterben adjuk át a tömb címét, ahol egyszerűen a tömb nevével hivatkozunk a tömb első elemének a címére.


Utolsó frissítés: 2020-10-19 17:18:58