Neusporiadaný 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 na koniec zoznamu. Na konci zoznam vypíšte a zmažte.
Vzorový príklad
Vstup
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
Výstup
výpis zoznamu: je rovnaký ako vstupné dáta.
Analýza úlohy
Na reprezentáciu dát si vytvoríme štruktúry TDatum a TStudent, ktorá nám opisujú jedného študenta.
struct TDatum
{
int d,m,y;
};
struct TStudent
{
char meno[32],priezvisko[32];
TDatum datum_narodenia;
char znamka_ZI;
};
Príklad sa má riešiť pomocou lineárneho zoznamu. Vytvoríme si štruktúru TPrvok, ktorá bude jedným prvkom zoznamu.
struct TPrvok
{
TStudent student;
TPrvok *dalsi;
};
Nakoniec ešte potrebujeme samotnú štruktúru zoznam.
struct TZoznam
{
TPrvok *prvy, *posledny;
};
Vo vstupnom súbore nám každý riadok reprezentuje jedného študenta. Takže budeme naraz načítavať všetky údaje v riadku a uložíme ich do patričných položiek štruktúry TStudent. Na načítavanie použijeme funkciu Nacitaj(TStudent &s,istream &vstup). Zaujímavý je druhý parameter, je to odkaz na vstupný prúd (istream) - môže to byť cin, alebo vlastný dátový prúd (súbor).
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)
V ukážke sú uvedené aj ďalšie funkcie, VlozNaKoniec (funkcia vloží prvok do zoznamu na koniec), PorovnajS2 (funkcia bude porovnávať podľa dátumu, priezviska, mena), Vypis (funkcia vypíše celý zoznam), Zmaz (funkcia zmaže zoznam) a ZmazPosledny (funkcia zmaže zo zoznamu posledný prvok)
Riešenie v jazyku C
1 #include <iostream.h>
2 #include <fstream.h>
3 #include <string.h>
4 //-----------------datove struktury-------------------//
5 struct datum
6 { int d,m,y;
7 };
8 struct TStudent
9 { char meno[32],priezvisko[32];
10 datum datum_narodenia;
11 char znamka_ZI;
12 };
13 struct TPrvok
14 { TStudent student;
15 TPrvok *dalsi;
16 };
17 struct TZoznam
18 {
19 TPrvok *prvy, *posledny;
20 };
21
22 //-------------------funkcie-----------------------------//
23
24 int JePrazdny(TZoznam z)
25 {
26 return z.prvy == NULL;
27 }
28
29 void VypisPrvok(TPrvok *p)
30 {
31 cout << p->student.priezvisko <<" "<<p->student.meno<<" ("<<p->student.znamka_ZI<<") ";
32 cout<<p->student.datum_narodenia.d<<". "<<p->student.datum_narodenia.m<<". ";
33 cout<<p->student.datum_narodenia.y<<endl;
34 }
35
36 void Vypis(TZoznam z)
37 {
38 if (JePrazdny(z)) return;
39 TPrvok *p = z.prvy;
40 while (p->dalsi != NULL)
41 {
42 VypisPrvok(p);
43 p = p->dalsi;
44 }
45 VypisPrvok(p);
46 }
47
48 void ZmazPosledny(TZoznam &z)
49 {
50 if (z.prvy == NULL) // prazdny zoznam
51 return;
52
53 TPrvok *p = z.prvy;
54 if (p->dalsi == NULL) // je len jeden prvok
55 {
56 delete p;
57 z.prvy = z.posledny = NULL;
58 return;
59 }
60
61 // najdeme predposledny prvok
62 while (p->dalsi->dalsi != NULL)
63 p = p->dalsi;
64 delete p->dalsi;
65 p->dalsi = NULL;
66 z.posledny = p;
67 }
68
69 void Zmaz(TZoznam &z)
70 {
71 while (!JePrazdny(z))
72 ZmazPosledny(z);
73 }
74
75 void Nacitaj(TStudent &s,istream &vstup)
76 {
77 vstup>>s.meno>>s.priezvisko>>s.znamka_ZI;
78 vstup>>s.datum_narodenia.d>>s.datum_narodenia.m>>s.datum_narodenia.y;
79 }
80
81 void VlozNaKoniec(TZoznam &z,TStudent s)
82 {
83 TPrvok *novy = new TPrvok;
84 novy->student = s;
85 novy->dalsi = NULL;
86
87 if (z.prvy == NULL) // prazdny zoznam
88 z.prvy = novy;
89 else
90 z.posledny->dalsi = novy;
91 z.posledny = novy;
92 }
93
94 int main()
95 {
96 TZoznam zoznam;
97 zoznam.prvy = zoznam.posledny = NULL;
98 TStudent s;
99 int n=0;
100
101 ifstream vstup;
102 vstup.open("prvaci.txt");
103
104 Nacitaj(s,vstup);
105 VlozNaKoniec(zoznam,s);
106 while(s.datum_narodenia.d)
107 {
108 Nacitaj(s,vstup);
109 if(s.datum_narodenia.d)
110 VlozNaKoniec(zoznam,s);
111 n++;
112 }
113 vstup.close();
114 cout<<"--------vypis zoznamu--------------"<<endl;
115 cout<<"Pocet studentov: "<<n<<endl;;
116 Vypis(zoznam);
117 Zmaz(zoznam);
118
119 system("pause");
120 }
