1. 第1题

1.1 题目描述

修改程序清单17.2，让该程序既能正序也能逆序显示电影列表。一种方法是修改链表的定义，可以双向遍历链表。另一个方式是用递归。

1.2 递归方式

1.2.1 源码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define TSIZE	45

struct film{
	char title[TSIZE];
	int rating;
	struct film *next;
};

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) *find = '\0';
		else while(getchar()!='\0');
	}
	return ret_val;
}

void display(const struct film * f){
	const struct film *cur=f;
	if(cur->next){
		cur = cur->next;
		display(cur);
	}
	printf("Movie: %s Rating:%d\n", f->title, f->rating);
}

int main(void){	
	struct film *head=NULL;
	struct film *prev, *current;
	char input[TSIZE];
	
	puts("Enter first movie title\n");
	while(s_gets(input, TSIZE)!= NULL && input[0]!='\0'){
		current = (struct film *)malloc(sizeof(struct film));
		if(head == NULL) head = current;
		else prev->next = current;
		current->next = NULL;
		strcpy(current->title,input);
		puts("Enter your rating <0-10>:");
		scanf("%d",&current->rating );
		while(getchar()!='\n');
		puts("Enter next movie title(empty line to stop):");
		prev = current;
	}
	if(head==NULL)printf("No data entered.\n");
	else printf("Here is the movie list:\n");
	
	current = head;
	while(current!=NULL){
		printf("Movie: %s Rating:%d\n", current->title, current->rating);
		current = current->next;
	}
	
	display(head);
	
	current = head;
	while(head != NULL){
		current = head;
		head = current->next;
		free(current);
	}
	
	printf("Bye!\n");
	
	return 0;
}

1.2.1 结果显示

1.3 双向链表

1.3.1 源码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define TSIZE	45

struct film{
	char title[TSIZE];
	int rating;
	struct film *next;
	struct film *pre;
};

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) *find = '\0';
		else while(getchar()!='\0');
	}
	return ret_val;
}

int main(void){	
	struct film *head=NULL;
	struct film *prev, *current;
	char input[TSIZE];
	
	puts("Enter first movie title\n");
	while(s_gets(input, TSIZE)!= NULL && input[0]!='\0'){
		current = (struct film *)malloc(sizeof(struct film));
		if(head == NULL) {
			head = current;
			head->pre = NULL;
		}
		else {
			prev->next = current;
			current->pre = prev;
		}
		current->next = NULL;		
		strcpy(current->title,input);
		puts("Enter your rating <0-10>:");
		scanf("%d",&current->rating );
		while(getchar()!='\n');
		puts("Enter next movie title(empty line to stop):");
		prev = current;
	}
	if(head==NULL)printf("No data entered.\n");
	else printf("Here is the movie list:\n");
	
	current = head;
	while(current!=NULL){
		prev = current;
		current = current->next;		
	}
	current = prev;
	while(current != NULL){
		printf("Movie: %s Rating:%d\n", current->title, current->rating);
		current = current->pre;		
	}
		
	current = head;
	while(head != NULL){
		current = head;
		head = current->next;
		free(current);
	}
	
	printf("Bye!\n");
	
	return 0;
}

1.3.2 结果显示

---

2. 第2题

2.1 题目描述

假设list.h（程序清单17.3）使用下面的list定义：

typedef struct list {
	Node *head;
	Node *end;
} List;

重写list.c（程序清单17.5）中的函数以适应新的定义，并通过films.c（程序清单17.4）测试最终代码。

2.2 编程源码

film.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include "list.h"

#define TSIZE	45

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) *find = '\0';
		else while(getchar()!='\0');
	}
	return ret_val;
}

