Lineárny zoznam - História úprav

Juraj na 20:18, 16. august 2010

2010-08-16T20:18:57Z

Juraj: /* Práca s lineárnym zoznamom */

2010-07-30T12:56:28Z

Práca s lineárnym zoznamom

Juraj na 14:28, 28. marec 2010

2010-03-28T14:28:20Z

Jehro77: /* Vkladanie nového prvku do usporiadaného zoznamu */

2010-03-27T11:26:51Z

Vkladanie nového prvku do usporiadaného zoznamu

Jehro77: /* Vkladanie nového prvku do usporiadaného zoznamu */

2010-03-27T11:26:15Z

Vkladanie nového prvku do usporiadaného zoznamu

Juraj: /* Vkladanie nového prvku do usporiadaného zoznamu */

2010-03-22T21:24:05Z

Vkladanie nového prvku do usporiadaného zoznamu

Juraj na 21:22, 22. marec 2010

2010-03-22T21:22:01Z

Zobraziť rozdiely

Juraj na 21:56, 21. marec 2010

2010-03-21T21:56:42Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC {{Cvicenie|Lineárny zoznam (rieše…“

2010-03-21T18:25:35Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ {{Cvicenie|Lineárny zoznam (rieše…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
__TOC__
{{Cvicenie|Lineárny zoznam (riešené príklady)}}
'''Lineárny zoznam''' <ref>Lineární seznam - http://cs.wikipedia.org/wiki/Line%C3%A1rn%C3%AD_seznam</ref>(lineárny spojový zoznam) je dynamická dátová štruktúra, navonok podobná poľu (umožňuje uložiť viacero hodnôt, ale iným spôsobom), obsahujúca jednu alebo viacero dátových položiek (štruktúr) rovnakého typu, ktoré sú navzájom lineárne previazané vzájomnými odkazmi pomocou smerníkov alebo referencií. Aby bol zoznam lineárny, nesmú v ňom existovať cykly so vzájomnými odkazmi.

Lineárny zoznam poznáme jednosmerný a obojsmerný. V jednosmernom zozname odkazuje každá položka na nasledujúcu položku a v obojsmernom zozname odkazuje aktuálna položka na nasledujúcu ale aj predchádzajúcu položku. Definuje sa tu smerník alebo odkaz na určitý prvok zoznamu. Na konci (a začiatku) musí byť definovaná zarážka, ktorá označuje koniec zoznamu. Ak vytvoríme taký cyklus, že posledný prvok zoznamu odkazuje na prvý prvok zoznamu, dostaneme kruhový zoznam.
<gallery widths=250px>
Súbor:ll1.svg|Jednosmerný lineárny zoznam.Každý prvok zoznamu okrem svojej hodnoty obsahuje i odkaz na nasledujúci prvok v seznamu. Posledný prvok odkazuje „nikam“.
Súbor:ll2.svg|Jednosmerný kruhový zoznam. Posledný prvok zoznamu odkazuje opäť na začiatok.
Súbor:ll3.svg|Obojsmerný lineárny zoznam. Každý prvok zoznamu obsahuje, okrem svojej hodnoty, odkaz na nasledujúci i predchádzajúci prvok zoznamu
</gallery>

V nasledujúcom texte bude opisovaný '''jednosmerný lineárny zoznam'''.
==Vlastnosti lineárneho zoznamu==
*Jednosmerný lineárny zoznam je pamäťovo nenáročná dátová štruktúra
*Dovoľuje zoskupiť ľubovoľný počet prvkov. Počet prvkov je obmedzený len dostupnou pamäťovou kapacitou počítača.
*Dokáže jednoducho meniť svoju veľkosť počas behu programu.
*Prvky zoznamu, na rozdiel od polí neležia vedľa seba, ale v pamäti sú alokované podľa toho, kde je dostatok miesta.
Nasledujúci obrázok znázorňuje spôsob uloženia prvkov v pamäti pri použití poľa a lineárneho zoznamu.

[[Súbor:lz1.png|framed|center|Rozdiel medzi vnútornou štruktúrou poľa a lineárneho zoznamu]]

==Štruktúra lineárneho zozamu==
Lineárny zoznam sa skladá z určitých prvkov (alebo uzlov), ktoré sú navzájom previazané vzájomnými odkazmi. Inak povedané stavebný prvok lineárneho zoznamuje samotnú hodnotu prvku (číslo, reťazec, štruktúra, ...) a odkaz na ďalší prvok. Ešte pripomeňme, že všetky prvky lineárneho zoznamu sú rovnakého typu.

Definujme štruktúru '''TPrvok''' (záznam pracovnej povahy), ktorý bude obsahovať:
*dátovú časť (ľubovolná položka, v našom prípade celé číslo)
*ukazovateľ na na ďalší záznam typu TPrvok

Definícia v jazyku C:
<source lang="c">
struct TPrvok
{
int data;
TPrvok *dalsi;
};
</source>

Vysvetlenie:
Štruktúra TPrvok obsahuje dátovú časť označenú ako '''data'''. Odkaz na ďalší prvok je označený ako '''dalsi''', a je to smetník na štruktúru TPrvok.

V nasledujúcom príklade budú ukážky definície prvkov lineárneho zoznamu, ktorý namiesto hodnoty celého čísla obsahuje inú dátovú časť.
<source lang="c" line>
struct TPrvok
{
char retazec[64];
TPrvok *dalsi;
};
//------------------------------------
struct TPrvok
{
TZlomok data;
TPrvok *dalsi;
};
//------------------------------------
struct TPrvok
{
double data[10];
TPrvok *dalsi;
};
</source>
* riadok 1: prvok lineárneho zoznamu je reťazec o dĺžke 63 znakov
* riadok 7: prvok lineárneho zoznamu je [[Štruktúry (riešené príklady)|zlomok]]
* riadok 13: prvok lineárneho zoznamu je pole reálnych čísel o veľkosti 10.

[[Súbor:lz2.png|framed|center|Vizualizácia dátovej štruktúry TPrvok]]

Pre uloženie informácie o tom, kde má zoznam začiatok a kde končí si definujme ďalšiu štruktúru, ktorú nazveme '''TZoznam''', ktorá bude obsahovať 2 smerníky na štruktúru TPrvok. Jeden smerník ukazuje na začiatok zoznamu a druhý smerník ukazuje na koniec zoznamu.
<source lang="c">
struct TZoznam {
TPrvok *prvy;
TPrvok *posledny;
} ;
</source>
[[Súbor:lz3.png|framed|center|Vizualizácia dátovej štruktúry TZoznam]]
===Práca s lineárnym zoznamom===
Pre lineárny zoznam platí nasledovné:
*Prvky ''prvy'', ''posledny'', ''dalsi'' sú ukazovatele na '''TPrvok'''.
*Časť štruktúry TPrvok označené ako ''data'' môže byť ľubovoľný dátový typ: reťazec, štruktúra, číslo...
*Ak je zoznam prázdny informačná štruktúra TZoznam má dva ukazovatele a oba majú hodnotu NULL. Teda ukazujú "nikam".
*Ak je v zozname jeden prvok tak ukazovatele ''prvy'' a ''posledny'' (TZoznam) ukazujú ne tento prvok a ''dalsi'' (TPrvok) má hodnotu NULL.
*Ak je v zozname dva a viac prvkov tak
**smerník ''prvy'' (TZoznam) ukazuje na prvý prvok v lineárnom zozname,
**smerník ''posledny'' (TZoznam) ukazuje na posledný prvok v lineárnom zozname,
**Smerník ''dalsi'' (TPrvok) prvého prvku ukazuje na druhy prvok zoznamu a ''dalsi'' druhého prvku ukazuje na NULL.
<gallery widths=500px>
Súbor:lz4.png|Prázdny lineárny zoznam
Súbor:lz5.png|Lineárny zoznam s jedným prvkom
</gallery>
====Prechod cez lineárny zoznam====
Uvedieme psseudokód, ktorý ukazuje princíp prechodu cez všetky prvky lineárneho zoznamu.

<source lang="delphi" line>
TZoznam LinZ;
// naplnenie zoznamu datami
begin
TPrvok *pom;
pom=LinZ.prvy;
rob
begin
vypis pom->data
pom=pom->dalsi;
pokial( pom != LinZ.posledny )
end
end
</source>
Na riadku 1 si vytvoríme premennú typu TZoznam (Lineárny zoznam, ktorý udržuje informáciu o prvom a posledom prvku zoznamu). Naplnenie zoznamu je symbolicky naznačené na riadku 2. Zoznam pozostáva zo štruktúr typu smerník na TPrvok. Preto si na riadku 4 vytvárame premennú ''pom'' typu smerník na TPrvok. Pre túto premennú netreba alokovať miesto v pamäti, pretože pomocou tejto premennej budeme prechádzať po existujúcich prvkoch zoznamu. Na začiatok nastavíme premennú ''pom'' na prvý prvok zoznamu. V cykle (riadok 6) vypíšeme obsah prvku (riadok 8). Na riadku 9 je posunutie sa o jeden prvok ďalej (riadok 9). Cyklus ukončíme vtedy ak bude prvok pom zhodný z posledným prvkom zoznamu (smerní na posledný prvok zoznamu obsahuje premenná LinZ.
<source lang="c">
</source>

<source lang="c">
</source>
==Odkazy==
<references/>

← Staršia verzia		Verzia zo dňa a času 20:18, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:Informatika]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie}}		{{Skripta programovanie}}

@@ Riadok 89: / Riadok 89: @@
 **Smerník ''dalsi'' (TPrvok) prvého prvku ukazuje na druhy prvok zoznamu a ''dalsi'' druhého prvku ukazuje na NULL.
 <gallery widths=500px>
-Súbor:lz4.png|Prázdny lineárny zoznam
+Súbor:lz6.png|Prázdny lineárny zoznam
-Súbor:lz5.png|Lineárny zoznam s jedným prvkom
+Súbor:lz4.png|Lineárny zoznam s jedným prvkom
 </gallery>
 ====Prechod cez lineárny zoznam====
@@ Riadok 120: / Riadok 120: @@
 *Na riadku 9 je posunutie sa o jeden prvok ďalej.
 *Cyklus ukončíme vtedy ak bude prvok pom zhodný z posledným prvkom zoznamu (smerní na posledný prvok zoznamu obsahuje premenná LinZ.
 ==Vkladanie záznamov zo lineárneho zoznamu==
 Prvok môžeme do zoznamu vkladať dvoma spôsobmi:

@@ Riadok 153: / Riadok 153: @@
 [[Súbor:lz10.png|framed|center|Vloženie nového prvku na začiatok zoznamu]]
-Do zoznamu vkladáme nová prvok s hodnotou "20". Zistili sme že tento prvok je väčší ako posledný prvok, preto ho umiestnime na koniec zoznamu. Po vložení to bude nový posledný prvok zoznamu.
+Do zoznamu vkladáme nový prvok s hodnotou "20". Zistili sme že tento prvok je väčší ako posledný prvok, preto ho umiestnime na koniec zoznamu. Po vložení to bude nový posledný prvok zoznamu.
 [[Súbor:lz11.png|framed|center|Vloženie nového prvku na koniec zoznamu]]

@@ Riadok 149: / Riadok 149: @@
 [[Súbor:lz9.png|framed|center|Nerázdny usporiadaný lineárny zoznam]]
-Do zoznamu vkladáme nová prvok s hodnotou "-5". Zistili sme že tento prvok je menší ako prvý prvok, preto ho umiestnime na začiatok zoznamu. Po vložení to bude nový prvý prvok zoznamu.
+Do zoznamu vkladáme nový prvok s hodnotou "-5". Zistili sme že tento prvok je menší ako prvý prvok, preto ho umiestnime na začiatok zoznamu. Po vložení to bude nový prvý prvok zoznamu.
 [[Súbor:lz10.png|framed|center|Vloženie nového prvku na začiatok zoznamu]]

@@ Riadok 164: / Riadok 164: @@
 [[Súbor:lz12.png|framed|center|]]
 ==Implementácia lineárneho zoznamu v jazyku C==
 ===Dátová štruktúra opisujúca lineárny zoznam===

@@ Riadok 10: / Riadok 10: @@
 Lineárny zoznam poznáme jednosmerný a obojsmerný. V jednosmernom zozname odkazuje každá položka na nasledujúcu položku a v obojsmernom zozname odkazuje aktuálna položka na nasledujúcu ale aj predchádzajúcu položku. Definuje sa tu smerník alebo odkaz na určitý prvok zoznamu. Na konci (a začiatku) musí byť definovaná zarážka, ktorá označuje koniec zoznamu. Ak vytvoríme taký cyklus, že posledný prvok zoznamu odkazuje na prvý prvok zoznamu, dostaneme kruhový zoznam.
 <gallery widths=250px>
-Súbor:ll1.svg|Jednosmerný lineárny zoznam.Každý prvok zoznamu okrem svojej hodnoty obsahuje i odkaz na nasledujúci prvok v seznamu. Posledný prvok odkazuje „nikam“.
+Súbor:ll1.svg|Jednosmerný lineárny zoznam.Každý prvok zoznamu okrem svojej hodnoty obsahuje i odkaz na nasledujúci prvok v zozname. Posledný prvok odkazuje „nikam“.
 Súbor:ll2.svg|Jednosmerný kruhový zoznam. Posledný prvok zoznamu odkazuje opäť na začiatok.
 Súbor:ll3.svg|Obojsmerný lineárny zoznam. Každý prvok zoznamu obsahuje, okrem svojej hodnoty, odkaz na nasledujúci i predchádzajúci prvok zoznamu

@@ Riadok 109: / Riadok 109: @@
 end
 </source>
-Na riadku 1 si vytvoríme premennú typu TZoznam (Lineárny zoznam, ktorý udržuje informáciu o prvom a posledom prvku zoznamu). Naplnenie zoznamu je symbolicky naznačené na riadku 2. Zoznam pozostáva zo štruktúr typu smerník na TPrvok. Preto si na riadku 4 vytvárame premennú ''pom'' typu smerník na TPrvok. Pre túto premennú netreba alokovať miesto v pamäti, pretože pomocou tejto premennej budeme prechádzať po existujúcich prvkoch zoznamu. Na začiatok nastavíme premennú ''pom'' na prvý prvok zoznamu. V cykle (riadok 6) vypíšeme obsah prvku (riadok 8). Na riadku 9 je posunutie sa o jeden prvok ďalej (riadok 9). Cyklus ukončíme vtedy ak bude prvok pom zhodný z posledným prvkom zoznamu (smerní na posledný prvok zoznamu obsahuje premenná LinZ.
 <source lang="c">
 </source>

Lineárny zoznam - História úprav

Juraj na 20:18, 16. august 2010

Juraj: /* Práca s lineárnym zoznamom */

Juraj na 14:28, 28. marec 2010

Jehro77: /* Vkladanie nového prvku do usporiadaného zoznamu */

Jehro77: /* Vkladanie nového prvku do usporiadaného zoznamu */

Juraj: /* Vkladanie nového prvku do usporiadaného zoznamu */

Juraj na 21:22, 22. marec 2010

Juraj na 21:56, 21. marec 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ {{Cvicenie|Lineárny zoznam (rieše…“

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC {{Cvicenie|Lineárny zoznam (rieše…“