Jednosměrně vázaný seznam

Vytvořte modul programu, který bude schopen uložit větší množství hodnot do pole. Předpokládejte, že pole může být i velice řídké (a mělo by tedy docházet i k jisté „kompresi“ při ukládání dat). Vyřešte odebírání prvků (se současným rušením těchto prvků – bude-li to nutné). Předpokládá se i požadavek na řazení prvků v poli podle velikosti.

Pro danou úlohu se hodí tzv. jednosměrně vázaný (lineární) seznam. Umožňuje rychlé vložení a vypuštění prvku (zvláště výhodné v setříděné variantě) bez nutnosti provádět posuvy prvků (vytvoření místa pro vkládaný prvek a posun prvků po odebrání prvku). Za to platíme paměťovým místem pro uložení „režijní“ proměnné, kterou je ukazatel na další prvek.

Napište tedy program pracující s jednosměrně vázaným seznamem (základem seznamu je struktura, která obsahuje v datové části „užitečné“ hodnoty a ukazatel na prvek stejného typu (strukturu). Tento ukazatel ukazuje na následující prvek seznamu, nebo nabývá hodnotu NULL je-li posledním prvkem.) V programu (nejlépe ve funkci) vytvořte pěti prvkový lineární seznam, hodnoty jehož prvků budou indexy pořadí v seznamu. Napište funkci, která má jeden parametr (počátek seznamu) a vytiskne indexy všech prvků v seznamu.

Nezapomeňte, že naalokované prvky musí být odalokovány.

Realizujte funkce:

Vytvoření seznamu – ve funkci, dynamicky (pomocí alokací)

Tisk seznamu – ve funkci

Zrušení seznamu – ve funkci (odalokování)

Seřazení seznamu – ve funkci podle indexů (od největšího)

Pro inspiraci jedna z možných „koster“ programu

struct LinSeznam {
// vlastní data
// ukazatel na další prvek LinSeznam
};

int Vytvor(LinSeznam ** UkNaPrvni, int počet)
{
// vytvorte pocet prvku LinSeznamu
// jako hodnoty naplňte číslem vytvoření 1 až počet
return 1; // uspech
}

void TiskniSeznam(LinSeznam *UkNaPrvni)
{
// vytisknout seznam
}

void SetridSeznam(LinSeznam **UkNaPrvni)
{

}

int ZrusSeznam(LinSeznam **UkNaPrvni)
{
// zrusi seznam
int pocet = 0;
return pocet ; // vrati pocet zrusenych
}

int main(int argc, char* argv[])
{
LinSeznam *Prvni;
Vytvor( ,5); // pokusime se vytvořit pětiprvkový seznam
TiskniSeznam( ); // předáme seznam a vytiskneme
SetridSeznam( ); // předáme seznam k seřazení
TiskniSeznam( ); // předáme seznam a vytiskneme
ZrusSeznam( ); // předáme seznam a zrušíme jeho prvky
SetridSeznam( ); // předáme seznam k seřazení
TiskniSeznam( ); // předáme seznam a vytiskneme
ZrusSeznam( ); // předáme seznam a zrušíme jeho prvky
return 0;
}

poslední úpravy 2008-10-24