Systemnahe Programmierung in C: Verändern von binären Bäumen
| Systemnahe Programmierung in C: Verändern von binären Bäumen |
|
|
1#include "Set.h"
2
3#include <stdlib.h>
4#include <stdio.h>
5#include <assert.h>
6
7/*--------------------*/
8
9/* ... */
10
11/*--------------------*/
12
13Set
14insertElem(Element e, Set s)
15{
16 if (isEmptySet(s))
17 return mkOneElementSet(e);
18
19 switch (compare(e, s->info))
20 {
21 case -1:
22 s->l = insertElem(e, s->l);
23 break;
24 case 0:
25 /* nothing to do */
26 break;
27 case +1:
28 s->r = insertElem(e, s->r);
29 break;
30 }
31
32 return s;
33}
34
35/*--------------------*/
36
37static Set
38removeRoot(Set s);
39
40Set
41removeElem(Element e, Set s)
42{
43 if (isEmptySet(s))
44 return s; /* or: return mkEmptySet() */
45
46 switch (compare(e, s->info))
47 {
48 case -1:
49 s->l = removeElem(e, s->l);
50 break;
51 case 0:
52 s = removeRoot(s);
53 break;
54 case +1:
55 s->r = removeElem(e, s->r);
56 break;
57 }
58
59 return s;
60}
61
62/*--------------------*/
|
|
1Set
2Set
3insertElem(Element e, Set s)
4removeElem(Element e, Set s)
5{
6{
7 if (isEmptySet(s))
8 if (isEmptySet(s))
9 return mkOneElementSet(e);
10 return s; /* or: return mkEmptySet() */
11
12
13 switch (compare(e, s->info))
14 switch (compare(e, s->info))
15 {
16 {
17 case -1:
18 case -1:
19 s->l = insertElem(e, s->l);
20 s->l = removeElem(e, s->l);
21 break;
22 break;
23 case 0:
24 case 0:
25 /* nothing to do */
26 s = removeRoot(s);
27 break;
28 break;
29 case +1:
30 case +1:
31 s->r = insertElem(e, s->r);
32 s->r = removeElem(e, s->r);
33 break;
34 break;
35 }
36 }
37
38
39 return s;
40 return s;
41}
42}
43
44
45
|
|
1#include "Set.c"
2
3typedef Set (*ProcessEmpty)(Element e);
4typedef Set (*ProcessNode )(Set s);
5
6Set
7change (Element e, Set s, ProcessEmpty notFound, ProcessNode found )
8{
9 if ( isEmptySet(s) )
10 return notFound(e);
11
12 switch ( compare(e, s->info) )
13 {
14 case -1:
15 s->l = change(e, s->l, notFound, found);
16 break;
17 case 0:
18 s = found(s);
19 break;
20 case +1:
21 s->r = change(e, s->r, notFound, found);
22 break;
23 }
24
25 return s;
26}
27
28/* ---------------------------------------- */
29
30static Set
31idSet(Set s) { return s; }
32
33Set
34insertElem2(Element e, Set s)
35{
36 return change(e, s, mkOneElementSet, idSet);
37}
38
39/* ---------------------------------------- */
40
41static Set
42mkEmptySet1(Element e) { return mkEmptySet(); }
43
44Set
45removeElem2(Element e, Set s)
46{
47 return change(e, s, mkEmptySet1, removeRoot);
48}
49
|
| Letzte Änderung: 11.01.2007 | © Prof. Dr. Uwe Schmidt |
