O mojí osobě

Něco ke staení

Články a návody

Poezie

Odkazy

Spojové seznamy


Spojové seznamy slouží k uložení posloupnosti prvků. Protože existuje více různých druhů spojových seznamů, ukážeme si tady nejdřív to, co mají společné, a pak si pro jejich různé varianty ukážeme konkrétní vlastnosti.

Pro tvorbu spojového seznamu si nejdřív musíme vytvořit datový typ, v našem případě to bude struktura Uzel(myšleno struct v C, pascalisti použijí record, samozřejmě se používají i objekty), která bude obsahovat ukládaný prvek a ukazatel na struct Uzel. Výsledné uložení da pak bude vypadat tak, že si budeme pamatovat ukazatel na první strukturu. Ta bude obsahovat nějaký prvek a ukazatel na strukturu následující, atd., až poslední struktura v řadě bude obsahovat nullový ukazatel.

Na obrázku si ukážeme, jak si takový spoják můžeme představit (ta divnost na konci spojáku symbolizuje NULL).

Příklad spojového seznamu

Operace běžně používané na spojových seznamech jsou tři - najdi prvek, smaž prvek a přidej prvek.

Hledání prvku ve spojovém seznamu uděláme tak, že si vezmeme pomocný ukazatel, do kterého si uložíme ukazatel na začátek spojáku. Pak v cyklu budeme testovat, jestli prvek, na který ukazujeme, se rovná prvku hledanému. Jesli ano, vrátíme ukazatel, jestli ne, do ukazatele uložíme odkaz na další stukturu (je jednou z položek struktury, na kterou si právě ukazujeme). Cyklus ukončíme, pokud dojdeme na konec spojového seznamu, což poznáme tak, že odkaz na následující prvek bude obsahovat hodnotu NULL.

Vkládání prvku znamená vytvoření nové struktury Uzel, do které uložíme vkládaný prvek. Strukturu Uzel pak zatřídíme do spojového seznamu tak, že do jejího ukazatele na následující prvek uložíme odkaz na první prvek spojáku (ten si pamatujeme ve speciálním ukazateli), a do ukazatele na první prvek pak uložíme ukazatel na nově vytvořenou strukturu. Pokud máme zajištěno, že ukazatel na první strukturu obsahuje NULL, pokud je spoják prázdný, bude to fungovat spolehlivě i při vkládání prvního prvku. Protože vždy vkládáme na začátek, zajistíme si takhle, že poslení struktura odkazuje na NULL.

Mazání prvku je už trochu složitější. Problém je v tom, že nejdřív musíme prvek najít. Pokud ale použijeme funkci najdi prvek pro vyhledání prvku, budeme mít problém při jeho mazání. Při mazání totiž musíme nejen odstranit nalezenou strukturu, ale i upravit ukazatel předchozího prvku, aby ukazoval na prvek následující po prvku smazaném. Jedině tak si totiž zajistíme, že neztratíme žádná jiná data kromě těch, která odstranit chceme.

Vyřešit to můžeme třeba takhle: použijeme dva ukazatele, uzel a minuly_uzel. Prvním ukazatelem budeme postupovat jako při hledání prvku, ale než přejdeme do následujícího uzlu, tak si ukazatel na současný uzel uložím do minuly_uzel. Když pak ukazatel uzel bude ukazovat na strukturu, kterou chci smazat, tak si do ukazatele na další strukturu ve struktuře na kterou ukazuje minuly_uzel uložím strukturu následující po té rušené a pak mohu požadovanou strukturu smazat.

Tahle metoda ale vyžaduje speciální testy, jesli nechceme zrušit první prvek ve spojovém seznamu, protože pro něj by výše (nebo níže, pokud máte otočený monitor) popsaný způsob nefungoval (protože před ním není žádný předchozí uzel, kterému se mění ukazatel, ale samotný ukazatel na spojový seznam). Proto si v příkladu uvedeném na konci tohohle textu ukážeme trochu jinou metodu, která používá ukazatele na ukazatele na strukturu a nepotřebuje test pro první strukturu.


Jak jsem psal na začátku, spojových seznamů existuje více druhů, takže si tady ukážeme některé modifikace.

Obousměrný spojový seznam se liší od základní verze tím, že každý uzel kromě ukazatele na následující uzel ukazuje i na uzel předchozí. To nám umožní jednodušší pohyb po spojáku, dokonce i od konce spojáku směrem k začátku. Při vkládání a mazání prvků ale nesmíme zapomenou na modifikaci ukazatelů v obou sousedech upravovaného uzlu.

