Usporiadaný lineárny zoznam (riešené príklady)
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)
#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");
}
