Ebben a részben a tömbökkel kapcsolatos leggyakoribb műveletekkel foglalkozunk. Nem is vesztegetném tovább a szót, vágjunk bele.
Van egy tömbünk: int tomb[ELEMEK] értékekkel feltöltve és van egy változónk: szam
Feladatunk eldönteni, hogy van-e a tömbben olyan elem, aminek értéke a paraméterként átvett szam értékével megegyezik. Ennek megoldására a for ciklust fogjuk használni. Addig haladunk a tömb elemein, amíg nem találkozunk egy olyan elemmel, amelyik értéke megegyezik szam értékével. Ha ez bekövetkezik, egyből kilépünk a függvényből 1-es visszatérési értékkel. Ha viszont a ciklus végigfutott, az azt jelenti, hogy nincs szam értékű elem, ezért a függvény 0 értékkel tér vissza.
int eldont(int szam)
{
for (i = 0; i < ELEMEK; i++)
{
if (tomb[i] == szam) return 1;
}
return 0;
}
Ehhez nem is fűznék több kommentárt, a programrészlet magáért beszél. Látható persze a hátránya is, csak az első egyezést találja meg, nem vizsgálja, hány ilyen elem van a tömbben.
Lényegében az eldöntés során is lineáris keresést használunk, bár fentebb nem bajlódtunk a keresett elem visszaadásával, csak örültünk, hogy van ilyen. Ha viszont szükségünk van az elemre, akkor végigfutunk a tömbön, és ha az adott indexű elem értéke megegyzik a keresett elemmel, akkor visszaadjuk az index értékét, ha viszont nem találunk ilyen elemet, akkor -1 értéket adunk vissza, mert nem akarjuk összekeverni az index értékekkel. (-1 értékű index ugyebár nem lehet J). Részletesebb magyarázatra a fentiek ismeretében nincs is szükség, a kód önmagában érthető.
int lin_keres(int szam)
{
for (i = 0; i < ELEMEK; i++)
{
if (tomb[i] == szam) return i;
}
return -1;
}
A logaritmikus keresés esetén feltételezzük, hogy az n elemű tömb rendezett. Azért hívják logaritmikus (vagy bináris) keresésnek, mert az elem megtalálásához szükséges lépések szám körülbelül log2n. A kérdés most is az, hogy szerepel-e a keresett elem a sorozatban, és ha igen, akkor melyik az?
Ennél az algoritmusnál először kettéosztjuk a tömböt és a középső elemnél kezdjük a keresést. Ha ez az, akkor kész vagyunk (ezért kell do-while ciklust használnunk). Ha nem, akkor megnézzük, hogy az elem a tömb felső vagy alsó részében van-e (a tömb rendezett, tehát egyszerű összehasonlítással el tudjuk dönteni!). Ezután a tömbnek azon részével foglalkozunk, amiben a keresett elem van. Ugyanúgy járunk el, mint az egész tömbben. Felosztjuk ketté, megnézzük a középső elemet, ha az, akkor megvagyunk, ha nem haladunk tovább az előbbiek szerint.
Akkor nézzük az algoritmust, ebben is lesz néhány ismeretlen dolog.
int log_keres(int szam)
{
int also = 0, felso = ELEMEK-1, kozepso;
do
{
kozepso = (int)((also + felso)/2); /*Castolás*/
if (tomb[kozepso] < szam) also = kozepso + 1;
if (tomb[kozepso] > szam) felso = kozepso - 1;
} while (also <= felso && tomb[kozepso] != szam);
/*Két esetben áll le a ciklus: Ha megvan a keresett elem (tomb[kozepso] == szam) vagy a teljes tömbön végigmentünk és nincs meg a keresett elem (also > felso)*/
if (also > felso)
return -1; //tulszaladtunk, nincs ilyen ertek
else
return kozepso; // ez a keresett ertek indexe
}
Az első ismeretlen dolog a do-while ciklusban jelenik meg, ki is emeltem egy kommenttel: „castolás”. Mit jelent ez? Egyszerűen megfogalmazva explicit típuskonverzió. Érthető, nemJ? Szóval a C-ben beszélünk implicit és explicit típuskonverzióról. Az implicit típuskonverziót a fordítóprogram hajtja végre, ha szükséges, például egy lebegőpontos számot szorzunk egésszel és az eredmény automatikusan lebegőpontos lesz.
Esetünkben előfordulhat, hogy páratlan számú elem esetén az osztás eredménye tört szám lesz ezért a biztonság kedvéért odabiggyesztettünk egy (int)-et, ez az explicit típuskonverzó. Ki lehetett találni, hogy ezt pedig a programozó teszi ha szüksége van rá, és nekünk szükségünk is van, mert a középső elem indexe (és a többié is) csak egész szám lehet. Más esetekben is egy tetszőleges tört számból úgy kaphatjuk meg az egész részt, hogy egyszerűen integerré konvertáljuk a típusát.
A második újdonság a do-while ciklus feltételében található: a && operátor. Találkoztunk már vele, de még nem használtuk. Emlékeztetőül: ez jelenti a logikai ÉS-t. Ha valakit esetleg zavarna, definiálhat egy makrót:
#define AND &&
A mellékelt keresesek.c fájl tartalmazza a futtatható kódot, de az algoritmusok jobb megértése érdekében itt látható a fájl tartalma teljes egészében, kommentezve. Most éppen egy páros integerekből álló rendezett tömbben fogunk keresgélni, nevezetesen a 14-es értékű elemet. Az ékezetek azért maradtak le, hogy a különböző oprendszereken ne okozzon problémát. L
#include <stdio.h>
#define ELEMEK 10
int tomb[ELEMEK];
int szam = 14;
int eldont(int szam) //van benne ilyen elem?
{
int i;
for (i = 0; i < ELEMEK; i++)
{
if (tomb[i] == szam)
return 1; //talalt ilyen elemet
}
return 0; //nincs ilyen elem
}
int lin_keres(int szam)
{
int i;
for (i = 0; i < ELEMEK; i++)
{
if (tomb[i] == szam)
return i; // a megtalalt elem indexet adja vissza
}
return -1; //nincs ilyen elem (azert -1, mert 0. indexu elem is lehet)
}
int log_keres(int szam)
{
int also = 0, felso = ELEMEK-1, kozepso;
do
{
kozepso = (int)((also + felso)/2);
if (tomb[kozepso] < szam)
also = kozepso+1;
if (tomb[kozepso] > szam)
felso = kozepso-1;
} while (also <= felso && tomb[kozepso] != szam);
/*Ket esetben all le a ciklus: Ha megvan a keresett elem (tomb[kozepso] == szam) vagy
a teljes tombon vegigmentunk es nincs meg (also > felso)*/
if (also > felso)
return -1; //tulszaladtunk, nincs ilyen ertek
else
return kozepso; // ez a keresett ertek indexe
}
void main() // itt hivjuk meg a fuggvenyeket
{
int index, i;
for (i=0; i<ELEMEK; i++)
tomb[i] = i*2; //feltoltunk egy tombot ertekekkel
index = log_keres(szam); //logaritmikus kereses, csak rendezett tombon lehetseges
if (index == -1)
printf("nincs ilyen ertek a tombben\n");
else
printf("a keresett elem indexe: %d, erteke: %d\n", index, tomb[index]);
if (eldont(szam) == 1) //csak azt akarjuk tudni, letezik-e az elem
printf("van ilyen elem a tombben\n");
else
printf("a keresett elem nem talalhato\n");
if (lin_keres(szam) == -1) //linearis kereses, nem elofeltetel a rendezettseg
printf("a linearis kereses nem talalt semmit\n");
else
printf("linearis keresesben az elem indexe: %d, erteke: %d\n", lin_keres(szam), tomb[lin_keres(szam)]);
}