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.

K realizaci použijte lineární seznam a pro něj napište 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)

Pozn.:

Při programování je často nutné udržovat větší množství dat. Jedním z možných přístupů je použití pole (spojitá část buněk v paměti). Výhodou pole je, že se v něm snadno manipuluje (náhodný přístup), snadno se přidává a ubírá poslední prvek, Jeho nevýhodou je, potřebujeme-li prvek vložit/vybrat uprostřed pole. Tato činnost je časově náročná z důvodu nutnosti přeskládat prvky za použitou pozicí.

Druhou skupinou pro ukládání dat jsou přístupy založené na struktuře, která obsahuje dvě části – datovou a „vazební“. V datové části se nacházejí data, vazební část zajišťuje propojení jednotlivých struktur, která je realizovaná pomocí ukazatelů (jeden, dva ...). Výhodou je snadné vkládání a vybírání prvků, které se skládá pouze s přesunu ukazatelů, nevýhodou je sekvenční přístup k prvkům a vyšší datová náročnost (pomocné ukazatele). Výhodou je množství realizovatelných prvků ((oboustranný) seznam, LIFO, FIFO, stromy, pole …).

Pro danou úlohu se tedy hodí 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.

Je tedy nutné napsat 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 pro vazbu 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.) Důležité je vyřešení uložení informace o počátku seznamu, která je vstupem do všech funkcí (důkladně promyslete).

Krok 0: založte si nový projekt – zdrojový soubor projektu (funkce main, volající funkci test ve které budou volány následující funkce), zdrojový a hlavičkový soubor seznamu.
Krok 1: nadefinujte strukturu seznamu a vytvořte její proměnnou (definice struktury bude v *.h souboru, proměnná v main, je nutné zajistit nulování=inicializaci)
Krok 2: napište funkci pro přidání prvku na konec seznamu (přidejte do seznamu 20 prvků s hodnotami 1 až 20)
Krok 3: napište funkci pro zrušení seznamu (zavolejte 2krát po sobě, poté opět proveďte přidání prvků jako v kroku 2. (Tím se zjistí, zda je ošetřeno vícenásobné odalokování, a zda po odalokování je možné seznam znovu použít)
Krok 4: napište funkci pro tisk seznamu (vytiskněte seznam)
Útržek kódu této funkce by mohl vypadat například takto:
akt = pocatek;
while (akt != NULL) {
printf(“%f “, akt->data);
akt = akt->dalsi;
}

Krok 5: napište funkci pro seřazení prvků seznamu od největšího po nejmenší.
Krok 6: napište funkci pro zařazení prvku na danou pozici (zařaďte prvek s hodnotou 100 na 14-tou pozici, vytiskněte, zařaďte prvek s hodnotou 200 na pozici 21,-1, 0 a 200, vytiskněte). Nebude-li pozice existovat, nezařazujte.
Krok 7: napište funkci pro odebrání prvku z dané pozice (odeberte prvky se stejnými čísly jako v příkladě 5 (v opačném pořadí) a vytiskněte) – prvek je odebrán ze seznamu a vrácen volající funkci.
Krok 8: Doplňte program tak aby pracoval korektně. Zkuste volání (například tisk) ihned po vytvoření proměnné Seznam a; tisk(a);

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

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

int Vytvor(LinSeznam ** UkNaPrvni, int pocet)
{
// 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 2010-10-18