Kiwiki - Príspevky používateľa [sk]

Usporiadaný lineárny zoznam (riešené príklady)

2010-04-11T17:34:34Z

Jehro77: /* Analýza riešenia */

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}

==Zadanie==
Vo vstupnom súbore máme zoznam študentov - v každom riadku sa nachádza meno, priezvisko, známka zo ZI, den, mesiac a rok narodenia. V poslednom riadku je 5 núl.

Zostavte program, ktorý zo súboru načíta všetkých študentov a vytvorí lineárny zreťazený zoznam, ktorého jednotlivé prvky budú obsahovať údaje jedného riadku. Prvky do zoznamu vkladajte tak, aby sa hneď pri vkladaní zotriedili. Triedenie bude podľa nasledujúcich požiadaviek.
#Zoznam bude utriedený podľa abecedy (od A po Z)
#Zoznam bude utriedený podľa priezviska
#ak je priezvisko rovnaké, tak budeme triediť podľa mena
#ak je meno rovnaké, tak budeme triediť podľa dátumu narodenia

Ďalej v programe budeme chcieť vyhľadať, či sa nejaký študent vyskytuje v zozname. Načítajte hľadaný reťazec a vyhľadajte daného študenta. Na toto vytvorte funkciu ''hladaj'', ktorá bude zoznam prehľadávať a nájde všetky výskyty podľa zadaného kritéria.

==Vzorový príklad==
'''Vstup'''

Nasledujúce údaje sú načítané zo súboru

Jan Mrkvicka A 4 6 1985
Ferdinand Tell C 4 12 1986
Viliam Tell F 1 1 1987
johanka Z_arku C 5 4 1238
0 0 0 0 0 0

Nasledujúci údaj je načítaný z klávesnice

Tell

'''Výstup'''
Tell Ferdinand,C , 4.12.1986
Tell Viliam, F , 1.1.1987

==Analýza riešenia==
Budeme pokračovať v predchádzajúcom príklade ([[Neusporiadaný lineárny zoznnam (riešené príklady)]]).

Pri vkladaní údajov si musíme naprogramovať porovnávaciu funkciu, pomocou ktorej budeme porovnávať záznamy (študentov) aby sme ich mohli vkladať na správne miesto. Vo funkcii ''PorovnajS(TStudent a, TStudent b)'' porovnávame dvoch študentov, podľa zadaných kritérií. Funkcia vráti 1 ak je študent a v abecednom poradí na vyššej pozícii ako b, v opačnom prípade vráti hodnotu -1. Ak sú údaje rovnaké vráti 0 .

Pri vkladaní údajov rozoznávame 3 prípady: údaje vkladáme na začiatok zoznamu, na koniec zoznamu, alebo niekde (na správne miesto) do stredu zoznamu. Pri všetkých prípadoch musíme upraviť štrukrúru TZoznam, aby ukazovatele ''prvy'' a ''posledny'' ukazovali na začiatok, resp. na koniec zoznamu. Taktiež treba správne nastaviť ukazovatele ''dalsi'' (štruktúry TPrvok) aby sa zoznam niekde neprerušil.

Pri vyhľadávaní študenta budeme zoznamom postupne prechádzať od prvého prvku až pokiaľ prvok nenájdeme. Pri úspechu vráti funkcia ukazovateľ na prvok, ktorý obsahuje hľadaného študenta:
''TPrvok* Najdi(TZoznam z, char *hladane,TPrvok *start=NULL,int podla_p=1)''. Parametrami funkcie sú: zoznam, v ktorom budeme hľadať, reťazec ''hladane'' - čo hľadáme. Podľa zadania máme vypísať všetky výskyty hľadaného reťazca. V prípade ak sú v zozname dvaja študenti s rovnakým priezviskom, funkcia nájde iba toho prvého. Aby funkcia pracovala univerzálnejšie, použijeme 3-ti parameter (Ukazovateľ na TPrvok), ktorý má význam: budeme hľadať od prvku ''start''. Posledný argument má význam: ak bude ''podla_p=1'' budeme hľadať priezvisko, ak bude'' podla_p=0'', budeme vyhľadávať podľa mena. Pri ďalšom hľadaní získame prvok ''start'' jednoducho: použijeme posledne nájdený prvok.

Pre výpis prvku môžeme použiť funkciu ''VypisPrvok(TPrvok *p)'', ktorá bude vypisovať obsah prvku p (p obsahuje štrukúru TStudent, ktorá obsahuje položky meno, priezvisko, datum a znamka_ZI)

<source lang="c">
#include <iostream.h>
#include <fstream.h>
#include <string.h>
//-----------------datove struktury-------------------//
struct datum
{ int d,m,y;
};
struct TStudent
{ char meno[32],priezvisko[32];
datum datum_narodenia;
char znamka_ZI;
};
struct TPrvok
{ TStudent student;
TPrvok *dalsi;
};
struct TZoznam
{
TPrvok *prvy, *posledny;
};

//-------------------funkcie-----------------------------//

int JePrazdny(TZoznam z)
{
return z.prvy == NULL;
}

void VlozNaKoniec(TZoznam &z,TStudent s)
{
TPrvok *novy = new TPrvok;
novy->student = s;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = novy;
else
z.posledny->dalsi = novy;
z.posledny = novy;
}
// nova funkcia !!!
int PorovnajS(TStudent a, TStudent b)
{ // podla priezviska, mena, datumu
int porovanie;
porovanie=strcmp(strlwr(a.priezvisko),strlwr(b.priezvisko));
if(porovanie!=0) return porovanie;
porovanie=strcmp(strlwr(a.meno),strlwr(b.meno));
if(porovanie!=0) return porovanie;
long da,db;
da=a.datum_narodenia.d+a.datum_narodenia.m*100+a.datum_narodenia.y*10000;
db=b.datum_narodenia.d+b.datum_narodenia.m*100+b.datum_narodenia.y*10000;
if(da>db) return 1;
if(da<db) return -1;
return 0;
}

// nova funkcia !!!
void Vloz(TZoznam &z, TStudent x) // vlozi prvok zotriedene
{
TPrvok *novy = new TPrvok;
novy->student=x;
novy->dalsi = NULL;
if (z.prvy == NULL) // prazdny zoznam
z.prvy = z.posledny = novy;
else
if ( PorovnajS(x,z.prvy->student)==-1 ) // x < z.prvy->x / treba na zaciatok zoznamu
{
novy->dalsi = z.prvy;
z.prvy = novy;
}
else
if (PorovnajS(x,z.posledny->student)==1 ) // x > z.posledny->x / treba na koniec zoznamu
{
z.posledny->dalsi = novy;
z.posledny = novy;
}
else
{
TPrvok *p1 = z.prvy, *p2 = z.prvy->dalsi;
while (PorovnajS(p2->student,x)==-1) //p2->x < x
{
p1 = p2; p2 = p2->dalsi;
}
p1->dalsi = novy;
novy->dalsi = p2;
}
}
// nova funkcia !!!
TPrvok* Najdi(TZoznam z, char *hladane,TPrvok *start=NULL,int podla_p=1)
{ // ak je posledny parameter uvedeny, bude sa hladat od toho prvku dalej
// inak sa hlada od zaciatku

TPrvok *p;
if(start==NULL)
p = z.prvy;
else
p=start->dalsi;
char hladane_pr[32];

while (p != NULL)
{ if(podla_p)
strcpy(hladane_pr,p->student.priezvisko); // aby som si nezmenil povodne priezvisko
else
strcpy(hladane_pr,p->student.meno); // aby som si nezmenil povodne priezvisko
if (strcmp(strlwr(hladane_pr),strlwr(hladane))==0) return p;
p = p->dalsi;
}
return NULL;
}

void VypisPrvok(TPrvok *p)
{
cout << p->student.priezvisko <<" "<<p->student.meno<<" ("<<p->student.znamka_ZI<<") ";
cout<<p->student.datum_narodenia.d<<". "<<p->student.datum_narodenia.m<<". ";
cout<<p->student.datum_narodenia.y<<endl;
}

void Vypis(TZoznam z)
{
if (JePrazdny(z)) return;
TPrvok *p = z.prvy;
while (p->dalsi != NULL)
{
VypisPrvok(p);
p = p->dalsi;
}
VypisPrvok(p);
}

void ZmazPosledny(TZoznam &z)
{
if (z.prvy == NULL) // prazdny zoznam
return;

TPrvok *p = z.prvy;
if (p->dalsi == NULL) // je len jeden prvok
{
delete p;
z.prvy = z.posledny = NULL;
return;
}

// najdeme predposledny prvok
while (p->dalsi->dalsi != NULL)
p = p->dalsi;
delete p->dalsi;
p->dalsi = NULL;
z.posledny = p;
}

void Zmaz(TZoznam &z)
{
while (!JePrazdny(z))
ZmazPosledny(z);
}

void Nacitaj(TStudent &s,istream &vstup)
{
vstup>>s.meno>>s.priezvisko>>s.znamka_ZI;
vstup>>s.datum_narodenia.d>>s.datum_narodenia.m>>s.datum_narodenia.y;
}
int main()
{
TZoznam zoznam;
zoznam.prvy = zoznam.posledny = NULL;
TStudent s;
int n=0;

ifstream vstup;
vstup.open("prvaci.txt");

Nacitaj(s,vstup);
Vloz(zoznam,s);
while(s.datum_narodenia.d)
{
Nacitaj(s,vstup);
if(s.datum_narodenia.d)
Vloz(zoznam,s);
n++;
}
vstup.close();
cout<<"--------vypis zoznamu--------------"<<endl;
cout<<"Pocet studentov: "<<n<<endl;;
// Vypis(zoznam);
int kriterium;
cout<<"Podla coho chces vyhladavat? meno(0)/priezvisko(1)";
cin>>kriterium;
cout<<endl<<"Zadaj retazec, ktory chces vyhladat: ";
char przv[32];
cin>>przv;

cout<<"-----------------------------"<<endl;
TPrvok *ja=Najdi(zoznam,przv,NULL,kriterium); // hladame prvy vyskyt
int pocet=0;
while(ja)
{ pocet++;
if(ja)
VypisPrvok(ja);
ja=Najdi(zoznam,przv,ja,kriterium); // hladame dalsie vyskyty od podledneho najdeneho studenta
}
cout<<"-----------------------------"<<endl;
cout<<"Pocet najdenych studentov: "<<pocet<<endl;
Zmaz(zoznam);
system("pause");
}
</source>

