-
Notifications
You must be signed in to change notification settings - Fork 1
/
c401.c
executable file
·261 lines (226 loc) · 10.2 KB
/
c401.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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
/* c401.c: **********************************************************}
{* Téma: Rekurzivní implementace operací nad BVS
** Vytvořil: Petr Přikryl, listopad 1994
** Úpravy: Andrea Němcová, prosinec 1995
** Petr Přikryl, duben 1996
** Petr Přikryl, listopad 1997
** Převod do jazyka C: Martin Tuček, říjen 2005
** Úpravy: Bohuslav Křena, listopad 2009
** Upravy: Karel Masarik, rijen 2013
**
** Implementujte rekurzivním způsobem operace nad binárním vyhledávacím
** stromem (BVS; v angličtině BST - Binary Search Tree).
**
** Klíčem uzlu stromu je jeden znak (obecně jím může být cokoliv, podle
** čeho se vyhledává). Užitečným (vyhledávaným) obsahem je zde integer.
** Uzly s menším klíčem leží vlevo, uzly s větším klíčem leží ve stromu
** vpravo. Využijte dynamického přidělování paměti.
** Rekurzivním způsobem implementujte následující funkce:
**
** BSTInit ...... inicializace vyhledávacího stromu
** BSTSearch .... vyhledávání hodnoty uzlu zadaného klíčem
** BSTInsert .... vkládání nové hodnoty
** BSTDelete .... zrušení uzlu se zadaným klíčem
** BSTDispose ... zrušení celého stromu
**
** ADT BVS je reprezentován kořenovým ukazatelem stromu (typ tBSTNodePtr).
** Uzel stromu (struktura typu tBSTNode) obsahuje klíč (typu char), podle
** kterého se ve stromu vyhledává, vlastní obsah uzlu (pro jednoduchost
** typu int) a ukazatel na levý a pravý podstrom (LPtr a RPtr). Přesnou definici typů
** naleznete v souboru c401.h.
**
** Pozor! Je třeba správně rozlišovat, kdy použít dereferenční operátor *
** (typicky při modifikaci) a kdy budeme pracovat pouze se samotným ukazatelem
** (např. při vyhledávání). V tomto příkladu vám napoví prototypy funkcí.
** Pokud pracujeme s ukazatelem na ukazatel, použijeme dereferenci.
**/
#include "c401.h"
int solved;
void BSTInit (tBSTNodePtr *RootPtr) {
/* -------
** Funkce provede počáteční inicializaci stromu před jeho prvním použitím.
**
** Ověřit, zda byl již strom předaný přes RootPtr inicializován, nelze,
** protože před první inicializací má ukazatel nedefinovanou (tedy libovolnou)
** hodnotu. Programátor využívající ADT BVS tedy musí zajistit, aby inicializace
** byla volána pouze jednou, a to před vlastní prací s BVS. Provedení
** inicializace nad neprázdným stromem by totiž mohlo vést ke ztrátě přístupu
** k dynamicky alokované paměti (tzv. "memory leak").
**
** Všimněte si, že se v hlavičce objevuje typ ukazatel na ukazatel.
** Proto je třeba při přiřazení přes RootPtr použít dereferenční operátor *.
** Ten bude použit i ve funkcích BSTDelete, BSTInsert a BSTDispose.
**/
*RootPtr = NULL; //Inicializujeme tak ze Korenovy bude mat hodnotu NULL,nebude mat ziadne kluce, data atd.
return;
}
int BSTSearch (tBSTNodePtr RootPtr, char K, int *Content) {
/* ---------
** Funkce vyhledá uzel v BVS s klíčem K.
**
** Pokud je takový nalezen, vrací funkce hodnotu TRUE a v proměnné Content se
** vrací obsah příslušného uzlu.´Pokud příslušný uzel není nalezen, vrací funkce
** hodnotu FALSE a obsah proměnné Content není definován (nic do ní proto
** nepřiřazujte).
**
** Při vyhledávání v binárním stromu bychom typicky použili cyklus ukončený
** testem dosažení listu nebo nalezení uzlu s klíčem K. V tomto případě ale
** problém řešte rekurzivním volání této funkce, přičemž nedeklarujte žádnou
** pomocnou funkci.
**/
if(RootPtr == NULL) //Ak je korenovy NULL, tak sa nic neda najst, teda vracia FALSE
return FALSE;
else
{
if(RootPtr->Key == K) //Ak sa kluce rovnaju, je zhoda, nasli sme, vrat TRUE a este daj do premennej Content to co si nasiel
{
*Content = RootPtr->BSTNodeCont;
return TRUE;
}
else
{
if(RootPtr->Key > K) //Ak je kluc mensi tak sa posun dolava a rekurzivne volaj tuto funkciu...vlastne az potial ked nenajdes zhodu
{
RootPtr=RootPtr->LPtr;
return BSTSearch(RootPtr, K, Content);
}
else //Ak teda (RootPtr->Key < K) -->> Ak je kluc vacsi tak sa posun dolava a rekurzivne volaj tuto funkciu...vlastne az potial ked nenajdes zhodu
{
RootPtr=RootPtr->RPtr;
return BSTSearch(RootPtr, K, Content);
}
}
}
}
void BSTInsert (tBSTNodePtr* RootPtr, char K, int Content) {
/* ---------
** Vloží do stromu RootPtr hodnotu Content s klíčem K.
**
** Pokud již uzel se zadaným klíčem ve stromu existuje, bude obsah uzlu
** s klíčem K nahrazen novou hodnotou. Pokud bude do stromu vložen nový
** uzel, bude vložen vždy jako list stromu.
**
** Funkci implementujte rekurzivně. Nedeklarujte žádnou pomocnou funkci.
**
** Rekurzivní implementace je méně efektivní, protože se při každém
** rekurzivním zanoření ukládá na zásobník obsah uzlu (zde integer).
** Nerekurzivní varianta by v tomto případě byla efektivnější jak z hlediska
** rychlosti, tak z hlediska paměťových nároků. Zde jde ale o školní
** příklad, na kterém si chceme ukázat eleganci rekurzivního zápisu.
**/
if (*RootPtr == NULL) //Vlozime do prazdneho stromu
{
tBSTNodePtr PomVar = malloc(sizeof(struct tBSTNode));
if(PomVar == NULL) //Ak sa nepodari alokacia tak nepokracuj, vyjdi z funkcie
return;
else if(PomVar != NULL) //Ak sa podari, tak do prazdneho stromu priradime to co sme alokovali, a predali ako parametry funkcie
{
(*RootPtr) = PomVar;
(*RootPtr)->Key = K;
(*RootPtr)->BSTNodeCont = Content;
(*RootPtr)->LPtr = NULL; //Co lavych a pravych uzlov budu mat hodnotu NULL, lebo niesu vytvorene
(*RootPtr)->RPtr = NULL;
}
}
else
{
if((*RootPtr)->Key > K) //Ak strom nieje prazdny tak rekurzivne volam tuto funkciu, pricom "korenovy" pointer bude zmeneny, bud nalavo alebo napravo, podla kluca
BSTInsert(&(*RootPtr)->LPtr, K, Content);
else if((*RootPtr)->Key < K)
BSTInsert(&(*RootPtr)->RPtr, K, Content);
else if((*RootPtr)->Key == K) //Ak sa kluce rovnaju, tak iba prepis obsah uzlu
(*RootPtr)->BSTNodeCont = Content;
}
}
void ReplaceByRightmost (tBSTNodePtr PtrReplaced, tBSTNodePtr *RootPtr) {
/* ------------------
** Pomocná funkce pro vyhledání, přesun a uvolnění nejpravějšího uzlu.
**
** Ukazatel PtrReplaced ukazuje na uzel, do kterého bude přesunuta hodnota
** nejpravějšího uzlu v podstromu, který je určen ukazatelem RootPtr.
** Předpokládá se, že hodnota ukazatele RootPtr nebude NULL (zajistěte to
** testováním před volání této funkce). Tuto funkci implementujte rekurzivně.
**
** Tato pomocná funkce bude použita dále. Než ji začnete implementovat,
** přečtěte si komentář k funkci BSTDelete().
**/
if((*RootPtr)->RPtr == NULL) //Ako 2. parameter sme dostali lavy uzol, a teraz hladame najpravsi. Najdeme ho tak, ze ukazatel na jeho pravy uzol bude NULL, cize je najpravsi
{
tBSTNodePtr PomUk = (*RootPtr); //vytvorime si novy pomocny ukazatel, priradime donho koren
PtrReplaced->Key = (*RootPtr)->Key; //korenovy kluc aj obsah dame do 1.parametru, teda v podstate nahradime najpravsi co sme nasli za ten co neskor zrusime.
PtrReplaced->BSTNodeCont = (*RootPtr)->BSTNodeCont;
(*RootPtr) = PomUk->LPtr;
free(PomUk); //zrusime najpravsi. uz nieje treba, presunul sa do toho ktory budeme rusit
}
else
ReplaceByRightmost(PtrReplaced, &(*RootPtr)->RPtr); //Popisane v 1. riadku, rekurzivne volam tuto funkciu a parameter bude vzdy dalsi pravy uzol (bude sa ukladat ako root)
}
void BSTDelete (tBSTNodePtr *RootPtr, char K) {
/* ---------
** Zruší uzel stromu, který obsahuje klíč K.
**
** Pokud uzel se zadaným klíčem neexistuje, nedělá funkce nic.
** Pokud má rušený uzel jen jeden podstrom, pak jej zdědí otec rušeného uzlu.
** Pokud má rušený uzel oba podstromy, pak je rušený uzel nahrazen nejpravějším
** uzlem levého podstromu. Pozor! Nejpravější uzel nemusí být listem.
**
** Tuto funkci implementujte rekurzivně s využitím dříve deklarované
** pomocné funkce ReplaceByRightmost.
**/
if((*RootPtr) == NULL) //Korenovy je prazdny, nerob nic vyjdi z funkcie
return;
else
{
if((*RootPtr)->Key < K) //musime najst ten co chceme rusit, najdeme podla kluca, princip podobny ako v BSTSearch, porovnavanim klucov.
{
BSTDelete(&(*RootPtr)->RPtr, K); //ak je kluc vacsi tak zavolame rekurzivne tuto funkciu a korenovy bude ten co sa nachadzal napravo
}
else if((*RootPtr)->Key > K)
{
BSTDelete(&(*RootPtr)->LPtr, K); //symetricke s ((*RootPtr)->Key < K)
}
else if((*RootPtr)->Key == K) //kluce sa zhoduju, nasli sme prvok ktory ideme odstranit
{
tBSTNodePtr PomUk = (*RootPtr); //definujeme si pomocnu premennu a vlozime do nej sucasny korenovy uzol
if((*RootPtr)->RPtr == NULL) //Ak existuje iba jeden podstrom, lavy, tak ho zdedi otec ruseneho , a nasledne mozeme rusit
{
(*RootPtr) = PomUk->LPtr;
free(PomUk);
}
else if((*RootPtr)->LPtr == NULL) //symetricke k predchadzajucej podmienke
{
(*RootPtr) = PomUk->RPtr;
free(PomUk);
}
else
ReplaceByRightmost((*RootPtr), &(*RootPtr)->LPtr); //Ak ma ruseny 2 podstromy, tak sa postupuje trosku inak, vyhlada sa najpravsi z laveho podstromu a ten sa nahradi za ruseny
}
}
}
void BSTDispose (tBSTNodePtr *RootPtr) {
/* ----------
** Zruší celý binární vyhledávací strom a korektně uvolní paměť.
**
** Po zrušení se bude BVS nacházet ve stejném stavu, jako se nacházel po
** inicializaci. Tuto funkci implementujte rekurzivně bez deklarování pomocné
** funkce.
**/
if((*RootPtr) == NULL) //Ak je strom prazdny tak sa nic nedeje
return;
else //ale ak nieje, tak ideme rusit :)
{
if((*RootPtr)->LPtr != NULL) //ak ma lavy podstrom tak rekurzivne zavolame tuto funkciu, pricom bude ako parameter lavy podstrom, teda koren sa posunie dolava
{
(*RootPtr)=(*RootPtr)->LPtr;
BSTDispose(RootPtr);
}
else if(((*RootPtr)->RPtr != NULL)) //symetricke s predchadzajucou podmienkou
{
(*RootPtr)=(*RootPtr)->RPtr;
BSTDispose(RootPtr);
}
}
free(*RootPtr); //Korenovy (v tomto pripade korenove) sa uvolnuju rekurzivne..pokial uz nieje ziadny podstrom
(*RootPtr) = NULL; //nakoniec dame strom do pociatocneho stavu, teda ako sme ho inicializovali. Korenovy = NULL.
}
/* konec c401.c */