Vítejte u dalšího dílu seriálu věnovaného datovým strukturám. V minulé části jsme se konečně dostali k lineárním spojovým seznamům. Naučili jsme se vytvářet prázdný seznam se zarážkou, vkládat na konec i začátek tohoto seznamu, hledat v něm prvky a to jak se zarážkou - speciálním prvkem - tak bez ní. A samozřejmě jsme si ukázali jak smazat spojový seznam. Dnes se dostaneme k metodám vkládajícím prvky do vnitřku seznamu, mazání vybraných prvků. Přeji příjemné čtení.
Nejprve si připomeneme třídu obsluhující lineární spojový seznam. Je to třída, kterou jsme vytvořili v minulém dílu a dnes k ní přidáme několik nových metod:
#ifndef LINSPOJSEZNAM_H
#define LINSPOJSEZNAM_H
template
// ...
};
template<class T> class CLinSpojSeznam {
private:
CPrvek<T> *m_lpPrvni, *m_lpPosledni;
public:
CLinSpojSeznam() : m_lpPrvni(NULL), m_lpPosledni(NULL) { }
~CLinSpojSeznam() { if(!JePrazdny()) { SmazSeznam(); } }
bool VytvorPrazdny();
bool SmazSeznam();
bool JePrazdny() { return (m_lpPrvni == m_lpPosledni); }
bool VlozNaKonec(const T& _Data); // vklada na konec seznamu
bool VlozNaZacatek(const T& _Data); // vklada na zacatek seznamu
CPrvek<T>* Najdi(const T& _Data); // vrati ukazatel na nalezeny prvek nebo NULL
CPrvek<T>* NajdiBezZarazky(const T& _Data);
CPrvek<T>* Najdi(const T& _Data, unsigned int _k);
bool VlozZa(CPrvek<T>* _lpPrvek, const T& _Data);
bool VlozPred(CPrvek
bool SmazZa(CPrvek<T>* _lpPrvek);
bool SmazPrvek(CPrvek<T>* _lpPrvek);
bool SmazPrvekNePosledni(CPrvek
CPrvek
void SetridVyberem();
void Vypis();
};
// ...
template<class T> bool VlozZa(CPrvek<T>* _lpPrvek, const T&
_Data)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek)
{
CPrvek<T> *lpNovy = new CPrvek<T>(_Data);
if(lpNovy)
{
lpNovy->NastavDalsi(_lpPrvek->VratDalsi());
_lpPrvek->NastavDalsi(lpNovy);
bNavrat = true;
}
// klasicky nesmime prvek smazat
}
return bNavrat;
}
Pokud seznam není prázdný a ukazatel na prvek, za který se má vkládat je platný, pak vloží nový prvek za tento prvek. Je třeba jen dát pozor na pořadí přiřazení ukazatelů na následovníky jednotlivých prvků. Metoda nekontroluje, zda prvek, za který chceme vkládat, opravdu leží v konkrétní instanci.
Nyní se podíváme na metodu vkládání prvku před daný prvek. Na první pohled se může zdát, že to bude velice složitá akce - budeme přeci muset nalézt předchůdce prvku před který chceme vložit a za něj přidat (pomocí metody VlozZa()) nový prvek. To by znamenalo projít seznam od začátku. My však použijeme triku, kdy nový prvek vložíme za prvek na který ukazuje parametr metody VlozPred() a pak jen prohodíme data v těchto dvou prvcích:
template<class T> bool CLinSpojSeznam<T>::VlozPred(CPrvek<T>*
_lpPrvek, const T& _Data)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek)
{
CPrvek<T> *lpNovy = new CPrvek<T>(_lpPrvek->VratData());
if(lpNovy)
{
_lpPrvek->NastavData(_Data);
// data jsou prohozena
lpNovy->NastavDalsi(_lpPrvek->VratDalsi());
_lpPrvek->NastavDalsi(lpNovy);
bNavrat = true;
}
}
return bNavrat;
}
template<class T> bool CLinSpojSeznam<T>::SmazZa(CPrvek<T>* _lpPrvek)
{
bool bNavrat = false;
if(!JePrazdny() && (_lpPrvek != m_lpPosledni) && _lpPrvek)
// nemuzeme mazat zarazku
{
CPrvek<T> *lpMazany
= _lpPrvek->VratDalsi();
if(lpMazany)
// radeji zkontrolujeme jestli tam
vubec je prvek
{
_lpPrvek->NastavDalsi(lpMazany->VratDalsi());
// vypustime mazany prvek
delete(lpMazany); // smazeme prvek
bNavrat = true;
}
}
return bNavrat;
}
Známe-li prvek předcházející mazanému prvku, je metoda velice jednoduchá. Jen si musíme dát pozor, abychom se nesnažili smazat poslední prvek seznamu, za kterým následuje zarážka - to je ošetřeno v podmínce. Nyní metoda vypuštění konkrétního prvku:
template<class T> bool CLinSpojSeznam<T>::SmazPrvek(CPrvek<T>* _lpPrvek)
{
bool bNavrat = false;
if(!JePrazdny() && _lpPrvek)
{
CPrvek<T> *lpMazany= m_lpPrvni;
CPrvek<T> *lpPredchudce
= NULL;
while(lpMazany!= _lpPrvek)
// najdeme si predchudce
{
lpPredchudce = lpMazany;
lpMazany= lpMazany->VratDalsi();
}
// nyni mame predchudce, takze
smazeme jeho naslednika
if(lpPredchudce)
{
SmazZa(lpPredchudce);
bNavrat = true;
}
}
return bNavrat;
}
Pokud chceme metodu pro vypuštění jakéhokoliv prvku ze seznamu, pak si musíme najít předchůdce. Pokud chceme mazat prvky uvnitř seznamu (tedy všechny kromě posledního), můžeme opět použít malý trik. Spočívá v tom, že přesuneme data z následovníka rušeného uzlu a smažeme prvek za prvkem který jsme chtěli smazat, samozřejmě upravíme i ukazatele:
template<class T> bool CLinSpojSeznam<T>::SmazPrvekNePosledni(CPrvek<T>*
_lpPrvek)
{
bool bNavrat = false;
if(!JePrazdny() && (_lpPrvek->VratDalsi() != m_lpPosledni) && _lpPrvek)
// nelze
mazat posledni prvek
{
CPrvek<T>* lpMazany = _lpPrvek->VratDalsi();
// budeme mazat nasledovnika
if(lpMazany)
{
_lpPrvek->NastavData(lpMazany->VratData());
// presuneme data
_lpPrvek->NastavDalsi(lpMazany->VratDalsi());
// preskocime nasledovnika prvku
delete(lpMazany);
bNavrat = true;
}
}
return bNavrat;
}
Na závěr implementace jednosměrného seznamu si ukážeme, jak lze setřídit lineární spojový seznam pomocí metody přímého výběru. K tomu budeme potřebovat pomocnou metodu, která bude vyhledávat v úseku pole nejmenší hodnotu. Pokud si vzpomeneme na algoritmus třídění přímým výběrem v poli, pak v levém úseku vzniká tříděná posloupnost a z pravého, dosud neutříděného úseku vybíráme prvky. Metoda NajdiNejmensi() tedy bude mít pouze jeden parametr, ten bude určovat od jakého prvku se má vyhledávat a vyhledávání skončí až na konci seznamu:
template<class T> CPrvek<T>* CLinSpojSeznam<T>::NajdiNejmensi(CPrvek<T>*
_lpPrvek)
{
CPrvek<T> *lpNavrat = NULL; // implicitne nenalezeno
if(!JePrazdny())
{
if(!_lpPrvek)
{
_lpPrvek = m_lpPrvni;
}
CPrvek<T> *lpZkoumany = _lpPrvek;
// prvni prvek je nejdriv nejmensi
T Data = lpZkoumany->VratData();
lpNavrat = lpZkoumany;
while(lpZkoumany != m_lpPosledni)
{
if(Data > lpZkoumany->VratData())
// pokud nalezneme mensi
{
lpNavrat = lpZkoumany; // tak jsme prozatim nalezli nejmensi prvek
Data = lpZkoumany->VratData(); // a mame novou nejmensi hodnotu
}
lpZkoumany = lpZkoumany->VratDalsi();
// posun na dalsi
}
}
return lpNavrat;
}
Pokud metodě předáme NULL, pak bude vyhledávat od prvního prvku v seznamu. Nyní už jen vlastní metodu přímého výběru:
template<class T> void CLinSpojSeznam<T>::SetridVyberem()
{
if(!JePrazdny())
{
CPrvek<T> *lpPosledni, *lpNejmensi;
// lpPosledni ukazuje na posledni jiz
zatrideny prvek
T Vymena;
lpPosledni = m_lpPrvni;
while(lpPosledni->VratDalsi() != m_lpPosledni)
{
lpNejmensi = NajdiNejmensi(lpPosledni->VratDalsi());
if(lpNejmensi && (lpNejmensi->VratData() <
lpPosledni ->VratData()))
{
Vymena =
lpPosledni ->VratData();
// prohodime data
lpPosledni ->NastavData(lpNejmensi->VratData());
lpNejmensi->NastavData(Vymena);
}
lpPosledni =
lpPosledni->VratDalsi();
}
}
}
#endif
Při třídění neprohazujeme celé prvky, ale pouze data, která obsahují. Jako další užitečná metoda by se, pokud už máme setříděný seznam, dala implementovat funkce pro vložení hodnoty na správné místo.
K realizaci obou datových struktur si plně vystačíme s jednosměrně zřetězeným seznamem. Budeme tak mít k dispozici v podstatě nekonečnou frontu a zásobník (samozřejmě s ohledem na kapacitu paměti počítače).
Nejprve se podíváme na zásobník. Stačí si uvědomit, jak správně zřetězit prvky, aby operace byly co nejjednodušší. Víme, že vkládat prvky na začátek i konec seznamu není problém (pokud si pamatujeme ukazatel na poslední prvek) a vypuštění prvku ze začátku seznamu je také jednoduchá operace. Proto vrchol zásobníku bude prvním prvkem seznamu. Připomeneme si, že vrchol zásobníku je přesně to místo, kde v zásobníku mohou probíhat vkládací a vypouštěcí operace.
U fronty pak zvolíme uspořádání tak, aby její začátek (odkud prvky odebíráme) byl prvním prvkem seznamu a konec fronty (kam prvky vkládáme) bude koncem seznamu. Nemusíme tak vypouštět poslední prvek, což by znamenalo najít vždy předchůdce posledního prvku. V normálním životě, např. u lékaře, fronta funguje tak, že si každý pamatuje člověka, za kterým půjde na řadu. Pokud frontu naprogramujeme tak, jak jsme si uvedli, bude to obráceně, každý prvek si bude pamatovat svého následovníka. Pro nižší časovou náročnost vkládání prvku si pak budeme navíc pamatovat i ukazatel na poslední prvek fronty (ostatně to už jsme dělali u našeho seznamu). Není to sice nutné, ale jinak bychom museli projít celý seznam od začátku při každém vkládání.
Dnes jsme ukončili implementaci třídy obsluhující jednosměrný lineární spojový seznam a pověděli jsme si o tom, jak vytvořit nekonečně dlouhou frontu a zásobník. V příštím pokračování se budeme věnovat obousměrnému seznamu.
Příště nashledanou.