0%

《C Primer Plus 第六版》读书笔记 - 第十七章

  • 高级数据表示

第17章 高级数据表示

17.3 抽象数据类型(ADT)

计算机科学领域已开发了一种定义新类型的好方法,用3个步骤完成从抽象到具体的过程。

  1. 提供类型属性和相关操作的抽象描述,这些描述既不能依赖特定的实现,也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型(ADT)。
  2. 开发一个实现ADT的编程接口。也就是说,指明如何储存数据和执行所需操作的函数。例如在C中,可以提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于作用于C基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程
  3. 编写代码实现接口。这一步至关重要,但是使用该新类型的程序员无需了解具体的实现细节。

17.3.2 建立接口

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
/* list.h -- header file for a simple list type */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99 feature */

/* program-specific declarations */

#define TSIZE 45 /* size of array to hold title */
struct film
{
char title[TSIZE];
int rating;
};

/* general type definitions */

typedef struct film Item;

typedef struct node
{
Item item;
struct node * next;
} Node;

typedef Node * List;

/* function prototypes */

/* operation: initialize a list */
/* preconditions: plist points to a list */
/* postconditions: the list is initialized to empty */
void InitializeList(List * plist);

/* operation: determine if list is empty */
/* plist points to an initialized list */
/* postconditions: function returns True if list is empty */
/* and returns False otherwise */
bool ListIsEmpty(const List *plist);

/* operation: determine if list is full */
/* plist points to an initialized list */
/* postconditions: function returns True if list is full */
/* and returns False otherwise */
bool ListIsFull(const List *plist);

/* operation: determine number of items in list */
/* plist points to an initialized list */
/* postconditions: function returns number of items in list */
unsigned int ListItemCount(const List *plist);

/* operation: add item to end of list */
/* preconditions: item is an item to be added to list */
/* plist points to an initialized list */
/* postconditions: if possible, function adds item to end */
/* of list and returns True; otherwise the */
/* function returns False */
bool AddItem(Item item, List * plist);

/* operation: apply a function to each item in list */
/* plist points to an initialized list */
/* pfun points to a function that takes an */
/* Item argument and has no return value */
/* postcondition: the function pointed to by pfun is */
/* executed once for each item in the list */
void Traverse (const List *plist, void (* pfun)(Item item) );

/* operation: free allocated memory, if any */
/* plist points to an initialized list */
/* postconditions: any memory allocated for the list is freed */
/* and the list is set to empty */
void EmptyTheList(List * plist);

#endif

17.3.3 使用接口

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
/* films3.c -- using an ADT-style linked list */
/* compile with list.c */
#include <stdio.h>
#include <stdlib.h> /* prototype for exit() */
#include "list.h" /* defines List, Item */
void showmovies(Item item);
char * s_gets(char * st, int n);
int main(void)
{
List movies;
Item temp;


/* initialize */
InitializeList(&movies);
if (ListIsFull(&movies))
{
fprintf(stderr,"No memory available! Bye!\n");
exit(1);
}

/* gather and store */
puts("Enter first movie title:");
while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0')
{
puts("Enter your rating <0-10>:");
scanf("%d", &temp.rating);
while(getchar() != '\n')
continue;
if (AddItem(temp, &movies)==false)
{
fprintf(stderr,"Problem allocating memory\n");
break;
}
if (ListIsFull(&movies))
{
puts("The list is now full.");
break;
}
puts("Enter next movie title (empty line to stop):");
}

/* display */
if (ListIsEmpty(&movies))
printf("No data entered. ");
else
{
printf ("Here is the movie list:\n");
Traverse(&movies, showmovies);
}
printf("You entered %d movies.\n", ListItemCount(&movies));


/* clean up */
EmptyTheList(&movies);
printf("Bye!\n");

return 0;
}

void showmovies(Item item)
{
printf("Movie: %s Rating: %d\n", item.title,
item.rating);
}

char * s_gets(char * st, int n)
{
char * ret_val;
char * find;

ret_val = fgets(st, n, stdin);
if (ret_val)
{
find = strchr(st, '\n'); // look for newline
if (find) // if the address is not NULL,
*find = '\0'; // place a null character there
else
while (getchar() != '\n')
continue; // dispose of rest of line
}
return ret_val;
}

17.3.4 实现接口

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
/* list.c -- functions supporting list operations */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

/* local function prototype */
static void CopyToNode(Item item, Node * pnode);

/* interface functions */
/* set the list to empty */
void InitializeList(List * plist)
{
* plist = NULL;
}

