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.
