V minul²ch dφlech jsme se seznßmili s datov²mi strukturami zßsobnφk a fronta, kterΘ jsme implementovali staticky, tedy pomocφ pole. Pole sice bylo dynamicky alokovanΘ, ale to bylo jen z toho d∙vodu, abychom mohli urΦit dΘlku fronty. Dnes se podφvßme na poslednφ modifikaci fronty - frontu prioritnφ. Dnes takΘ zaΦneme s ·vodem k dynamickΘ struktu°e naz²vanΘ lineßrnφ spojov² seznam.
Tento druh fronty se n∞kdy takΘ oznaΦuje jako fronta s p°edbφhßnφm. Stejn∞ jako se v normßlnφm ₧ivot∞ cφtφ n∞kte°φ lidΘ d∙le₧itφ, ₧e mohou p°edbφhat, tak je tomu i u prvk∙ naÜφ datovΘ struktury. Proto do implementacφ fronty z minulΘho dφlu p°idßme dalÜφ pole, kterΘ bude udßvat prioritu prvku - pou₧ijeme pole slo₧enΘ z cel²ch Φφsel.
Nynφ stojφme p°ed problΘmem jak sprßvn∞ umφstit prvek do pole. Ud∞lßme to t°eba nßsledovn∞: pokusφme se p°idat nov² prvek, pak p∙jdeme od konce fronty (budeme uva₧ovat jednostrannou frontu) a podφvßme se do pole priorit. Ov∞°φme, zda-li je priorita vklßdanΘho prvku vyÜÜφ ne₧ priorita prvku poslednφho, pokud ano, pak posuneme poslednφ prvek na mφsto nov∞ vznikajφcφho prvku a vklßdan² prvek budeme takhle umφs¥ovat dßle. Pokud narazφme na prvek s vyÜÜφ prioritou, pak je nov∞ umφs¥ovan² prvek na sprßvnΘm mφst∞. Implementace:
#ifndef FRONTA_H
#define FRONTA_H
#include <iostream.h>
template<class T> class CPrioFronta {
private :
T *m_Pole;
int *m_Priority;
int m_Velikost; // maximalni velikost (delka) fronty
int m_Zacatek, m_Konec; // kde je zacatek a konec fronty
int m_Pocet; // pocet prvku prave se nachazejicich ve fronte
public :
CPrioFronta(int _Velikost);
~CPrioFronta();
bool Vloz(const T& _Vklad, int _iPriorita);
bool Vyjmi(T& _Vyber);
bool JePrazdna() { return ((0 == m_Pocet) ? true : false); }
bool JePlna() { return ((m_Pocet == m_Velikost) ? true : false); }
void Vypis();
};
Vidφme, ₧e deklarace t°φdy CPrioFronta je shodnß s jednoduchou frontou, jen p°ibylo navφc celoΦφselnΘ pole pro priority a u metody Vloz() pak p°ibyl parametr udßvajφcφ prioritu pro prvek ulo₧en² v poli m_Pole se stejn²m indexem. Pokud vklßdßme prvek, pak je za°azen prßv∞ podle tohoto Φφsla, pole priorit je sestupn∞ set°φd∞n²m polem.
template<class T> CPrioFronta<T>::CPrioFronta(int _Velikost)
{
m_Velikost = -1;
m_Pocet = 0;
m_Zacatek = 0;
m_Konec = -1;
// abychom v metode Vloz dostali spravny konec po prvnim vlozeni
m_Pole = new T[_Velikost];
if(m_Pole)
{
// Vytvorime pole priorit pro prvky
m_Priority = new int[_Velikost];
if(m_Priority)
{
// pokud se podarilo nastavime velikost
m_Velikost = _Velikost;
}
else
{
// jinak smazeme druhe pole
delete[] m_Pole;
}
}
}
V konstruktoru pak navφc vytvo°φme pole priorit a pokud by se nepovedlo p°id∞lit pam∞¥, pak sma₧eme i d°φve vytvo°enΘ pole pro prvky. VÜimn∞te si, ₧e zde nenφ inicializace pole priorit, vklßdßnφ funguje sprßvn∞ i bez n∞j.
template<class T> CPrioFronta<T>::~CPrioFronta()
{
if(m_Priority)
{
delete[] m_Priority;
m_Priority = NULL;
}
if(m_Pole)
{
delete[] m_Pole;
m_Pole = NULL;
m_Velikost = 0;
}
}
template<class T> bool CPrioFronta<T>::Vloz(const T& _Vklad, int _iPriorita)
{
bool bNavrat = false;
if(m_Pole && m_Priority)
{
if(!JePlna())
{
if(m_Konec == (m_Velikost - 1))
{
// pokud konec dosahne konce pole, pak koncime na prvnim prvku pole
m_Konec = 0;
}
else
{
m_Konec++;
}
// hledame misto pro novy prvek
int zarazpoz = m_Konec;
int poz;
// nasledujici promenna znaci jestli je index konce pred zacatkem, musime
overit i prazdnost fronty
bool bPrekroucena = (m_Konec < m_Zacatek);
while((zarazpoz > m_Zacatek) || bPrekroucena)
{
poz = zarazpoz - 1;
if(poz < 0)
{
poz = m_Velikost - 1;
}
if(m_Priority[poz] < _iPriorita)
{
// posuneme prvek s nizsi prioritou
m_Pole[zarazpoz] = m_Pole[poz];
m_Priority[zarazpoz] = m_Priority[poz];
// a jdeme na dalsi prvek - ovsem kdyz dosahneme zacatku,
tak preskocime na konec
if(zarazpoz == 0)
{
zarazpoz = m_Velikost - 1;
bPrekroucena = false; // uz je zacatek pred koncem
}
else
{
zarazpoz--;
}
}
else
{
break; // prerusime cyklus
}
}
// na nalezene misto ulozime novy prvek
m_Pole[zarazpoz] = _Vklad;
m_Priority[zarazpoz] = _iPriorita;
// ulozime prioritu
m_Pocet++; // pribyl prvek
bNavrat = true;
}
}
return bNavrat;
}
#endif
K≤d naleznete v sekci Downloads (projekt PrioFronta).
Destruktor je jasn², jen navφc uvolnφme pole priorit. OvÜem metoda Vloz() je upravenß. Po kontrole, zda existujφ ob∞ pole a tedy nedojde k chybnΘmu p°φstupu do pam∞ti si ov∞°φme, zda m∙₧eme do pole jeÜt∞ p°idat dalÜφ prvek. Pokud ano, zaΦneme od konce pole urΦenΘho indexem m_Konec prochßzet pole priorit a₧ k prvku, kter² je urΦen prom∞nnou m_Zacatek. OvÜem vyu₧φvßme cyklickΘho pole a proto se jednoduÜe m∙₧e stßt, ₧e pole bude p°ekroucenΘ. To znamenß, ₧e index m_Konec je menÜφ ne₧ m_Zacatek a nebyla by tak spln∞na podmφnka pro cyklus pr∙chodu polem. Prom∞nnß zarazpoz urΦuje, kam ulo₧φme nov² prvek, prom∞nnß poz pak urΦuje prvek p°edchozφ, p°iΦem₧ po prvku s indexem nula nßsleduje op∞t prvek s indexem poslednφho prvku v poli (tedy m_Velikost - 1). Pokud mß prvek na pozici poz menÜφ prioritu ne₧li prvek vklßdan², pak prvek p°esuneme z pozice poz na pozici blφ₧e ke konci naÜeho cyklickΘho pole (tedy blφ₧e k indexu m_Konec) a porovnßvßme prioritu vklßdanΘho prvku s prvkem p°edchßzejφcφm p°esunutΘmu prvku. Tak pokraΦujeme dokud nenalezneme sprßvnou pozici. Podmφnka (zarazpoz == 0) nßm °eÜφ problΘm s p°ekroucen²m polem, p°eskoΦφ ze zaΦßtku fronty na konec fronty a zruÜφ p°φznak, ₧e pole je p°ekroucenΘ. Indexy jsou pak ve sprßvnΘm po°adφ a nic nßm nebrßnφ v prozkoumßnφ zbytku pole.
Ostatnφ metody (Vyjmi() a Vypis()) jsou shodnΘ jako v p°edchozφ implementaci jednoduchΘ fronty.
Samoz°ejm∞ existujφ i jinΘ mo₧nosti implementace, m∙₧eme nap°φklad vybφrat prvky podle priority a₧ v metod∞ Vyjmi(), staΦilo by projφt neset°φd∞nΘ pole priorit a najφt prvek s nejvyÜÜφ prioritou. Potom bychom ovÜem stejn∞ museli posunout vÜechny prvky obsa₧enΘ v poli nßsledujφcφ vypuÜt∞n² prvek. Jinou mo₧nostφ je pou₧φt pro vyhledßnφ pozice algoritmu binßrnφho vyhledßvßnφ, se kter²m jsme se ji₧ seznßmili. V tomto p°φpad∞ bude pole priorit polem set°φd∞n²ch Φφsel (a¥ u₧ vzestupn∞ nebo sestupn∞), pro nalezenφ sprßvnΘ pozice. Po nalezenφ sprßvnΘ pozice bychom odsunuli vÜechny nßsledujφcφ prvky.
V tomto odstavci si bez implementace povφme o datovΘ struktu°e nazvanΘ strom. Strom lze ve specißlnφm p°φpad∞ implementovat pomocφ statickΘho pole. Je zalo₧en na tom, ₧e ka₧d² prvek, krom∞ prvnφho obsahuje odkaz na maximßln∞ n dalÜφch prvk∙, kte°φ jsou jeho nßsledovnφky. Prvnφ prvek naz²vßme ko°enem, dalÜφ pak uzly a prvky, kterΘ nemajφ ₧ßdnΘ nßsledovnφky pak listy stromu. Spojnice mezi prvky se oznaΦujφ jako v∞tve. Pokud jste n∞kdy vid∞li rodokmen, pak strom se graficky znßzor≥uje stejn∞:
My se budeme zab²vat stromem binßrnφm, tedy p°φpadem, kdy n = 2. Vyu₧ijeme toho, ₧e pro ka₧d² uzel krom∞ prvnφho platφ: pokud i je index prvku, pro kter² chceme urΦit nßsledovnφky, pak prvnφ nßsledovnφk le₧φ na pozici 2*i a druh² na 2*i + 1, jak je vid∞t z obrßzku (tyto vztahy platφ jen pro n = 2). StaΦφ tedy alokovat pole o velikosti 2n - 1, kde n udßvß v²Üku stromu (poΦet hladin stromu). V²hodou tΘto implementace je, ₧e znßme-li prvek ze stromu, pak jednoduÜe urΦφme jeho p°edch∙dce (je to prvek nachßzejφcφ se na indexu prvku vyd∞lenΘho dv∞ma). OvÜem velikou nev²hodou je pam∞¥ovß nßroΦnost, kterou odstranφme v n∞kterΘm z p°φÜtφch dφl∙ pomocφ dynamickΘ reprezentace. Pokud strom toti₧ nenφ ·pln², tedy nemß obsazeny vÜechny prvky, pak v poli zbyteΦn∞ pl²tvßme pam∞tφ.
Dnes jsme prozatφm dokonΦili datovΘ struktury vyu₧φvajφcφ pole pro uklßdßnφ prvk∙ - v n∞kterΘm z dalÜφch dφl∙ se jeÜt∞ urΦit∞ seznßmφme s haldou. V dalÜφch kapitolßch p°ejdeme na dynamickΘ struktury - prvnφ z nich bude lineßrnφ spojov² seznam, pomocφ kterΘho budeme implementovat stromy.
PřφÜtě nashledanou.
