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