int main(void){	
	List movies;
	Item temp;
	
	InitializeList(&movies);
	if(ListIsFull(&movies)){
		fprintf(stderr, "NO memory availabel! 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');
		
		if(AddItem(temp, &movies) == false){
			puts("The list is now full.\n");
			break;
		}
		
		if(ListIsFull(&movies)){
			fprintf(stderr, "Problem allocating memory\n");
			break;
		}
		puts("Enter next movie title(empty line to stop):");
	}
	if(movies.head==NULL)printf("No data entered.\n");
	else printf("Here is the movie list:\n");
	
	if(ListIsEmpty(&movies)) printf("No Data entered.\n");
	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;
}

list.h

#ifndef LIST_H_
#define LIST_H_

#include<stdbool.h>

#define TSIZE	45

typedef struct film{
	char title[TSIZE];
	int rating;
}Item;

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

typedef struct list{
	Node * head;
	Node * end;
}List;

void InitializeList(List *plist);
bool ListIsEmpty(const List *plist);
bool ListIsFull(const List *plist);
unsigned int ListItemCount(const List *plist);
bool AddItem(Item item, List*plist);
void Traverse(const List*plist, void(*pfun)(Item item));
void EmptyTheList(List*plist);

#endif

list.c

#include<stdio.h>
#include<stdlib.h>
#include "list.h"

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

void InitializeList(List *plist){
	plist->head = NULL;
	plist->end = NULL;
}

bool ListIsEmpty(const List *plist){
	if(plist == NULL || 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;
	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->end;
	
	pnew = (Node*) malloc(sizeof(Node));
	if(pnew == NULL) return false;
	
	CopyToNode(item,pnew);
	pnew->next = NULL;
	
	if(plist->head == NULL) {
		plist->head = pnew;
		plist->end = pnew;
	}
	else {
		scan->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=plist->head;
	Node *tmp;
	
	while(psave->next != NULL){
		tmp = psave;
		psave = psave->next;
		free(tmp);
	}
	if(psave!=NULL) free(psave);
}

makefile

a.exe:test.o list.h list.o
	gcc -o a.exe test.o list.o
list.o:list.h
	gcc -c list.c
test.o:list.h test.c
	gcc -c test.c 
	
clean:
	del *.o,a.exe

2.3 结果显示

---

3. 第3题

3.1 题目描述

假设list.h（程序清单17.3）使用下面的list定义：

#define MAXSIZE 100
typedef struct list {
	Item entries[MAXSIZE];
	int items;
} List;

重写list.c（程序清单17.5）中的函数以适应新的定义，并通过films.c（程序清单17.4）测试最终代码。

3.2 编程源码

film.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include "list.h"

#define TSIZE	45

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) *find = '\0';
		else while(getchar()!='\0');
	}
	return ret_val;
}

