Spojový seznam
V programování rozlišujeme statické a dynamické datové struktury. Statické datové struktury mají po celou dobu trvání programu stejnou velikost. Dynamické datové struktury přizpůsobují svou velikost počtu uložených informací. Jejich principem je dynamické přidělování a uvolňování paměti podle požadavků běžícího programu. Jsou to například spojové seznamy nebo stromové struktury.
Obousměrný spojový seznam
Spojový seznam patří mezi dynamické datové struktury. Jedná se o lineárně uspořádané prvky (uzly), které jsou propojeny ukazateli. Pokud ukazatel neukazuje na žádný uzel, má hodnotu nullptr.
Seznam může být jednosměrný (každý uzel obsahuje ukazatel na následující prvek) nebo obousměrný (každý uzel obsahuje ukazatel na předchozí i následující uzel).
V obousměrném seznamu platí, že každý uzel v seznamu má informaci o tom, který uzel je před ním a který je za ním. První prvek seznamu nemá předchůdce a poslední prvek nemá následovníka. Jednotlivé odpovídající ukazatele potom ukazují do "prázdna", mají hodnotu nullptr.
Vstupním bodem do spojového seznamu je ukazatel na jeho první uzel, který se také nazývá hlavička (head). Prázdný spojový seznam poznáme tak, že do prázdna ukazuje už přímo jeho hlavička. Pro zefektivnění práce se seznamem můžeme ještě používat ukazatel na poslední prvek v seznamu.
Každý uzel v sobě nese datové hodnoty (například čísla, řetězce nebo jiný objekt) a ukazatele. Při vysvětlení principu práce se seznamem (přidávání, procházení, odstraňování...) se však konkrétním obsahem dat nemusíme zabývat. Je ale zřejmé, že bez datových hodnot samotný seznam nemá vůbec smysl.
Definice třídy pro uzel v obousměrném seznamu:
class Uzel {
private:
int cislo; // data
Uzel* pred; //ukazatel na predchozi uzel
Uzel* nasl; //ukazatel na nasledujici uzel
public:
Uzel();
Uzel(int c);
};
Při vytváření uzlu je nutné "vynulovat" odpovídající ukazatele. Dále je potřebné vytvořit přístupové metody (get, set), abychom zabezpečili přístup k datovým položkám pro zpracování ve spojovém seznamu.
Definice třídy pro obousměrný seznam:
class Seznam {
private:
Uzel* prvni; //ukazatel na první uzel v seznamu
public:
Seznam(); //konstruktor
~Seznam(); //destruktor
bool PridejNaZacatek(int c); //přidá uzel na začátek seznamu
void VypisSeznam() const; //vypíše všechny informace ze seznamu
};
Metody pro spojový seznam
Konstruktor: na začátku práce se spojovým seznamem je seznam prázdný:
Seznam::Seznam() {
prvni = nullptr; //inicializace spojového seznamu v konstruktoru
}
Přidání uzlu do seznamu: pokud vkládáme nový prvek do spojového seznamu, postupujeme následovně:
- alokujeme místo pro nový uzel
- naplníme datové položky - informace předáme jako parametr metody (lze nastavit zároveň s alokováním paměti např. použitím konstruktoru)
- nový uzel zařadíme do spojového seznamu nastavením ukazatelů
Nové uzly můžeme přidávat na začátek nebo na konec seznamu, případně je můžeme vkládat na určené místo uprostřed spojového seznamu. V následujícím kódu je prvek umístěn na začátek seznamu t.j. před první uzel.
// Metoda pro přidání prvku na začátek seznamu
bool Seznam::PridejNaZacatek(int c) {
Uzel* novyUzel = new Uzel(c); //alokace paměti
if (!novyUzel){ //když paměť nebyla přidělena
return false;
}
if (this->prvni == nullptr) { //když je seznam prázdný
this->prvni = novyUzel;
} else {
novyUzel->NastavNasl(this->prvni); //"zřetězení" seznamu a nového uzlu
this->prvni->NastavPred(novyUzel);
this->prvni = novyUzel;
}
return true;
}
//metody NastavNasl() a NastavPred() jsou definovány pro třídu Uzel
Výpis informací ze spojového seznamu: procházíme seznam od začátku až do konce.
// Metoda pro výpis obsahu seznamu
void Seznam::VypisSeznam() const {
Uzel* pom;
//smyčka pro procházení všech uzlů spojového seznamu
for ( pom = this->prvni; pom != nullptr; pom = pom->DejNasl()) {
cout << pom->DejCislo() << " ";
}
cout << endl;
}
//metody DejNasl() a DejCislo() jsou definovány pro třídu Uzel