修改程序清单17.2，使其既能以正序又能以逆序显示电影列表。一种方法修改链表定义以使链表能被双向遍历；另一种方法是使用递归。
#include#include #include #define TSIZE 45typedef struct film { char title[TSIZE]; int rating; struct film * next; struct film * up;}Film;void positive(Film * p); //正序显示void reversed(Film * p); //逆序显示void recursion(Film * p); //逆序递归显示void empty(Film * p);int main(void){ Film * head = NULL; //指向链表头结点的指针，始终指向头结点保持不变 Film * current; //动态内存分配的地址。 Film * prev; //尾结点，可变，每次用来更新结构体内指针变量的值和自身的值。 char input[TSIZE]; puts("Enter first movie title: "); while (gets(input) != NULL && input[0] != '\0') { current = (Film *)malloc(sizeof(Film)); /* if ((current = (Film *)malloc(sizeof(Film))) == NULL) { printf("内存分配失败：\n"); exit(EXIT_FAILURE); } */ if (head == NULL) { head = current; current->up = NULL; } else { prev->next = current; current->up = prev; } current->next = NULL; strcpy(current->title, input); puts("Enter your rating <0-10>: "); scanf("%d", ¤t->rating); while (getchar() != '\n') continue; puts("Enter next movie title (empty line to stop): "); prev = current; } if (head == NULL) printf("No data entered. "); else { printf("Here is the movie list: \n"); positive(head); printf("\n"); printf("Here is the movie list: \n"); reversed(prev); printf("\n"); printf("Here is the movie list: \n"); recursion(head); } printf("Bye!\n"); return 0;}void positive(Film * p){ while (p != NULL) { printf("Movie: %s Rating: %d\n", p->title, p->rating); p = p->next; }}void reversed(Film * p){ while (p != NULL) { printf("Movie: %s Rating: %d\n", p->title, p->rating); p = p->up; }}void recursion(Film * p){ if (p->next != NULL) recursion(p->next); printf("Movie: %s Rating: %d\n", p->title, p->rating);}void empty(Film * p){ Film * temp; while (p != NULL) { temp = p; p = p->next;; free(temp); }}
2.假设list.h(程序清单17.3)如下定义列表：
typedef struct list
{
Node * nead; /*指向列表首*/
Node * end; /*指向列表尾*/
}List;
根据这个定义，重写list.c（程序清单17.5）函数，并用films3.c（程序清单17.4）测试结果代码。
/* 重写list.c */#include#include #include "list_17_3.h"static void CopyToNode(Item item, Node * pnode);void InitializeList(List * plist){ //plist = NULL; //Error plist是一个变量地址，只能改变变量的值 ，不能改变地址。 plist->head = NULL; plist->end = NULL;}bool ListIsEmpty(const List * plist){ if (plist->head == NULL) return true; else return false;}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;}unsigned int ListItemCount(const List * plist){ unsigned int count = 0; Node * pnode = plist->head; while (pnode != NULL) { ++count; pnode = pnode->next; } return count;}bool AddItem(Item item, List * plist){ Node * pnew; Node * scan = plist->head; pnew = (Node *)malloc(sizeof(Node)); if (pnew == NULL) return false; CopyToNode(item, pnew); pnew->next = NULL; if (scan == NULL) plist->head = pnew; else plist->end->next = pnew; plist->end = pnew; return true;}void Traverse(const List * plist, void(*pfun)(Item item)){ Node * pnode = plist->head; while (pnode != NULL) { (*pfun)(pnode->item); pnode = pnode->next; }}void EmptyTheList(List * plist){ Node * psave; while (plist->head != NULL) { psave = plist->head->next; free(plist->head); plist->head = psave; }}static void CopyToNode(Item item, Node * pnode){ pnode->item = item; }
3.假设list.h(程序清单17.3)如下定义列表：
#define MAXZIZE 100
typedef struct list
{
Item entries[MAXAIZE]; /*项目数组*/
int items; /*列表中项目的个数*/
}List;
根据这个定义，重写list.c(程序清单17.5)函数，并用films3.c（程序清单17.4）测试结果代码
/* 重写list.c */#include#include #include "list_17_3.h"static void CopyToNode(Item item, Item * pnode);void InitializeList(List * plist){ plist->items = 0;}bool ListIsEmpty(const List * plist){ if (plist->items == 0) return true; else return false;}bool ListIsFull(const List * plist){ if (plist->items < MAXSIZE) return false; else return true;}unsigned int ListItemCount(const List * plist){ return plist->items;}bool AddItem(Item item, List * plist){ int i = plist->items; if (i < MAXSIZE) { CopyToNode(item, &plist->entries[i]); plist->items++; return true; } return false;}void Traverse(const List * plist, void(*pfun)(Item item)){ int i; for (i = 0; i < plist->items; i++) (*pfun)(plist->entries[i]);}void EmptyTheList(List * plist){ plist->items = 0;}static void CopyToNode(Item item, Node * pnode){ pnode->item = item; }
4.重写mall.c(程序清单17.7)使其用两个队列模拟两个摊位。
//mall.c明明是程序清单17.9，书上搞错了？？？
/* 重写mall.c 用两个队列模拟二个摊位*//* 以分钟为单位程序有局限性。 当有两个摊位时，因为每分钟才会有一个顾客生成，所以一个小时最多只可能有60个顾客 就算每个顾客都要三分钟，那么两个摊位可以接客40人，再加上两个队列可容纳20人 所以永远不可能出现被拒绝加入队列的情况。*/#include#include #include #include "queue.h"#define MIN_PER_HR 60.0bool newcustomer(double x);Item customertime(long when);int main(void){ Queue line1, line2; Item temp; int hours; int perhour; long cycle, cyclelimit; long turnaways = 0; long customers = 0; long served1 = 0, served2 = 0; long sum_line1 = 0, sum_line2 = 0; int wait_time1 = 0, wait_time2 = 0; double min_per_cust; long line_wait1 = 0, line_wait2 = 0; InitQueue(&line1); InitQueue(&line2); srand((unsigned)time(NULL)); puts("Case Study: Sigmund Lander's Advice Booth"); puts("Enter the number of simulation hours:"); scanf("%d", &hours); //以秒为单位 cyclelimit = MIN_PER_HR * hours; puts("Enter the average number of customers per hour: "); scanf("%d", &perhour); min_per_cust = perhour / MIN_PER_HR; printf("%.2lf\n", min_per_cust); int i = 0; for (cycle = 0; cycle < cyclelimit; cycle++) { if (newcustomer(min_per_cust)) { i++; if (QueueIsFull(&line1) && QueueIsFull(&line2)) turnaways++; else { customers++; temp = customertime(cycle); if (QueueItemCount(&line1) < QueueItemCount(&line2)) EnQueue(temp, &line1); else EnQueue(temp, &line2); } } if (wait_time1 <= 0 && !QueueIsEmpty(&line1)) { DeQueue(&temp, &line1); wait_time1 = temp.processtime; line_wait1 += cycle - temp.arrive; served1++; } if (wait_time2 <= 0 && !QueueIsEmpty(&line2)) { DeQueue(&temp, &line2); wait_time2 = temp.processtime; line_wait2 += cycle - temp.arrive; served2++; } if (wait_time1 > 0) wait_time1--; if (wait_time2 > 0) wait_time2--; sum_line1 += QueueItemCount(&line1); sum_line2 += QueueItemCount(&line1); } if (customers > 0) { //两个摊位总的营业情况 printf("customers accepted: %ld\n", customers); printf(" custmers served: %ld\n", served1 + served2); printf(" turnaways: %ld\n", turnaways); printf("average queue size: %.2f\n", (double)(sum_line1 + sum_line2) / cyclelimit); printf("average wait time: %.2f minutes\n", (double)(line_wait1 + line_wait2) / (served1 + served2)); } else puts("No customers!"); printf("i = %d\n", i); return 0;}bool newcustomer(double x){ if (rand()*x / RAND_MAX < 1) return true; else return false;}Item customertime(long when){ Item cust; cust.processtime = rand() % 3 + 1; cust.arrive = when; return cust;}
5.编写一个程序，让您输入一个字符串。该程序将此字符串中的字符逐个地压入一个栈（请参见复习题5），然后弹出这些字符并显示。结果是将字符串按逆序显示。
/* stack.h -- 栈接口 */#ifndef _STACK_H_#define _STACK_H_#includetypedef char Item;typedef struct node{ Item item; struct node * next;} Node;typedef struct stack{ Node * top; Node * bottom;}Stack;void InitStack(Stack * ps);bool StackIsFull(const Stack * ps);bool StackIsEmpty(const Stack * ps);int StackItemCount(const Stack * ps);bool push(Item item, Stack * ps);bool Pop(Item * pitem, Stack * ps);#endif
/* stack.c -- 栈相关函数定义 */#include#include #include "stack.h"static void CopyToNode(Item item, Node * pn);static void CopyToItem(Node * pn, Item * pi);void InitStack(Stack * ps){ ps->bottom = ps->top = NULL;}bool StackIsFull(const Stack * ps){ Node * temp; temp = (Node *)malloc(sizeof(Node)); if (temp == NULL) return true; else free(temp); return false;}bool StackIsEmpty(const Stack * ps){ return ps->top == NULL;}bool push(Item item, Stack * ps){ Node * pnew; if (StackIsFull(ps)) return false; pnew = (Node *)malloc(sizeof(Node)); if (pnew == NULL) { fprintf(stderr, "Unable to allocate memory!\n"); exit(1); } CopyToNode(item, pnew); if (StackIsEmpty(ps)) { pnew->next = NULL; ps->bottom = pnew; } else pnew->next = ps->top; ps->top = pnew; return true;}bool Pop(Item * pitem, Stack * ps){ Node * pt; if (StackIsEmpty(ps)) return false; CopyToItem(ps->top, pitem); pt = ps->top; ps->top = ps->top->next; free(pt); if (ps->top == NULL) ps->bottom = NULL; return true;}static void CopyToNode(Item item, Node * pn){ pn->item = item;}static void CopyToItem(Node * pn, Item * pi){ *pi = pn->item;}
/* test.c -- 测试栈，与stack.c一起编译 */#include#include "stack.h"#define STRLEN 80int main(void){ char str[STRLEN]; Stack stack; int i; Item ch; InitStack(&stack); printf("请输入字符串："); gets(str); for (i = 0; str[i] != '\0' && i < STRLEN; i++) push(str[i], &stack); printf("出栈输出字符串："); while (Pop(&ch, &stack)) putchar(ch); putchar('\n'); return 0;}
6.写一个接受3个参数的函数。这3个参数为：存有已排序的整数的数组名，数组元素个数和要查找的整数。如果该整数在数组中，函数返回1；否则返回0。函数用折半搜索法实现。
/*折半查找1-99中有哪些数包含在数组中*/#include#include int search(int table[], int max, int number);#define M 10//前提条件：数组要求有序排列int table[M] = { 1, 3, 5, 6, 9, 13, 19, 21, 34, 45 };int main(void){ int i ; for (i = 0; i<100; i++) if (search(table, M-1, i)) printf("%d ", i); printf("\n"); return 0;}int search(int table[], int max, int number){ int min = 0, half; int i = 0; while (1) { i++; half = (min + max) / 2; //最小数加最大数除以2等于这两个数的中间数 if (number > table[half]) { min = half + 1; //确定最小数 } else { if (number < table[half]) max = half - 1; //确定最大数 else return true; } if (min + 1 == max) { //如果重合说明中中间已没有数，直接判断临的两个数 if (number == table[min] || number == table[max]) return true; else return false; } }}
7.编写一个程序，能打开、读入一个文本文件并统计文件中每个单词出现的次数。用改进的二叉搜索树存储单词及出现的次数。程序读入文件后，会提供一个有三个选项的菜单。第一个选项为列出所有的单词连同其出现的次数。第二个选项为让您输入一个单词，程序报告该单词在文件中出现的次数。第三个选项为退出。
/* tree.h */#ifndef _TEST_H_#define _TEST_H_#include#define WORDLEN 55typedef struct item{ char word[WORDLEN]; int word_size;}Item;typedef struct node{ Item item; struct node * left; struct node * right;}Node;typedef struct tree{ Node * root; int node_size;}Tree;void InitTree(Tree * pt);bool TreeIsEmpty(Tree * pt);bool TreeIsFull(Tree * pt);int TreeItemCount(const Tree * pt);bool AddItem(const Item * pi, Tree * pt);Node * InItem(const Item * pi, Tree * pt);bool DeItem(const Item * pi, Tree * pt);void traverse(const Tree * pt, void(* pfun)(Item item));void DeAll(Tree * pt);#endif
/* tree.c */#include#include #include #include "tree.h"typedef struct pair{ Node * parent; Node * child;}Pair;/* 局部函数 */static Node * 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(Node * new_node, Node * root);static void InOrder(const Node * root, void(*pfun)(Item item));static Pair SeekItem(const Item * pi, const Tree * ptree);static void DeNode(Node ** ptr);static void DeAllNodes(Node * ptr);void InitTree(Tree * pt){ pt->node_size = 0; pt->root = NULL;}bool TreeIsEmpty(Tree * pt){ return pt->root == NULL;}bool TreeIsFull(Tree * pt){ Node * ptemp; ptemp = (Node *)malloc(sizeof(Node)); if (ptemp == NULL) return true; else return false;}int TreeItemCount(const Tree * pt){ return pt->node_size;}bool AddItem(const Item * pi, Tree * pt){ Node * new_node; if (TreeIsFull(pt)) { fprintf(stderr, "Tree is full\n"); return false; } new_node = MakeNode(pi); if (new_node == NULL) { fprintf(stderr, "Couldn't create node\n"); return false; } if (SeekItem(pi, pt).child != NULL) { SeekItem(pi, pt).child->item.word_size++; free(new_node); return true; } if (pt->root == NULL) pt->root = new_node; else AddNode(new_node, pt->root); pt->node_size++; return true;}Node * InItem(const Item * pi, Tree * pt){ return SeekItem(pi, pt).child;}bool DeItem(const Item * pi, Tree * pt){ Pair look; look = SeekItem(pi, pt); if (look.child == NULL) return false; if (look.parent == NULL) DeNode(&pt->root); else if (look.parent->left == look.child) DeNode(&look.parent->left); else if (look.parent->right == look.child) DeNode(&look.parent->right); pt->node_size--; return true;}void traverse(const Tree * pt, void(*pfun)(Item item)){ if (pt != NULL) InOrder(pt->root, pfun);}void DeAll(Tree * pt){ if (pt != NULL) DeAllNodes(pt->root); pt->node_size = 0; pt->root = NULL;}static Node * MakeNode(const Item * pi){ Node * new_node; new_node = (Node *)malloc(sizeof(Node)); if (new_node != NULL) { new_node->item = *pi; new_node->left = NULL; new_node->right = NULL; } return new_node;}static bool ToLeft(const Item * i1, const Item * i2){ if (strcmp(&i1->word[0], &i2->word[0]) < 0) return true; else return false;}static bool ToRight(const Item * i1, const Item * i2){ if (strcmp(&i1->word[0], &i2->word[0]) > 0) return true; else return false;}static void AddNode(Node * new_node, Node * root){ if (ToLeft(&new_node->item, &root->item)) { if (root->left == NULL) root->left = new_node; else AddNode(new_node, root->left); } else { if (ToRight(&new_node->item, &root->item)) { if (root->right == NULL) root->right = new_node; else AddNode(new_node, root->right); } }}static void InOrder(const Node * root, void(*pfun)(Item item)){ if (root != NULL) { InOrder(root->left, pfun); (*pfun)(root->item); InOrder(root->right, pfun); }}static Pair SeekItem(const Item * pi, const Tree * ptree){ Pair look; look.parent = NULL; look.child = ptree->root; if (look.child == NULL) return look; 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 break; } } return look;}static void DeNode(Node ** ptr){ //形参ptr是父节点中用来保存子节点地址的变量，实参让其初始化为父节点的指针域 //*ptr是子节点本身，也就是要删除的节点。 //子节点删除后，将*ptr指向新的节点也就更改了父节点的指针域。 //ptr的值只要不更改，*ptr永远是父节点的指向。 Node * temp; puts((*ptr)->item.word); if ((*ptr)->left = NULL) { temp = *ptr; *ptr = (*ptr)->right; free(temp); } else { if ((*ptr)->right == NULL) { temp = *ptr; *ptr = (*ptr)->left; free(temp); } else { temp = (*ptr)->left; while (temp->right != NULL) temp = temp->right; temp->right = (*ptr)->right; temp = *ptr; *ptr = (*ptr)->left; free(temp); } }}static void DeAllNodes(Node * root){ Node * temp; if (root != NULL) { /* 保存右子树指针 找到左子树为空的节点，释放节点内存 用保存的右子指针找左子树为空的节点，释放内存 直到右子树指针为空 */ temp = root->right; DeAllNodes(root->left); free(root); DeAllNodes(temp); }}
/* test.c */#include#include #include #include #include "tree.h"void menu(void);int get_ch(char * str);void printItem(Item item);int main(void){ FILE * fp; Tree tree; Item word = { {'\0'}, 1 }; char ch; bool n = false; InitTree(&tree); if ((fp = fopen("f:\\test\\emma.txt", "r")) == NULL) { fprintf(stderr, "文件打开失败\n"); exit(EXIT_FAILURE); } while ((ch=getc(fp)) != EOF) { int i = 0; while (isalpha(ch)) { word.word[i++] = ch; ch = getc(fp); } if (i > 0) { word.word[i++] = '\0'; AddItem(&word, &tree); } //putchar('a'); } putchar('\n'); fclose(fp); menu(); while ((ch = get_ch("abq")) != 'q') { if (ch == 'a') { puts("包含的单词\t\t单词出现的次数"); traverse(&tree, printItem); } if (ch == 'b') { puts("请输入要查找的单词："); scanf("%s", word.word); while (getchar() != '\n') ; if (InItem(&word, &tree)) { printf("单词%s在文件中出现%d次\n", word.word, InItem(&word, &tree)->item.word_size); } else printf("文件中没有找到单词%s\n", word.word); } printf("\n"); menu(); }}void menu(void){ puts("请输入选项："); puts("a)列出所有的单词连同其出现的次数"); puts("b)输入一个单词，程序报告该单词在文件中出现的次数"); puts("q)退出程序");}int get_ch(char * str){ int ch; ch = getchar(); while (getchar() != '\n') ; while (strchr(str, ch) == NULL) { printf("请输入正确的选项%s:", str); ch = getchar(); while (getchar() != '\n') ; } return ch;}void printItem(Item item){ printf("%10s\t\t%14d\n", item.word, item.word_size);}
8.修改宠物俱乐部程序，使所有同名的宠物存储在相同节点中的一个列表中。当用户选择查找一个宠物时，程序要求用户给出宠物名，而后列出所有具有此名字的宠物（连同它们的种类）。
// tree.h -- 二叉搜索树接口#ifndef _TREE_H#define _TREE_H#include#define TREEMAX 20typedef struct item{ char petname[20]; char petkind[20];}Item;typedef struct node_list{ Item item; struct node_list * next;}List;typedef struct node_tree{ List * list; //同名宠物的项目列表 int list_size; //列表中项目个数 struct node_tree * left; //指向左分支的指针 struct node_tree * right; //指向右分支的指针}Node;typedef struct tree{ Node * root; //指向树根的指针 int size; //树中项目的个数}Tree;void InitTree(Tree * ptree);bool TreeIsEmpty(const Tree * ptree);bool TreeIsFull(const Tree * ptree);int TreeItemCount(const Tree * ptree);bool InTree(const Item * pi, const Tree * ptree);bool AddTreeItem(const Item * pi, Tree * ptree);bool DeleteItem(const Item * pi, Tree * ptree);void Traverse(const Tree * ptree, void(*pfun)(List * list));void DeleteAll(Tree * ptree);#endif
//tree.c -- 接口函数定义#include#include #include #include "tree.h"typedef struct pair{ Node * parent; Node * child;}Pair;//局部函数声明static bool AddListItem(const Item * pi, Node * root);static List * MakeListNode(const Item * pi);static Node * MakeTreeNode(const Item * pi);static void AddTreeNode(Node * new_node, Node * root);static Pair SeekItem(const Item * pi, const Tree * ptree);static bool ToLeft(const Item * i1, const Item * i2);static bool ToRight(const Item * i1, const Item * i2);static bool SeekListItem(const Item * pi, List * pl);static void DeNode(const Item * pi, Node ** ptr);static List * DeListNode(const Item * pi, List * pl);static void InOrder(const Node * root, void(*pfun)(List * list));static void DeleteAllNodes(Node * root);static void DeList(List * list);static void DeleteAllList(Node * root);//局部函数定义static bool AddListItem(const Item * pi, Node * root){ //OK List * new_listnode, *temp = root->list; new_listnode = MakeListNode(pi); if (new_listnode == NULL) { fprintf(stderr, "新的成员生成失败\n"); return false; } while (NULL != temp->next) temp = temp->next; temp->next = new_listnode; root->list_size++; return true;}static List * MakeListNode(const Item* pi){ //OK List * new_list; new_list = (List *)malloc(sizeof(List)); if (new_list != NULL) { new_list->item = *pi; new_list->next = NULL; } return new_list;}static Node * MakeTreeNode(const Item * pi){ //OK Node * new_node; List * new_list_node; new_list_node = MakeListNode(pi); if (new_list_node == NULL) return NULL; new_node = (Node *)malloc(sizeof(Node)); if (new_node != NULL) { new_node->list = new_list_node; new_node->list_size = 1; new_node->left = NULL; new_node->right = NULL; } return new_node;}static void AddTreeNode(Node * new_node, Node * root){ //OK if (ToLeft(&new_node->list->item, &root->list->item)) { if (NULL == root->left) root->left = new_node; } else if (ToRight(&new_node->list->item, &root->list->item)) { if (NULL == root->right) root->right = new_node; }}static bool ToLeft(const Item * i1, const Item * i2){ //OK if (strcmp(i1->petname, i2->petname) < 0) return true; return false;}static bool ToRight(const Item * i1, const Item * i2){ //OK if (strcmp(i1->petname, i2->petname) > 0) return true; return false;}static bool SeekListItem(const Item * pi, List * pl){ //OK List * temp = pl; while (NULL != temp) { if (strcmp(pi->petkind, temp->item.petkind) == 0) return true; temp = temp->next; } return false;}static Pair SeekItem(const Item * pi, const Tree * ptree){ //OK Pair look; look.parent = NULL; look.child = ptree->root; if (NULL == look.child) return look; while (NULL != look.child) { if (ToLeft(pi, &look.child->list->item)) { look.parent = look.child; look.child = look.child->left; } else if (ToRight(pi, &look.child->list->item)) { look.parent = look.child; look.child = look.child->right; } else { break; } } return look;}static void DeNode(const Item * pi, Node ** ptr){ //OK Node * temp; if (1 == (*ptr)->list_size) { //列表内只有一个项目，删整个节点 if (NULL == (*ptr)->left) { temp = *ptr; *ptr = (*ptr)->right; free(temp); } else if (NULL == (*ptr)->right) { temp = *ptr; *ptr = (*ptr)->left; free(temp); } else { temp = (*ptr)->left; while (NULL != temp->right) temp = temp->right; temp->right = (*ptr)->right; temp = *ptr; *ptr = (*ptr)->left; free(temp); } } else if ((*ptr)->list_size > 1) { //列表内有多个项目，删列表中的一个项目 (*ptr)->list = DeListNode(pi, (*ptr)->list); (*ptr)->list_size--; }}static List * DeListNode(const Item * pi, List * pl){ //OK List * phead = pl; //保存链表头指针 List * temp; if (strcmp(pi->petkind, phead->item.petkind) == 0) { phead = pl->next; free(pl); } else { do { temp = pl; pl = pl->next; } while (strcmp(pi->petkind, pl->item.petkind) != 0); temp->next = pl->next; free(pl); } return phead;}static void InOrder(const Node * root, void(*pfun)(List * list)){ //OK if (root != NULL) { InOrder(root->left, pfun); (*pfun)(root->list); InOrder(root->right, pfun); }}static void DeleteAllNodes(Node * root){ Node * temp = root; if (root != NULL) { temp = root->right; DeleteAllNodes(root->left); DeList(root->list); free(root); DeleteAllNodes(temp); }}static void DeList(List * list){ List * temp; while (list != NULL) { temp = list; list = list->next; free(temp); }}//全局函数定义void InitTree(Tree * ptree){ //OK ptree->root = NULL; ptree->size = 0;}bool TreeIsEmpty(const Tree * ptree){ //OK return ptree->root == NULL;}bool TreeIsFull(const Tree * ptree){ //OK return ptree->size >= TREEMAX;}int TreeItemCount(const Tree * ptree){ //OK return ptree->size;}bool InTree(const Item * pi, const Tree * ptree){ Pair look = SeekItem(pi, ptree); return look.child != NULL && SeekListItem(pi, look.child->list);}bool AddTreeItem(const Item * pi, Tree * ptree){ //OK Node * new_node; Pair seek; if (TreeIsFull(ptree)) { fprintf(stderr, "Tree is ull\n"); return false; } seek = SeekItem(pi, ptree); if (seek.child != NULL) { if (AddListItem(pi, seek.child)); return true; return false; } new_node = MakeTreeNode(pi); if (new_node == NULL) { fprintf(stderr, "Couldn't create node\n"); return false; } if (ptree->root == NULL) ptree->root = new_node; else AddTreeNode(new_node, ptree->root); ptree->size++; return true;}bool DeleteItem(const Item * pi, Tree * ptree){ //OK Pair look; look = SeekItem(pi, ptree); int i = TreeItemCount(ptree); if (NULL == look.child) return false; //是否找到同名项 if (!SeekListItem(pi, look.child->list)) return false; //是否找到同类项 DeNode(pi, &look.child); int j = TreeItemCount(ptree); if (i == j) ptree->size--; if (ptree->size == 0) ptree->root = NULL; return true;}void Traverse(const Tree * ptree, void(*pfun)(List * list)){ //OK if (ptree->root != NULL) InOrder(ptree->root, pfun);}void DeleteAll(Tree * ptree){ if (ptree->root != NULL) DeleteAllNodes(ptree->root); ptree->size = 0;}
//test_tree.c -- 测试二叉搜索树#include#include #include #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(List * list); //打印项目内容void uppercase(char * str); //转换大写int ListItemCount(Node * root);int main(void){ Tree pets; //定义树变量 char choice; int conut=0, temp=0; InitTree(&pets); while ((choice = menu()) != 'q') { switch (choice) { case 'a': addpet(&pets); break; case 'l': showpets(&pets); break; case 'f': findpet(&pets); break; case 'n': conut = ListItemCount(pets.root); conut -= temp; temp += conut; printf("%d pets in club\n", conut); 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 per l)show list of pets"); puts("n)number of pets f)find pets"); puts("d)delete apet q)quit"); while ((ch = getchar()) != EOF) { while (getchar() != '\n') //丢弃输入行的剩余部分 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) //令EOF导致程序退出 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: "); gets(temp.petname); puts("Please enter pet kind: "); gets(temp.petkind); uppercase(temp.petname); uppercase(temp.petkind); AddTreeItem(&temp, pt); }}void showpets(const Tree * pt){ if (TreeIsEmpty(pt)) puts("No enteries!"); else Traverse(pt, printitem);}void printitem(List * list){ while (list != NULL) { printf("pet: %-19s kind: %-19s\n", list->item.petname, list->item.petkind); list = list->next; }}void findpet(const Tree * pt){ Item temp; if (TreeIsEmpty(pt)) { puts("No entries!"); return; } puts("Please enter name of pet you wish to find: "); gets(temp.petname); puts("Please enter pet kind: "); gets(temp.petkind); uppercase(temp.petname); uppercase(temp.petkind); printf("%s the %s ", temp.petkind, temp.petname); 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; } puts("Please enter name of pet you wish to delete: "); gets(temp.petname); puts("Please enter pet dind: "); gets(temp.petkind); 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++; }}int ListItemCount(Node * root){ static int conut = 0; if (root != NULL) { ListItemCount(root->left); conut += root->list_size; ListItemCount(root->right); } return conut;}