10 Dátové štruktúry
Každý program má dve základné časti, ktoré profesor Wirth zhrnul do známej rovnice
Programy = Datové štruktúry + Algoritmy.
Zdá sa, že jedným zo základných princípov moderných technológií vytvárania programov je práve oddelenie časti, zaoberajúcej sa údržbou informácií v datových štruktúrach od vlastného algoritmu riešenia úlohy . Obidve časti môžu byť v programe v rôznej miere rozptýlené. Sústredením pamäťových prostriedkov a kódu pre manipuláciu s nimi do samostatných modulov získame prehľadnejšie, čitateľnejšie, modifikovateľnejšie, lepšie dokumentované a predovšetkým spoľahlivejšie programy, ktoré sú aj efektívnejšie, lebo nedochádza napr. k opakovaniu kódu. Dá sa povedať, že vhodným návrhom dátovej štruktúry pre danú úlohu je spravidla aj algoritmus riešenia úlohy jednoduchší a prehľadnejší.
V ďalšej časti sa budeme zaoberať základnými dátovými štruktúrami. Podrobnejšie preberieme lineárne zoznamy. Kapitolu uzavrieme stručným popisom stromových štruktúr.
Slovo lineárny udáva, že počet predchodcov aj nasledníkov hociktorej položky zoznamu je maximálne 1. To znamená, že v lineárnom zozname existuje maximálne jedna predchádzajúca a jedna nasledujúca položka. Z toho dôvodu lineárne zoznamy slúžia pre reprezentáciu úplného usporiadania. Podľa spôsobu vkladania a vyberania položiek rozoznávame tri typy lineárnych dátových štruktúr: front, zásobník a zoznam.
10.1 Lineárny zoznam
Pre vzájomné pospájanie položiek danej množiny stačí jediný spojovací článok, ktorý ukazuje na nasledujúcu položku množiny. Týmto článkom je smerník, pričom smerník poslednej položky má hodnotu NULL. Pridanie, resp. zrušenie položky v zozname sa potom jednoducho realizuje príslušnou zmenou jednotlivých smerníkov. Pre pridanie položky 3 do zoznamu medzi položku 1 a 2 značí zmeniť smerník položky 1 tak, aby ukazoval na položku 3 a smerník položky 3 bude ukazovať na položku 2 (nadobudne predchádzajúcu hodnotu smerníka položky 1).
Front je spôsob organizácie, ktorý sa používa vtedy, ak potrebujeme spracovať položky v takom poradí, v akom prichádzajú. Spôsob vkladania a vyberania položiek sa označuje ako FIFO (first-in, first-out).
Front je obyčajne charakterizovaný
- typom položiek
- maximálnym počtom položiek, ktoré je možné do frontu vložiť
- operáciami
- vytvorenie frontu
- vložiť položku do frontu (na koniec)
- vrátiť prvú položku
- odobrať prvú položku (všetky ostatné posunúť)
- test na prázdnosť frontu
- test na plnosť frontu
- vrátiť dĺžku frontu
Je zrejmé, že vložiť položku je možné len do frontu, ktorý nie je plný, a naopak, odobrať prvú položku je možné len z neprázdneho frontu. Odobranie položky znamená skrátenie frontu.
Prvá položka prázdneho frontu nie je definovaná. Dĺžka frontu je daná počtom všetkých položiek. Ak tento počet je rovný maximálnemu počtu položiek, front je plný.
Chybové stavy : pridanie položky do plného frontu výber položky z prázdneho frontu
Programová realizácia frontu môže vychádzať z implementácie pomocou
- poľa (pri odobraní prvej položky presun ostatných položiek)
- kruhového poľa (spojenie prvej a poslednej položky, odobranie prvej položky znamená iba presun začiatku frontu)
- spojových štruktúr (realizované smerníkmi, odobranie prvej položky znamená iba zmenu smerníka na začiatok frontu).
Zásobník je front typu LIFO (last-in first-out) - posledná vložená položka bude vybraná ako prvá. Používa sa tam, kde potrebujeme odložiť informácie a cestou späť sa k nim vrátiť (stack pri volaní funkcií, riešenie rekurzívnych problémov).
Zásobník je obyčajne charakterizovaný
- typom položiek
- max. počtom položiek, ktoré je možné do zásobníka vložiť
- operáciami
- vytvorenie zásobníka
- vložiť položku do zásobníka (na vrchol)
- vrátiť položku z vrcholu zásobníka
- odobrať položku z vrcholu zásobníka
- test na prázdnosť zásobníka
- test na plnosť zásobníka
- vrátiť dĺžku zásobníka
Ak máme pre zásobník vyhradenú dostatočne veľkú pamäť, môžu byť maximálny počet položiek a test na plnosť zásobníka nezaujímavé. Z uvedeného je zrejmé, že vrchol zásobníka tvorí posledná vložená položka. Odobraním položky z neprázdneho zásobníka sa jeho dĺžka skráti (vložením zvýši) o 1. Prázdny zásobník nemá vrchol. Položky sú zo zásobníka vyberané v opačnom poradí, ako sú vkladané.
Chybové stavy : výber položky z prázdneho zásobníka vloženie položky do plného zásobníka
Programová realizácia zásobníka môže vychádzať z implementácie pomocou
- poľa
- spojových štruktúr.
Implementácia pomocou poľa sa používa vtedy, ak poznáme maximálny počet položiek. Na aktuálny vrchol zásobníka ukazuje premenná index, ktorá sa modifikuje príslušným spôsobom pri každom vložení, resp. výbere zo zásobníka.
Implementácia pomocou spojových štruktúr využíva smerníkové spojenie položiek. Pri vložení, resp. výbere sa tu namiesto premennej index príslušným spôsobom modifikuje smerník na vrchol zásobníka. V tomto prípade je výhodné používať trojicu smerníkov, ktoré indikujú aktuálny vrchol zásobníka (ako premenná index) a začiatok i koniec pamäte pre zásobník (analógia s deklaráciou poľa).
Zoznam predstavuje takú postupnosť, do ktorej môžeme pridávať, resp. rušiť položky na ľubovoľnom mieste, ktoré je označené premennou index (tzv. ukazovateľ, ktorý označuje ľubovoľné miesto práce so zoznamom od začiatku až po koniec). Tým sa zoznam líši od frontu, resp. zásobníka, kde je možná aktualizácia iba na koncoch postupnosti. Zoznam je teda všeobecným prípadom lineárnej dátovej štruktúry. Je charakterizovaný
- typom položiek
- maximálnym počtom položiek
- operáciami
- vytvoriť zoznam
- vložiť položku do zoznamu na miesto označené ukazovateľom
- nastaviť ukazovateľ na začiatok zoznamu
- nastaviť ukazovateľ na koniec zoznamu
- nastaviť ukazovateľ na ďalšiu položku zoznamu
- nastaviť ukazovateľ na predchádzajúcu položku zoznamu
- vrátiť položku zoznamu, označenú ukazovateľom
- vrátiť dĺžku zoznamu
- test na prázdnosť zoznamu
- test na plnosť zoznamu
Rovnako ako v predchádzajúcom platí pri dostatočne veľkej vyhradenej pamäti, že maximálny počet položiek a test na plnosť zoznamu môžu byť nezaujímavé. Je zrejmé, že vkladať novú položku je možné len do rozsahu zoznamu a rušiť položku je možné len v neprázdnom zozname. Každým vložením, resp. rušením položky sa príslušne mení dĺžka zoznamu.
Chybové stavy : výber položky z prázdneho zoznamu vloženie položky do plného zoznamu
Programová realizácia môže rovnako ako v predchádzajúcich prípadoch vychádzať z implementácie pomocou
- poľa
- spojových štruktúr.
Implementáciu pomocou poľa ilustruje príklad p10_1, ktorý rieši veľmi jednoduchý telefónny zoznam s dvoma základnými funkciami vloz a zrus. Položka zoznam je reprezentovaná štruktúrou ex1, pozostávajúcou z mena a telefónneho čísla účastníka. Zoznam je tvorený poľom p. Pri práci s poľom sa využívajú premenné ukaz na pohyb po zozname a dĺžka. V prvej časti programu sa generujú mená účastníkov a ich telefónne číslo, v druhej časti sa zruší prvá položka zoznamu a nová položka sa vloží na druhé a pred posledné miesto zoznamu. Všimnite si, že tak pri vkladaní, ako aj pri rušení položky vo funkciách vloz a zrus, dochádza k fyzickému presunu príslušnej časti poľa p jedným alebo druhým smerom.
/* p10_1.c zoznam pomocou pola tel. zoznam */
#include <STDIO.H>
#include <STDLIB.H>
#include <STRING.H>
#define N 9
struct ex1{
char m[8];
float cislo;
} p[N],t;
int ukaz,dlzka;
void vloz(struct ex1 q);
void zrus();
struct ex1 read();
main()
{
int i,j;
randomize();
printf("\Telefonny zoznam povodny\n");
for(dlzka=0;dlzka<N;DLZKA++){ i for(i="dlzka;" *
prvok novy pre miesto uvolni } return; plny\n?);
je printf(?Zoznam N){ if(dlzka="=" i;
int { ukaz="dlzka-2;" danu poziciu na polozku vlozit q)
ex1 vloz(struct void }; %.0f\n?,ukaz-1,t.m,t.cislo);
%s printf(?%d. t="read();" ){ for(ukaz="0;ukaz>dlzka;"
upraveny\n?); zoznam printf(?\nTelefonny vloz(t); zrus();
dlzka--; t.cislo="100000+100*random(90)+random(10000);"
sprintf(t.m,?Meno%03d?,N+100); %.0f\n?,dlzka,p[dlzka].m,
p[dlzka].cislo); p[dlzka].cislo="100000+100*random(90)+
random(10000);" sprintf(p[dlzka].m,?Meno%03d?,
dlzka);>ukaz; ) p[i]=p[--i];
p[ukaz++] = q;
dlzka++;
}
void zrus()
/* zrusit polozku na pozicii danej ukaz */
{
register int i;
for(i=ukaz; i<DLZKA; * }
{ polozku ex1 dlzka--;
if(ukaz pozicie danej z citat
read() struct p[i]="p[++i]; " )>= dlzka){
printf("V zozname uz nie je ziadny prvok\n");
return (p[0]);
}
return p[ukaz++];
}
Príklad p10_2 ilustruje implementáciu zoznamu pomocou spojových štruktúr, pričom sa využíva zreťazenie v jednom smere (jeden smerník na ďalšiu položku zoznamu). Náplňou je ten istý jednoduchý telefónny zoznam. Reťazenie zoznamu si vyžiadalo doplniť v strukture ex1 smerník ďalší a ďalšiu pomocnú štruktúru POM, ktorá obsahuje tri smerníky na zoznam, a to na začiatok zoznamu - prvy, na aktuálnu pozíciu v zozname - aktual a na poslednú položku v zozname - posledny. Položky zoznamu nie sú uložené v poli, ale v dynamicky prideľovanej pamäti, čím sa činnosť funkcií pre pridávanie do zoznamu pridaj, vkladanie do zoznamu vloz a pre zrušenie položky zoznamu zrus mení (vzhľadom na príklad p10_1) a spočíva v príslušnej úprave smerníkov a alokácii, resp. uvoľnení pamäte. Vo funkciách musia byť správne ošetrené situácie pre prázdny zoznam, zoznam s jednou položkou a s viacerými položkami, a taktiež vkladanie, resp. rušenie prvej, bežnej aj poslednej položky zoznamu. Výhodou takéhoto prístupu k riešeniu problému je to, že pri zostavovaní programu nepotrebujeme poznať presný počet položiek zoznamu (odpovedajúce deklarácie polí). V hlavnom programe je preverené tak vkladanie, ako aj rušenie položiek v rôznych miestach zoznamu. Všimnite si, že každej manipulácii so zoznamom predchádza nastavenie smerníka ,aktual. Počiatočné generovanie zoznamu je rovnaké, ako v predchádzajúcom príklade.
/* p10_2.c zoznam pomocou smernikov
zretazenie v jednom smere
tel. zoznam */
#include <STDIO.H>
#include <STDLIB.H>
#include <STRING.H>
#define N 9
struct ex1{
char m[8];
float cislo;
struct ex1 *dalsi;
} p,t;
struct POM{
struct ex1 *prvy;
struct ex1 *aktual;
struct ex1 *posledny;
int dlzka;
} POM;
void pridaj(struct POM *s, struct ex1 *q);
void vloz(struct POM *s, struct ex1 *q);
void zrus(struct POM *s);
main()
{
int i;
struct ex1 *pex=&p, *t, *tp;
struct POM *pp=&POM;
randomize();
printf("\Telefonny zoznam povodny\n");
for(i=0;i<N;I++){ * 4)pp- if(i="=" pridaj(pp,pex);
p.cislo="100000+100*random(90)+random(10000);
" sprintf(p.m,?Meno%03d?,i);
strukturu naplnit>aktual = pp->posledny;
printf("%2d. %s %.0f\n",i,p.m,p.cislo);
}
sprintf(tp->m,"Meno%03d",N+100);
tp->cislo=100000+100*random(90)+random(10000);
pridaj(pp,tp);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 1. pridat posledny\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
zrus(pp);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 2. zrusit 5. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
vloz(pp,pex);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 3. vloz za 6. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
pp->aktual = pp->prvy;
vloz(pp,pex);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 4. vloz za 1. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
zrus(pp);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 5. zrus 1. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
pp->aktual = pp->posledny;
vloz(pp,pex);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 6. vloz za posl. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
getchar();
pp->aktual = pp->posledny;
zrus(pp);
i=0;
t=pp->prvy;
printf("\nTel. zoznam 7. zrus posl. polozku\n");
while(t){
printf("%2d. %s %.0f\n",i++,t->m,t->cislo);
t=t->dalsi;
};
}
void pridaj(struct POM *s, struct ex1 *q)
/* pridaj novu polozku na koniec zoznamu */
{
register struct ex1 *h;
h = malloc(sizeof(struct ex1)); /* pamat */
if(h == NULL){
printf("\nMalo pamate\n");
return;
};
h->cislo = q->cislo; /* kopia */
strcpy(h->m,q->m);
if(s->dlzka++==0) /* 1. polozka */
s->prvy = h;
else
s->posledny->dalsi = h;
h->dalsi = NULL; /* posledna polozka */
s->posledny = h; /* pripoj polozku */
}
void vloz(struct POM *s, struct ex1 *q)
/* vloz polozku na poziciu aktual */
{
register struct ex1 *h;
h = malloc(sizeof(struct ex1)); /* pamat */
if(h == NULL){
printf("\nMalo pamate\n");
return;
};
h->cislo = q->cislo; /* kopia */
strcpy(h->m,q->m);
if(s->dlzka++ == 0){ /* prazdny zoznam */
/* vloz na zaciatok */
s->prvy = s->aktual = s->posledny = h;
h->dalsi = NULL;
}
if(s->aktual == s->posledny){ /* vloz na koniec */
s->posledny->dalsi = h;
h->dalsi = NULL;
s->posledny = h;
}
else{ /* vloz na poziciu aktual */
h->dalsi = s->aktual->dalsi;
s->aktual->dalsi = h;
};
}
void zrus(struct POM *s)
/* zrus polozku aktual */
{
register struct ex1 *h, *t;
int prvy=1; /* sprac. 1. polozky */
if(s->dlzka == 0) /* prazdny zoznam */
return NULL;
t = s->aktual;
if(s->dlzka == 1) /* zoznam s 1 polozkou */
s->prvy = s->aktual = s->posledny = NULL;
else{
if(s->aktual == s->prvy){ /* 1. polozka */
s->prvy = s->prvy->dalsi;
prvy = 0;
};
if(s->aktual == s->posledny){
/* posledna polozka */
s->posledny = s->prvy;
while(s->posledny->dalsi != s->aktual)
s->posledny = s->posledny->dalsi;
};
if((s->aktual != s->prvy)&&prvy){
h = s->prvy; /* najst predchadzajucu */
while(h->dalsi != s->aktual)
h = h->dalsi;
h->dalsi = s->aktual->dalsi;
}; /* spojit s nasledujucou */
s->aktual = s->aktual->dalsi;
}
s->dlzka--; /* znensit dlzku */
free(t); /* uvolnit pamat */
return ;
}
V príklade p10_3 sa naďalej zaoberáme spomenutým jednoduchým telefónnym zoznamom, realizovaným pomocou spojových štruktúr, ktoré sú zreťazené v obidvoch smeroch. Toto zreťazenie je realizované pomocou dvoch smerníkov v štruktúre ex1. Prvý smerník pred ukazuje na predchádzajúcu položku zoznamu (v prípade 1. položky má hodnotu NULL), druhý smerník dalši ukazuje na nasledujúcu položku zoznamu (v prípade poslednej položky má hodnotu NULL). Zreťazenie položiek zoznamu v obidvoch smeroch umožňuje, resp. zjednodušuje ďalšie operácie so zoznamom (funkcia vypis2 pre výpis zoznamu od konca po začiatok). V tomto príklade pracujeme s tzv. usporiadaným zoznamom (podľa mien), ktorý je výhodný najmä pri vyhľadávaní informácií. Realizáciu usporiadania má na starosti funkcia sortvloz, ktorá vkladá každú novú položku na odpovedajúce miesto v zozname (s využitím lexikografického porovnania reťazcov pomocou štandardnej funkcie strcmp). Pridávanie nových položiek obstaráva funkcia vstup (alokácia pamäte pre položku) pomocou funkcie input pre načítanie reťazca s kontrolou jeho dĺžky. Zrušenie položky (funkcia zrus) spočíva v príslušnej úprave smerníkov susedných položiek (ak je potrebné, aj smerníkov štruktúry POM) a uvoľnení pamäte alokovanej pre položku. Všimnime si, že tak vo funkcii sortvloz, ako aj vo funkcii zrus musia byť ošetrené všetky možné polohy položky v zozname (na začiatku, uprostred a na konci). Funkcia hladaj a najdi slúži pre vyhľadanie položky v zozname podľa mena, resp. podľa čísla. Samotnú realizáciu výpisu údajov danej položky zabezpečuje funkcia display. Pre naznačenie spôsobu praktického využívania takéhoto zoznamu sú uvedené aj funkcie pre zápis všetkých položiek zoznamu do súboru na disk a pre spätné načítanie položiek zoznamu zo súboru do pamäte. Funkcia vstup je navrhnutá pre opakovaný vstup položiek. Zadávanie sa ukončí stlačením klávesa Enter. Celý program je riadený veľmi jednoduchým "menu".
/* p10_3.c zoznam pomocou smernikov
zretazenie v dvoch smeroch
tel. zoznam */
#include <STDIO.H>
#include <STDLIB.H>
#include <STRING.H>
struct ex1{
char m[8];
float cislo;
struct ex1 *pred;
struct ex1 *dalsi;
} p;
struct POM{
struct ex1 *prvy;
struct ex1 *aktual;
struct ex1 *posledny;
int dlzka;
} a,*sa=&a;
int menu(void);
struct ex1 *sortvloz(struct POM *sa, struct ex1 *q);
void vstup(void);
void input(char *vyzva, char *s, int count);
void zrus(void);
struct ex1 *najdi(struct ex1 h1, int druh);
void vypis1(void);
void vypis2(void);
void display(struct ex1 *q);
void hladaj(int druh);
void zapis(void);
void citaj(void);
main()
{
for(;;){
switch(menu()){
case 1 : vstup(); break; /* vloz polozku */
case 2 : zrus(); break; /* zrus polozku */
case 3 : vypis1(); /* vypis zoznamu od zac. */
break;
case 4 : vypis2(); /* vypis zoznamu od konca */
break;
case 5 : hladaj(0); /* hladanie mena v zozname */
break;
case 6 : hladaj(1); /* hlad. cisla v zozname */
break;
case 7 : zapis(); /* zapis na disk */
break;
case 8 : citaj(); /* citanie z disku */
break;
default : exit(0); /* koniec */
break;
}
}
}
int menu(void)
{
char s[80];
int c;
printf("1. Vlozit polozku\n");
printf("2. Zrusit polozku\n");
printf("3. Vypis zoznamu vpred\n");
printf("4. Vypis zoznamu odzadu\n");
printf("5. Hladanie mena\n");
printf("6. Hladanie cisla\n");
printf("7. Zapis na disk\n");
printf("8. Citanie z disku\n");
printf("9. Koniec\n");
do{
printf("Volba cinnosti <1-9> : ");
gets(s);
c = atoi(s);
} while ( c< 1 || c > 9);
return c;
}
struct ex1 *sortvloz(struct POM *sa, struct ex1 *q)
/* vloz polozku do zotriedeneho zoznamu */
{
struct ex1 *old, *top, *beg;
beg = sa->prvy;
if(sa->dlzka++==0){ /* 1. polozka */
q->pred = q->dalsi = NULL;
sa->prvy = sa->aktual = sa->posledny = q;
return q;
};
old = NULL;
top = beg;
while(top){
if(strcmp(top->m,q->m) < 0){
old = top; /* najdi kam zaradit */
top = top->dalsi;
}
else { /* zarad medzi old a top */
q->dalsi = top;
q->pred = old;
top->pred = q;
if(!old)
sa->prvy = q;
if(old){
old->dalsi = sa->aktual = q;
};
return q;
};
};
old->dalsi = q; /* posledna polozka */
sa->posledny = q;
q->dalsi = NULL;
q->pred = old;
return q;
}
void vstup(void)
{
struct ex1 *h;
char p[20];
for(;;){
h = malloc(sizeof(struct ex1)); /* pamat */
if(h == NULL){
printf("\nMalo pamate\n");
return;
};
input("Meno : ",h->m,8); /* kopia */
if(!h->m[0]) break; /* koniec vstupov */
input("Telefonne cislo : ",p,6);
h->cislo = atof(p);
a.aktual = sortvloz(sa,h);
}
}
void input(char *vyzva, char *s, int count)
/* vstup retazca o max. dlzke count s vyzvou */
{
char p[80];
printf(vyzva);
gets(p);
if(strlen(p) > count){
printf(" prilis dlhy vstup\n");
p[count] ='\0';
};
strcpy(s,p);
}
void zrus(void)
/* zrusenie polozky */
{
struct ex1 *h,h1;
printf("Meno pre zrusenie : ");
gets(h1.m);
h = najdi(h1,0);
if(h){
if(sa->prvy == h){
sa->prvy = h->dalsi;
if(sa->prvy) sa->prvy->pred = NULL;
else sa->posledny = NULL;
}
else{
h->pred->dalsi = h->dalsi;
if(h != sa->posledny)
h->dalsi->pred = h->pred;
else
sa->posledny = h->pred;
};
free(h);
a.dlzka--;
}
else printf("sa nenaslo\n");
}
struct ex1 *najdi(struct ex1 h1, int druh)
/* najst vyskyt 0 - mena, 1- cisla v zozname */
{
struct ex1 *h;
h = sa->prvy;
while(h){
if(!druh) /* hladaj meno */
if(!strcmp(h1.m,h->m))
return h;
if(druh) /* hladaj cislo */
if(h1.cislo == h->cislo)
return h;
h = h->dalsi;
};
return NULL;
}
void vypis1(void)
/* vypis poloziek zoznamu vpred */
{
register struct ex1 *h;
h = sa->prvy;
while(h){
display(h);
h = h->dalsi;
};
}
void vypis2(void)
/* vypis poloziek od konca zoznamu */
{
register struct ex1 *h;
h = sa->posledny;
while(h){
display(h);
h = h->pred;
};
}
void display(struct ex1 *q)
/* zobrazit jednu polozku */
{
printf("%s %.0f\n",q->m,q->cislo);
}
void hladaj(int druh)
/* najdenie polozky podla 0 - mena, 1 - cisla */
{
char p[80];
struct ex1 *h,h1;
if(!druh){
printf("Meno pre hladanie : ");
gets(h1.m);
}
else{
printf("Cislo pre hladanie : ");
gets(p);
h1.cislo = atoi(p);
}
if(!(h=najdi(h1,druh))) printf(" sa nenaslo\n");
else display(h);
}
void zapis(void)
/* zapis suboru na disk */
{
int t,size;
struct ex1 *h;
char *c;
FILE *fp;
if((fp=fopen("Zoznam","w")) == 0){
perror("Zoznam");
exit(0);
};
printf("\nZapis na disk...\n");
size = sizeof(struct ex1);
h = sa->prvy;
while(h){
c = (char *)h; /* prevod na ukazatel na char */
for(t=0;t<SIZE;++T) h="h-" putc(*c++,fp);>dalsi;
};
putc(EOF,fp);
fclose(fp);
}
void citaj(void)
/* citanie suboru z disku */
{
int t,size;
struct ex1 *h,*tmp=NULL;
char *c,cc[16];
FILE *fp;
if((fp=fopen("Zoznam","r")) == 0){
perror("Zoznam");
exit(0);
};
printf("\nCitanie z disku...\n");
sa->dlzka = 0;
size = sizeof(struct ex1);
sa->prvy = malloc(size);
if(!sa->prvy){
printf("\nNedostatok pamate\n");
return;
};
h = sa->prvy;
c = (char*)h;
while( (*c++ = getc(fp)) != EOF){
for(t=0;t<SIZE-1;++T) sa- *c++="getc(fp);">dlzka++;
h->dalsi = malloc(size); /* priestor
na dalsiu polozku */
if(!h->dalsi){
printf("\nMalo pamate\n");
return;
};
h->pred = tmp;
tmp = h;
h = h->dalsi;
c = (char *)h;
*c='\0';
};
tmp->dalsi = NULL;
sa->aktual = sa->prvy;
sa->posledny = tmp;
sa->prvy->pred = NULL;
fclose(fp);
}
10.2 Strom
Strom je nelineárna dátová štruktúra, ktorá má vrchol s konečným počtom pripojených stromových štruktúr, ktoré sa nazývajú podstromy. Vrchol stromu sa nazýva aj koreň stromu. V stromovej štruktúre teda každý prvok má jedného bezprostredného predchodcu (okrem koreňa stromu) a žiadneho, jedného či viacerých nasledovníkov. Prvok, ktorý nemá nasledovníkov, je koncový prvok alebo list stromu. Prvok, ktorý nie je listom ani koreňom, je vnútorným vrcholom stromu. Ak je počet nasledovníkov rovný dvom, hovoríme o binárnom strome, pri väčšom počte o viaccestnom strome. Počet nasledovníkov udáva stupeň stromu. Lineárny zoznam je z tohoto hľadiska stromová štruktúra s jedným nasledovníkom, ktorá sa preto tiež nazýva degenerovaný strom. Najbežnejší spôsob zobrazenie stromu je v tvare grafu.
V ďalšom sa budeme zaoberať binárnymi stromami. Typickým príkladom binárneho stromu je rodokmeň človeka (s tým, že rodičia sú nasledníkmi). Každý vrchol stromu obsahuje vlastnú informáciu (kľúč) a môže mať dvoch nasledovníkov, ktoré sa označujú ako ľavý a pravý.
Binárne stromy sa často používajú pre reprezentáciu čiastočného usporiadania množiny údajov, ktorej prvky sa majú vyberať na základe daného kľúča. Strom, v ktorom všetky kľúče ľavého podstromu sú menšie ako kľúč vrcholu a kľúče pravého podstromu zase väčšie (pre všetky vrcholy), sa nazýva vyhľadávací, resp. usporiadaný strom. Vyhľadanie prvku v takomto strome je jednoduché a pritom efektívne : začneme pri koreni stromu a pokračujeme v príslušnom podstrome (o druhý podstrom sa viac nestaráme), až kým prvok nenájdeme alebo nedôjdeme na koniec (list) stromu.
Problematika vyhľadávania, pridávania a rušenia vrcholov v strome tvorí náplň základných operácií so stromami. Je obdobná ako u lineárneho zoznamu s tým, že musí zohľadňovať a ošetrovať viac možných situácií, ako napr.:
- prvok s kľúčom sa v strome nenachádza
- prvok s kľúčom má jedného nasledovníka
- uprvok s kľúčom má dvoch nasledovníkov
Príklad p10_4 ilustruje použitie binárneho stromu na zotriedenie poľa reťazcov. Východzie pole reťazcov vytvára s použitím generátora náhodných čísiel funkcia vytvor. Funkcia vlož realizuje rekurzívne vkladanie prvkov do binárneho stromu. Pre nový vrchol (v programe označený ako uzol) alokuje príslušnú pamäť. Usporiadanie stromu je zabezpečené porovnaním nového a starého reťazca (kľúča) s následným uložením nového reťazca vľavo alebo vpravo (podľa výsledku porovnania strcmp). Ak by sme pracovali s číslami ako s kľúčmi, bolo by to obyčajné porovnanie menší, väčší. Funkcia zobraz vykonáva prezeranie vrcholov usporiadaného binárneho stromu.
/* p10_4.c binarny strom pomocou pola
triedenie poli retazcov */
#include <STDIO.H>
#include <STDLIB.H>
#include <STRING.H>
#include <CONIO.H>
#define POCET 30
#define RET 50
typedef struct bstrom uzol;
typedef struct bstrom* puzol;
struct bstrom{
char* m;
puzol lavy;
puzol pravy;
} ;
puzol vloz(puzol, char *);
void vytvor(char [][], int *);
void zobraz(puzol);
main()
{
int i,n;
char ret[POCET][RET+1];
puzol koren = NULL;
printf("Pocet retazcov <MAX. %d> : ",POCET);
scanf("%d",&n);
if( n < 1 || n > POCET)
n = POCET;
vytvor(ret, &n);
puts("vytvaram binarny strom");
for (i=0; i<N; * }
{ koren- koren="vloz(koren," NULL)
{ if(koren="=" stromu binarneho
do prvkov vkladanie rekurzivne *m)
char koren, vloz(puzol puzol zobraz(koren); :\n?);
retazcov pole puts(?zotriedene ret[i]); i++)>m = m;
koren->lavy = koren->pravy = NULL;
}
else{
if(strcmp(m,koren->m) < 0)
koren->lavy = vloz(koren->lavy,m);
else
koren->pravy = vloz(koren->pravy,m);
}
return(koren);
}
void vytvor(char x[][RET+1], int *n)
/* generovanie pola nahodnych retazcov */
{
int i,j;
char pom[RET+1];
randomize();
if(*n < 1 || *n > POCET)
*n = POCET;
for(i=0; i<*n; i++){
for(j=0; j<RET; * } { void stromu rekurzivne
if(koren- bin. uzlov prezeranie koren)
zobraz(puzol ; *(x+i)+j)="\0" *( j);
pom, strncpy(*(x+i), j="random(RET-1);" 0)
(j="=" if pom[RET]="\0" random(26);
+ *(pom+j)="a" j++)>lavy != NULL)
zobraz(koren->lavy);
printf("\t %s \n",koren->m);
if(koren->pravy != NULL)
zobraz(koren->pravy);
}
Obvykle sa pri práci so stromami jednotlivé vrcholy vytvárajú dynamicky a môže byť potrebné vytvoriť celý rad rôznych pomocných funkcií, ako sme to uviedli v príklade p10_3 (hľadať, rušiť, zápis a čítanie stromu a pod.).