int main(void){	
	List movies;
	Item temp;
	
	InitializeList(&movies);
	if(ListIsFull(&movies)){
		fprintf(stderr, "NO memory availabel! 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');
		
		if(AddItem(temp, &movies) == false){
			puts("The list is now full.\n");
			break;
		}
		
		if(ListIsFull(&movies)){
			fprintf(stderr, "Problem allocating memory\n");
			break;
		}
		puts("Enter next movie title(empty line to stop):");
	}
	if(movies.items==0)printf("No data entered.\n");
	else printf("Here is the movie list:\n");
	
	if(ListIsEmpty(&movies)) printf("No Data entered.\n");
	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;
}

list.h

#ifndef LIST_H_
#define LIST_H_

#include<stdbool.h>

#define TSIZE	45

typedef struct film{
	char title[TSIZE];
	int rating;
}Item;

#define MAXSIZE 100
typedef struct list {
	Item entries[MAXSIZE];
	int items;
} List;

void InitializeList(List *plist);
bool ListIsEmpty(const List *plist);
bool ListIsFull(const List *plist);
unsigned int ListItemCount(const List *plist);
bool AddItem(Item item, List*plist);
void Traverse(const List*plist, void(*pfun)(Item item));
void EmptyTheList(List*plist);


#endif

list.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "list.h"

void InitializeList(List *plist){
	for(int i=0;i<MAXSIZE;++i){
		strcpy(plist->entries[i].title, "\0");
		plist->entries[i].rating = 0;
	}
	plist->items=0;
}

bool ListIsEmpty(const List *plist){
	if(plist->items) return false;
	else return true;
}

bool ListIsFull(const List *plist){
	if(plist->items >= MAXSIZE) return true;
	else return false;
}

unsigned int ListItemCount(const List *plist){
	return plist->items;
}

bool AddItem(Item item, List* plist){
	plist->entries[plist->items++] = item;
	return true;
}

void Traverse(const List*plist, void(*pfun)(Item item)){
	for(int i=0;i<plist->items;++i)	(*pfun)(plist->entries[i]);
}

void EmptyTheList(List*plist){
	for(int i=0;i<plist->items;++i){
		strcpy(plist->entries[i].title, "\0");
		plist->entries[i].rating = 0;
	}
	plist->items=0;
}

makefile

a.exe:test.o list.h list.o
	gcc -o a.exe test.o list.o
list.o:list.h
	gcc -c list.c
test.o:list.h test.c
	gcc -c test.c 
	
clean:
	del *.o,a.exe

3.3 结果显示

---

4. 第4题

4.1 题目描述

重写mall.c（程序清单17.7），用两个队列模拟两个摊位。

4.2 编程源码

mall.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#include "list.h"

#define MIN_PER_HR	60.0

bool newcustomer(double x){
	if(rand()*x/ RAND_MAX < 1) return true;
	return false;
}
Item customertime(long when){
	Item cust;
	
	cust.processtime = rand()%3+1;
	cust.arrive = when;
	return cust;
}

int main(void){	
	Queue line1,line2;
	Item temp1,temp2;
	int hours;
	int perhour;
	long cycle,cyclelimit;
	long turnaways = 0;
	long customers = 0;
	long served = 0;
	long sun_line =0;
	int wait_time1 = 0;
	int wait_time2 = 0;
	double min_per_cust;
	long line_wait = 0;
	
	InitializeQueue(&line1);
	InitializeQueue(&line2);
	srand((unsigned int)time(0));
	puts("Case Study: Sigmund Lander`s Advice Booth\n");
	puts("Enter the number of simulation hours:");
	scanf("%d", &hours);
	cyclelimit = MIN_PER_HR * hours*2;
	puts("Enter the average number of customers per hours:");
	scanf("%d", &perhour);
	min_per_cust = MIN_PER_HR/perhour;
	
	for(cycle = 0;cycle<cyclelimit;++cycle){
		if(newcustomer(min_per_cust)){
			if(QueueIsFull(&line1) && QueueIsFull(&line2))turnaways++;
			else {
				customers++;
				temp1 = customertime(cycle);
				temp2 = customertime(cycle);
				if(!QueueIsFull(&line1))	EnQueue(temp1, &line2);
				if(!QueueIsFull(&line2))	EnQueue(temp2, &line1);
			}			
		}
		
		if((wait_time1<=0 || wait_time2<0)&& !(QueueIsEmpty(&line1)&& QueueIsEmpty(&line2))){
			if(!QueueIsEmpty(&line1))DeQueue(&temp1, &line1);
			if(!QueueIsEmpty(&line2))DeQueue(&temp2, &line2);
			wait_time1 = temp1.processtime;
			wait_time2 = temp2.processtime;
			line_wait += 2*cycle - temp1.arrive -temp2.arrive;
			served+=1;
		}
		if(wait_time1>0) wait_time1--;
		if(wait_time2>0) wait_time2--;
		sun_line += QueueItemCount(&line1)+QueueItemCount(&line2);
	}
	
	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)sun_line/cyclelimit);
		printf("average wait time: %.2f\n", (double)line_wait/served);
	}else puts("No customers");
	
	EmptyTheQueue(&line1);
	EmptyTheQueue(&line2);
	puts("Bye!");
	
	return 0;
}

queue.h

#ifndef LIST_H_
#define LIST_H_

#include<stdbool.h>

typedef struct item{
	long arrive;
	int processtime;
} Item;

#define MAXQUEUE	10

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

typedef struct queue{
	Node *front;
	Node *rear;
	int items;
}Queue;

void InitializeQueue(Queue *pq);
bool QueueIsFull(const Queue *pq);
bool QueueIsEmpty(const Queue *pq);
int	QueueItemCount(const Queue *pq);
bool EnQueue(Item item, Queue *pq);
bool DeQueue(Item *pitem, Queue *pq);
void EmptyTheQueue(Queue *pq);


#endif

queue.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "list.h"

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

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

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

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

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

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);
	if(QueueIsEmpty(pq)) pq->front = pnew;
	else pq->rear->next = pnew;
	pq->rear = pnew;
	pq->items++;
	
	return true;
}
bool DeQueue(Item *pitem, Queue *pq){
	Node *pt;
	if(QueueIsEmpty(pq)) return false;
	CopyToItem(pitem, pq->front);
	pt = pq->front;
	pq->front = pq->front->next;
	free(pt);
	pq->items--;
	
	if(pq->items == 0) pq->rear = NULL;
	return true;
}
void EmptyTheQueue(Queue *pq){
	Item dummy;
	while(!QueueIsEmpty(pq))DeQueue(&dummy,pq);
}