Usporiadaný lineárny zoznam (riešené príklady)

2010-04-11T17:34:07Z

Jehro77: /* Analýza riešenia */

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}

==Zadanie==
Vo vstupnom súbore máme zoznam študentov - v každom riadku sa nachádza meno, priezvisko, známka zo ZI, den, mesiac a rok narodenia. V poslednom riadku je 5 núl.

Zostavte program, ktorý zo súboru načíta všetkých študentov a vytvorí lineárny zreťazený zoznam, ktorého jednotlivé prvky budú obsahovať údaje jedného riadku. Prvky do zoznamu vkladajte tak, aby sa hneď pri vkladaní zotriedili. Triedenie bude podľa nasledujúcich požiadaviek.
#Zoznam bude utriedený podľa abecedy (od A po Z)
#Zoznam bude utriedený podľa priezviska
#ak je priezvisko rovnaké, tak budeme triediť podľa mena
#ak je meno rovnaké, tak budeme triediť podľa dátumu narodenia

Ďalej v programe budeme chcieť vyhľadať, či sa nejaký študent vyskytuje v zozname. Načítajte hľadaný reťazec a vyhľadajte daného študenta. Na toto vytvorte funkciu ''hladaj'', ktorá bude zoznam prehľadávať a nájde všetky výskyty podľa zadaného kritéria.

==Vzorový príklad==
'''Vstup'''

Nasledujúce údaje sú načítané zo súboru

Jan Mrkvicka A 4 6 1985
Ferdinand Tell C 4 12 1986
Viliam Tell F 1 1 1987
johanka Z_arku C 5 4 1238
0 0 0 0 0 0

Nasledujúci údaj je načítaný z klávesnice

Tell

'''Výstup'''
Tell Ferdinand,C , 4.12.1986
Tell Viliam, F , 1.1.1987

==Analýza riešenia==
Budeme pokračovať v predchádzajúcom príklade ([[Neusporiadaný lineárny zoznnam (riešené príklady)]]).

Pri vkladaní údajov si musíme naprogramovať porovnávaciu funkciu, pomocou ktorej budeme porovnávať záznamy (študentov) aby sme ich mohli vkladať na správne miesto. Vo funkcii ''PorovnajS(TStudent a, TStudent b)'' porovnávame dvoch študentov, podľa zadaných kritérií. Funkcia vráti 1 ak je študent a v abecednom poradí na vyššej pozícii ako b, v opačnom prípade vráti hodnotu -1. Ak sú údaje rovnaké vráti 0 .

Pri vkladaní údajov rozoznávame 3 prípady: údaje vkladáme na začiatok zoznamu, na koniec zoznamu, alebo niekde (na správne miesto) do stredu zoznamu. Pri všetkých prípadoch musíme upraviť štrukrúru TZoznam, aby ukazovatele ''prvy'' a ''posledny'' ukazovali na začiatok, resp. na koniec zoznamu. Taktiež treba správne nastaviť ukazovatele ''dalsi'' (štruktúry TPrvok) aby sa zoznam niekde neprerušil.

Pri vyhľadávaní študenta budeme zoznamom postupne prechádzať od prvého prvku až pokiaľ prvok nenájdeme. Pri úspechu vráti funkcia ukazovateľ na prvok, ktorý obsahuje hľadaného študenta:
''TPrvok* Najdi(TZoznam z, char *hladane,TPrvok *start=NULL,int podla_p=1)''. Parametrami funkcie sú: zoznam, v ktorom budeme hľadať, reťazec ''hladane'' - čo hľadáme. Podľa zadania máme vypísať všetky výskyty hľadaného reťazca. V prípade ak sú v zozname dvaja študenti s rovnakým priezviskom, funkcia nájde iba toho prvého. Aby funkcia pracovala univerzálnejšie, použijeme 3-ti parameter (Ukazovateľ na TPrvok), ktorý má význam: budeme hľadať od prvku ''start''. Posledný argument má význam: ak bude ''podla_p=1'' budeme hľadať priezvisko, ak bude'' podla_p=0'', budeme vyhľadávať podľa mena. Pri ďalšom hľadaní získame prvok ''start'' jednoducho: použijeme posledne nájdený prvok.

Pre výpis prvku môžeme použiť funkciu ''VypisPrvok(TPrvok *p)'', ktorá bude vypisovať obsah prvku p (p obsahuje štrukúru TStudent, ktorá obsahuje položky meno, priezvisko, dátum a znamka_ZI)

<source lang="c">
#include <iostream.h>
#include <fstream.h>
#include <string.h>
//-----------------datove struktury-------------------//
struct datum
{ int d,m,y;
};
struct TStudent
{ char meno[32],priezvisko[32];
datum datum_narodenia;
char znamka_ZI;
};
struct TPrvok
{ TStudent student;
TPrvok *dalsi;
};
struct TZoznam
{
TPrvok *prvy, *posledny;
};

//-------------------funkcie-----------------------------//

int JePrazdny(TZoznam z)
{
return z.prvy == NULL;
}

void VlozNaKoniec(TZoznam &z,TStudent s)
{
TPrvok *novy = new TPrvok;
novy->student = s;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = novy;
else
z.posledny->dalsi = novy;
z.posledny = novy;
}
// nova funkcia !!!
int PorovnajS(TStudent a, TStudent b)
{ // podla priezviska, mena, datumu
int porovanie;
porovanie=strcmp(strlwr(a.priezvisko),strlwr(b.priezvisko));
if(porovanie!=0) return porovanie;
porovanie=strcmp(strlwr(a.meno),strlwr(b.meno));
if(porovanie!=0) return porovanie;
long da,db;
da=a.datum_narodenia.d+a.datum_narodenia.m*100+a.datum_narodenia.y*10000;
db=b.datum_narodenia.d+b.datum_narodenia.m*100+b.datum_narodenia.y*10000;
if(da>db) return 1;
if(da<db) return -1;
return 0;
}

// nova funkcia !!!
void Vloz(TZoznam &z, TStudent x) // vlozi prvok zotriedene
{
TPrvok *novy = new TPrvok;
novy->student=x;
novy->dalsi = NULL;
if (z.prvy == NULL) // prazdny zoznam
z.prvy = z.posledny = novy;
else
if ( PorovnajS(x,z.prvy->student)==-1 ) // x < z.prvy->x / treba na zaciatok zoznamu
{
novy->dalsi = z.prvy;
z.prvy = novy;
}
else
if (PorovnajS(x,z.posledny->student)==1 ) // x > z.posledny->x / treba na koniec zoznamu
{
z.posledny->dalsi = novy;
z.posledny = novy;
}
else
{
TPrvok *p1 = z.prvy, *p2 = z.prvy->dalsi;
while (PorovnajS(p2->student,x)==-1) //p2->x < x
{
p1 = p2; p2 = p2->dalsi;
}
p1->dalsi = novy;
novy->dalsi = p2;
}
}
// nova funkcia !!!
TPrvok* Najdi(TZoznam z, char *hladane,TPrvok *start=NULL,int podla_p=1)
{ // ak je posledny parameter uvedeny, bude sa hladat od toho prvku dalej
// inak sa hlada od zaciatku

TPrvok *p;
if(start==NULL)
p = z.prvy;
else
p=start->dalsi;
char hladane_pr[32];

while (p != NULL)
{ if(podla_p)
strcpy(hladane_pr,p->student.priezvisko); // aby som si nezmenil povodne priezvisko
else
strcpy(hladane_pr,p->student.meno); // aby som si nezmenil povodne priezvisko
if (strcmp(strlwr(hladane_pr),strlwr(hladane))==0) return p;
p = p->dalsi;
}
return NULL;
}

void VypisPrvok(TPrvok *p)
{
cout << p->student.priezvisko <<" "<<p->student.meno<<" ("<<p->student.znamka_ZI<<") ";
cout<<p->student.datum_narodenia.d<<". "<<p->student.datum_narodenia.m<<". ";
cout<<p->student.datum_narodenia.y<<endl;
}

void Vypis(TZoznam z)
{
if (JePrazdny(z)) return;
TPrvok *p = z.prvy;
while (p->dalsi != NULL)
{
VypisPrvok(p);
p = p->dalsi;
}
VypisPrvok(p);
}

void ZmazPosledny(TZoznam &z)
{
if (z.prvy == NULL) // prazdny zoznam
return;

TPrvok *p = z.prvy;
if (p->dalsi == NULL) // je len jeden prvok
{
delete p;
z.prvy = z.posledny = NULL;
return;
}

// najdeme predposledny prvok
while (p->dalsi->dalsi != NULL)
p = p->dalsi;
delete p->dalsi;
p->dalsi = NULL;
z.posledny = p;
}

void Zmaz(TZoznam &z)
{
while (!JePrazdny(z))
ZmazPosledny(z);
}

void Nacitaj(TStudent &s,istream &vstup)
{
vstup>>s.meno>>s.priezvisko>>s.znamka_ZI;
vstup>>s.datum_narodenia.d>>s.datum_narodenia.m>>s.datum_narodenia.y;
}
int main()
{
TZoznam zoznam;
zoznam.prvy = zoznam.posledny = NULL;
TStudent s;
int n=0;

ifstream vstup;
vstup.open("prvaci.txt");

Nacitaj(s,vstup);
Vloz(zoznam,s);
while(s.datum_narodenia.d)
{
Nacitaj(s,vstup);
if(s.datum_narodenia.d)
Vloz(zoznam,s);
n++;
}
vstup.close();
cout<<"--------vypis zoznamu--------------"<<endl;
cout<<"Pocet studentov: "<<n<<endl;;
// Vypis(zoznam);
int kriterium;
cout<<"Podla coho chces vyhladavat? meno(0)/priezvisko(1)";
cin>>kriterium;
cout<<endl<<"Zadaj retazec, ktory chces vyhladat: ";
char przv[32];
cin>>przv;

cout<<"-----------------------------"<<endl;
TPrvok *ja=Najdi(zoznam,przv,NULL,kriterium); // hladame prvy vyskyt
int pocet=0;
while(ja)
{ pocet++;
if(ja)
VypisPrvok(ja);
ja=Najdi(zoznam,przv,ja,kriterium); // hladame dalsie vyskyty od podledneho najdeneho studenta
}
cout<<"-----------------------------"<<endl;
cout<<"Pocet najdenych studentov: "<<pocet<<endl;
Zmaz(zoznam);
system("pause");
}
</source>

