Lineární spojový seznam - ih.cas.cz

1 Jan Hnilica Počítačové modelování 11

Lineární spojový seznam (úvod do dynamických datových struktur)

Jan Hnilica Počítačové modelování 11 2

Dynamické datové struktury

Definice • dynamické struktury jsou vytvářeny za běhu programu z dynamicky alokovaných proměnných

• jednotlivé prvky struktury jsou mezi sebou spojeny pomocí pointerů, struktura se může za běhu programu měnit připojováním nových prvků, nebo dealokací prvků stávajících

• technicky je prvek realizován jako nějaký složený datový typ (v C struktura – struct, v Pascalu záznam - record), který má mezi položkami jeden či více pointerů na další prvky

Poznámky k definici • dynamickou datovou strukturou se tedy nemíní např. obyčejné pole, byť by bylo dynamicky

alokované

• jazyk C umožňuje dynamickou alokaci na zásobníku a na haldě - v případě dynamických datových struktur je typicky míněna alokace na haldě, v C pomocí funkce malloc (už známe)

Výhody a nevýhody + velikost datové struktury je určována za běhu programu podle skutečných nároků

+ provázání prvků pomocí pointerů umožňuje vytvářet různě složité vazby (stromy, grafy...)

- komplikovanější pohyb ve struktuře pomocí pointerů (ve srovnání například s polem)

- kromě paměti potřebné pro uložení užitečných informací je potřeba alokovat paměť pro pointery


Lineární spojový seznam (LSS)

