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.