Podíváme se na datovou strukturu nazývanou jednoduchý seznam a ukážeme si jak ji programovat. Příkladem nám budiž seznam žáků v učebně. Každý prvek seznamu bude mít v sobě dvě věci, jméno osoby a ukazatel na další prvek seznamu. Seznam budeme postupně naplňovat příkazem p (osoba přišla do třídy). Tato funkce přidá prvek do seznamu, paměť budememe alokovat dynamicky pomocí funkce malloc() standardní C knihovny. Pokud někdo odejde, ubereme ho ze seznamu příkazem o (odešel ze třídy). Naprogramujeme si funkci najdi v seznamu, která prohledá seznam a zjistí, zda se hledaná osoba s daným jménem nachází v místnosti. Dále si uděláme funkci pro tisk celého seznamu a ještě jednu funkci pro úklid, která uvolní dynamicky alokovanou paměť pro celý seznam.
V programu se též naučíme zpracovávat standardní vstup od uživatele.
seznam1.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
/* seznam osob v místnosti
* seznam1.c
* (c) Jirka Chráska 2025; <jirka@lixis.cz>
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// datový typ OSOBA
typedef struct osoba {
char jmeno[128]; // pole pro jméno osoby
struct osoba *next; // ukazatel na další prvek seznamu
} OSOBA;
OSOBA *osoby_zde = NULL; // ukazatel na začátek seznamu osob
// -----------------------------------------------------------------------
/* Přidá osobu na začátek seznamu osob
* OSOBA *o -- ukazatel na začátek seznamu osob
* const char* jmeno -- jméno přidávané osoby
* Vrací ukazatel na nový začátek seznamu nebo NULL pokud je nedostatek paměti.
* Volající musí zajistit uložení vráceného ukazatele.
*/
OSOBA * pridej_osobu(OSOBA *o, const char *jmeno)
{
OSOBA *res;
res = malloc(sizeof(OSOBA));
if( res == NULL ) {
printf("Nedostatek paměti!\n");
return NULL;
}
res->next = o;
strncpy(res->jmeno, jmeno, 127); // omezení kopírování na 127 znaků
return res;
}
// -----------------------------------------------------------------------
/* Pokusí se najít osobu jmeno v seznamu o
* parametr: OSOBA *o - ukazatel na začátek prohledávaného seznamu osob
* parametr: const char *jmeno - hledané jméno
* Vrací prvek seznamu s nalezenou osobou nebo NULL, pokus osoba nebyla nalezena.
*/
OSOBA * najdi_osobu( OSOBA *o, const char *jmeno)
{
for( ; o!=NULL; o = o->next) {
if(strcmp(o->jmeno, jmeno) == 0) { // osoba nalezena
return o;
}
}
return NULL; // osobu jsme nenalezli
}
// -----------------------------------------------------------------------
/* Odebere osobu jmeno ze seznamu o
* parametr: OSOBA **head - adresa ukazatele na začátek seznamu osob
* parametr: const char *jmeno - osoba k odebrání
* Vrací true pokus byla osoba se seznamu odebrána
* nebo false, pokud se nepodařilo osobu nalézt.
* Pokud ostraňujeme první prvek seznamu, do parametru **head se zapíše
* ukazatel na nový počátek seznamu.
*/
bool uber_osobu(OSOBA **head, const char *jmeno)
{
OSOBA *n = NULL; // nalezená osoba
OSOBA *p = NULL; // předchozí
OSOBA *o;
for(o = *head ; o != NULL; o = o->next) {
if( strcmp(o->jmeno, jmeno) == 0 ) {
n = o;
break;
}
p = o;
}
if( n != NULL ) { // nalezli jsme
if( p == NULL ) { // musíme odstranit první prvek seznamu
*head = n->next;
free(o);
} else { // není to 1.prvek seznamu
p->next = n->next;
free(n);
}
return true;
}
return false;
}
// -----------------------------------------------------------------------
/* Zrušení seznamu osob a uvolnění paměti
* parametr: OSOBA *o - ukazatel na začátek seznamu
*/
void zrus_seznam( OSOBA *o )
{
OSOBA *p;
// prvky seznamu budeme odstrňovat od začátku seznamu
// dokud nenarazíme na NULL
for(p=o ; p!=NULL; ) {
o = p->next; // zapamatujeme si ukazatel na další prvek
free(p); // uvolníme paměť
p = o; // posuneme se na další prvek seznamu
}
return;
}
// -----------------------------------------------------------------------
/* Tisk seznamu
* parametr: OSOBA *o očekává ukazatel na začátek seznamu
*/
void tiskni_seznam( OSOBA *o )
{
OSOBA *p;
if( o == NULL ) { // prázdný seznam nebudeme tisknout
printf("Prázdný seznam.\n");
return;
}
// tiskneme od začátku dokud nenarazíme na NULL (konec seznamu)
for(p=o; p!=NULL; p = p->next) {
if( p->next == NULL ) {
printf("'%s' next=NULL;\n",p->jmeno);
}
else {
printf("'%s' next=%p; ",p->jmeno, p->next);
}
}
}
// -----------------------------------------------------------------------
// příkazy programu
typedef enum {
konec = 1,
prisel,
odesel,
najdi,
tiskni,
nevim
} PRIKAZ;
// -----------------------------------------------------------------------
int main( void )
{
char cmd[10];
char jmeno[1024];
PRIKAZ prikaz = konec;
int c;
printf("Evidence osob v místnosti\n");
printf("Příkazy: p<někdo přišel>,\no<někdo odešel>,\nn<najdi osobu>,\n"
"t - tisk seznamu,\nq - konec programu.\n");
do {
memset(cmd,'\0',10);
memset(jmeno,'\0',1024);
// cyklus zpracování vstupu od uživatele
printf("Zadejte příkaz: ");
// přečteme příkaz ze vstupu (jedno písmenko)
c = getchar();
switch(c) {
case 'p': prikaz=prisel; break;
case 'o': prikaz=odesel; break;
case 'n': prikaz=najdi; break;
case 'q': prikaz=konec; break;
case 't': prikaz=tiskni; break;
default: prikaz=nevim; break;
}
// přečteme další vstup pro příkazy, které potřebují jméno
// vstup je omezen na 1023 znaků, aby nám nepřeteklo pole: char vstup[1024]
if( prikaz == prisel || prikaz == odesel || prikaz == najdi ){
char *ptr = &jmeno[0];
int i = 1;
do {
c = getchar();
if( c != '\n' ) { // znak konec řádku budeme zahazovat
*ptr = c;
ptr++;
*ptr = '\0';
i++;
}
} while (! (c=='\n' || c==EOF ) && i<1024) ;
}
if( prikaz == prisel ) {
OSOBA *o = pridej_osobu( osoby_zde, jmeno );
if( o != NULL ) {
osoby_zde = o;
printf("'%s' přišel.\n", jmeno);
} else { // problém, máme nedostatek paměti, končíme program
prikaz = konec;
break;
}
}
if( prikaz == odesel ) {
bool an = uber_osobu( &osoby_zde, jmeno);
if( an ) {
printf("Osoba '%s' odešla.\n", jmeno);
} else {
printf("Nenalezl jsem '%s'\n", jmeno);
}
}
if( prikaz == najdi ) {
OSOBA *o = najdi_osobu( osoby_zde, jmeno );
if( o != NULL ) {
printf("Nalezl jsem '%s' - ukazatel %p\n", jmeno, o);
} else {
printf("Osoba %s nenalezena\n", jmeno);
}
}
if( prikaz == tiskni ) {
// musíme přečíst znaky ze vstupu (vyprázdnit vstup)
while((c=getchar()) != '\n' && c != EOF) {}
tiskni_seznam(osoby_zde);
}
if( prikaz == nevim ) {
// musíme přečíst znaky ze vstupu (vyprázdnit vstup)
while((c=getchar()) != '\n' && c != EOF) {}
printf("Nevím co požadujete. Klávesou q a ENTER ukončíte program.\n");
}
} while (prikaz!=konec);
// úklid dynamicky alokované paměti
zrus_seznam(osoby_zde);
return 0;
}
// -----------------------------------------------------------------------
Použité funkce z C knihovny stdlib:
#include <stdlib.c>
void * malloc( size_t size);
void free( void *_Nullable ptr);Použité funkce z C knihovny string:
#include <string.h>
char *strncpy( char dst[restrict .dsize], const char *restrict src, size_t dsize);
/* funkce strcmp porovná dva řetězce znaků s1 a s2
* Funkce vrací:
* 0 pokud je řetězec s1 stejný jako řetězec s2
* -1 pokud je řetezec s1 lexikálně menší než řetezec s2
* 1 pokud je řetězec s1 lexikálně větší než řetezec s2
*/
int strcmp( const char *s1, const char *s2);Použité funkce z C knihovny stdio:
int printf( const char *restrict format, ...);
int getchar( void );Sestavení programu na Linuxu
gcc -Wall -o seznam1 seznam1.cHotový program spustitelný na Linuxu: seznam1
| V další hodině budete psát samostatně na známky program, který bude umět naplněný seznam osob setřídit podle abecedy. |