makefile

a.exe:test.o list.h list.o
	gcc -o a.exe test.o list.o
list.o:list.h
	gcc -c list.c
test.o:list.h test.c
	gcc -c test.c 
	
clean:
	del *.o,a.exe

4.3 结果显示

---

5. 第5题

5.1 题目描述

编写一个程序，提示用户输入一个字符串。然后该程序把该字符串的字符逐个艳茹一个栈，然后从栈中弹出这些字符，并显示他们。结果显示为字符串的逆序。

5.2 编程源码

#include<stdio.h>

int main(void){	
	printf("请输入字符串：");
	char c;
	char zhan[100];
	int num=0;
	
	while((c=getchar())!='\n'){
		zhan[num++] = c;
	}
	
	for(int i=num-1;i>=0;--i)putchar(zhan[i]);
	
	return 0;
}

5.3 结果显示

---

6. 第6题

6.1 题目描述

编写一个函数接受3个参数，一个数组名（内含已排序的整数），该数组的元素个数和待查找的整数。如果待查找的整数在数组中，那么该函数返回1，如果该数不在数组中，该函数则返回0。用二分查找法实现。

6.2 编程源码

#include<stdio.h>

int find(const int *num,int len,int n){
	int s = 0;
	int e = len;
	int m = (s+e)>>1;
	
	while(s < e-1){
		if(num[m]<n)s = m;
		else if(n<num[m])e=m;
		else return 1;
		m = (s+e)>>1; 
	}
	return 0;
}

int main(void){	
	int num[10]={0,1,2,3,4,5,6,7,8,9};
	
	printf("%d\n",find(num,10,9));
	printf("%d\n",find(num,10,2));
	printf("%d\n",find(num,10,20));
	return 0;
}

6.3 结果显示

---

7. 第7题

7.1 题目描述

编写一个程序，打开和读取一个文本文件，并统计文件中每个单词出现的次数。用改进的二叉查找树存储单词及其出现的次数。程序在读入文件后，会提供一个有3个选项的菜单。第1个选项是列出所有的单词和出现的次数。第2个选项是让用户输入一个单词，程序报告该单词在文件中出现的次数。第3个选项是退出。

7.2 编程源码

t.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include "tree.h"

char menu(void){
	puts("请输入你的选项：");
	puts("a. 列出全部单词与次数");
	puts("b. 根据用户所列单词，查询次数");
	puts("c. 退出");
	char c;
	c =getchar();
	while(getchar()!='\n');
	return c;
}

void  display(Item item){
	printf("%s: %d\n", item.petname, item.num);
}

void showTree(const Tree*pt){
	Traverse(pt,display);	
}

void showWord(const Tree*pt){
	puts("请输入你的单词：");
	char w[20];
	scanf("%s",w);
	while(getchar()!='\n');
	
	Trnode *t = wordInTree(w,pt);
	printf("%s: %d\n", t->item.petname, t->item.num);
}

int main(int argc, char **argv){
	if(argc<2){
		puts("Please use as follow:");
		exit(1);
	}
	
	FILE *in;
	if((in=fopen(argv[1],"r"))==NULL){
		fprintf(stderr,"Can`t open file %s \n", argv[1]);
		exit(1);
	}
	
	char word[20];
	char c;
	int i=0;
	Item t;
	Tree wTree;
	InitializeTree(&wTree);
	
	while((c=getc(in))!= EOF){
		if(isalpha(c)) word[i++] = c;
		else if(i){
			word[i]='\0';
			strcpy(t.petname, word);
			t.num = 1;
			i = 0;
			word[i]='\0';
			AddItem(&t,&wTree);
		}
	}
	fclose(in);
	
	while(c=menu()){
		switch(c){
			case 'a':showTree(&wTree);break;
			case 'b':showWord(&wTree);break;
			default:puts("Bye!");DeleteAll(&wTree);exit(0);
		}
	}	
	
	return 0;
}

tree.h

#ifndef LIST_H_
#define LIST_H_