typedef struct prvek { char znak; // uložená hodnota struct prvek * dalsi; // pointer na další prvek seznamu } Prvek;

• nejjednodušší dynamická struktura • každý prvek obsahuje pointer na další prvek seznamu • poslední prvek má tento pointer nastaven na NULL (zakončení seznamu)

LSS budeme pro jednoduchost demonstrovat na seznamu, jehož prvky obsahují jeden znak (seznam v tomto provedení je tedy jakýsi plastický řetězec).

A

dalsi

LSS obsahující pozdrav AHOJ! vypadá takto:

Prvek * S; // počátek seznamu

S NULL H

dalsi

O

dalsi

J

dalsi

!

dalsi


Základní operace s lineárním seznamem

Prvek * P = (Prvek*) malloc(sizeof(Prvek)); // nezapomeneme přetypovat P->znak = 'a'; // nastavení informace P->dalsi = NULL; // pointer pro pořádek nastavíme na NULL

• Vytvoření (alokace) jednoho prvku

Prvek * AlokujPrvek(char z) { Prvek * P = (Prvek*) malloc(sizeof(Prvek)); P->znak = z; P->dalsi = NULL; return P; }

• Alokace jako funkce - vhodné, pokud budeme v programu vytvářet nové prvky na více místech - funkce vrací pointer na alokovaný prvek (tzn. vrací paměťovou adresu, na které prvek leží)



Prvek * VytvorSeznam() { Prvek *S, *P, *Q; S = (Prvek*)malloc(sizeof(Prvek)); // první prvek vytvoříme zvlášť S->znak = 'a'; Q = S; // pomocný pointer na aktuální konec seznamu for (char z = 'b'; z <= 'z'; z++) // další prvky vytvoříme v cyklu { P = (Prvek*)malloc(sizeof(Prvek)); // nový prvek P->znak = z; Q->dalsi = P; // připojíme ho na konec seznamu Q = P; // posuneme aktuální konec } Q->dalsi = NULL; // zakončení seznamu return S; // vracíme pointer na začátek seznamu }

• Vytvoření seznamu obsahujícího malá písmena abecedy a - z - napíšeme jako funkci vracející pointer na začátek seznamu - první prvek vytvoříme zvlášť, další prvky pak postupně připojujeme na konec seznamu



Prvek * VytvorSeznam() { Prvek *S, *P; S = NULL; // máme prázdný seznam for (char z = 'z'; z >= 'a'; z--) { P = (Prvek*)malloc(sizeof(Prvek)); // nový prvek P->znak = z; P->dalsi = S; // připojíme za něj zbytek seznamu S = P; // posuneme počátek na nový prvek } return S; // vracíme pointer na začátek seznamu }

• Jiné provedení funkce pro vytvoření seznamu - funkce bude jednodušší, pokud seznam vytváříme od konce - nové prvky připojujeme na začátek seznamu, první prvek nemusíme vytvářet zvlášť



void VypisSeznam(Prvek * S) { while (S != NULL) { printf("%c ", S->znak); // výpis aktuálního prvku S = S->dalsi; // posun na další prvek } }

• Průchod přes všechny prvky seznamu (spojený s nějakou akcí, např. s výpisem znaků) - napíšeme jako funkci, která jako parametr obdrží pointer S na začátek seznamu

Poznámka: Je potřeba si uvědomit, že pointer S na začátek seznamu byl do funkce předán hodnotou. To znamená, že se vytvořila jeho lokální kopie, se kterou si uvnitř funkce můžeme „dělat co chceme“. Pomocí tohoto pointeru (kopie) můžeme dokráčet na konec seznamu, aniž bychom tím ovlivnili hodnotu pointeru ve volající funkci.

while (S != NULL) // průchod seznamem S = S->dalsi; // posun na další prvek, k předchozímu S už se nedostaneme

Řešením by bylo vytvořit pomocný pointer na seznam: a seznam projít tímto pomocným pointerem, původní hodnota S zůstane zachována.

Prvek * P = S;

Pokud bychom následující cyklus provedli ve volající funkci, nenávratně bychom ztratili začátek seznamu:



Prvek * NajdiPosledniPrvek(Prvek * S) { if (S == NULL) return S; while (S->dalsi != NULL) S = S->dalsi; return S; }

• Nalezení posledního prvku - funkce dostává pointer na počátek seznamu S, vrací pointer na poslední prvek (tedy na prvek, jehož následník je NULL) - pokud je seznam prázdný, funkce vrací NULL

• Spojení dvou seznamů P a S

Prvek *P, *S; ... // vytvoření seznamů Prvek * Q = NajdiPosledniPrvek(P); if (Q != NULL) Q->dalsi = S; // spojení



Prvek * NajdiPrvek(Prvek * S, char z) { if (S == NULL) return S; while (S != NULL && S->znak != z) S = S->dalsi; return S; }

• Nalezení prvku obsahujícího daný znak - funkce přebírá pointer S na počátek seznamu a hledaný znak z, vrací pointer na první prvek obsahující hledaný znak - pokud znak v seznamu není nebo pokud je seznam prázdný, funkce vrací NULL

Pro podmínku v cyklu while je nezbytné zkrácené vyhodnocování výrazů, které probíhá v jazyce C. Pokud jsme dokráčeli na konec seznamu a aktuálně S == NULL, vyhodnocování podmínky končí a test S->znak != z se neprovede (pokud by se provedl, program by zhavaroval).



• Smazání prvku ze seznamu - chceme ze seznamu smazat prvek, na který ukazuje pointer P a zachovat seznam propojený:

S NULL

P

S NULL

P

Výchozí stav:

Cílový stav:

Potřebujeme tedy propojit předchůdce a následníka prvku P. Přitom je potřeba ošetřit možnost, že P ukazuje na první prvek seznamu, v tom případě se jen posune začátek seznamu (a nic se nepropojuje).



• Smazání prvku ze seznamu - funkce přebírá pointery na začátek seznamu S a na rušený prvek P - předpokládáme, že P v seznamu je (nalezli jsme ho už dříve)

Komplikace: pokud budeme rušit první prvek, musíme posunout začátek seznamu. To ale nejde provést, pokud pointer na začátek seznamu předáváme do funkce hodnotou.

void SmazPrvek(Prvek * S, Prvek * P) { while (S->dalsi != P) // nalezneme předchůdce P S = S->dalsi; S->dalsi = P->dalsi; // propojíme předchůdce a následníka P free((void*)P); // smažeme P }

Řešení 1: ve funkci nebudeme tuto variantu uvažovat, ošetříme ji před jejím voláním:

Použití funkce v programu: (ne moc hezké...)

if (P == S) // mažeme první prvek { S = S->dalsi; // posuneme začátek free((void*)P); // smažeme P } else SmazPrvek(S, P);



Řešení 2: posunutí začátku vyřešíme v samotné funkci (hezčí) => funkce musí mít možnost změnit samotný obsah pointeru na začátek seznamu => funkce přebírá pointer odkazem, tzn přebírá pointer na pointer: **S

=> dereference uvnitř funkce: *S je pointer na začátek seznamu

void SmazPrvek(Prvek ** S, Prvek * P) { if (*S == P) // mažeme první prvek *S = (*S)->dalsi; // posuneme začátek seznamu else { Prvek * Q = *S; // nalezneme předchůdce P while (Q->dalsi != P) Q = Q->dalsi; Q->dalsi = P->dalsi; // propojíme předchůdce a následníka P } free((void*)P); // smažeme P }

SmazPrvek(&S, P); // předáváme adresu pointeru na začátek seznamu

V programu:



Poznámka: při mazání prvku P nemusíme procházet seznam a hledat jeho předchůdce - smažeme následníka P (na toho se dostaneme z P), předtím ale obsah následníka zkopírujeme do prvku P - toto nelze provést pro poslední prvek seznamu (který nemá následníka)

if (P->dalsi != NULL) // pokud P není poslední { Prvek * Q = P->dalsi; // “přidržíme” si následníka *P = *Q; // zkopírování celého obsahu následníka do P free((void*)Q); // smazání následníka }

- funkce využívá toho, že na struktury můžeme aplikovat operátor přiřazení (=), který způsobí kopírování celého obsahu struktury, tedy včetně pointeru na další prvek seznamu!



• Smazání celého seznamu - je nutné projít prvek po prvku a všechny postupně smazat - pokud bychom pouze nastavili počátek na NULL, došlo by k tzv. úniku paměti (k prvkům seznamu by už nevedla žádná cesta a nešlo by uvolnit alokovanou paměť)

void SmazSeznam(Prvek * S) { Prvek * P = S; // pomocný pointer na aktuálně mazaný prvek while (S != NULL) { S = S->dalsi; // postup na další prvek free((void*)P); // smazání aktuálního prvku P = S; // posun pomocného pointeru } }

- v programu by bylo vhodné po zrušení seznamu nastavit pointer S na NULL:

SmazSeznam(S); S = NULL;



• Vložení prvku do seznamu - vložení je jednoduché, pokud máme pointer na prvek ZA který vkládáme - funkce přebírá dva pointery: P (nový prvek) a Q (prvek za který vkládáme)

void VlozPrvekZa(Prvek * P, Prvek * Q) { P->dalsi = Q->dalsi; Q->dalsi = P; }

pořadí těchto dvou operací nesmíme prohodit!

S NULL

Q

P

Výchozí stav:

Cílový stav: S NULL

Q

P



• Vložení prvku do seznamu - pokud máme pointer Q na prvek PŘED který vkládáme, můžeme:

1) projít seznamem od začátku, najít předchůdce prvku Q a vložit nový prvek za tohoto předchůdce (už umíme)

2) zapojit nový prvek za Q a vzájemně vyměnit data těchto prvků (obdobně jako u mazání) - funkce přebírá dva pointery: P (nový prvek) a Q (prvek před který vkládáme)

void VlozPrvekPred(Prvek * P, Prvek * Q) { char znak = P->znak; // uložíme si znak z P *P = *Q; // zkopírujeme veškerá data Q do P Q->znak = znak; // do Q uložíme znak z P Q->dalsi = P; // Q zapojíme před P }

void VlozPrvekPred(Prvek * P, Prvek * Q) { P->dalsi = Q->dalsi; // P zapojíme za Q Q->dalsi = P; char znak = P->znak; // vyměníme znaky P->znak = Q->znak; Q->znak = znak; }

1. varianta - zapojení prvku a výměna znaků

2. varianta - využijeme přiřazení mezi strukturami


Obousměrný lineární seznam

- každý prvek obsahuje pointery na předchůdce i následníka

typedef struct prvek { char znak; // uložená hodnota struct prvek * dalsi; // propojení dozadu struct prvek * predchozi; // propojení dopředu } Prvek;

A

dalsi S

NULL predchozi

H

dalsi

predchozi

O

dalsi

predchozi

J

dalsi

predchozi

!

dalsi

predchozi NULL

- spotřebuje více paměti na pointery, ale umožňuje procházet seznamem oběma směry - snadnější operace mazání a vkládání prvku – nemusíme procházet seznam a hledat předchůdce


Použití lineárních seznamů

Náhrada pole

• užitečné např. pokud - načítáme data a nemáme žádnou představu o jejich možném počtu - potřebujeme přidávat a mazat data a udržovat přitom pole setříděné (do LSS snadno přidáme prvky na určené místo (nebo smažeme), aniž bychom museli posouvat ostatní)

• Nevýhody LSS oproti polím - v LSS nejde přistupovat k prvkům pomocí indexů (je potřeba projít seznam od začátku a prvek vyhledat, tzn. většina operací v LSS má lineární časovou složitost O(n), kde n je počet prvků seznamu)

- spotřebujeme určitou paměť na uložení pointerů



Spravování zásobníku a fronty pomocí LSS

• LSS představují ideální způsob k naprogramování zásobníku a fronty

• nejsme omezeni délkou pole (nemusíme ošetřovat případ, kdy už pro přidání prvku není místo)

• vyhneme se problému posouvání fronty

Zásobník pomocí LSS

Prvek * Z NULL

• přidávání i odebírání na zásobníku se děje na jeho vrcholu => začátek seznamu bude vrchol, protože na začátek se dobře přidává i odebírá

• prázdný zásobník je představován hodnotou NULL, test na prázdný zásobník je samozřejmě nutné provádět při operaci odebírání prvku (nebo před ní)

vrchol zásobníku

// vytvoření prázdného zásobníku Prvek * Z = NULL;



Zásobník – operace přidání prvku

void PridejPrvek(Prvek ** Z, char znak) { Prvek * P = (Prvek*) malloc(sizeof(Prvek)); // alokace nového prvku P->znak = znak; P->dalsi = *Z; // zapojení nového prvku na vrchol *Z = P; // posunutí vrcholu }

• funkce dostává pointer Z na vrchol zásobníku (odkazem, protože ho musí změnit) a hodnotu nového prvku

PridejPrvek(&Z, znak); // předáváme adresu pointeru Z

• volání funkce v programu



Zásobník – operace odebrání prvku

char OdeberPrvek(Prvek ** Z) { char znak = (*Z)->znak; // uložíme si odebíraný znak Prvek * P = *Z; // přidržíme si aktuální vrchol *Z = (*Z)->dalsi; // posuneme vrchol free((void*)P); // smažeme starý vrchol return znak; // návrat }

• funkce opět mění pointer Z na vrchol zásobníku, takže ho dostává odkazem návratovou hodnotou je znak z vrcholu zásobníku

char odebiranyZnak; if (Z != NULL) odebiranyZnak = OdeberPrvek(&Z);

• volání funkce v programu obsahuje test na prázdný zásobník

Pozn. Test by šel zakomponovat i do funkce samotné, která by v takovém případě vracela nějaký dohodnutý chybový znak. Pak by ale musel být testován vrácený znak ve volající funkci. Jinou alternativou jsou tzv. výjimky (později).



Fronta pomocí LSS

• do fronty se na jednom konci přidávají prvky a na druhém konci se odebírají

• na začátku LSS se dobře přidává i odebírá, ale na konci LSS se špatně odebírá (musíme najít předchůdce rušeného prvku a jeho pointer na další prvek nastavit na NULL)

• => na začátku seznamu budeme odebírat, na konci přidávat => budeme si udržovat dna pointery – na odchod i na příchod z fronty

// frontu si vytvoříme jako strukturu typedef struct fronta { Prvek * odchod; Prvek * prichod; } Fronta;

NULL

Fronta.odchod Fronta.prichod

// vytvoření prázdné fronty Fronta F; F.odchod = F.prichod = NULL;



Fronta – operace přidání prvku

• funkce přebírá pointer na frontu a ukládanou hodnotu

void PridejPrvek(Fronta * F, char z) { Prvek * P = (Prvek*)malloc(sizeof(Prvek)); // vytvoříme nový prvek P->znak = z; if (F->odchod == NULL) // fronta je prázdná F->prichod = F->odchod = P; else { F->prichod->dalsi = P; // zapojíme nový prvek F->prichod = P; // posuneme konec fronty } }

• volání v programu

PridejPrvek(&F, znak);



Fronta – operace odebrání prvku

• funkce přebírá pointer na frontu, návratovou hodnotou je znak z počátku fronty

char OdeberPrvek(Fronta * F) { char z = F->odchod->znak; Prvek * P = F->odchod; if (F->odchod == F->prichod) // po odebrání bude fronta prázdná F->odchod = F->prichod = NULL; else F->odchod = F->odchod->dalsi; free((void*)P); return z; }

• volání funkce v programu

char odebiranyZnak; if (F.odchod != NULL) odebiranyZnak = OdeberPrvek(&F);

Date post:	03-Oct-2021
Category:	Documents
Upload:	others
View:	3 times
Download:	0 times

Lineární spojový seznam - ih.cas.cz

Documents