/* returns true if list is empty */
bool ListIsEmpty(const List * plist)
{
if (*plist == NULL)
return true;
else
return false;
}

/* returns true if list is full */
bool ListIsFull(const List * plist)
{
Node * pt;
bool full;

pt = (Node *) malloc(sizeof(Node));
if (pt == NULL)
full = true;
else
full = false;
free(pt);

return full;
}

/* returns number of nodes */
unsigned int ListItemCount(const List * plist)
{
unsigned int count = 0;
Node * pnode = *plist; /* set to start of list */

while (pnode != NULL)
{
++count;
pnode = pnode->next; /* set to next node */
}

return count;
}

/* creates node to hold item and adds it to the end of */
/* the list pointed to by plist (slow implementation) */
bool AddItem(Item item, List * plist)
{
Node * pnew;
Node * scan = *plist;

pnew = (Node *) malloc(sizeof(Node));
if (pnew == NULL)
return false; /* quit function on failure */

CopyToNode(item, pnew);
pnew->next = NULL;
if (scan == NULL) /* empty list, so place */
*plist = pnew; /* pnew at head of list */
else
{
while (scan->next != NULL)
scan = scan->next; /* find end of list */
scan->next = pnew; /* add pnew to end */
}

return true;
}

/* visit each node and execute function pointed to by pfun */
void Traverse (const List * plist, void (* pfun)(Item item) )
{
Node * pnode = *plist; /* set to start of list */

while (pnode != NULL)
{
(*pfun)(pnode->item); /* apply function to item */
pnode = pnode->next; /* advance to next item */
}
}

/* free memory allocated by malloc() */
/* set list pointer to NULL */
void EmptyTheList(List * plist)
{
Node * psave;

while (*plist != NULL)
{
psave = (*plist)->next; /* save address of next node */
free(*plist); /* free current node */
*plist = psave; /* advance to next node */
}
}

/* local function definition */
/* copies an item into a node */
static void CopyToNode(Item item, Node * pnode)
{
pnode->item = item; /* structure copy */
}

17.4 队列ADT

17.4.3 实现接口数据表示

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
/* queue.h -- interface for a queue */
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>

// INSERT ITEM TYPE HERE
// FOR EXAMPLE,
//typedef int Item; // for use_q.c
// OR typedef struct item {int gumption; int charisma;} Item;
// OR (for mall.c)
/**/
typedef struct item
{
long arrive; // the time when a customer joins the queue
int processtime; // the number of consultation minutes desired
} Item;
/**/

#define MAXQUEUE 10

typedef struct node
{
Item item;
struct node * next;
} Node;

typedef struct queue
{
Node * front; /* pointer to front of queue */
Node * rear; /* pointer to rear of queue */
int items; /* number of items in queue */
} Queue;

/* operation: initialize the queue */
/* precondition: pq points to a queue */
/* postcondition: queue is initialized to being empty */
void InitializeQueue(Queue * pq);

/* operation: check if queue is full */
/* precondition: pq points to previously initialized queue */
/* postcondition: returns True if queue is full, else False */
bool QueueIsFull(const Queue * pq);

/* operation: check if queue is empty */
/* precondition: pq points to previously initialized queue */
/* postcondition: returns True if queue is empty, else False */
bool QueueIsEmpty(const Queue *pq);

/* operation: determine number of items in queue */
/* precondition: pq points to previously initialized queue */
/* postcondition: returns number of items in queue */
int QueueItemCount(const Queue * pq);

/* operation: add item to rear of queue */
/* precondition: pq points to previously initialized queue */
/* item is to be placed at rear of queue */
/* postcondition: if queue is not empty, item is placed at */
/* rear of queue and function returns */
/* True; otherwise, queue is unchanged and */
/* function returns False */
bool EnQueue(Item item, Queue * pq);

/* operation: remove item from front of queue */
/* precondition: pq points to previously initialized queue */
/* postcondition: if queue is not empty, item at head of */
/* queue is copied to *pitem and deleted from */
/* queue, and function returns True; if the */
/* operation empties the queue, the queue is */
/* reset to empty. If the queue is empty to */
/* begin with, queue is unchanged and the */
/* function returns False */
bool DeQueue(Item *pitem, Queue * pq);

/* operation: empty the queue */
/* precondition: pq points to previously initialized queue */
/* postconditions: the queue is empty */
void EmptyTheQueue(Queue * pq);

#endif

实现接口函数

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
/* queue.c -- the Queue type implementation*/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/* local functions */
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node * pn, Item * pi);

void InitializeQueue(Queue * pq)
{
pq->front = pq->rear = NULL;
pq->items = 0;
}