#include<stdbool.h>

#define SLEN	20

typedef struct item{
	char petname[SLEN];
	int num;
} Item;

#define MAXITEMS	1000

typedef struct trnode{
	Item item;
	struct trnode *left;
	struct trnode *right;
}Trnode;

typedef struct tree{
	Trnode *root;
	int size;
}Tree;

void InitializeTree(Tree *ptree);
bool TreeIsFull(const Tree *ptree);
bool TreeIsEmpty(const Tree *ptree);
int	TreeItemCount(const Tree *ptree);
bool AddItem(const Item *pi, Tree *ptree);
bool InTree(const Item *pi, const Tree *ptree);
Trnode* wordInTree(char *word,const Tree *ptree);
bool DeleteItem(const Item *pi, Tree *ptree);
void Traverse(const Tree *ptree,void(*pfun)(Item item));
void DeleteAll(Tree *ptree);

#endif

tree.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "tree.h"

typedef struct pair{
	Trnode *parent;
	Trnode *child;
}Pair;

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 bool ToLeft(const Item *i1, const Item *i2){
	int comp1;
	if((comp1 = strcmp(i1->petname, i2->petname))<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 return false;
}

static void AddNode(Trnode *new_node, Trnode *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);
	}else {
		fprintf(stderr, "location error in AddNode()\n");
		exit(1);
	}
}

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 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 DeleteNode(Trnode **ptr){
	Trnode *temp;
	if((*ptr)->left == NULL){
		temp = *ptr;
		*ptr = (*ptr)->right;
		free(temp);
	}else if((*ptr)->left == NULL){
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}else{
		for(temp = (*ptr)->left;temp->right != NULL; temp = temp->right) ;
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
}

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

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

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

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

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

bool AddItem(const Item *pi, Tree *ptree){
	Trnode *new_node;
	if(TreeIsFull(ptree)){
		fprintf(stderr, "Ttee is full\n");
		return false;
	}
	if(SeekItem(pi,ptree).child != NULL){
		new_node = SeekItem(pi,ptree).parent;
		new_node->item.num++;
		return true;
	}
	new_node = MakeNode(pi);
	if(new_node == NULL){
		fprintf(stderr, "Couldn`t create node\n");
		return false;
	}
	ptree->size++;
	if(ptree->root ==NULL) ptree->root = new_node;
	else AddNode(new_node, ptree->root);
	
	return true;	
}

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

Trnode* wordInTree(char *word,const Tree *ptree){
	Item t;
	strcpy(t.petname,word);
	t.num = 0;
	return SeekItem(&t,ptree).child;
}

bool DeleteItem(const Item *pi, Tree *ptree){
	Pair look;
	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);
	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;
}

makefile

a.exe:tree.o tree.h t.o
	gcc -o a.exe tree.o t.o
tree.o:tree.h
	gcc -c tree.c
t.o:tree.h t.c
	gcc -c t.c 
	
clean:
	del *.o,a.exe

7.3 结果显示

---

8. 第8题

8.1 题目描述

修改宠物俱乐部程序，把所有同名的宠物都存储在同一个节点中。当用户选择查找宠物时，程序应询问用户该宠物的名字，然后列出该名字的所有宠物（及种类）。

8.2 编程源码