Příklad obousměrného spojového seznamu

Spojový seznam s hlavou vypadá prakticky stejně jako původní spojový seznam, ale s tím rozdílem, že na jeho začátek dáme uzel nazývaný hlava s neplatným prvkem (pro další použití pak budeme předpokládat, že podle toho prvku dokážeme poznat, jestli pracujeme s hlavou, nebo obyčejným uzlem). V této úpravě nám bude sloužit k odstranění nutnosti kontroly při mazání prvku, jestli mažeme první prvek (mazat hlavu je nepřípustné, ta se zruší až při likvidaci celé datové struktury). Tahle úprava nám ale bude užitečnější ve spojení s dalším rozšířením.

Příklad spojového seznamu s hlavou

Cyklický spojový seznam s hlavou cyklický se nazývá proto, protože poslední prvek místo toho, aby jeho ukazatel na následující prvek obsahoval hodnotu NULL, tak ukazuje zpátky na první prvek (v našem případě hlavu spojového seznamu). Při procházení spojového seznamu tak můžeme snadno procházet dokola. Vložená hlava nám pak pomůže k tomu, abychom například při hledání prvku dokázali zastavit po průchodu celého spojového seznamu (v předchozím textu jsme si dali předpoklad, že podle prvku dokážeme hlavu poznat - ve zbytku spojáku se teda takový prvek nesmí objevit).

Příklad cyklického spojového seznamu s hlavou

Setříděný spojový seznam nám může pomoci trochu zlepšit vlastnosti vyhledávání. Pokud budeme mít seznam setříděný (předpokládejme že od nejmenšího prvku k největšímu), pak při hledání prvku nám stačí procházet spoják jen tak dlouho, dokud ho nenajdeme, nebo nenarazíme na větší prvek. To nám dává trochu lepší čas, protože průměrně projdeme jen n/2 prvků (kde n je počet prvků ve spojáku). V předchozích variantách jsme průměrně procházeli n/2 prvků, když tam prvek byl a n prvků, když tam nebyl. Naopak se nám trochu ztíží přidávání prvků - musíme totiž nejdřív najít místo, kam ho zatřídit.

Výhodně se ale tato úprava dá použít v případě, kdy potřebuju ze spojáku odebírat nejmenší (případně největší) prvky. Příkladem může být program, který má nějaké úkoly, které plní v předem nastavené časy - teda třeba budík, který bude moci být nastavený na více časů, kdy má zazvonit. Když uložíme tyhle úkoly do setříděného spojáku, pak nám stačí odebírat prvky ze spojáku a provádět úkoly. Po provedení úkolu si zjistíme, kdy se má spustit další úkol, a do té doby čekáme.

Příklad setříděného spojového seznamu

To by snad na úvod stačilo, jednotlivé metody se dají různě kombinovat a nebo se používají různé jiné vylepšení (např. Round Robin používaný při plánování procesů je také založený na rozšíření spojáků). Ukážeme si tady ještě příklad kódu na nejjednodušší verzi spojových seznamů.

struct Uzel{
        int prvek;
        struct Uzel *dalsi;
        };
struct Uzel *spojak;
//ukazatel na zacatek spojaku

int vloz(int prvek)
{
struct Uzel *novy;

novy=(struct Uzel *)malloc(sizeof(struct Uzel));
if (novy==NULL) return -1;
//proste osetreni chyby

novy->prvek=prvek;
novy->dalsi=spojak;
spojak=novy;
return 0;
};

struct Uzel *najdi(int prvek)
{
struct Uzel *ukaz;
ukaz=spojak;

while (ukaz!=NULL)
        {
        if (ukaz->prvek==prvek)
                {
                //nalezeno !
                return ukaz;
                };
        ukaz=ukaz->dalsi;
        };
//nenalezeno
return NULL;
};

int smaz(int prvek)
{
struct Uzel **ukaz;
struct Uzel *pomocny;

ukaz=&spojak;

while((*ukaz)!=NULL)
//dokud neukazujeme na ukazatel obsahujici NULL
        {
        if ((*ukaz)->prvek==prvek)
                {
                pomocny=(*ukaz);
                (*ukaz)=(*ukaz)->dalsi;
                free(pomocny);
                return 0;
                };
        ukaz=&((*ukaz)->dalsi);
        };

return 1; //mazany prvek nenalezen
};



Zpět na index