Lineární datové struktury
Seznam
Seznam
Abstraktní představa seznamu je na obr.
.
Sémantický význam
Seznam je dynamická lineární homogenní datová struktura s proměnným počtem prvků, představovaná posloupností jednotlivých prvků. Prvky seznamu jsou uspořádané. Seznam může být prázdný nebo může obsahovat prvky stejného typu. Každému prvku neprázdného seznamu, který není na konci seznamu, jednoznačně přísluší jeden další prvek a každému prvku neprázdného seznamu, který není na začátku seznamu, jednoznačně přísluší jeden předchozí prvek. Prvek seznamu, který se právě zpracovává, se nazývá běžný.
Povolené operace se seznamem:
- vytvoření prázdného seznamu (inicializace seznamu)
- vložení nového prvku do seznamu za běžný prvek
- vložení nového prvku do seznamu před běžný prvek
- vyjmutí určitého prvku do seznamu
- zpřístupnění běžného prvku seznamu
- nastavení běžného prvku na začátek nebo konec
- posunutí běžného prvku na předchozí prvek
- posunutí běžného prvku na následující prvek
- test, zda je seznam prázdný
- test zda běžný prvek je první
- test, zda běžný prvek je poslední
Implementace seznamu se provádí dvojím způsobem:
- polem
- dynamickými proměnnými propojenými ukazateli do tzv. spojového seznamu
Implementace polem
požaduje předem definovat dostatečně dlouhé pole. Tomuto poli přísluší řídící proměnné, které obsahuje index posledně obsazeného prvku pole (L), délku rezervovaného pole (M) a index běžného prvku(C). Realizace seznamu polem má řadu nevýhod. Kromě nutnosti statické rezervace zbytečně velkého pole a nutnosti přesunů prvků pole při vkládání a rušení není možné další zobecnění. Proto se obvykle seznam realizuje dynamickými proměnnými formou spojového seznamu - zřetězením.
Spojový seznam
má tyto vlastnosti:
- řídící proměnné seznamu obsahují ukazatel na první prvek seznamu (H -hlavička, head)
- řídící proměnné seznamu mohou dále obsahovat ukazatel na poslední prvek seznamu (T - patička, anglicky se používá tail, doslovně ocas) a ukazatel na právě zpracovávaný prvek seznamu (C - běžný, current)
- logicky sousední prvky nemusí být fyzicky sousední, při realizaci v paměti se používá dynamicky přidělovaná paměť, při realizaci na disku správa volných míst nebo záznamů
- každý prvek seznamu obsahuje kromě uživatelské informace ještě ukazatel na další prvek seznamu
- pokud prvek neobsahuje další ukazatel na jiný prvek seznamu, hovoříme o jednosměrném seznamu
- poslední prvek jednosměrného seznamu může obsahovat prázdný ukazatel (nil), pokud ukazuje na první prvek seznamu, hovoříme o jednosměrném cyklickém seznamu
- každý prvek seznamu může dále obsahovat ukazatel na předchozí prvek seznamu, pak hovoříme o obousměrném seznamu
- pokud poslední prvek obousměrného seznamu ukazuje na první prvek a první prvek na poslední hovoříme o cyklickém obousměrném seznamu