Lineárny zoznam

2010-03-27T11:26:51Z

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

[[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>

'''Vysvetlenie uvedeného pseudokódu:'''

*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.
*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:
#Vloženie prvku na koniec (na začiatok). Vytváraný zoznam bude neusporiadaný.
#Vloženie prvku na správne miesto. V tomto prípade sa snažíme aby bol zoznam stále usporiadaný od najmenšieho (najväčšieho) prvku po najväčší (najmenší).
===Vkladanie nového prvku na koniec zoznamu===
Pri vkladaní prvku do lineárneho zoznamu musíme rozlíšiť 2 rôzne situácie
#Zoznam je prázdny
#*Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu
#Zoznam nie je prázdny.
#*Vložený prvok umiestnime na koniec zoznamu. Tento nový prvok bude zároveň posledným prvkom zoznamu.
Na nasledujúcich obrázkoch bude znázornená situácia vloženia nového prvku do prázdneho a neprázdneho zoznamu na koniec.
<gallery widths=250px>
Súbor:lz6.png|Prázdny zoznam. Do zoznamu budeme vkladať nový prvok s hodnotou "-5"
Súbor:lz7.png|Do prázdneho zoznamu sme vložili nový prvok s hodnotou "-5". Tento prvok sa stal zároveň prvým aj posledným prvkom zoznamu.
Súbor:lz8.png|Do zoznamu sme vložili nový prvok s hodnotou "20". Tento nový prvok bude posledným prvkom v zozname. Pred pridaním mal prvok "-5" smerník ''dalsi'' nastavený na hodnou NULL (pretože bol posledný). Teraz smetník ''dalsi'' prvku "-5" ukazuje na prvok "20", ktorého smerník ''dalsi'' ma hodnotu NULL.
</gallery>
===Vkladanie nového prvku do usporiadaného zoznamu===
Pri vkladaní prvku do usporiadaného lineárneho zoznamu musíme rozlíšiť nasledujúce situácie
#Zoznam je prázdny
#*Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu. Toto riešenie je rovnaké ako v predchádzajúcom príklade.
#Zoznam nie je prázdny.
##Nový prvok je menší ako prvý prvok.
##Nový prvok je väčší ako posledný prvok.
##Nový prvok treba umiestniť na správne miesto v zozname.
Na nasledujúcich obrázkoch bude znázornené jednotlivé prípady.
Budeme vychádzať z neprázdneho zoznamu z nasledujúceho obrázka.

[[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.

[[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.

[[Súbor:lz11.png|framed|center|Vloženie nového prvku na koniec zoznamu]]

Do zoznamu vkladáme nová prvok s hodnotou "5". Zistili sme že tento prvok treba umiestniť na správne miesto v zozname. Po nájdení správneho miesta (medzi prvky 0 a 10) ho medzi tieto prvky vložíme. Prvky medzi ktoré budeme nový prvok vkladať si označme ako ''lavy'' a ''pravy''. Postupnosť operácií, ktoré musíme urobiť je na nasledujúcom obrázku:
#Smerník ''dalsi'' nového prvku nastavíme na prvok ''pravy''
#Zmažeme smerník ''dalsi'', ktorý ukazuje z prvku ''lavy'' na ''pravy''.
#Smerník ''dalsi'' prvku ''lavy'' nastavíme tak, aby ukazoval na nový prvok.

[[Súbor:lz12.png|framed|center|]]

==Implementácia lineárneho zoznamu v jazyku C==
===Dátová štruktúra opisujúca lineárny zoznam===
<source lang="c">
struct TPrvok
{
int data;
TPrvok *dalsi;
};

struct TZoznam {
TPrvok *prvy;
TPrvok *posledny;
} ;
</source>
===Vloženie prvku na koniec zoznamu===
Vo funkcii Vloz_k budeme do zoznamu vkladať nový prvok na koniec zoznamu.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Do zoznamu budeme vkladať nový prvok, ktorého hodnota je definované vo vstupnom parametri x. Keďže sa zoznam skladá iba zo smerníkov na štruktúru TPrvok, je potrebné si vytvoriť (a alokovať miesto) smerník (riadok 3) na štruktúru TPrvok. Do tejto štruktúry je potom treba nastaviť hodnotu x (riadok 4). Premenná ''novy'' reprezentuje prvok, ktorý budeme do zoznamu vkladať.
Ak je zoznam ''z'' prázdny, tak novo vložený prvok bude zároveň prvým aj posledným prvkom zoznamu (riadok 8 a 11). Ak v zozname ''z'' existuje nejaký prvok, tak teba nový prvok vložiť na koniec zoznamu. Poradie operácií, ktoré treba urobiť je:
#Hodnota smerníku ''dalsi'' posledného prvku zoznamu je NULL. Po pridaní nového prvku bude mať tento smerník <nowiki>z.posledny->dalsi</nowiki> hodnotu adresy nového prvku (riadok 10)
#Po pridaní nového prvku na koniec treba upraviť smerník ''posledny'' (''z.posledny'') zoznamu z: posledný prvok je v skutočnosti novo vložený prvok (riadok 11).
<source lang="c" line>
void Vloz_k(TZoznam &z, int x) // vlozi prvok na koniec
{ // vlozime novy prvok, ktory ma hodnotu x
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = novy;
else
z.posledny->dalsi = novy;
z.posledny = novy;
}
</source>
===Vloženie prvku na začiatok zoznamu===
Vo funkcii Vloz_z budeme do zoznamu vkladať nový prvok na začiatok zoznamu.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Význam riadkov 3 až 5 je rovnaký ako v predchádzajúcej funkcii.
Ak je zoznam ''z'' prázdny, tak novo vložený prvok bude zároveň prvým aj posledným prvkom zoznamu (riadok 8 a 11). Ak v zozname ''z'' existuje nejaký prvok, tak teba nový prvok vložiť na začiatok zoznamu. Poradie operácií, ktoré treba urobiť je:
#Hodnota smerníku ''dalsi'' vkladaného prvku zoznamu je NULL (riadok 5). Po pridaní nového prvku bude hodnota jeho smerníka ''dalsi'' obsahovať adresu prvku, ktorý bol pred vložením prvý (riadok 10)
#Po pridaní nového prvku na začiatok treba upraviť smerník ''prvy'' (''z.prvy'') zoznamu z: prvý prvok je v skutočnosti novo vložený prvok (riadok 11).
<source lang="c" line>
void Vloz_z(TZoznam &z, int x)
{ // vlozime novy prvok, ktory ma hodnotu x
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.posledny = novy;
else
novy->dalsi=z.prvy
z.prvy = novy;
}
</source>
===Vloženie prvku do usporiadaného zoznamu===
Vo funkcii Vloz budeme do zoznamu vkladať nový prvok do zoznamu na také miesto, aby bol zoznam stále usporiadaný.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Princíp vkladania vkladania nového prvku je opísaný v kapitole [[#Vkladanie nového prvku do usporiadaného zoznamu]]. V nasledujúcom texte bude vysvetlená len implementácia v jazyku C.
*riadok 7-8 : vkladanie do prázdneho zoznamu
*riadok 9-30 : vkladanie do neprázdneho zoznamu
**riadok 10: hodnota x <nowiki><</nowiki> hodnota prvého prvku zoznamu. Nový prvok bude vložený na začiatok zoznamu.
**riadok 16-20: hodnota x <nowiki>></nowiki> hodnota posledného prvku zoznamu. Nový prvok bude vložený na koniec zoznamu.
**riadok 21-30: hodnota x menšia hodnota prvého prvku a zároveň menšia ako hodnota posledného prvku
***riadok 23: 2 pomocné smerníky p1 a p2. p1 ukazuje na prvý prvok (''p1=z.prvy''), p2 ukazuje na druhý prvok zoznamu (''p2=z.prvy-<nowiki>></nowiki>dalsi'')
***riadok 24: v cykle while hľadáme také miesto kde neplatí, že hodnota x je väčšia ako hodnota prvku p2. V prípade, ak platí že <nowiki>x>p2->data</nowiki>, tak smerníky p1 a p2 posunieme o jedno miesto z zozname ďalej (riadok 25 a 26).
*** Po skončení cyklu while platí že hodnota prvku x je menšia ako hodnota dátovej časti prvku p2. Našli sme teda miesto, kde budeme prvok ''novy'' vkladať. Nový prvok vložíme medzi prvky p1 a p2.
*** riadok 28-29: vloženie nového prvku medzi prvky p1 a p2.
<source lang="c" line>
void Vloz(TZoznam &z, int x) // vlozi prvok zotriedene
{
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = z.posledny = novy;
else // v zozname je nejaky prvok
if (x < z.prvy->data) // ak je x < ako hodnota prveho
{ // prvku vlozim novy prvok na zaciatok
novy->dalsi = z.prvy;
z.prvy = novy;
}
else
if (x > z.posledny->data) // x > ako posledny prvok zoznamu
{
z.posledny->dalsi = novy;
z.posledny = novy;
}
else // vlozenie niekde do stredu zoznamu
{
TPrvok *p1 = z.prvy, *p2 = z.prvy->dalsi;
while (p2->data < x) // hladame miesto, kde vlozime prvok
{ p1 = p2;
p2 = p2->dalsi; // posun o jeden prvok
}
p1->dalsi = novy; // vlozenie noveho zaznamu
novy->dalsi = p2; // na spravne miesto
}
}
</source>
===Vyhľadanie prvku v lineárnom zozname===
Vo funkcii ''hladaj'' budeme v zozname hľadať prvok s danou hodnotou.

Parametre funkcie:
* TZoznam z - lineárny zoznam, v ktorom budeme vyhľadávať
* int x - hodnota, ktorú budeme v zozname ''z'' hľadať.

Návratová hodnota: V prípade úspechu smerník na nájdený prvok. V prípade neúspechu NULL.

Princíp funkcie o opísaný v kapitole [[#Prechod cez lineárny zoznam|Prechod cez lineárny zoznam]].
<source lang="c">
TPrvok* hladaj(TZoznam z, int x)
{
TPrvok *p = z.prvy; // pomocny prvok typu TPrvok
while (p != NULL) // opakuj, pokial neprides na koniec zoznamu
{
if (p->data == x) return p; // ak sa prvok nasiel
p = p->dalsi; // chod na dalsi prvok zoznamu
}
return NULL; // ak si nic nenasiel, vrat 0
}
</source>
===Výpis prvkov lineárneho zoznamu===
Vo funkcii ''vypis'' budeme vypisovať postupne všetky prvku lineárneho zoznamu.

Parametre funkcie:
* TZoznam z - lineárny zoznam, ktorého prvky budeme vypisovať

Návratová hodnota: žiadna

Princíp funkcie o opísaný v kapitole [[#Prechod cez lineárny zoznam|Prechod cez lineárny zoznam]].
<source lang="c">
int JePrazdny(TZoznam z)
{ // ak je zoznam prazdny, funkcia vrati 1, inak 0
return z.prvy == NULL;
}
void vypis(TZoznam z)
{
if (JePrazdny(z)) return; // ak je zoznam prazdny, skonci
TPrvok *p = z.prvy; // pomocny prvok typu TPrvok
while (p->dalsi != NULL) // prechádzaj cez vsetky prvky
{
cout << p->data << ", "; // vypis datovu cast prvku
p = p->dalsi; // chod na dalsi prvok
}
cout << p->data << endl; // vypis posledny prvok
}
</source>
===Zmazanie prvého prvku zoznamu===
Vo funkcii ''ZmazPrvy'' budeme mazať prvý prvok zoznamu. Po zmazaní musia mať smerníky ''prvy'' a ''posledny'' zoznamu ''z'' aktuálne hodnoty.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, v ktorom budeme mazať prvý prvok.

Návratová hodnota: žiadna

Na riadku 4 je vytvorený pomocný smerník, ktorý bude mať hodnotu prvého prvku zoznamu. Ako prvé je potrebné nastaviť smerník ''prvy'' zoznamu ''z'' (''z.prvy'') na prvok, ktorý bude po zmazaní prvého prvku zoznamu nový prvý prvok. Toto je vlastne druhý prvok zoznamu (''<nowiki>p->dalsi</nowiki>''). Na koniec (riadok 6) treba zmazať prvý prvok.
<source lang="c" line>
void ZmazPrvy(TZoznam &z)
{ if (z.prvy == NULL) // prazdny zoznam
return;
TPrvok *p=z.prvy;
z.prvy=p->dalsi;
delete p;
}
</source>

===Zmazanie posledného prvku zoznamu===
Vo funkcii ''ZmazPosledny'' budeme mazať posledný prvok zoznamu. Po zmazaní musia mať smerníky ''prvy'' a ''posledny'' zoznamu ''z'' aktuálne hodnoty.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, v ktorom budeme mazať prvý prvok.

Návratová hodnota: žiadna

*riadok 2: zoznam je prázdny. Funkcia skončí
*riadok 5: v zozname je len jeden prvok. Po jeho zmazaní bude zoznam prázdny.
*riadok 11: v zozname je viac ako 1 prvok. Po zmazaní posledného prvku bude nový posledný prvok ten, ktorý bol v pôvodnom zozname predposledný.
** Hľadanie predposledného prvku: riadok 11 a 12. Predposledný prvok je taký prvok p, pre ktorý platí:
***''<nowiki>p->dalsi</nowiki>'' je posledný prvok zoznamu. Vieme, že posledný prvok zoznamu má hodnotu smerníka dalsi NULL. Preto ak platí výraz <nowiki>p->dalsi->dalsi == NULL</nowiki>, tak potom je prvok p predposledný.
***Ak sme našli predposledný prvok, tak môžeme zmazať posledný prvok (riadok 13)
***Prvok ''p'' sa stane posledným prvkom. Posledný prvok má hodnotu smerníka ''dalsi'' NULL (riadok 14)
***Prvok ''p'' nastavíme ako posledný prvok zoznamu ''z'' (riadok 15).
<source lang="c" line>
void ZmazPosledny(TZoznam &z)
{ if (z.prvy == NULL) // prazdny zoznam
return;
TPrvok *p = z.prvy;
if (p->dalsi == NULL) // je len jeden prvok
{ delete p;
z.prvy = z.posledny= NULL; // upravime strukturu z
return;
}
// najdeme predposledny prvok
while (p->dalsi->dalsi != NULL)
p = p->dalsi;
delete p->dalsi; // zmazeme posledny
p->dalsi = NULL; // a nastavime NULL na aktualny posledny prvok
z.posledny = p; //upravime zoznam tak, aby ukazoval spravne na
} // posledny prvok
</source>
===Zmazanie lineárneho zoznamu===
Vo funkcii ''Zmaz'' budeme mazať všetky prvky zoznamu.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, ktorého prvky budeme mazať.

Návratová hodnota: žiadna

Je jedno, či budeme mazať zoznam od začiatku, alebo od konca. Implementácia mazania Zmaz2 je ale efektívnejšia pretože zložitosť funkcie ''ZmazPrvy'' je O(1) a zložitosť funkcie ''ZmazPosledny'' je O(n).
<source lang="c">
void Zmaz(TZoznam &z)
{
while (!JePrazdny(z)) // pokial je v zozname nejaky prvok
ZmazPosledny(z); // zmaze posledny prvok
}

void Zmaz2(TZoznam &z)
{
while (!JePrazdny(z)) // pokial je v zozname nejaky prvok
ZmazPrvy(z); // zmaze prvy prvok
}
</source>
===Použitie lineárneho zoznamu v programe===
<source lang="c">
void main()
{ TZoznam zoznam;
zoznam.prvy =NULL;
zoznam.posledny = NULL;
int udaj,n=4; //pocet zaznamov
for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz_z(zoznam, udaj);
}
for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz_k(zoznam, udaj);
}
vypis(zoznam);
Zmaz(zoznam);

for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz(zoznam, udaj);
}
vypis(zoznam);
Zmaz(zoznam);
</source>

==Odkazy==
<references/>

Lineárny zoznam

2010-03-27T11:26:15Z

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

[[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>

'''Vysvetlenie uvedeného pseudokódu:'''

*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.
*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:
#Vloženie prvku na koniec (na začiatok). Vytváraný zoznam bude neusporiadaný.
#Vloženie prvku na správne miesto. V tomto prípade sa snažíme aby bol zoznam stále usporiadaný od najmenšieho (najväčšieho) prvku po najväčší (najmenší).
===Vkladanie nového prvku na koniec zoznamu===
Pri vkladaní prvku do lineárneho zoznamu musíme rozlíšiť 2 rôzne situácie
#Zoznam je prázdny
#*Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu
#Zoznam nie je prázdny.
#*Vložený prvok umiestnime na koniec zoznamu. Tento nový prvok bude zároveň posledným prvkom zoznamu.
Na nasledujúcich obrázkoch bude znázornená situácia vloženia nového prvku do prázdneho a neprázdneho zoznamu na koniec.
<gallery widths=250px>
Súbor:lz6.png|Prázdny zoznam. Do zoznamu budeme vkladať nový prvok s hodnotou "-5"
Súbor:lz7.png|Do prázdneho zoznamu sme vložili nový prvok s hodnotou "-5". Tento prvok sa stal zároveň prvým aj posledným prvkom zoznamu.
Súbor:lz8.png|Do zoznamu sme vložili nový prvok s hodnotou "20". Tento nový prvok bude posledným prvkom v zozname. Pred pridaním mal prvok "-5" smerník ''dalsi'' nastavený na hodnou NULL (pretože bol posledný). Teraz smetník ''dalsi'' prvku "-5" ukazuje na prvok "20", ktorého smerník ''dalsi'' ma hodnotu NULL.
</gallery>
===Vkladanie nového prvku do usporiadaného zoznamu===
Pri vkladaní prvku do usporiadaného lineárneho zoznamu musíme rozlíšiť nasledujúce situácie
#Zoznam je prázdny
#*Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu. Toto riešenie je rovnaké ako v predchádzajúcom príklade.
#Zoznam nie je prázdny.
##Nový prvok je menší ako prvý prvok.
##Nový prvok je väčší ako posledný prvok.
##Nový prvok treba umiestniť na správne miesto v zozname.
Na nasledujúcich obrázkoch bude znázornené jednotlivé prípady.
Budeme vychádzať z neprázdneho zoznamu z nasledujúceho obrázka.

[[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.

[[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.

[[Súbor:lz11.png|framed|center|Vloženie nového prvku na koniec zoznamu]]

Do zoznamu vkladáme nová prvok s hodnotou "5". Zistili sme že tento prvok treba umiestniť na správne miesto v zozname. Po nájdení správneho miesta (medzi prvky 0 a 10) ho medzi tieto prvky vložíme. Prvky medzi ktoré budeme nový prvok vkladať si označme ako ''lavy'' a ''pravy''. Postupnosť operácií, ktoré musíme urobiť je na nasledujúcom obrázku:
#Smerník ''dalsi'' nového prvku nastavíme na prvok ''pravy''
#Zmažeme smerník ''dalsi'', ktorý ukazuje z prvku ''lavy'' na ''pravy''.
#Smerník ''dalsi'' prvku ''lavy'' nastavíme tak, aby ukazoval na nový prvok.

[[Súbor:lz12.png|framed|center|]]

==Implementácia lineárneho zoznamu v jazyku C==
===Dátová štruktúra opisujúca lineárny zoznam===
<source lang="c">
struct TPrvok
{
int data;
TPrvok *dalsi;
};

struct TZoznam {
TPrvok *prvy;
TPrvok *posledny;
} ;
</source>
===Vloženie prvku na koniec zoznamu===
Vo funkcii Vloz_k budeme do zoznamu vkladať nový prvok na koniec zoznamu.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Do zoznamu budeme vkladať nový prvok, ktorého hodnota je definované vo vstupnom parametri x. Keďže sa zoznam skladá iba zo smerníkov na štruktúru TPrvok, je potrebné si vytvoriť (a alokovať miesto) smerník (riadok 3) na štruktúru TPrvok. Do tejto štruktúry je potom treba nastaviť hodnotu x (riadok 4). Premenná ''novy'' reprezentuje prvok, ktorý budeme do zoznamu vkladať.
Ak je zoznam ''z'' prázdny, tak novo vložený prvok bude zároveň prvým aj posledným prvkom zoznamu (riadok 8 a 11). Ak v zozname ''z'' existuje nejaký prvok, tak teba nový prvok vložiť na koniec zoznamu. Poradie operácií, ktoré treba urobiť je:
#Hodnota smerníku ''dalsi'' posledného prvku zoznamu je NULL. Po pridaní nového prvku bude mať tento smerník <nowiki>z.posledny->dalsi</nowiki> hodnotu adresy nového prvku (riadok 10)
#Po pridaní nového prvku na koniec treba upraviť smerník ''posledny'' (''z.posledny'') zoznamu z: posledný prvok je v skutočnosti novo vložený prvok (riadok 11).
<source lang="c" line>
void Vloz_k(TZoznam &z, int x) // vlozi prvok na koniec
{ // vlozime novy prvok, ktory ma hodnotu x
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = novy;
else
z.posledny->dalsi = novy;
z.posledny = novy;
}
</source>
===Vloženie prvku na začiatok zoznamu===
Vo funkcii Vloz_z budeme do zoznamu vkladať nový prvok na začiatok zoznamu.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Význam riadkov 3 až 5 je rovnaký ako v predchádzajúcej funkcii.
Ak je zoznam ''z'' prázdny, tak novo vložený prvok bude zároveň prvým aj posledným prvkom zoznamu (riadok 8 a 11). Ak v zozname ''z'' existuje nejaký prvok, tak teba nový prvok vložiť na začiatok zoznamu. Poradie operácií, ktoré treba urobiť je:
#Hodnota smerníku ''dalsi'' vkladaného prvku zoznamu je NULL (riadok 5). Po pridaní nového prvku bude hodnota jeho smerníka ''dalsi'' obsahovať adresu prvku, ktorý bol pred vložením prvý (riadok 10)
#Po pridaní nového prvku na začiatok treba upraviť smerník ''prvy'' (''z.prvy'') zoznamu z: prvý prvok je v skutočnosti novo vložený prvok (riadok 11).
<source lang="c" line>
void Vloz_z(TZoznam &z, int x)
{ // vlozime novy prvok, ktory ma hodnotu x
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.posledny = novy;
else
novy->dalsi=z.prvy
z.prvy = novy;
}
</source>
===Vloženie prvku do usporiadaného zoznamu===
Vo funkcii Vloz budeme do zoznamu vkladať nový prvok do zoznamu na také miesto, aby bol zoznam stále usporiadaný.

Parametre funkcie:
*TZoznam &z - odkaz na lineárny zoznam, do ktorého vkladáme nový údaj,
* int x - hodnota, ktorú budeme do zoznamu ''z'' vkladať.

Návratová hodnota: žiadna.

Princíp vkladania vkladania nového prvku je opísaný v kapitole [[#Vkladanie nového prvku do usporiadaného zoznamu]]. V nasledujúcom texte bude vysvetlená len implementácia v jazyku C.
*riadok 7-8 : vkladanie do prázdneho zoznamu
*riadok 9-30 : vkladanie do neprázdneho zoznamu
**riadok 10: hodnota x <nowiki><</nowiki> hodnota prvého prvku zoznamu. Nový prvok bude vložený na začiatok zoznamu.
**riadok 16-20: hodnota x <nowiki>></nowiki> hodnota posledného prvku zoznamu. Nový prvok bude vložený na koniec zoznamu.
**riadok 21-30: hodnota x menšia hodnota prvého prvku a zároveň menšia ako hodnota posledného prvku
***riadok 23: 2 pomocné smerníky p1 a p2. p1 ukazuje na prvý prvok (''p1=z.prvy''), p2 ukazuje na druhý prvok zoznamu (''p2=z.prvy-<nowiki>></nowiki>dalsi'')
***riadok 24: v cykle while hľadáme také miesto kde neplatí, že hodnota x je väčšia ako hodnota prvku p2. V prípade, ak platí že <nowiki>x>p2->data</nowiki>, tak smerníky p1 a p2 posunieme o jedno miesto z zozname ďalej (riadok 25 a 26).
*** Po skončení cyklu while platí že hodnota prvku x je menšia ako hodnota dátovej časti prvku p2. Našli sme teda miesto, kde budeme prvok ''novy'' vkladať. Nový prvok vložíme medzi prvky p1 a p2.
*** riadok 28-29: vloženie nového prvku medzi prvky p1 a p2.
<source lang="c" line>
void Vloz(TZoznam &z, int x) // vlozi prvok zotriedene
{
TPrvok *novy = new TPrvok;
novy->data = x;
novy->dalsi = NULL;

if (z.prvy == NULL) // prazdny zoznam
z.prvy = z.posledny = novy;
else // v zozname je nejaky prvok
if (x < z.prvy->data) // ak je x < ako hodnota prveho
{ // prvku vlozim novy prvok na zaciatok
novy->dalsi = z.prvy;
z.prvy = novy;
}
else
if (x > z.posledny->data) // x > ako posledny prvok zoznamu
{
z.posledny->dalsi = novy;
z.posledny = novy;
}
else // vlozenie niekde do stredu zoznamu
{
TPrvok *p1 = z.prvy, *p2 = z.prvy->dalsi;
while (p2->data < x) // hladame miesto, kde vlozime prvok
{ p1 = p2;
p2 = p2->dalsi; // posun o jeden prvok
}
p1->dalsi = novy; // vlozenie noveho zaznamu
novy->dalsi = p2; // na spravne miesto
}
}
</source>
===Vyhľadanie prvku v lineárnom zozname===
Vo funkcii ''hladaj'' budeme v zozname hľadať prvok s danou hodnotou.

Parametre funkcie:
* TZoznam z - lineárny zoznam, v ktorom budeme vyhľadávať
* int x - hodnota, ktorú budeme v zozname ''z'' hľadať.

Návratová hodnota: V prípade úspechu smerník na nájdený prvok. V prípade neúspechu NULL.

Princíp funkcie o opísaný v kapitole [[#Prechod cez lineárny zoznam|Prechod cez lineárny zoznam]].
<source lang="c">
TPrvok* hladaj(TZoznam z, int x)
{
TPrvok *p = z.prvy; // pomocny prvok typu TPrvok
while (p != NULL) // opakuj, pokial neprides na koniec zoznamu
{
if (p->data == x) return p; // ak sa prvok nasiel
p = p->dalsi; // chod na dalsi prvok zoznamu
}
return NULL; // ak si nic nenasiel, vrat 0
}
</source>
===Výpis prvkov lineárneho zoznamu===
Vo funkcii ''vypis'' budeme vypisovať postupne všetky prvku lineárneho zoznamu.

Parametre funkcie:
* TZoznam z - lineárny zoznam, ktorého prvky budeme vypisovať

Návratová hodnota: žiadna

Princíp funkcie o opísaný v kapitole [[#Prechod cez lineárny zoznam|Prechod cez lineárny zoznam]].
<source lang="c">
int JePrazdny(TZoznam z)
{ // ak je zoznam prazdny, funkcia vrati 1, inak 0
return z.prvy == NULL;
}
void vypis(TZoznam z)
{
if (JePrazdny(z)) return; // ak je zoznam prazdny, skonci
TPrvok *p = z.prvy; // pomocny prvok typu TPrvok
while (p->dalsi != NULL) // prechádzaj cez vsetky prvky
{
cout << p->data << ", "; // vypis datovu cast prvku
p = p->dalsi; // chod na dalsi prvok
}
cout << p->data << endl; // vypis posledny prvok
}
</source>
===Zmazanie prvého prvku zoznamu===
Vo funkcii ''ZmazPrvy'' budeme mazať prvý prvok zoznamu. Po zmazaní musia mať smerníky ''prvy'' a ''posledny'' zoznamu ''z'' aktuálne hodnoty.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, v ktorom budeme mazať prvý prvok.

Návratová hodnota: žiadna

Na riadku 4 je vytvorený pomocný smerník, ktorý bude mať hodnotu prvého prvku zoznamu. Ako prvé je potrebné nastaviť smerník ''prvy'' zoznamu ''z'' (''z.prvy'') na prvok, ktorý bude po zmazaní prvého prvku zoznamu nový prvý prvok. Toto je vlastne druhý prvok zoznamu (''<nowiki>p->dalsi</nowiki>''). Na koniec (riadok 6) treba zmazať prvý prvok.
<source lang="c" line>
void ZmazPrvy(TZoznam &z)
{ if (z.prvy == NULL) // prazdny zoznam
return;
TPrvok *p=z.prvy;
z.prvy=p->dalsi;
delete p;
}
</source>

===Zmazanie posledného prvku zoznamu===
Vo funkcii ''ZmazPosledny'' budeme mazať posledný prvok zoznamu. Po zmazaní musia mať smerníky ''prvy'' a ''posledny'' zoznamu ''z'' aktuálne hodnoty.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, v ktorom budeme mazať prvý prvok.

Návratová hodnota: žiadna

*riadok 2: zoznam je prázdny. Funkcia skončí
*riadok 5: v zozname je len jeden prvok. Po jeho zmazaní bude zoznam prázdny.
*riadok 11: v zozname je viac ako 1 prvok. Po zmazaní posledného prvku bude nový posledný prvok ten, ktorý bol v pôvodnom zozname predposledný.
** Hľadanie predposledného prvku: riadok 11 a 12. Predposledný prvok je taký prvok p, pre ktorý platí:
***''<nowiki>p->dalsi</nowiki>'' je posledný prvok zoznamu. Vieme, že posledný prvok zoznamu má hodnotu smerníka dalsi NULL. Preto ak platí výraz <nowiki>p->dalsi->dalsi == NULL</nowiki>, tak potom je prvok p predposledný.
***Ak sme našli predposledný prvok, tak môžeme zmazať posledný prvok (riadok 13)
***Prvok ''p'' sa stane posledným prvkom. Posledný prvok má hodnotu smerníka ''dalsi'' NULL (riadok 14)
***Prvok ''p'' nastavíme ako posledný prvok zoznamu ''z'' (riadok 15).
<source lang="c" line>
void ZmazPosledny(TZoznam &z)
{ if (z.prvy == NULL) // prazdny zoznam
return;
TPrvok *p = z.prvy;
if (p->dalsi == NULL) // je len jeden prvok
{ delete p;
z.prvy = z.posledny= NULL; // upravime strukturu z
return;
}
// najdeme predposledny prvok
while (p->dalsi->dalsi != NULL)
p = p->dalsi;
delete p->dalsi; // zmazeme posledny
p->dalsi = NULL; // a nastavime NULL na aktualny posledny prvok
z.posledny = p; //upravime zoznam tak, aby ukazoval spravne na
} // posledny prvok
</source>
===Zmazanie lineárneho zoznamu===
Vo funkcii ''Zmaz'' budeme mazať všetky prvky zoznamu.

Parametre funkcie:
* TZoznam &z - odkaz na lineárny zoznam, ktorého prvky budeme mazať.

Návratová hodnota: žiadna

Je jedno, či budeme mazať zoznam od začiatku, alebo od konca. Implementácia mazania Zmaz2 je ale efektívnejšia pretože zložitosť funkcie ''ZmazPrvy'' je O(1) a zložitosť funkcie ''ZmazPosledny'' je O(n).
<source lang="c">
void Zmaz(TZoznam &z)
{
while (!JePrazdny(z)) // pokial je v zozname nejaky prvok
ZmazPosledny(z); // zmaze posledny prvok
}

void Zmaz2(TZoznam &z)
{
while (!JePrazdny(z)) // pokial je v zozname nejaky prvok
ZmazPrvy(z); // zmaze prvy prvok
}
</source>
===Použitie lineárneho zoznamu v programe===
<source lang="c">
void main()
{ TZoznam zoznam;
zoznam.prvy =NULL;
zoznam.posledny = NULL;
int udaj,n=4; //pocet zaznamov
for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz_z(zoznam, udaj);
}
for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz_k(zoznam, udaj);
}
vypis(zoznam);
Zmaz(zoznam);

for(int i=0;i<n;i++)
{ cin>>udaj;
Vloz(zoznam, udaj);
}
vypis(zoznam);
Zmaz(zoznam);
</source>

==Odkazy==
<references/>

Rekurzia (riešené príklady)

2010-03-20T11:08:26Z

Jehro77: /* Tretie riešenie - viac optimalizované */

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}
__TOC__

==Prevod čísel z 10-vej sústavy==
'''Zadanie'''

Zostavte program, ktorý bude prevádzať prirodzené čísla do ľubovoľných číselných sústav so základom Z<10, využitím rekurzívnej funkcie. Túto funkciu postupne zdokonaľujte:
#Funkciu vylepšite, aby vedela prevádzať aj do sústav so základom Z<=16.
#Upravte funkciu tak, aby vedela prevádzať všetky celé čísla (čiže aj záporné a nulu).
#Pokúste sa funkciu obohatiť o prevod reálnych čísel (čiže aj desatinných).
V programe načítajte 2 vstupné údaje: číslo N v 10-vej sústave a základ novej sústavy z.

'''Vzorové príklady'''
{|
|-
!vstup
!
!výstup
|-
|80 2
| ->
|1010000
|-
|93 16
| ->
|5D
|-
|0 8
| ->
|0
|-
| -74 4
| ->
| -1022
|-
|3.141592654 16
| ->
|3.243F6A8A48AA
|-
| -0.1 2
| ->
| -0.0001100110011001100
|}

Je vhodné začať jednoduchou funkciou na prevod prirodzeného čísla. Ak máme základ cieľovej sústavy z<10, môžeme problém vyjadriť aj rekurentným vzťahom v matematickom tvare: P(n, z) = P(n/z, z) * 10 + n%z (pre n > 0), a teda by bolo možné vytvoriť funkciu, ktorej návratovou hodnotou by bolo celé číslo.

V prípade, že uvažujeme o vyššom základe, vo výsledku sa objavia aj symboly A, B, C, ... funkcia by už musela výsledok vracať vo forme reťazca. Pre zjednodušenie nám stačí funkcia, ktorá bude výsledok priamo vypisovať. Je treba si uvedomiť, ako sa počíta prevod čísla – číslo vydelíme základom sústavy, tento podiel prevedieme a za ním bude nasledovať zvyšok po pôvodnom delení.

Na vypísanie zvyšku pre vyššie sústavy by sme mohli pre zvyšky väčšie ako 9 použiť aj inkrementáciu znakového typu:
<source lang="c">
cout << char (‘A’ + n%z – 10);
</source>

Keďže základ sústavy sa počas celého prevodu samozrejme nemení, nemá význam v každom volaní funkcie vytvárať jeho kópiu v podobe vstupnej premennej, ale stačí nám referencia (ušetrí sa pár bajtíkov pri každom vnorení).

Ak chceme, aby funkcia dokázala prevádzať aj nulu a záporné čísla, musíme si pridať akúsi „úvodnú“ funkciu, ktorá ošetrí problematické situácie a až potom zavolá hlavnú rekurzívnu funkciu prevodu.

'''Možné riešenie:'''

<source lang="c">
#include <iostream.h>
#include <conio.h>
const char znaky[] = "0123456789ABCDEF";
void PrevodCele(int n, int &zaklad)
{
if (n == 0) return;
PrevodCele(n/zaklad, zaklad); // prevedie celu cast podielu
cout << znaky[n%zaklad]; // za tym napise zvysok
}

void PrevodReal(double r, int &zaklad, int presnost)
{
if (r == 0) return;
r *= zaklad; // posunie o jeden rad vlavo
cout << znaky[int(r)]; // celu cast vypise
PrevodReal(r - int(r), zaklad, presnost - 1); // zvysok prevedie
}

// uvodna funkcia na specialne pripady
void Prevod(double r, int zaklad, int presnost)
{
// ak je zaporne
if (r < 0)
{
r = -r; cout << '-';
}
// cela cast
int n = int(r);
if (n)
PrevodCele(n, zaklad);
else
cout << 0; // ak je nula, vypise ju

// desatinna cast (ak je)
if (r -= n)
{
cout << '.';
PrevodReal(r, zaklad, presnost);
}
}

void main()
{
double r;
int sustava;
cout << "cislo v 10-kovej sustave: "; cin >> r;
cout << "cielova sustava: "; cin >> sustava;
cout << "prevedene: ";
Prevod(r, sustava, 6);
getch();
}
</source>

==Prvočísla==

'''Zadanie:'''

Pomocou rekurzívneho riešenia vytvorte funkciu, ktorá otestuje, či je dané číslo prvočíslo.
===Prvé riešenie - neoptimalizované===

'''Analýza riešenia:'''

Testujeme číslo n na prvočíselnosť. Číslo n budeme postupne deliť číslami od 2 až po (n-1) aby sme zistili zvyšok po delení. Pri prvom zvyšku, ktorý je rovný 0 (teda číslo z delí číslo n bezo zvyšku) funkciu ukončíme a vrátime hodnotu 0 (n nie je prvočíslo). Ak je z<(n-1) tak funkciu is_prime1 voláme rekurzívne a v tomto volaní zvýšime parameter z o 1. (riadok č. 8). V prípade, že neplatí rovnosť z<(n-1) a ani jedno číslo z intervalu <2,n-1> nedelí číslo n bezo zvyšku, vrátime hodnotu 1 (n je prvočíslo).

'''Možné riešenie:'''

<source lang="c" line >
int is_prime1(int n, int z=2)
{
if((n%z)==0)
return 0;
else
{
if(z<(n-1))
return is_prime1(n,z+1);
else
return 1;
}
}
</source>
===Druhé riešenie - čiastočne optimalizované===
Optimalizácia v tomto prípade znamená eliminovať počet delení modulo. Myšlienka nájdenia hornej hranice hodnoty premennej ''z'' z predchádzajúceho príkladu:
*Číslo n delíme modulo hodnotou 2. (výsledok je rôzny od 0)
** nemá zmysel deliť číslom ''z'' väčším ako je n/2, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale (0,1)
*Číslo n delíme modulo hodnotou 3. (výsledok je rôzny od 0)
** nemá zmysel deliť číslom ''z'' väčším ako je n/3, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale <math>(1,2) \cup (2,3)</math>. Podiel nebude mať hodnotu 2, pretože v tom prípade by bolo číslo n delitelné číslom 3 bezo zvyšku.
*Delitel n budeme zväčšovať až pokiaľ platí <math>\frac {n}{d}>d</math>

Horná hranica hodnoty d sa dá určiť nasledovne: <math>d=\sqrt{n}</math>

'''Možné riešenie:'''

<source lang="c" line >
int is_prime2(int n, int z=2)
{
if((n%z)==0)
return 0;
else
{
if(z<sqrt(n))
return is_prime2(n,z+1);
else
return 1;
}
}
</source>

===Tretie riešenie - viac optimalizované===
V predchádzajúcom príklade sme delili číslo n hodnotami premennej d. Premenná d mala prvú hodnotu 2 a potom sa k nej vždy pripočítala hodnota 1. Teda, číslo n sme postupne delili hodnotami
2, 3, 4, 5, 6, 7, 8, ... <math>d=\sqrt{n}</math>.

Všimnime si, že niektoré delenia sú opäť zbytočné:
*ak delíme číslom 2, potom nemá zmysel deliť žiadnym jeho násobkom
*vo všeobecnosti platí: ak delíme číslom ''j'', potom nemá zmysel deliť žiadnym násobkom čísla ''j''.

Inak povedané, netreba deliť žiadnom zloženým číslom. Stačí deliť prvočíslami. A tu sa dostávame k rekurzívnej definícii prvočísel:

'''Rekurzívna definícia prvočísla''':
* Číslo 2 je najmenšie prvočíslo.
* Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.

Pri takto stanovenej podmienke je komplikovanejšie vytvoriť podmienku, ktoré by toto spĺňala. Preto skúsme napísať program, ktorý by zbytočne nedelil násobkami čísel 2 a 3.
Ak nechceme deliť násobkami čísla 2, tak potom budeme postupne deliť premennú n hodnotami 3,5,7,9,11,...

Ak nechceme deliť násobkami čísla 3, tak potom budeme postupne deliť premennú n hodnotami 4,5,7,8,10,11,13,14,...

Prienikom týchto dvoch podmienok je, že nám zostava deliť číslami 5,7,10,13,17,19, ...

V tejto postupnosti je jednoduché pravidlo: striedavé pripočítavanie hodnoty 2 a 4. Vyjadrené aritmetickou postupnosťou:
*<math>d_0=2</math>
*<math>d_1=3</math>
*<math>d_2=5</math>
*<math>d_n=d_{n-1} + 3-(-1)^{i+1}</math>

'''Možné riešenie:'''

<source lang="c" line >
int is_prime3(int n, int z,int krok)
{
int d=z+3+krok;
if((n%d)==0)
return 0;
else
{
if(d<sqrt(n))
return is_prime3(n,d,-krok);
else
return 1;
}
}

int is_prime(int n)
{
if((n%2)==0) return 0;
if((n%3)==0) return 0;
if((n%5)==0) return 0;
return is_prime3(n,5,-1);
}
</source>

'''Rozbor zdrojového kódu:'''

Pre hľadanie prvočísel použijeme funkciu is_prime, ktorá otestuje číslo n na deliteľnosť číslami 2, 3 a 5. Potom zavoláme pomocnú rekurzívnu funkciu is_prime3(int n, int z,int krok) ktorá bude testovať deliteľnosť čísla n prvkami postupnosti <math>\big\{d_n\big\}</math>. Aby sme sa vyhli zbytočným podmienkam, ktoré môžu celý algoritmus spomaliť, definujeme tretí parameter funkcie is_prime3 ''krok''. Parameter krok je v našej postupnosti výraz <math> 3-(-1)^{i+1}</math>, avšak tu nepočítame hodnotu mocniny <math>(-1)^{i+1}</math> ale využívame skutočnosť že tento výraz nadobúda hodnoty -1,1,-1,1, ... .

V premennej d je vypočítaná hodnota aktuálneho deliteľa podľa vzťahu: <math>d_n=d_{n-1} + 3-(-1)^{i+1}</math>.

===Riešenie s globálnym poľom===
Pre zjednodušenie tvorby programu si vytvorme globálne pole do ktorého uložíme prvých n prvočísel. Potom najväčšie číslo, ktoré môžeme testovať na prvočíselnosť je <math>N=n^2</math>.

'''Analýza riešenia:'''

Testujeme číslo n na prvočíselnosť. Ako prvé vypočítame zvyšok po delení prvým prvočíslom v poli ''pcisla'' (delíme číslom pcisla[0]=2). V prípade, ak je výsledok 0, tak výpočet ukončíme a vrátime hodnotu (0 - nie je prvočíslo). V opačnom prípade rekurzívne zavoláme funkciu jePrvocislo, kde druhý parameter (má význam indexu v poli ''pcisla'') zvýšime o 1. Teda v ďalšom volaní funkcie jePrvocislo už budeme deliť číslom pcisla[1]=3. Musíme však zabezpečiť, aby hodnota pcisla[i] v riadku č. 5 existovala. To zabezpečíme tak, že rekurzívne volanie dovolíme len ak je hodnota indexu i menšia ako počet hodnôt v pole pcisla.

'''Možné riešenie:'''

<source lang="c" line >
int prvocisla[]={2,3,5,7,11,13,17,19,23,29,31,37};

int is_prime4(int n, int i=0)
{
if(n%prvocisla[i]==0)
return 0;
if(i<223 && n>pow(prvocisla[i],2))
return is_prime4(n,i+1);
else
return 1;
}
</source>

'''Vzorové riešenie'''

Uvádzame postupnosť volaní funkcie '''is_prime4(31)'''

{| class=wikitable
|+
!Vnorenie
!Volaná funkcia
!prvocisla[i]
!n%prvocisla[i]
!rekurzívne volanie
|-
|0
|is_prime(31,0)
|2
|31%2=1
|is_prime(31,1)
|-
|1
|is_prime(31,1)
|3
|31%3=1
|is_prime(31,2)
|-
|2
|is_prime(31,2)
|5
|31%5=1
|is_prime(31,3)
|-
|3
|is_prime(31,3)
|7
|31%7=3
|is_prime(31,4)
|-
| 4
| is_prime(31,4)
| 11
| n.a.
| neplatí podmienka n>prvocisla[i]^2<br/>n=31, i=4, prvocisla[i]=11<br/>funkcia vracia hodnotu '''1'''
|-
| 3
| návrat na is_prime(31,3)
| 7
| n.a.
| spätný rekurzívny chod
|-
| 2
| návrat na is_prime(31,2)
| 5
| n.a.
| spätný rekurzívny chod
|-
| 1
| návrat na is_prime(31,1)
| 3
| n.a.
| spätný rekurzívny chod
|-
| 0
| návrat na is_prime(31,0)
| 2
| n.a.
| spätný rekurzívny chod
|}
====Porovnanie efektivity navrhovaných algoritmov====
Skôr ako budeme porovnávať ukázané algoritmy, poznamenajme, že tento spôsob zisťovania prvočíselnosti je pre veľké čísla veľmi neefektívny. Pri 8-cifernom čísle trvá výpočet funkcie is_prime približne 230 s. Pre zisťovanie prvočíselnosti existujú špeciálne algoritmy, napr. [http://en.wikipedia.org/wiki/AKS_primality_test ASK test], [http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test Test Solovay-Strassena], [http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Test Millera-Rabina] a iné.
V nasledujúcej tabuľke a na obrázku sú výsledky porovnania efektívnosti týchto algoritmov pri hľadaní prvočísel na intervale (100,n) kde n sme menili od 50 000 do 2 000 000. V tabuľke ani v grafe nie je zahrnutá funkcia is_prime1, pretože pri n=100 000 pri rekurzívnom volaní funkcia neočakávane skončila.
Aby sme mohli porovnávať aj funkciu is_prime4, musíme do poľa ''prvocisla'' pridať všetky prvočísla, ktoré sú menšie ako <math>\sqrt{n_{max}}</math>, kde n_max je v našom prípade 2 000 000. Pole ''prvocisla'' obsahuje prvých 233 prvočísel:
<source lang="c">
int prvocisla[]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,
191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,
397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,
617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,
1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,
1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423};
</source>
Naprogramované funkcie sme testovali nasledovne:

<source lang="c">
#include <iostream.h>
#include <time.h>

int main()
{
clock_t start, end;
double elapsed;
int n;
n=50000; //100000, 200000, ... 2000000
start = clock();
for(int i=100;i<n;i++)
is_prime(i);
end = clock();
elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
cout<<elapsed<<endl;
}
</source>
{| class=datatable
|+Tabuľka nameraných časov behu funkcií
|-
!n [tisíc]
!is_prime_2 t[s]
!is_prime t[s]
!is_prime4 t[s]
|-
|50
|0,16
|0,086
|0,061
|-
|100
|0,398
|0,134
|0,126
|-
|200
|1,034
|0,345
|0,304
|-
|500
|1,245
|1,237
|0,958
|-
|1000
|3,275
|3,264
|2,349
|-
|1500
|17,203
|5,831
|3,9
|-
|2000
|26
|8,6
|5,82
|}

<pLines ymin=0 ymax=27 colors=FF0000,00FF00,0000FF size=600x250 plots legend>
,is_prime2, is_prime, is_prime4
50 tis, 0.16, 0.08, 0.061
100 tis, 0.398, 0.134, 0.126
200 tis, 1.034, 0.345, 0.304
500 tis, 1.245, 1.237, 0.958
1 mil, 3.275, 3.264, 2.349
1.5 mil, 17.203, 5.831, 3.9
2 mil, 26, 8.6, 5.82
</pLines>

Podobné časy pri nižších hodnotách n sú dané tým, že vzdialenosť susedných prvočísel je väčšia pri vyšších prvočíslach. Z grafu taktiež vidieť účinok optimalizácie algoritmu.

==Odkazy==
*http://sk.wikipedia.org/wiki/Zoznam_prvo%C4%8D%C3%ADsiel
*http://www.prime-numbers.org/

Štruktúry (riešené príklady)

2010-03-19T18:29:06Z

Jehro77: /* Intepreter postfixových aritmetických výrazov */

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}
__TOC__

==Štruktúra Zlomok==
'''Úloha:'''

Zostavte program, ktorý pomôže pri práci so zlomkami – bude vedieť zlomok skrátiť a vypísať ho v čo najvhodnejšom tvare. Program načíta dva zlomky, každý hneď po načítaní upravene vypíše, ďalej vypíše ich súčin, súčet a podiel:
#Zostavte funkciu na načítanie zlomku z klávesnice a funkciu, ktorá vypíše zlomok na obrazovku v tvare „a/b“, napr. „3/4“. Postupne ju zdokonaľujte:
##V prípade, že zlomok má celú časť, vypíše ho v tvare „a b/c“, napr. namiesto „9/4“ bude písať „2 1/4“.
##V prípade, že jeho zvyšná časť je nulová, nebude ju vypisovať, napr. namiesto „6/2“ nebude písať „3 0/2“, ale iba „3“ a podobne, namiesto „0/2“ iba „0“.
#Vytvorte si pomocnú funkciu, ktorá zjednoduší (skráti) zlomok, napr. „36/48“ prevedie na „3/4“ a obohaťte ňou funkciu pre vypísanie zlomku (aby sa zlomok vypisoval už v zjednodušenom tvare).
#Zostavte funkcie, ktoré vypočítajú súčin, súčet a podiel dvoch zlomkov a použite ich v hlavnom programe.

'''Vzorový vstup:'''
5 4
1 1/4
6 8
3/4

'''Vzorový výstup:'''
sucin: 15/16
sucet: 2
podiel: 1 2/3

Cieľom je precvičiť si prácu so štruktúrou – bolo by vhodné ju v programe využiť.
Funkcia na načítanie zlomku môže využiť referenciu alebo štruktúru ako návratovú hodnotu. Pre krátenie zlomku môžeme využiť referenciu a pre matematické operácie so zlomkami zase návratovú hodnotu.

Pre krátenie zlomku treba funkciu na najväčší spoločný deliteľ – použijeme Euklidov algoritmus postupného odpočítavania menšieho čísla od väčšieho a jeho zdokonalenie cez operáciu modulo.
Pri matematických funkciách môžeme využiť akýsi „akoby konštruktor“ na vytvorenie zlomku, no nie je to nutné.

'''Možné riešenie:'''
<source lang="c" line>
#include <iostream.h>
#include <conio.h>
struct TZlomok { int citatel, menovatel; };
void CitajZlomok(TZlomok &z)
{
cin >> z.citatel;
cin >> z.menovatel;
}

int NSD(int a, int b)
{
while (b)
{
int c = a % b;
a = b;
b = c;
}
return a;
}

void SkratZlomok(TZlomok &z)
{
int nsd = NSD(z.citatel, z.menovatel);
z.citatel /= nsd;
z.menovatel /= nsd;
}

void VypisZlomok(TZlomok z)
{
SkratZlomok(z);
int cela_cast = z.citatel / z.menovatel;
if (cela_cast)
{
cout << cela_cast;
int zvysok = z.citatel % z.menovatel;
if (zvysok) cout << " " << zvysok << "/" << z.menovatel;
}
else
{
cout << z.citatel;
if (z.citatel) // ak je nula, napise len ju a nie napr. 0/1
cout << "/" << z.menovatel;
}
cout << endl;
}

TZlomok Zlomok(int cit, int men)
{
TZlomok z;
z.citatel = cit;
z.menovatel = men;
SkratZlomok(z);
return z;
}

TZlomok SucinZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.citatel, z1.menovatel * z2.menovatel);
}

TZlomok SucetZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.menovatel + z2.citatel * z1.menovatel,
z1.menovatel * z2.menovatel);
}

TZlomok PodielZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.menovatel, z1.menovatel * z2.citatel);
}

void main()
{
TZlomok z1, z2;
CitajZlomok(z1); VypisZlomok(z1);
CitajZlomok(z2); VypisZlomok(z2);
cout << "sucin: "; VypisZlomok(SucinZlomkov(z1, z2));
cout << "sucet: "; VypisZlomok(SucetZlomkov(z1, z2));
cout << "podiel: "; VypisZlomok(PodielZlomkov(z1, z2));
getch();
}
</source>

==Zásobník - pamäť typu LIFO==
===Intepreter postfixových aritmetických výrazov===
'''Zadanie:'''

Vytvorte program v jazyku C, ktorý po spustení načíta od používateľa postfixový aritmetický výraz, vyhodnotí ho, vypíše jeho hodnotu do konzoly (na monitor) a skončí.

'''Analýza:'''

V postfixovom aritmetickom výraze sa operátor zapisuje vždy po svojich dvoch operandoch, ako to môžeme vidieť v nasledujúcom takomto výraze
5 9 8 + 4 6 * * 7 + *
ktorý má hodnotu 2075.
Každý infixový aritmetický výraz, môže byť prepísaný na postfixový. Infixová verzia uvedeného postfixového výrazu je nasledovná:
5 * ( ( (9 + 8) * (4 * 6) ) + 7)
a tá má samozrejme po vyhodnotení rovnakú hodnotu 2075.

Pomocou abstraktného dátového typu (ADT) zásobníka sa dajú veľmi dobre vyhodnocovať práve postfixové aritmetické výrazy. Každý operátor si z vrcholu zásobníka načíta svoje dva operandy a po vykonaní operácie na nich vráti jej výsledok namiesto týchto dvoch operandov na vrchol zásobníka (využitie princípu dátovej štruktúry typu LIFO). Nasledujúci obrázok demonštruje tento jednoduchý princíp na vyhodnocovaní vyššie uvedeného postfixového aritmetického výrazu.

{| border="1" class=wikitable
|+ Spracovanie postfixového výrazu 5 9 8 + 4 6 * * 7 + *
|-
!index v pamati zásobníka<hr/>číslo kroku
! 0
! 1
! 2
! 3
! 4
! operácia
|-
| 1
| 5
|
|
|
|
|
|-
| 2
| 5
| 9
|
|
|
|
|-
| 3
| 5
| 9
| 8
|
|
|
|-
| 4
| 5
|
|
|
|
| 8+9
|-
| 5
| 5
| 17
|
|
|
|
|-
| 6
| 5
| 17
| 4
|
|
|
|-
| 7
| 5
| 17
| 4
| 6
|
|
|-
| 8
| 5
| 17
|
|
|
| 6 * 4
|-
| 9
| 5
| 17
| 24
|
|
|
|-
| 10
| 5
|
|
|
|
| 24*17
|-
| 11
| 5
| 408
|
|
|
|
|-
| 12
| 5
| 408
| 7
|
|
|
|-
| 13
| 5
|
|
|
|
| 408 + 7
|-
| 14
| 5
| 415
|
|
|
|
|-
| 15
|
|
|
|
|
| 415 * 5
|-
| 16
| 2075
|
|
|
|
|
|}
Tabuľka ukazuje použitie zásobníka reprezentovaného celočíselným poľom (zasobnik.pamat[ ]) pre vyhodnotenie postfixového výrazu 5 9 8 + 4 6 * * 7 + * uloženého v znakovom poli (vyraz[ ]). Tento výraz postupne prechádzame zľava doprava. Ak narazíme na znak reprezentujúci číslo, vložíme ho na vrchol zásobníka (zasobnik.pamat[zasobnik.vrchol]), ak narazíme na znak reprezentujúci operátor, potom vyberieme z vrcholu zásobníka 2 operandy, aplikujeme na ne operátor a namiesto týchto dvoch operandov vložíme na vrchol zásobníka výsledok samotnej operácie.
Na reprezentáciu zásobníka použijeme štruktúru LIFO. Pre základné operácie so zásobníkom, vloženie položky na vrchol zásobníka a vybratie položky z jeho vrcholu, si vytvoríme dve funkcie:
<source lang="c">
stav zasobnika push(LIFO &zasobnik, int x);
int pop(LIFO &zasobnik);
</source>
'''Príklad vstupu do programu:'''

5 9 8 + 4 6 * * 7 + *

'''Príklad výstupu z programu:'''

2075

'''Možné riešenie:'''

<source lang="c" line>
#include<iostream>
#include <string.h>
using namespace std;

#define MAX_PAMAT 40

enum stav_zasobnika{OK=-1, FULL=-2, EMPTY=-3};

struct LIFO
{
int pamat[MAX_PAMAT]; //pole reprezentujuce ADT zasobnik
int vrchol; //index vrcholu zasobnika, indexova premenna

};

//VLOZI novu polozku 'x' do pola 'zasobnik.pamat' (do zasobnika) a zvacsi indexovu premennu //'zasobnik.vrchol' o 1
stav_zasobnika push(LIFO &zasobnik, int x)
{
if(zasobnik.vrchol<MAX_PAMAT)
zasobnik.pamat[zasobnik.vrchol++]=x;
else
return FULL;
return OK;
}

//zmensi indexovu premennu 'zasobnik.vrchol' o 1 a VYBERIE poslednu vlozenu polozku z pola //'zasobnik.pamat' (zo zasobnika)
int pop(LIFO &zasobnik)
{
if(zasobnik.vrchol>0)
return zasobnik.pamat[--zasobnik.vrchol];
else
return EMPTY;
}

int main()
{
LIFO f; //deklaracia strukturovej premennej typu 'LIFO' reprezentujucej zasobnik
f.vrchol=0;
int X, i;
char vyraz[40];

//cout<<"Vlozte postfixovy vyraz na vyhodnotenie:\n";
cin.getline(vyraz,39)

X=(int)strlen(vyraz); //v 'X' je dlzka nacitaneho retazca zo standardneho vstupu
//v cykle 'for' prechadzame vstupny vyraz ulozeny v poli 'vyraz' zlava doprava. Ak narazime na znak
//reprezentujuci cislo, vlozime ho na vrchol zasobnika ('f.pamat[f.vrchol]'), ak narazime na znak
//reprezentujuci operator, potom vyberieme z vrcholu zasobnika 2 operandy, aplikujeme na ne
//operator a namiesto tychto dvoch operandov vlozime na vrchol zasobnika vysledok samotnej
//operacie

for(i=0; i<X; i++)
{
if (vyraz[i]=='+')
push(f, (pop(f) + pop(f)));
if (vyraz[i]=='*')
push(f, (pop(f) * pop(f)));
if ((vyraz[i]>='0') && (vyraz[i]<='9'))
push(f, 0);

//vlozenie cisla (v datovom type 'int') reprezentovaneho jednym alebo viacerymi znakmi v poli
//'a' na vrchol zasobnika
while ((vyraz[i]>='0') && (vyraz[i]<='9'))
push(f, (10 * pop(f) + (vyraz[i++] - '0')));
//obsluzenie //ziskanie cisla typu 'int' reprezentovaneho
//viaccifernych cis. //znakom ulozenym v 'a[i]' a zvascsenie 'i' o 1
//pre posun na dalsiu iteraciu cyklu 'while'
}
//na vrchole zasobnika je uz vysledok vyhodnoteneho postfixoveho aritmetickeho vyrazu, takze ho
//vypiseme
cout<<pop(f);
return 0;
}
</source>