bool QueueIsFull(const Queue * pq)
{
return pq->items == MAXQUEUE;
}

bool QueueIsEmpty(const Queue * pq)
{
return pq->items == 0;
}

int QueueItemCount(const Queue * pq)
{
return pq->items;
}

bool EnQueue(Item item, Queue * pq)
{
Node * pnew;

if (QueueIsFull(pq))
return false;
pnew = (Node *) malloc( sizeof(Node));
if (pnew == NULL)
{
fprintf(stderr,"Unable to allocate memory!\n");
exit(1);
}
CopyToNode(item, pnew);
pnew->next = NULL;
if (QueueIsEmpty(pq))
pq->front = pnew; /* item goes to front */
else
pq->rear->next = pnew; /* link at end of queue */
pq->rear = pnew; /* record location of end */
pq->items++; /* one more item in queue */

return true;
}

bool DeQueue(Item * pitem, Queue * pq)
{
Node * pt;

if (QueueIsEmpty(pq))
return false;
CopyToItem(pq->front, pitem);
pt = pq->front;
pq->front = pq->front->next;
free(pt);
pq->items--;
if (pq->items == 0)
pq->rear = NULL;

return true;
}

/* empty the queue */
void EmptyTheQueue(Queue * pq)
{
Item dummy;
while (!QueueIsEmpty(pq))
DeQueue(&dummy, pq);
}

/* Local functions */

static void CopyToNode(Item item, Node * pn)
{
pn->item = item;
}

static void CopyToItem(Node * pn, Item * pi)
{
*pi = pn->item;
}

17.4.4 测试队列

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
/* use_q.c -- driver testing the Queue interface */
/* compile with queue.c */
#include <stdio.h>
#include "queue.h" /* defines Queue, Item */

int main(void)
{
Queue line;
Item temp;
char ch;

InitializeQueue(&line);
puts("Testing the Queue interface. Type a to add a value,");
puts("type d to delete a value, and type q to quit.");
while ((ch = getchar()) != 'q')
{
if (ch != 'a' && ch != 'd') /* ignore other input */
continue;
if ( ch == 'a')
{
printf("Integer to add: ");
scanf("%d", &temp);
if (!QueueIsFull(&line))
{
printf("Putting %d into queue\n", temp);
EnQueue(temp,&line);
}
else
puts("Queue is full!");
}
else
{
if (QueueIsEmpty(&line))
puts("Nothing to delete!");
else
{
DeQueue(&temp,&line);
printf("Removing %d from queue\n", temp);
}
}
printf("%d items in queue\n", QueueItemCount(&line));
puts("Type a to add, d to delete, q to quit:");
}
EmptyTheQueue(&line);
puts("Bye!");

return 0;
}

17.7 二叉查找树

17.7.2 二叉查找树接口

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
/* tree.h -- binary search tree                          */
/* no duplicate items are allowed in this tree */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

/* redefine Item as appropriate */
#define SLEN 20
typedef struct item
{
char petname[SLEN];
char petkind[SLEN];
} Item;

#define MAXITEMS 10

typedef struct trnode
{
Item item;
struct trnode * left; /* pointer to right branch */
struct trnode * right; /* pointer to left branch */
} Trnode;

typedef struct tree
{
Trnode * root; /* pointer to root of tree */
int size; /* number of items in tree */
} Tree;

/* function prototypes */

/* operation: initialize a tree to empty */
/* preconditions: ptree points to a tree */
/* postconditions: the tree is initialized to empty */
void InitializeTree(Tree * ptree);

/* operation: determine if tree is empty */
/* preconditions: ptree points to a tree */
/* postconditions: function returns true if tree is */
/* empty and returns false otherwise */
bool TreeIsEmpty(const Tree * ptree);

/* operation: determine if tree is full */
/* preconditions: ptree points to a tree */
/* postconditions: function returns true if tree is */
/* full and returns false otherwise */
bool TreeIsFull(const Tree * ptree);

/* operation: determine number of items in tree */
/* preconditions: ptree points to a tree */
/* postconditions: function returns number of items in */
/* tree */
int TreeItemCount(const Tree * ptree);

/* operation: add an item to a tree */
/* preconditions: pi is address of item to be added */
/* ptree points to an initialized tree */
/* postconditions: if possible, function adds item to */
/* tree and returns true; otherwise, */
/* the function returns false */
bool AddItem(const Item * pi, Tree * ptree);

/* operation: find an item in a tree */
/* preconditions: pi points to an item */
/* ptree points to an initialized tree */
/* postconditions: function returns true if item is in */
/* tree and returns false otherwise */
bool InTree(const Item * pi, const Tree * ptree);

