Uplynul dalÜφ m∞sφc a je tu tedy i pokraΦovßnφ kurzu v∞novanΘho datov²m strukturßm. V minulΘm opakovacφm dφlu jsme si p°ipomenuli datovΘ struktury, se kter²mi se setkßme ve v∞tÜin∞ dneÜnφch p°ekladaΦ∙. KonΦili jsme poli a dnes se budeme zab²vat jednorozm∞rn²mi poli. Ukß₧eme si, jak v poli hledat hodnotu, pak se budeme v∞novat zajφmav∞jÜφmu - set°φd∞nφ ·daj∙ ulo₧en²ch v poli, p°iΦem₧ nez∙staneme jen u jednoho zp∙sobu.
Proto₧e doposud jsme neprobrali ₧ßdn² z algoritm∙ t°φd∞nφ pole, pak naÜe pole pro tento odstaveΦek bude polem neset°φd∞n²m podle velikosti prvk∙. Jedin²m zp∙sobem, jak v takovΘmto poli nalΘzt zadanou hodnotu je prozkoumat prvky pole. V nejhorÜφm p°φpad∞ tedy budeme muset prozkoumat ·pln∞ vÜechny prvky pole. Pozd∞ji si ukß₧eme, jak lze v set°φd∞nΘm poli nalΘzt zadanou hodnotu mnohem rychleji.
P°edpoklßdejme, ₧e se v prohledßvanΘm poli hledanß hodnota nachßzφ pouze jednou. Pokud bychom cht∞li nalΘzt a₧ n-t² v²skyt, pak staΦφ p°idat parametr a poΦφtadlo v²skyt∙. Ukß₧eme si tedy prvnφ implementaci vyhledßnφ prvku se zadanou hodnotou:
#include <iostream.h>
int Hledani(int *pPole, unsigned int dwVelikost, int iHodnota)
{
int iIndex = -1;
// nastavime priznak, ze jsme nenalezli
for(unsigned int i = 0; i < dwVelikost; i++)
{
if(iHodnota == pPole[i])
// pokud bude hodnota v poli vicekrat,
dostaneme se az na posledni vyskyt hodnoty v poli
{
iIndex = i;
}
// pro vyhledani prvniho vyskytu staci pouzit podminku ve tvaru
// if((Hodnota == pPole[i]) && (-1 == iIndex))
}
return iIndex;
}
int Pole[20];
int *pPole;
int main(int argc, char* argv[])
{
pPole = new int[20];
for(int i = 0; i < 20; i++)
{
Pole[i] = i;
// nastavime nejake hodnoty
pPole[i] = 20-i;
}
int iIndex = Hledani(Pole, 20, 19);
// pro hledani v dynamickem poli staci
zamenit Pole za pPole
if(iIndex != -1)
{
cout << "Hledana hodnota je na pozici : " << iIndex << " a je to cislo " <<
Pole[iIndex] << endl;
}
else
{
cout << "Hledana hodnota se v poli nevyskytuje" << endl;
}
char c;
cin >> c;
delete pPole; //
nezapomeneme smazat dynamicke pole
return 0;
}
Algoritmus sice provßdφ to, co se po n∞m chce, ale nenφ nejefektivn∞jÜφ. P°edstavte si, ₧e se hledanß hodnota nachßzφ hned v prvnφm prvku pole. Cyklus se vÜak nezastavφ a zbyteΦn∞ tedy projde vÜechny prvky pole. Pro vy°eÜenφ tohoto problΘmu staΦφ p°idat po nastavenφ nßvratovΘ hodnoty bu∩ p°φkaz pro p°eruÜenφ cyklu break nebo rovnou vrßtit nalezen² index pomocφ return. DalÜφ mo₧nostφ je p°epsßnφ funkce s vyu₧itφm cyklu while. Poslednφ mo₧nostφ je pak jeÜt∞ p°epsßnφ s pomocnou hodnotou typu boolean, kterß urΦuje zda-li se mß pokraΦovat v hledßnφ prvku:
int Hledani(int *pPole,
unsigned int dwVelikost, int
iHodnota)
{
bool bDalsi = true;
// nastavime priznak, ze chceme hledat
int iIndex = -1;
unsigned int i = 0;
while(bDalsi)
{
if(iHodnota == pPole[i])
{
bDalsi = false;
iIndex = i;
// nalezli jsme prvek
}
else if(i == (dwVelikost - 1))
{
bDalsi = false;
// jsme na konci
}
else
{
i++;
// dalsi prvek
}
}
return iIndex;
}
Jako dalÜφ mo₧nost vyhledßvßnφ v neset°φd∞nΘm poli si ukß₧eme metodu hledßnφ se zarß₧kou, kterß se pak s v²hodou vyu₧φvß u lineßrnφch spojov²ch seznam∙. Celß v∞c spoΦφvß v tom, ₧e jako poslednφ prvek umφstφme do pole nßmi hledanou hodnotu. Mßme tedy jistotu, ₧e tento prvek najdeme v₧dy a nemusφme tedy testovat p°ekroΦenφ indexu pole. Jedin²m problΘmem je, ₧e pole musφ mφt o jeden prvek navφc, abychom m∞li mφsto na ulo₧enφ tΘto zarß₧ky:
int Hledani(int *pPole,
unsigned int dwVelikost, int iHodnota)
{
// predpokladame, ze pole je o 1 vetsi
pPole[dwVelikost] = iHodnota;
// posledni platny prvek je pPole[nVelikost-1]
unsigned int i = 0;
while(iHodnota != pPole[i])
{
i++;
}
if(i < dwVelikost)
{
return i;
}
return -1;
}
VÜechny funkce se navenek chovajφ stejn∞, vrßtφ index do pole na kterΘm se nachßzφ hledanß hodnota. Pokud v poli hodnota nenφ, pak vracφ hodnotu -1 a je na volajφcφm, aby omylem neindexoval pole zßporn²m Φφslem. Jedin²m rozdφlem je, ₧e pro poslednφ vyhledßvacφ funkci musφ b²t velikost pole o 1 v∞tÜφ, jinak dojde k chyb∞ p°φstupu do pam∞ti.
Hledßnφ bylo napsßno pouze pro jednoduchΘ prom∞nnΘ typu int, ale s vyu₧itφm objekt∙ a p°et∞₧ovßnφ operßtor∙ je mo₧no tyto algoritmy upravit na set°φd∞nφ pole slo₧enΘho z libovoln²ch datov²ch typ∙.
T°φd∞nφm budeme rozum∞t uspo°ßdßnφ ·daj∙ podle velikosti (vzestupn∞ nebo sestupn∞) na zßklad∞ klφΦe, co₧ m∙₧e b²t libovoln² ·daj spojen² s prvkem datovΘ struktury. Jako p°φklad nßm poslou₧φ vzestupnΘ set°φd∞nφ jednorozm∞rnΘho pole obsahujφcφho celoΦφselnΘ prvky.
K Φemu se nßm m∙₧e hodit uspo°ßdßnφ prvk∙ podle velikosti? Jestli₧e vφme, ₧e pole naplnφme hodnotami a v pr∙b∞hu programu v n∞m budeme vyhledßvat hodnoty, pak je vhodnΘ pole set°φdit n∞kter²m z mnoha t°φdicφch algoritm∙ podle velikosti prvk∙. Nakonec si toti₧ ukß₧eme algoritmus pro vyhledßvßnφ v set°φd∞nΘm poli, kter² je mnohem rychlejÜφ ne₧ v²Üe uvedenΘ algoritmy.
Algoritmy pro t°φd∞nφ se d∞lφ nap°. nßsledovn∞:
vnit°nφ t°φd∞nφ - t°φd∞nφ kterΘ probφhß p°φmo v poli ulo₧enΘm v operaΦnφ pam∞ti poΦφtaΦe
vn∞jÜφ t°φd∞nφ - t°φd∞nφ velkΘho mno₧stvφ dat, kterΘ nenφ mo₧nΘ najednou ulo₧it do operaΦnφ pam∞ti poΦφtaΦe. Data se t°φdφ po Φßstech a postupn∞ se z nich tvo°φ delÜφ ·seky. K odklßdßnφ dat se pou₧φvajφ soubory
V dalÜφm textu se budeme zab²vat algoritmy vnit°nφho t°φd∞nφ. Mimoto dneÜnφ operaΦnφ systΘmy pracujφ s odklßdacφmi soubory, kterΘ mohou v p°φpad∞ nedostatku nahradit fyzickou pam∞¥, tak₧e nenφ problΘm t°φdit i velkß pole.
Nejprve si vÜak pro ·plnost vytvo°φme proceduru, kterß vypφÜe obsah pole p°edanΘho parametrem:
void TiskPole(int *pPole, unsigned int dwVel)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
cout << pPole[i] << " ";
}
cout << endl;
}
}
Abychom m∞li n∞jakß data, kterß bychom mohli t°φdit, pak si napφÜeme jeÜt∞ proceduru pro napln∞nφ pole nßhodn²mi Φφsly:
void NaplnPole(int *pPole, unsigned int
dwVel)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
pPole[i] = rand();
// generuje nahodna cisla od 0 do
konstanty RAND_MAX (0x7FFF)
}
}
}
Funkce rand() je definovßna v hlaviΦkovΘm souboru stdlib.h, kter² tedy musφme vlo₧it. Jestli₧e chceme Φφsla pouze do urΦitΘ hodnoty, pak staΦφ na funkci rand() pou₧φt operßtor modulo (%). Chceme-li Φφsla od 0 do 100 napφÜeme:
cislood0do100 = rand() % 100;
Pokud zkusφte vygenerovat nßhodnß Φφsla, program vypnete a znovu spustφte, dostanete stejnß nßhodnß Φφsla. Je to tφm, ₧e Φφsla nejsou ·pln∞ nßhodnß, ale jen pseudonßhodnß. Pro vy°eÜenφ tohoto problΘmu pou₧ijeme funkci srand(int seed), kterß nastavφ poΦßteΦnφ bod pro generovßnφ posloupnostφ nßhodn²ch Φφsel. Funkci srand(int seed) se p°edßvß parametr typu int, my pou₧ijeme hodnotu Φasu, kterß se stßle m∞nφ. Budeme tedy navφc pot°ebovat hlaviΦkov² soubor time.h, kter² obsahuje funkci time(). Tato funkce vracφ poΦet vte°in, kterΘ ub∞hly od p∙lnoci 1.1.1970. Mezi prvnφmi p°φkazy ve funkci main() tedy bude nßsledujφcφ °ßdek:
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL)); // abychom dostali pri kazdem spusteni jina cisla
...
}
V∞tÜin∞ funkcφ pro t°φd∞nφ p°edßvßme pouze ukazatel na pole a velikost tohoto pole, lze je samoz°ejm∞ pou₧φt jak na staticky, tak na dynamicky alokovanß pole.
Prvnφm algoritmem, kter²m se budeme zab²vat je p°φm² v²b∞r. Tento algoritmus spoΦφvß ve vybφrßnφ nejmenÜφho Φφsla z Φφsel, kterß jsme jeÜt∞ nezat°φdili. V levΘ Φßsti pole tak postupn∞ vznikß uspo°ßdanß posloupnost Φφsel a vpravo jsou Φφsla neuspo°ßdanß. Z pravΘho ·seku v ka₧dΘm pr∙b∞hu algoritmu vybereme nejmenÜφ Φφslo, kterΘ pak jen p°ipojφme na konec levΘho ·seku (prohodφme nalezen² menÜφ prvek a p∙vodnφ prvek):
void PrimyVyber(int *pPole, unsigned int
dwVel)
{
unsigned int dwNejmensi; // index, ne hodnota !!!
int iVymena; // pro vymenu prvku
for(unsigned int i = 0; i < (dwVel - 1); i++)
{
dwNejmensi = i; // index prvku, ke kteremu hledame mensi
for(unsigned int j = i + 1; j < dwVel; j++)
// hledame od dalsiho nesetrideneho
{
// najdeme index nejmensiho prvku, pokud
existuje
if(pPole[j] < pPole[dwNejmensi])
{
dwNejmensi = j;
}
}
if(dwNejmensi > i) // pokud jsme nasli mensi prvek
{
iVymena = pPole[i];
pPole[i] = pPole[dwNejmensi]; // vymenime oba prvky
pPole[dwNejmensi] = iVymena;
}
}
}
Podmφnka (iNejmensi > i) nenφ nutnß, ale pokud v neset°φd∞nΘm ·seku nenajdeme menÜφ prvek ne₧ poslednφ v set°φd∞nΘm ·seku, uÜet°φme zbyteΦnΘ p°φstupy do pam∞ti pro "prohozenφ" stejn²ch prvk∙.
DalÜφ t°φd∞nφ je zalo₧enΘ na porovnßvßnφ sousednφch prvk∙. Pokud po v∞tÜφm Φφslu nßsleduje Φφslo menÜφ, pak dojde k prohozenφ. Na konci algoritmu jsou se°azeny vÜechny dvojice a tedy i celΘ pole. Ukß₧eme si jednoduchou implementaci:
void Bublinka(int *pPole, unsigned int dwVel)
{
int iVymena;
for(unsigned int i = 1; i < dwVel; i++)
{
for(unsigned int j = dwVel; j >= i; j--)
{
if(pPole[j-1] > pPole[j]) // vetsi pred mensim
{
// prohodime prvky
iVymena = pPole[j-1];
pPole[j-1] = pPole[j];
pPole[j] = iVymena;
}
}
}
}
Proto₧e pole prochßzφme od poslednφho prvku, pak se p°i prvnφm pr∙chodu na prvnφ mφsto dostane nejmenÜφ prvek. Ve druhΘm pr∙chodu se dostane na druhΘ mφsto druh² nejmenÜφ prvek, tak₧e nemusφme ji₧ prochßzet celΘ pole. Nejv∞tÜφ prvek klesß poka₧dΘ o jedno mφsto dol∙.
Tato implementace algoritmu mß takΘ nev²hodu, ₧e nepoznß ut°φd∞n² ·sek pole, dochßzφ tedy ke zbyteΦn²m pr∙chod∙m p°es set°φd∞nΘ prvky. Proto ho vylepÜφme a budeme sledovat, jestli nastalo prohozenφ pomocφ bool hodnoty. Pokud nedojde k prohozenφ, pak je pole ji₧ set°φd∞nΘ a m∙₧eme t°φd∞nφ ukonΦit:
void Bublinka2(int *pPole, unsigned int dwVel)
{
bool bProhoz = true; // musi byt nastaveno,
aby zacal cyklus
int iVymena;
// Budeme prochazet pole, dokud budou nastavat prohozeni
while(bProhoz)
{
// pred pruchodem polem neni zadne prohozeni
bProhoz = 0;
// Zkontroluj vedle sebe lezici prvky
for(unsigned int i = 0; i < (dwVel - 1); i++)
{
if(pPole[i] > pPole[i+1]) // vetsi pred mensim
{
// prohodime prvky
iVymena = pPole[i+1];
pPole[i+1] = pPole[i];
pPole[i] = iVymena;
bProhoz = true; // nastala vymena
}
}
}
}
V jednotliv²ch pr∙chodech dochßzφ v₧dy k prohozenφ dvou sousednφch prvk∙, kterΘ nele₧φ ve sprßvnΘm po°adφ. Nedojde tedy k p°esunutφ nejmenÜφho prvku na prvnφ mφsto, jako tomu bylo v p°edchozφ implementaci.
Zajφmavou ·pravu bublinkovΘho t°φd∞nφ si ukß₧eme v nßsledujφcφm odstaveΦku.
V prvnφ implementaci bublinkovΘho t°φd∞nφ se nßm postupn∞ dostßvaly na sprßvnß mφsta nejrychleji nejmenÜφ prvky pole. Upravφme tedy algoritmus tak, ₧e budeme st°φdav∞ prochßzet pole z obou stran, nejprve se tedy na zaΦßtek dostane nejmenÜφ prvek, potom se nejv∞tÜφ prvek dostane na poslednφ mφsto atd. Tak nßm na obou okrajφch pole budou vznikat uspo°ßdanΘ ·seky. Pokud se indexy set°φd∞n²ch ·sek∙ p°ek°φ₧φ, pak je t°φd∞nφ ukonΦeno:
void Pretres(int *pPole, unsigned int dwVel)
{
unsigned int dwLevy = 1, dwPravy = dwVel - 1, dwVymena = dwVel;
int iVymena;
do
{
for(unsigned int i = dwPravy; i >= dwLevy; i--)
{
if(pPole[i-1] > pPole[i])
{
iVymena = pPole[i-1];
pPole[i-1] = pPole[i];
// vymena
pPole[i] = iVymena;
dwVymena = i; // posledni vymena
}
}
dwLevy = dwVymena + 1; // priste uz jen od posledniho vymeneneho prvku
for(i = dwLevy; i <= dwPravy; i++)
{
if(pPole[i-1] > pPole[i])
{
iVymena = pPole[i-1];
pPole[i-1] = pPole[i];
// vymena
pPole[i] = iVymena;
dwVymena = i; // posledni vymena
}
}
dwPravy = dwVymena - 1;
} while(dwLevy < dwPravy);
}
Dnes jsme se seznßmili s n∞kter²mi metodami t°φd∞nφ polφ, p°φÜt∞ si jeÜt∞ n∞kolik metod p°idßme a porovnßme algoritmy z hlediska rychlosti, podφvßme se tedy na jejich slo₧itost. TakΘ p°idßme funkci, kterß bude v set°φd∞nΘm poli vyhledßvat zadanou hodnotu. V p°φÜtφm dφlu takΘ s nejv∞tÜφ pravd∞podobnostφ zaΦneme s odvozen²mi datov²mi strukturami.
PřφÜtě nashledanou.