pets.c

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include"tree.h"
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) *find = '\0';
		else{
			while(getchar()!='\n');
		}
	}
	return ret_val;
}
void printitem(Item item){
	for(int i=0;i<item.num;++i)
		printf("Pets: %-19s Kind:%-19s\n", item.petname, item.petkind[i]);
}
char menu(void){
	int ch;
	puts("Nerfville Pet Club Membership Program");
	puts("Enter the lettercorresponding to your choice");
	puts("a. add a pet\t\tl. show list of pets");
	puts("n. nuber of pets\t\tf.find pets");
	puts("d. delete a pet\t\tq. quit");
	while((ch=getchar())!=EOF){
		while(getchar() != '\n');
		ch = tolower(ch);
		if(strchr("alfndq",ch)==NULL) puts("Please enter an a,l,f,n,d or q:");
		else break;
	}
	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 name of kind:");
		s_gets(temp.petkind[0], SLEN);
		uppercase(temp.petname);
		uppercase(temp.petkind[0]);
		temp.num = 1;
		AddItem(&temp, pt);
	}
}
void droppet(Tree *pt){
	Item temp;
	if(TreeIsEmpty(pt)){
		puts("No entries!");
		return;
	}
	puts("Please enter name of pet you wish to delete:");
	s_gets(temp.petname, SLEN);
	puts("Please enter name of kind:");
	s_gets(temp.petkind[0], SLEN);
	uppercase(temp.petname);
	uppercase(temp.petkind[0]);
	printf("%s the %s", temp.petname, temp.petkind[0]);
	if(DeleteItem(&temp, pt)) printf("is dropped from the club\n");
	else printf("is not a member\n");
}
void showpets(const Tree *pt){
	if(TreeIsEmpty(pt))puts("No entries!");
	else Traverse(pt, printitem);
}
void findpet(const Tree *pt){
	Item temp;
	if(TreeIsEmpty(pt)){
		puts("No entries!");
		return;
	}
	puts("Please enter name of pet you wish to find:");
	s_gets(temp.petname, SLEN);
	puts("Please enter name of kind:");
	s_gets(temp.petkind[0], SLEN);
	uppercase(temp.petname);
	uppercase(temp.petkind[0]);
	printf("%s the %s", temp.petname, temp.petkind[0]);
	if(InTree(&temp, pt)) printf("is a member\n");
	else printf("is not a member\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\n");
	
	return 0;
}

tree.h

#ifndef LIST_H_
#define LIST_H_

#include<stdbool.h>

#define SLEN	20
#define MAXKIND 20

typedef struct item{
	char petname[SLEN];
	char petkind[MAXKIND][SLEN];
	int num;
} Item;

#define MAXITEMS	1000

typedef struct trnode{
	Item item;
	struct trnode *left;
	struct trnode *right;
}Trnode;

typedef struct tree{
	Trnode *root;
	int size;
}Tree;

void InitializeTree(Tree *ptree);
bool TreeIsFull(const Tree *ptree);
bool TreeIsEmpty(const Tree *ptree);
int	TreeItemCount(const Tree *ptree);
bool AddItem(const Item *pi, Tree *ptree);
bool InTree(const Item *pi, const Tree *ptree);
bool DeleteItem(const Item *pi, Tree *ptree);
void Traverse(const Tree *ptree,void(*pfun)(Item item));
void DeleteAll(Tree *ptree);

#endif

tree.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "tree.h"

typedef struct pair{
	Trnode *parent;
	Trnode *child;
}Pair;

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 bool ToLeft(const Item *i1, const Item *i2){
	int comp1;
	if((comp1 = strcmp(i1->petname, i2->petname))<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 return false;
}

static void AddNode(Trnode *new_node, Trnode *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);
	}else {
		fprintf(stderr, "location error in AddNode()\n");
		exit(1);
	}
}

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 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 DeleteNode(Trnode **ptr){
	Trnode *temp;
	if((*ptr)->left == NULL){
		temp = *ptr;
		*ptr = (*ptr)->right;
		free(temp);
	}else if((*ptr)->left == NULL){
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}else{
		for(temp = (*ptr)->left;temp->right != NULL; temp = temp->right) ;
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
}

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

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

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

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

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

bool AddItem(const Item *pi, Tree *ptree){
	Trnode *new_node;
	if(TreeIsFull(ptree)){
		fprintf(stderr, "Ttee is full\n");
		return false;
	}
	if(SeekItem(pi,ptree).child != NULL){
		new_node = SeekItem(pi,ptree).child;
		printf("%d ",new_node->item.num);
		strcpy(new_node->item.petkind[new_node->item.num++], pi->petkind[0]);
		printf("%d ",new_node->item.num);
		return true;
	}
	new_node = MakeNode(pi);
	if(new_node == NULL){
		fprintf(stderr, "Couldn`t create node\n");
		return false;
	}
	ptree->size++;
	if(ptree->root ==NULL) ptree->root = new_node;
	else AddNode(new_node, ptree->root);
	
	return true;	
}

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) 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;
}

makefile

a.exe:tree.o tree.h pets.o
	gcc -o a.exe tree.o pets.o
tree.o:tree.h
	gcc -c tree.c
pets.o:tree.h 
	gcc -c pets.c
	
clean:
	del *.o,a.exe

8.3 结果显示

---