/* operation: delete an item from a tree */
/* preconditions: pi is address of item to be deleted */
/* ptree points to an initialized tree */
/* postconditions: if possible, function deletes item */
/* from tree and returns true; */
/* otherwise the function returns false*/
bool DeleteItem(const Item * pi, Tree * ptree);

/* operation: apply a function to each item in */
/* the tree */
/* preconditions: ptree points to a tree */
/* pfun points to a function that takes*/
/* an Item argument and has no return */
/* value */
/* postcondition: the function pointed to by pfun is */
/* executed once for each item in tree */
void Traverse (const Tree * ptree, void (* pfun)(Item item));

/* operation: delete everything from a tree */
/* preconditions: ptree points to an initialized tree */
/* postconditions: tree is empty */
void DeleteAll(Tree * ptree);

#endif

17.7.3 二叉查找树的实现

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
261
262
263
264
265
266
/* tree.c -- tree support functions */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

/* local data type */
typedef struct pair {
Trnode * parent;
Trnode * child;
} Pair;

/* protototypes for local functions */
static Trnode * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode (Trnode * new_node, Trnode * root);
static void InOrder(const Trnode * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode * ptr);

/* function definitions */
void InitializeTree(Tree * ptree)
{
ptree->root = NULL;
ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
if (ptree->root == NULL)
return true;
else
return false;
}

bool TreeIsFull(const Tree * ptree)
{
if (ptree->size == MAXITEMS)
return true;
else
return false;
}

int TreeItemCount(const Tree * ptree)
{
return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
Trnode * new_node;

if (TreeIsFull(ptree))
{
fprintf(stderr,"Tree is full\n");
return false; /* early return */
}
if (SeekItem(pi, ptree).child != NULL)
{
fprintf(stderr, "Attempted to add duplicate item\n");
return false; /* early return */
}
new_node = MakeNode(pi); /* points to new node */
if (new_node == NULL)
{
fprintf(stderr, "Couldn't create node\n");
return false; /* early return */
}
/* succeeded in creating a new node */
ptree->size++;

if (ptree->root == NULL) /* case 1: tree is empty */
ptree->root = new_node; /* new node is tree root */
else /* case 2: not empty */
AddNode(new_node,ptree->root); /* add node to tree */

return true; /* successful return */
}

bool InTree(const Item * pi, const Tree * ptree)
{
return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item * pi, Tree * ptree)
{
Pair look;

look = SeekItem(pi, ptree);
if (look.child == NULL)
return false;

if (look.parent == NULL) /* delete root item */
DeleteNode(&ptree->root);
else if (look.parent->left == look.child)
DeleteNode(&look.parent->left);
else
DeleteNode(&look.parent->right);
ptree->size--;

return true;
}

void Traverse (const Tree * ptree, void (* pfun)(Item item))
{

if (ptree != NULL)
InOrder(ptree->root, pfun);
}

void DeleteAll(Tree * ptree)
{
if (ptree != NULL)
DeleteAllNodes(ptree->root);
ptree->root = NULL;
ptree->size = 0;
}


/* local functions */
static void InOrder(const Trnode * root, void (* pfun)(Item item))
{
if (root != NULL)
{
InOrder(root->left, pfun);
(*pfun)(root->item);
InOrder(root->right, pfun);
}
}

static void DeleteAllNodes(Trnode * root)
{
Trnode * pright;

if (root != NULL)
{
pright = root->right;
DeleteAllNodes(root->left);
free(root);
DeleteAllNodes(pright);
}
}

static void AddNode (Trnode * new_node, Trnode * root)
{
if (ToLeft(&new_node->item, &root->item))
{
if (root->left == NULL) /* empty subtree */
root->left = new_node; /* so add node here */
else
AddNode(new_node, root->left);/* else process subtree*/
}
else if (ToRight(&new_node->item, &root->item))
{
if (root->right == NULL)
root->right = new_node;
else
AddNode(new_node, root->right);
}
else /* should be no duplicates */
{
fprintf(stderr,"location error in AddNode()\n");
exit(1);
}
}

static bool ToLeft(const Item * i1, const Item * i2)
{
int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
return true;
else if (comp1 == 0 &&
strcmp(i1->petkind, i2->petkind) < 0 )
return true;
else
return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
int comp1;

if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
return true;
else if (comp1 == 0 &&
strcmp(i1->petkind, i2->petkind) > 0 )
return true;
else
return false;
}

