Nejprve si ukážeme grafickou reprezentaci obousměrné fronty:
Vidíme, že budeme v třídě prvku spojového seznamu potřebovat jeden ukazatel navíc. Tento ukazatel bude ukazovat buď na předchůdce prvku nebo na NULL, pokud prvek bude prvním prvkem seznamu. Popřípadě bychom pro zjednodušení vyhledávání mohli implementovat obousměrný seznam se zarážkou. Jinak se zatím nic nezmění. Upravená třída prvku bude tedy vypadat následovně:
#ifndef OBOUSEZNAM_H
#define OBOUSEZNAM_H
template<class T> class CObouPrvek {
private:
T m_Data;
CPrvek<T> *m_lpDalsi;
CPrvek<T> *m_lpPredchozi;
public:
CPrvek() : m_lpDalsi(NULL), m_lpPredchozi(NULL) { }
CPrvek(const T& _Data) : m_Data(_Data), m_lpDalsi(NULL), m_lpPredchozi(NULL) { }
T VratData() const { return m_Data; }
CPrvek<T>* VratDalsi() const { return m_lpDalsi; }
CPrvek<T>* VratPredchozi() const { return m_lpPredchozi; }
void NastavDalsi(CPrvek<T> *_lpDalsi) { m_lpDalsi = _lpDalsi; }
void NastavPredchozi(CPrvek<T> *_lpPredchozi) { m_lpPredchozi = _lpPredchozi; }
void NastavData(const T& _Data) { m_Data = _Data; }
};
Nyní třída CObouSeznam, která bude obsluhovat naší obousměrnou frontu. Nejprve si ukážeme deklaraci třídy a pak budeme implementovat jednotlivé metody. Tato třída bude mít obdobné metody jako měla třída pro obsluhu jednosměrného seznamu. Vytvoříme třídu která bude mít na každé straně prvek navíc - zarážku - pomocí kterého budeme provádět vyhledávání hodnot:
template<class T> class CObouSeznam {
private:
CObouPrvek<T> *m_lpPrvni, *m_lpPosledni;
public:
CObouSeznam() : m_lpPrvni(NULL), m_lpPosledni(NULL) { }
~CObouSeznam() { if(!JePrazdny()) { SmazSeznam(); } }
bool VytvorPrazdny();
bool SmazSeznam();
bool JePrazdny();
bool VlozNaKonec(const T& _Data); // vklada na konec seznamu
bool VlozNaZacatek(const T& _Data); // vklada na zacatek seznamu
CObouPrvek<T>* Najdi(const T& _Data); // vrati ukazatel na nalezeny prvek nebo NULL
CObouPrvek<T>* NajdiBezZarazky(const T& _Data);
CObouPrvek<T>* Najdi(const T& _Data, unsigned int _k);
bool VlozZa(CObouPrvek<T>* _lpPrvek, const T& _Data);
bool VlozPred(CObouPrvek<T>* _lpPrvek, const T& _Data);
bool SmazZa(CObouPrvek<T>* _lpPrvek);
bool SmazPrvek(CObouPrvek<T>* _lpPrvek);
CObouPrvek<T>* NajdiNejmensi(CObouPrvek<T>* _lpPrvek);
void SetridVyberem();
void VypisOdZacatku();
void VypisOdKonce();
};
Metoda JePrazdny() vrací, zda je ukazatel na předchozí prvek posledního prvku (pokud tento ovšem existuje) roven prvku prvnímu. Tedy vrací, jestli naše zarážky na sebe ukazují:
template<class T> bool CObouSeznam<T>::JePrazdny()
{
bool bNavrat = true;
if(m_lpPosledni) { bNavrat = (m_lpPosledni->VratPredchozi() == m_lpPrvni); }
return bNavrat;
}
Následuje metoda, kterou musíme zavolat před použitím seznamu nebo pro novou inicializaci seznamu (například po smazání):
template<class T> bool CObouSeznam<T>::VytvorPrazdny()
{
bool bNavrat = false;
if(!JePrazdny()) // lze zavolat i pro existujici seznam, proto radeji overime i toto
{
SmazSeznam(); // smazeme puvodni seznam
}
// nova inicializace promennych
m_lpPrvni = new CObouPrvek;
if(m_lpPrvni)
{
m_lpPosledni = new CObouPrvek;
if(m_lpPosledni)
{
// NULL do predchoziho prvku da konstruktor
m_lpPrvni->NastavDalsi(m_lpPosledni);
// NULL do nasledujiciho prvku da konstruktor
m_lpPosledni->NastavPredchozi(m_lpPrvni);
bNavrat = true;
}
else
{
delete m_lpPrvni; // pokud se nevytvoril posledni, smazeme prvni
m_lpPrvni = NULL;
}
}
return bNavrat;
}
Nyní je na čase vložit do seznamu nějaké prvky. Začneme vkládáním na začátek a na konec, které je nejlehčí. Jeden z možných způsobů implementace:
template<class T> bool CObouSeznam<T>::VlozNaZacatek(const T& _Data)
{
bool bNavrat = false;
if(m_lpPrvni) // pokud je seznam inicializovan
{
CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data);
if(lpNovy)
{
lpNovy->NastavPredchozi(m_lpPrvni); // predchudcem noveho prvku je zarazka
lpNovy->NastavDalsi(m_lpPrvni->VratDalsi()); // a ukazuje na nasledujici
m_lpPrvni->VratDalsi()->NastavPredchozi(lpNovy);
m_lpPrvni->NastavDalsi(lpNovy);
bNavrat = true;
}
// novy prvek nemazeme
}
return bNavrat;
}
template<class T> bool CObouSeznam<T>::VlozNaKonec(const T& _Data)
{
bool bNavrat = false;
if(m_lpPosledni) // pokud je seznam inicializovan
{
CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data);
if(lpNovy)
{
lpNovy->NastavPredchozi(m_lpPosledni->VratPredchozi());
lpNovy->NastavDalsi(m_lpPosledni);
m_lpPosledni->VratPredchozi()->NastavDalsi(lpNovy);
m_lpPosledni->NastavPredchozi(lpNovy);
bNavrat = true;
}
}
return bNavrat;
}
Ať prvek vkládáme na začátek nebo na konec, obě zarážky vždy zůstávají na svých místech, jsou krajními prvky seznamu. Jiným způsobem implementace by mohlo být vložení dat do původní zarážky, vytvoření zarážky nové a potom samozřejmě nastavení příslušných ukazatelů. Teď si ukážeme jak vložit prvek za nějaký prvek v seznamu (to, že prvek opravdu patří do tohoto seznamu nekontrolujeme, stejně jako jsme to nedělali doposud):
template<class T> bool CObouSeznam<T>::VlozZa(CObouPrvek<T>* _lpPrvek, const T& _Data)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek)
{
CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data); // vytvorime novy prvek
if(lpNovy)
{
// naslednik prvku z parametru je naslednikem noveho
lpNovy->NastavDalsi(_lpPrvek->VratDalsi());
// prvek z parametru je predchudcem noveho prvku
lpNovy->NastavPredchozi(_lpPrvek);
// novy prvek je predchudce naslednika prvku
_lpPrvek->VratDalsi()->NastavPredchozi(lpNovy);
// novy prvek je za prvkem v parametru
_lpPrvek->NastavDalsi(lpNovy);
bNavrat = true;
}
// klasicky nesmime prvek smazat
}
return bNavrat;
}
Podobně se implementuje vkládání před prvek, je tu tedy vynecháno (najdete ho v kódu). Jediné na co je nutné dát si v obou případech pozor je pořadí přiřazení, abychom si nesmazali důležité ukazatele. Další věc, kterou je důležité si uvědomit je, že pokud vkládáme prvek, tak musíme vždy změnit čtyři ukazatele, které si řekneme u vkládání za. Slovem prvek nyní budeme rozumět prvek z argumentu funkce, tedy prvek za který se bude vkládat. Nejprve zapojíme nový prvek, ten musí mít jako předchůdce prvek, jako následníka pak následníka prvku. Poté upravíme ukazatel na předchozí prvek následníka prvku, ten musí ukazovat na nový prvek a konečně nastavíme ukazatel na následníka v prvku, ten bude ukazovat na nově vložený prvek.
Již umíme vkládat prvky do seznamu, je tedy na čase naučit se prvky mazat, nejprve se ale podíváme na smazání celého seznamu. To je naprosto shodné jako u jednosměrného seznamu, ale navíc si můžeme vybrat směr odkud budeme prvky mazat:
template<class T> bool CObouSeznam<T>::SmazSeznam()
{
bool bNavrat = false;
if(m_lpPrvni && m_lpPosledni) // pokud je seznam platny, tak ho cely smazeme ...
{
CObouPrvek<T> *lpMazany;
while(m_lpPrvni)
{
lpMazany = m_lpPrvni;
m_lpPrvni = m_lpPrvni->VratDalsi(); // posun na dalsi prvek
delete lpMazany;
}
m_lpPrvni = NULL;
m_lpPosledni = NULL;
bNavrat = true;
}
return bNavrat;
}
Tato metoda smaže kompletně celý seznam, včetně zarážek a začíná od první zarážky. Pro znovupoužití instance CObouSeznam je v této implementaci opět nutné zavolat metodu VytvorPrazdny(). Nyní mazání konkrétního prvku:
template<class T> bool CObouSeznam<T>::SmazPrvek(CObouPrvek<T>* _lpPrvek)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek)
{
_lpPrvek->VratPredchozi()->NastavDalsi(_lpPrvek->VratDalsi());
_lpPrvek->VratDalsi()->NastavPredchozi(_lpPrvek->VratPredchozi());
// Vse v poradku, muzeme prvek smazat
delete(_lpPrvek);
_lpPrvek = NULL;
bNavrat = true;
}
return bNavrat;
}
Jde tedy jen o to, vynechat prvek ze seznamu a pote ho smazat. Pro jistotu ho ještě nastavíme na NULL, aby nenastaly nějaké potíže. Zde nám stačí navázat na sebe prvek před a za vynechávaným prvkem, tedy dva ukazatele. Metody pro mazání prvku za daným prvkem, popřípadě před ním pak implementujeme velice jednoduše, právě s využitím této metody:
template<class T> bool CObouSeznam<T>::SmazZa(CObouPrvek<T>* _lpPrvek)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek) // nemuzeme mazat zarazku
{
CObouPrvek<T> *lpMazany = _lpPrvek->VratDalsi();
// zkontrolujeme jestli prvek existuje a jestli to neni zarazka
if(lpMazany && (lpMazany != m_lpPosledni))
{
bNavrat = SmazPrvek(lpMazany);
}
}
return bNavrat;
}
#endif
Metoda mazání prvku předcházejícího je pak zcela analogická.
Ostatní metody zůstávají shodné s jednosměrným lineárním spojovým seznamem. Jen si u naší implementace musíme uvědomit, že data jsou uložena až v prvku následujícím za zarážkou, resp. před ní. Tedy na místech v paměti m_lpPrvni->VratDalsi(), resp. m_lpPosledni->VratPredchozi(). Také je dobré si uvědomit, že většinu metod lze implementovat z obou stran, čehož se dá někdy s výhodou využít. Jedinou metodu, kterou jsem napsal zvlášť pro obě strany je metoda pro výpis. Tato oboustranná metoda je vhodná při tvorbě nových metod, kde potřebujeme zjistit, jestli jsme v seznamu při přiřazování ukazatelů neudělali chybu. Seznam totiž z jedné strany může být v pořádku a z druhé mohou být některé prvky vynechány nebo seznam jinak porušen. Ukážeme si tedy jen metodu najdi prvek s danou hodnotou a implementujeme ji pro hledání odzadu seznamu:
template<class T> CObouPrvek<T>* CObouSeznam<T>::Najdi(const T& _Data)
{
CObouPrvek<T> *lpNavrat = NULL; // implicitne nenalezeno
if(!JePrazdny())
{
CObouPrvek<T> *lpZkoumany = m_lpPosledni->VratPredchozi(); // zarazka nas nezajima
m_lpPrvni->NastavData(_Data); // ulozime data do zarazky
while(lpZkoumany->VratData() != _Data)
{
lpZkoumany = lpZkoumany->VratPredchozi();
}
if(lpZkoumany != m_lpPrvni)
{
lpNavrat = lpZkoumany; // nalezli jsme prvek
}
}
return lpNavrat;
}
Jen jako první zkoumaný prvek vezmeme předchůdce posledního prvku a pokud neobsahuje hledanou hodnotu, bereme předchůdce zkoumaného prvku. To děláme nejdéle tak dlouho, dokud nedosáhneme zarážky, prvku m_lpPrvni, která z definice obsahuje hledanou hodnotu. Porovnáme, zda nalezený ukazatel neukazuje na zarážku. Pokud ne, pak jsme nalezli hledaný prvek.
Obousměrný (i jednosměrný) seznam se dá zřetězit tak, že ukazatel posledního prvku bude ukazovat na první prvek a předchůdcem prvního prvku bude prvek poslední. Tak dostáváme kruhový seznam, stačila by nám tedy jen jedna zarážka a jeden ukazatel ve třídě kruhového seznamu. Takový seznam se nám může hodit při ladění (stačil by i jednosměrný), kdybychom ukládali např. 500 zpráv. Poté by se zase od začátku začaly přepisovat nejstarší uložené zprávy.
Jedinou nevýhodou obousměrného seznamu je větší paměťová náročnost, musíme uložit v každém uzlu jeden ukazatel navíc. Na druhou stranu, některé metody, např. pro vypouštění prvku se stanou jednoduššími. Složitost vložení nového prvku je u naší implementace konstantní, nezávislá na počtu prvků v seznamu. Pokud bychom si udržovali jen ukazatel na hlavu seznamu, pak bychom při vložení nového prvku museli přejít na konec seznamu - složitost by tedy byla O(n) ve všech případech. Konstantní složitost je nyní i u smazání prvku . Nemusíme totiž v případě mazání konkrétního prvku hledat jeho předchůdce, jak tomu bylo v případě jednosměrného seznamu. Složitost hledání v obousměrně zřetězeném seznamu se samozřejmě nemění a závisí na počtu prvku obsažených v seznamu - je to tedy O(n) v nejhorším případě, kdy hledaný prvek najdeme až na konci seznamu.
Příští měsíc se začneme zabývat stromy - nejprve obecnými a pak se podrobněji podíváme na binární stromy. Povíme si, co jsou to vyvážené stromy a ukážeme si jak lze procházet stromy, jakožto rekurzivními strukturami a mnoho dalšího.
Nashledanou u dalšího dílu