本文使用c语言定义并实现list、queue、tree抽象数据类型，代码有详尽注释，可以通过代码熟悉原理并运用数据结构。
0.ADT基础知识
类型包括两类信息，属性和操作。在编程时，根据编程问题匹配合适的数据类型。
定义一个新的数据类型，有三个步骤：
提供类型属性和相关操作的抽象描述。描述不依赖于特定实现和特定编程语言。开发一个实现ADT的编程接口。描述如何表示数据、描述实现ADT操作的函数，在c中，可以提供结构定义和操控该结构的函数原型。编写代码实现接口。
1.list(链表)的实现
根据三个步骤，定义一个list：
1.建立抽象：
类型名：简单链表。类型属性：可存储一系列项。类型操作：初始化链表为空、确定链表为空、确定链表已满、确定链表中的项数、在链表末尾添加项、遍历链表，处理链表中的项、清空链表。
2.建立接口：见list.h
建立接口后，可以使用这个接口编写程序，而不必知道具体实现细节，见film3.c
3.实现接口：见list.c
1.1 list.h
/* list.h -- header file for a simple list type */#ifndef LIST_H_#define LIST_H_#include <stdbool.h>/* C99 feature *//* 特定程序的声明 */#define TSIZE45 /* 存储电影名的数组大小 */struct film{char title[TSIZE];int rating;};/* 一般类型定义 */typedef struct film Item;/* 如果以后需要其他数据形式的链表，*//* 可以重新定义Item类型，不必更改其余的接口定义 */typedef struct node{Item item;struct node * next;} Node;/* 每一个链节叫做节点（Node） */typedef Node * List;/* 指向链表开始处的指针，List作为该类型的指针名*//* 函数原型 *//* 前提条件：调用该函数前应具备的条件 *//* 后置条件：执行完该函数后的情况 *//* 操作: 初始化一个链表*//* 前提条件: plist 指向一个链表 *//* 后置条件: 链表初始化为空 */void InitializeList(List * plist);/* 该函数的参数是指向链表的指针，*//* 如果函数想要修改一个参数，那么该参数的类型应该是指向相应类型的指针 *//* 调用时InitializeList(&movies) *//* operation: 确定链表是否为空 *//* plist 指向一个已初始化的链表 *//* postconditions: 如果链表为空，函数返回true*//* 否则返回false*/bool ListIsEmpty(const List *plist);/* operation: 确定链表是否已满 *//* plist points to an initialized list *//* postconditions: function returns True if list is full*//* and returns False otherwise*/bool ListIsFull(const List *plist);/* operation: 确定链表中的项数*//* plist points to an initialized list *//* postconditions: 函数返回链表中的项数 */unsigned int ListItemCount(const List *plist);/* operation: 在链表的末尾添加项*//* preconditions: item 是一个待添加至链表的项 *//* plist 指向一个已初始化的链表 *//* postconditions: 如果可以, 函数在链表末尾添加一个项*//* 且返回True; 否则返回False */ bool AddItem(Item item, List * plist);/* operation: 把函数作用于链表中的每一项*//* plist 指向一个已初始化的链表 *//* pfun 指向一个函数，该函数接受一个 *//* Item类型的参数，且无返回值*//* postcondition: pfun指向的函数作用于链表中的每个项一次 */void Traverse (const List *plist, void (* pfun)(Item item) );/* operation: 释放已分配的内存(如果有的话) *//* plist points to an initialized list *//* postconditions: 释放了为链表分配的所有内存 *//* 链表设置为空*/void EmptyTheList(List * plist);#endif
1.2 list.c
/* list.c -- 支持链表操作的函数 */#include <stdio.h>#include <stdlib.h>#include "list.h"/* 局部函数原型 *//* 该函数是实现的一部分，不是接口的一部分，*//* 使用static存储类别说明符将其隐藏在list.c文件夹中 */static void CopyToNode(Item item, Node * pnode);/* 接口函数 *//* 把链表设置为空 */void InitializeList(List * plist){* plist = NULL;}/* 如果链表为空，返回true */bool ListIsEmpty(const List * plist){if (*plist == NULL)return true;elsereturn false;}/* 如果链表已满，返回True */bool ListIsFull(const List * plist){Node * pt;bool full;/* 添加一个节点，分配一次内存 */pt = (Node *) malloc(sizeof(Node));if (pt == NULL)/* 系统把内存分配完了，此时表示链表满了 */full = true;elsefull = false;free(pt);return full;}/* 返回节点的数量 */unsigned int ListItemCount(const List * plist){unsigned int count = 0;Node * pnode = *plist; /*设置链表的开始 */while (pnode != NULL){++count;pnode = pnode->next; /* 设置下一个节点 */}return count;}/* 创建存储项的节点 *//* 并将其添加至由plist指向的链表末尾 */bool AddItem(Item item, List * plist){Node * pnew;Node * scan = *plist;pnew = (Node *) malloc(sizeof(Node));if (pnew == NULL)return false;/* 失败时退出函数 */CopyToNode(item, pnew);pnew->next = NULL;if (scan == NULL)/* 空链表, 所以把 */*plist = pnew; /* pnew 放在链表的开头 */else{while (scan->next != NULL)scan = scan->next; /* 找到链表的末尾 */scan->next = pnew;/* 把pnew添加到链表的末尾*/}return true;}/* 访问每个节点并执行pfun指向的函数 */void Traverse (const List * plist, void (* pfun)(Item item) ){Node * pnode = *plist; /* 设置链表的开始 */while (pnode != NULL){(*pfun)(pnode->item); /* 把函数应用于链表中的项 */pnode = pnode->next; /* 前进到下一项 */}}/* 释放由malloc()分配的内存 *//* 设置链表指针为 NULL*/void EmptyTheList(List * plist){Node * psave;while (*plist != NULL){psave = (*plist)->next; /* 保存下一个节点的地址 */free(*plist); /* 释放当前节点 */*plist = psave; /* 前进至下一个节点*/}}/* 局部函数定义 *//* 把一个项拷贝到节点中 */static void CopyToNode(Item item, Node * pnode){pnode->item = item; /* 拷贝结构 */}
1.3 film3.c
使用接口编写程序，但是不必知道具体的实现细节。
/* 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;/* 初始化 */InitializeList(&movies);if (ListIsFull(&movies)){fprintf(stderr,"No memory available! Bye!\n");exit(1);}/* 获取用户输入并存储 */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):");}/* 显示 */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));/* 清理 */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'); // 查找换行符if (find) // 如果地址不是NULL,*find = '\0';// 在此处放置一个空字符elsewhile (getchar() != '\n')continue;// 处理输入行的剩余内容}return ret_val;}
2.queue(队列)的实现
队列是具有两个特殊属性的链表，1.新项只能添加到链表的末尾，2.只能从链表的开头移除项。 先进先出的数据形式。
根据三个步骤，定义一个list：
1.建立抽象：
类型名：队列。类型属性：可存储一系列项。类型操作：初始化队列为空、确定队列为空、确定队列已满、确定队列中的项数、在队列末尾添加项、在队列开头删除或恢复项、清空队列。
2.建立接口：见queue.h
3.实现接口：见queue.c
4.测试接口：见use_q.c
5.使用队列：见mall.c
2.1 queue.h
/* queue.h -- interface for a queue */#ifndef _QUEUE_H_#define _QUEUE_H_#include <stdbool.h>// 在这里插入Item类型的定义// 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;// 一位顾客加入队列的时间int processtime; // 该顾客咨询时花费的时间} Item;/**/#define MAXQUEUE 10typedef struct node{Item item;struct node * next;} Node;typedef struct queue{Node * front; /* 指向队列首项的指针 */Node * rear; /* 指向队列尾项的指针 */int items;/* 队列中的项数 */} Queue;/* operation: 初始化队列 *//* 前提条件:pq 指向一个队列 *//* 后置条件:队列被初始化为空 */void InitializeQueue(Queue * pq);/* operation: 检查队列是否已满*//* precondition:pq 指向之前被初始化的队列 *//* postcondition: 如果队列已满则返回true，否则返回false */bool QueueIsFull(const Queue * pq);/* operation: 检查队列是否为空*//* precondition:pq 指向之前被初始化的队列 *//* postcondition: 如果队列为空则返回true，否则返回false */bool QueueIsEmpty(const Queue *pq);/* operation: 确定队列中的项数 *//* precondition:pq points to previously initialized queue *//* postcondition: 返回队列中的项数*/int QueueItemCount(const Queue * pq);/* operation: 在队列末尾添加项 *//* precondition:pq 指向之前被初始化的队列 *//* item是要被添加在队列末尾的项*//* postcondition: 如果队列不为空，item将被添加在队列的末尾， *//* 函数返回true； */bool EnQueue(Item item, Queue * pq);/* operation: 从队列的开头删除项 *//* precondition:pq 指向之前被初始化的队列 *//* postcondition: 如果队列不为空，*//* 队列首端的item将被拷贝到*pitem中， *//* 并被删除，且函数返回True *//* 如果该操作使队列为空， *//* 则重置队列为空 *//* 如果队列在操作前为空，*//* 该函数返回false */bool DeQueue(Item *pitem, Queue * pq);/* operation: 清空队列 *//* precondition:pq指向之前被初始化的队列 *//* postconditions: 队列被清空*/void EmptyTheQueue(Queue * pq);#endif
2.2 queue.c
/* 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; /* 项位于队列首端*/elsepq->rear->next = pnew;/* 链接到队列尾端 */pq->rear = pnew;/* 记录队列尾端位置 */pq->items++;/* 队列项数加1 */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;//首指针和尾指针都置为NULLreturn true;}/* 清空队列*/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;}
2.3 use_q.c
/* 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);}elseputs("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;}
2.4 mall.c
有一个提供快乐的摊位，顾客可以购买1分钟、2分钟或3分钟的快乐。为确保交通顺畅，每个摊位前排队等待的顾客最多为10人。假设顾客随机出现，并且他们花费的时间也是随机选择的(1\2\3分钟)，那么该摊位平均每小时接待多少名顾客？每位顾客平均花多长时间？排队等待的顾客平均有几人？
// mall.c -- use the Queue interface// compile with queue.c#include <stdio.h>#include <stdlib.h> // for rand() and srand()#include <time.h>// for time()#include "queue.h"// change Item typedef#define MIN_PER_HR 60.0bool newcustomer(double x); // 是否有新顾客来?Item customertime(long when); // 设置顾客参数int main(void){Queue line;Item temp;// 新的顾客数据int hours;// 模拟的小时数int perhour; // 每小时平均多少位顾客long cycle, cyclelimit; // 循环计数器、 计数器的上限long turnaways = 0; // 因队列已满被拒的顾客数量long customers = 0; // 加入队列的顾客数量long served = 0;// 在模拟期间到访过摊位的顾客数量long sum_line = 0; // 累计的队列总长int wait_time = 0; // 从当前到摊位空闲所需时间double min_per_cust;// 顾客到来的平均时间long line_wait = 0; // 队列累计的等待时间 InitializeQueue(&line);srand((unsigned int) time(0)); // rand()随机初始化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 = MIN_PER_HR / perhour;for (cycle = 0; cycle < cyclelimit; cycle++)//每次迭代对应一分钟的行为{if (newcustomer(min_per_cust))//如果1分钟内有顾客到来{if (QueueIsFull(&line))turnaways++;//被拒的顾客数量else{customers++;temp = customertime(cycle);/*设置temp结构中的arrive和processtime成员*/EnQueue(temp, &line);}}if (wait_time <= 0 && !QueueIsEmpty(&line)){//如果队列不为空且前面的顾客没有咨询，则删除队列首端的项DeQueue (&temp, &line);wait_time = temp.processtime;//该顾客咨询时花费的时间line_wait += cycle - temp.arrive;//到目前为止，队列中所有顾客的等待总时间served++;//咨询过的顾客数量}if (wait_time > 0)//完成当前顾客的需求所需的时间大于0wait_time--;sum_line += QueueItemCount(&line);//目前为止统计的队列长度}if (customers > 0){printf("customers accepted: %ld\n", customers);printf(" customers served: %ld\n", served);printf(" turnaways: %ld\n", turnaways);printf("average queue size: %.2f\n",(double) sum_line / cyclelimit);printf(" average wait time: %.2f minutes\n",(double) line_wait / served);}elseputs("No customers!");EmptyTheQueue(&line);puts("Bye!");return 0;}// x = 顾客到来的平均时间(单位：分钟) // 如果1分钟内有顾客到来，则返回truebool newcustomer(double x){if (rand() * x / RAND_MAX < 1)return true;elsereturn false;}// when是顾客到来的时间// 该函数返回一个Item结构，该顾客到达的时间设置成when// 咨询时间设置为1 - 3的随机值Item customertime(long when){Item cust;cust.processtime = rand() % 3 + 1;cust.arrive = when;return cust;}
3.tree(二叉查找树)的实现
访问元素有两种，随机访问：使用数组下标直接访问该数组中的任意元素；顺序访问：对于链表而言，必须从链表首节点开始，逐个节点移动到要访问的节点。
用数组可以实现二分查找，因为可以使用数组下标确定数组中任意部分的中点。但是链表只支持顺序访问，不提供跳至中间节点的方法，所以链表中不能使用二分查找。
有一种数据形式的需求，既支持频繁插入和删除项，又支持频繁查找。此时需要二叉查找树。
根据三个步骤，定义一个二叉树：
该定义假设二叉树不包含相同的项。
1.建立抽象：
类型名：二叉查找树。
类型属性：
二叉树要么是空节点的集合(空树)，要么是有一个根节点的节点集合。每个节点都有两个子树，叫做左子树和右子树每个子树本身也是一个二叉树，也可能是空树二叉查找树是一个有序的二叉树，每个节点包含一个项。左子树的所有项都在根节点项的前面，右子树所有项都在根节点项的后面
类型操作：初始化树为空、确定树是否为空、确定树是否已满、确定树中的项数、在树中添加一个项、在树中删除一个项、在树中查找一个项、在树种访问一个项、清空树。
2.建立接口：见tree.h
3.实现接口：见tree.c
4.使用二叉树：见petclub.c
3.1 tree.h
/* tree.h -- binary search tree 二叉查找树*//* 树中不允许有重复的项 */#ifndef _TREE_H_#define _TREE_H_#include <stdbool.h>/* 根据情况重新定义Item */#define SLEN 20typedef struct item{char petname[SLEN];char petkind[SLEN];} Item;#define MAXITEMS 10typedef struct trnode{Item item;struct trnode * left; /* 指向左分支的指针 */struct trnode * right; /* 指向右分支的指针 */} Trnode;typedef struct tree{Trnode * root; /* 指向根节点的指针 */int size; /* 树的项数 */} Tree;/* 函数原型 *//* 操作: 把树初始化为空*//* 前提条件: ptree 指向一个树 *//* 后置条件: 树被初始化为空*/void InitializeTree(Tree * ptree);/* operation:确定树是否为空*//* preconditions: ptree points to a tree *//* postconditions: 如果树为空，函数返回true *//* 否则返回false*/bool TreeIsEmpty(const Tree * ptree);/* operation:确定树是否已满 *//* preconditions: ptree points to a tree *//* postconditions: function returns true if tree is *//* full and returns false otherwise */bool TreeIsFull(const Tree * ptree);/* operation:确定树的项数*//* preconditions: ptree points to a tree *//* postconditions: 返回树的项数*/int TreeItemCount(const Tree * ptree);/* operation:在树中添加一个项*//* preconditions: pi 是待添加项的地址 *//* ptree 指向一个已初始化的树 *//* postconditions: 如果可以添加，该函数将在树中添加一个项 *//* 并返回true，否则返回false*/bool AddItem(const Item * pi, Tree * ptree);/* operation:在树中查找一个项 *//* preconditions: pi指向一个项*//* ptree 指向一个已初始化的树 *//* postconditions: 如果在树中找到指定项，该函数返回true *//* 否则返回false */bool InTree(const Item * pi, const Tree * ptree);/* operation:从树中删除一个项*//* preconditions: pi 是删除项的地址 *//* ptree 指向一个已初始化的树 *//* postconditions: 如果在树中成功删除一个项，该函数返回true *//* 否则返回false*/bool DeleteItem(const Item * pi, Tree * ptree);/* operation:把函数应用于树中的每一项*//* preconditions: ptree 指向一个树 *//* pfun 指向一个函数 *//* 该函数接受一个Item类型的参数，并无返回值 *//* postcondition: pfun指向的这个函数为树中的每一项执行一次 */void Traverse (const Tree * ptree, void (* pfun)(Item item));/* operation:删除树中的所有内容 *//* preconditions: ptree指向一个已初始化的树 *//* postconditions: 树为空 */void DeleteAll(Tree * ptree);#endif
3.2 tree.c
/* tree.c -- tree support functions */#include <string.h>#include <stdio.h>#include <stdlib.h>#include "tree.h"/* 局部数据类型 */typedef struct pair {Trnode * parent;Trnode * child;} Pair;/* 局部函数的原型 */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);/* 函数定义 */void InitializeTree(Tree * ptree){ptree->root = NULL;ptree->size = 0;}bool TreeIsEmpty(const Tree * ptree){if (ptree->root == NULL)return true;elsereturn false;}bool TreeIsFull(const Tree * ptree){if (ptree->size == MAXITEMS)return true;elsereturn 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; /* 提前返回 */}if (SeekItem(pi, ptree).child != NULL){/*检查该树是否有该项，因为要求二叉树中的项不能重复*/fprintf(stderr, "Attempted to add duplicate item\n");return false; /* 提前返回 */}new_node = MakeNode(pi);/* 指向新节点*/if (new_node == NULL){fprintf(stderr, "Couldn't create node\n");return false; /* 提前返回 */}/* 成功创建了一个新节点 */ptree->size++;/*找出应该把这个新节点放在树中哪个位置*/if (ptree->root == NULL)/* 情况 1: 树为空 */ptree->root = new_node; /* 新节点为树的根节点 */else/* case 2: 树不为空*/AddNode(new_node,ptree->root); /* 在树中添加新节点 */return true; /* 成功返回*/}/*在树中查找一个项*/bool InTree(const Item * pi, const Tree * ptree){/*SeekItem函数返回一个结构，该函数可以与结构成员运算符一起使用*/return (SeekItem(pi, ptree).child == NULL) ? false : true;}bool DeleteItem(const Item * pi, Tree * ptree){Pair look;/*SeekItem返回一个结构，*//*内含两个指针，一个指针look.parent指向父节点，*//*一个指针look.child指向包含特定项的节点*/look = SeekItem(pi, ptree);if (look.child == NULL)/*表明未找到指定项*/return false;/*找到了指定项，分三种情况处理*//*第一种情况，该项在根节点中*/if (look.parent == NULL)/* 删除根节点项 */DeleteNode(&ptree->root);/*第二种情况，待删除节点是父节点的左子节点*/else if (look.parent->left == look.child)DeleteNode(&look.parent->left);/*第三种情况，待删除节点是父节点的右子节点*/elseDeleteNode(&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);/*释放内存*//*处理Tree类型的结构，重置Tree类型结构成员，表明该树为空*/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;/*存储root->right，使其在释放根节点后仍然可用*/DeleteAllNodes(root->left);free(root);DeleteAllNodes(pright);}}/*确定新节点的位置，添加新节点*/static void AddNode (Trnode * new_node, Trnode * root){/*如果新项应放在左子树中，ToLeft()函数返回true*/if (ToLeft(&new_node->item, &root->item)){if (root->left == NULL)/* 空子树 */root->left = new_node; /* 把节点添加到此处 */else/*把新项和左子节点中的项作比较，*//*以确定新项该放在该子节点的左子树还是右子树*/AddNode(new_node, root->left);/* 否则处理该子树*/}/*如果新项应放在右子树中，ToRight()函数返回true*/else if (ToRight(&new_node->item, &root->item)){if (root->right == NULL)root->right = new_node;elseAddNode(new_node, root->right);}else/* 不允许有重复项 */{fprintf(stderr,"location error in AddNode()\n");exit(1);}}/*ToLeft和ToRight函数依赖于Item类型的性质。*//*成员名按字母排序，如果名字相同，按其种类排序*//*如果种类相同，属于重复项*/static bool ToLeft(const Item * i1, const Item * i2){int comp1;/*第一个字符串在第二个字符串前面，strcmp返回负数*//*两个字符串相同，strcmp返回0*/if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)return true;else if (comp1 == 0 &&strcmp(i1->petkind, i2->petkind) < 0 )return true;elsereturn 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;elsereturn 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;}/*查找特定项*//*返回的结构包含两个指针，*//*一个指针指向包含项的节点，如果未找到指定项则为NULL*//*一个指针指向父节点(如果该节点为根节点，没有父节点，则为NULL)*/static Pair SeekItem(const Item * pi, const Tree * ptree){Pair look;look.parent = NULL;/*开始时，设置look.child指向树的根节点*/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;//如果没有找到匹配的项，look.child将被设置为NULL}else if (ToRight(pi, &(look.child->item))){look.parent = look.child;look.child = look.child->right;}else /* 如果前两种情况都不满足，则必定是相等的情况 */break; /* look.child 目标项的节点 */}return look; /* 成功返回 */}static void DeleteNode(Trnode **ptr)/* ptr是指向待删除节点指针的地址 *//*那么*ptr就是把ptr地址里面的值取出来，就是指向待删除节点的指针*/ /*要修改的指针本身是Trnode*类型，指向Trnode的指针*//*该函数的参数是该指针的地址，所以参数的类型是Trnode** */{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 /* 被删除的节点有两个子节点 */{/* 找到重新连接右子树的位置 *//*沿左子树的右支查找到第1个空位*/for (temp = (*ptr)->left; temp->right != NULL;temp = temp->right)continue;/*把待删除节点的右子树与该空位连接*/temp->right = (*ptr)->right;/*处理完之后重置待删除节点的地址*//*重置之前先将*ptr存储在temp中，释放待删除节点的内存*/temp = *ptr;*ptr =(*ptr)->left;free(temp); }}
3.3 petclub.c
/* 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 petl) show list of pets");puts("n) number of petsf) find pets");puts("d) delete a pet 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:");elsebreak;}if (ch == 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:");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!");elseTraverse(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");elseprintf("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");elseprintf("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'); // 查找换行符if (find) // 如果地址不是 NULL,*find = '\0';// 在此处放置一个空字符elsewhile (getchar() != '\n')continue;// 处理输入行的剩余内容}return ret_val;}