static Trnode * MakeNode(const Item * pi)
{
Trnode * new_node;

new_node = (Trnode *) malloc(sizeof(Trnode));
if (new_node != NULL)
{
new_node->item = *pi;
new_node->left = NULL;
new_node->right = NULL;
}

return new_node;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
Pair look;
look.parent = NULL;
look.child = ptree->root;

if (look.child == NULL)
return look; /* early return */

while (look.child != NULL)
{
if (ToLeft(pi, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->left;
}
else if (ToRight(pi, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->right;
}
else /* must be same if not to left or right */
break; /* look.child is address of node with item */
}

return look; /* successful return */
}

static void DeleteNode(Trnode **ptr)
/* ptr is address of parent member pointing to target node */
{
Trnode * temp;

if ( (*ptr)->left == NULL)
{
temp = *ptr;
*ptr = (*ptr)->right;
free(temp);
}
else if ( (*ptr)->right == NULL)
{
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
}
else /* deleted node has two children */
{
/* find where to reattach right subtree */
for (temp = (*ptr)->left; temp->right != NULL;
temp = temp->right)
continue;
temp->right = (*ptr)->right;
temp = *ptr;
*ptr =(*ptr)->left;
free(temp);
}
}

17.7.4 使用二叉树

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
/* petclub.c -- use a binary search tree */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpet(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);
char * s_gets(char * st, int n);

int main(void)
{
Tree pets;
char choice;

InitializeTree(&pets);
while ((choice = menu()) != 'q')
{
switch (choice)
{
case 'a' : addpet(&pets);
break;
case 'l' : showpets(&pets);
break;
case 'f' : findpet(&pets);
break;
case 'n' : printf("%d pets in club\n",
TreeItemCount(&pets));
break;
case 'd' : droppet(&pets);
break;
default : puts("Switching error");
}
}
DeleteAll(&pets);
puts("Bye.");

return 0;
}

char menu(void)
{
int ch;

puts("Nerfville Pet Club Membership Program");
puts("Enter the letter corresponding to your choice:");
puts("a) add a pet l) show list of pets");
puts("n) number of pets f) find pets");
puts("d) delete a pet q) quit");
while ((ch = getchar()) != EOF)
{
while (getchar() != '\n') /* discard rest of line */
continue;
ch = tolower(ch);
if (strchr("alrfndq",ch) == NULL)
puts("Please enter an a, l, f, n, d, or q:");
else
break;
}
if (ch == EOF) /* make EOF cause program to quit */
ch = 'q';

return ch;
}

void addpet(Tree * pt)
{
Item temp;

if (TreeIsFull(pt))
puts("No room in the club!");
else
{
puts("Please enter name of pet:");
s_gets(temp.petname,SLEN);
puts("Please enter pet kind:");
s_gets(temp.petkind,SLEN);
uppercase(temp.petname);
uppercase(temp.petkind);
AddItem(&temp, pt);
}
}

void showpets(const Tree * pt)
{
if (TreeIsEmpty(pt))
puts("No entries!");
else
Traverse(pt, printitem);
}

void printitem(Item item)
{
printf("Pet: %-19s Kind: %-19s\n", item.petname,
item.petkind);
}

void findpet(const Tree * pt)
{
Item temp;

if (TreeIsEmpty(pt))
{
puts("No entries!");
return; /* quit function if tree is empty */
}

puts("Please enter name of pet you wish to find:");
s_gets(temp.petname, SLEN);
puts("Please enter pet kind:");
s_gets(temp.petkind, SLEN);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s ", temp.petname, temp.petkind);
if (InTree(&temp, pt))
printf("is a member.\n");
else
printf("is not a member.\n");
}

void droppet(Tree * pt)
{
Item temp;

if (TreeIsEmpty(pt))
{
puts("No entries!");
return; /* quit function if tree is empty */
}

puts("Please enter name of pet you wish to delete:");
s_gets(temp.petname, SLEN);
puts("Please enter pet kind:");
s_gets(temp.petkind, SLEN);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s ", temp.petname, temp.petkind);
if (DeleteItem(&temp, pt))
printf("is dropped from the club.\n");
else
printf("is not a member.\n");
}

void uppercase(char * str)
{
while (*str)
{
*str = toupper(*str);
str++;
}
}
char * s_gets(char * st, int n)
{
char * ret_val;
char * find;

ret_val = fgets(st, n, stdin);
if (ret_val)
{
find = strchr(st, '\n'); // look for newline
if (find) // if the address is not NULL,
*find = '\0'; // place a null character there
else
while (getchar() != '\n')
continue; // dispose of rest of line
}
return ret_val;
}