Usporiadaný lineárny zoznam (riešené príklady) - História úprav

Juraj na 20:29, 16. august 2010

2010-08-16T20:29:38Z

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

2010-04-11T17:34:34Z

Analýza riešenia

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

2010-04-11T17:34:07Z

Analýza riešenia

Juraj: Usporiadaný lineárny zoznnam (riešené príklady) premiestnená na Usporiadaný lineárny zoznam (riešené príklady)

2010-03-25T12:28:11Z

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

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vo vstupnom súbor…“

2010-03-23T09:49:18Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vo vstupnom súbor…“

Nová stránka

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

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

@@ Riadok 45: / Riadok 45: @@
 ''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)
+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">

← Staršia verzia	Verzia zo dňa a času 12:28, 25. marec 2010
(Žiaden rozdiel)