1. 修改程序清单17.2,使其既能以正序又能以逆序显示电影列表。一种方法是修改链表定义以使链表能被双向遍历;另一种方法是使用递归。
//使用结构链表 #include <stdio.h> #include <stdlib.h> //提供malloc()原型 #include <string.h> //提供strcpy()原型 #define TSIZE 15 //储存片名的数组大小 struct film { char title[TSIZE]; int rating; struct film *last; //指向链表中的上一个结构 struct film *next; //指向链表中的下一个结构 }; char *s_gets(char *str, int n); int main() { struct film *head = NULL; struct film *prev, *current; char input[TSIZE]; //收集并储存信息 puts("输入电影片名:"); while (s_gets(input, TSIZE) != NULL && input[0] != '\0') { current = (struct film *)malloc(sizeof(struct film)); if (head == NULL) //第一个结构 { head = current; head->last = NULL; } else //后续结构 { current->last = prev; prev->next = current; } current->next = NULL; strcpy_s(current->title, TSIZE, input); puts("输入你的评级<0-10>:"); scanf_s("%d", ¤t->rating); while (getchar() != '\n') continue; puts("输入下一个电影标题[空行停止]:"); prev = current; } //显示电影列表 if (head == NULL) printf("没有输入数据."); else { printf("这是电影列表:\n"); puts("倒序: "); while (current != NULL) { printf("电影: %s 评级: %d\n", current->title, current->rating); current = current->last; } puts("顺序: "); current = head; while (current != NULL) { printf("电影: %s 评级: %d\n", current->title, current->rating); current = current->next; } //完成任务,释放已分配的内存 current = head; while (current != NULL) { head = current->next; free(current); current = head; } } puts("再见"); system("pause"); return 0; } char *s_gets(char *str, int n) { char *ret_val, *find; ret_val = fgets(str, n, stdin); if (ret_val) { find = strchr(str, '\n'); if (find) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; }
2.
假设list.h(程序清单17.3)如下定义列表: typedef struct list { Node * head;/*指向列表首*/ Node * end;/*指向列表尾*/ } List; 根据这个定义,重写list.c(程序清单17.5)函数,并用films3.c(程序清单17.4)测试结果代码。
//简单链表类型的头文件 #ifndef LIST_H_ #define LIST_H_ #include <stdbool.h> //特定程序的声明 #define TSIZE 45 struct film { char title[TSIZE]; int rating; }; //一般类型的定义 typedef struct film Item; typedef struct node { Item item; struct node *next; } Node; typedef struct list { Node *head; //指向list的开头 Node *end; //指向list的末尾 } List; //函数原型 //操作 初始化一个链表 //前提条件 plist指向一个链表 //后置条件 链表初始化为空 void InitializeList(List *plist); //操作 确定链表是否为空定义,plist指向一个已初始化的链表 //后置条件 如果链表为空,该函数返回true; 否则返回false bool ListIsEmpty(const List *plist); //操作 确定链表中的项数,plist指向一个已初始化的链表 //后置条件 如果链表已满,该函数返回真,否则返回假 bool ListIsFull(const List *plist); //操作 确定链表中的项数,plist指向一个已初始化的链表 //后置条件 该函数返回链表中的项数 unsigned int ListItemCount(const List *plist); //操作 在链表的末尾添加项 //前提条件 item是一个待添加至链表的项,plist指向一个已初始化的链表 //后置条件 如果可以,该函数在链表末尾添加一个项,且返回true; 否则返回false bool AddItem(Item item, List *plist); //操作 把函数作用于链表中的每一项 // plist指向一个已初始化的链表 // pfun指向一个函数,该函数接受一个Item类型的参数,且无返回值 //后置条件 pfun指向的函数作用于链表中的每一项一次 void Traverse(const List *plist, void(*pfun)(Item item)); //操作 释放已分配的内存(如果有的话) // plist指向一个已初始化的链表 //后置条件 释放了为链表分配的所有内存,链表设置为空 void EmptyTheList(List *plist); #endif
//支持链表操作的函数 #include <stdio.h> #include <stdlib.h> #include "list.h" //局部函数原型 static void CopyToNode(Item item, Node *pnode); //接口函数 //把链表设置为空 void InitializeList(List *plist) { plist->head = NULL; plist->end = NULL; } //如果链表为空,返回true bool ListIsEmpty(const List *plist) { if (plist->head == NULL) return true; else return false; } //如果链表已满,返回true 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; } //创建储存项的节点,并将其添加至由plist指向的链表末尾(较慢的实现) bool AddItem(Item item, List *plist) { Node *pnew; pnew = (Node *)malloc(sizeof(Node)); if (pnew == NULL) return false; //失败时退出函数 CopyToNode(item, pnew); pnew->next = NULL; if (plist->end != NULL) plist->end->next = pnew; if (plist->head == NULL) //空链表,把pnew放在链表的开头 { plist->head = pnew; plist->end = pnew; } else plist->end = pnew; return true; } //访问每个节点并执行pfun指向的函数 void Traverse(const List *plist, void(*pfun)(Item item)) { Node *pnode = plist->head; //设置链表的开始 while (pnode != NULL) { (*pfun)(pnode->item); //把函数应用于链表中的项 pnode = pnode->next; //前进到下一项 } } //释放由malloc()分配的内存 //设置链表指针为NULL void EmptyTheList(List *plist) { Node *psave; Node *temp; temp = plist->head; while (temp != NULL) { psave = temp->next; //保存下一个节点的地址 free(temp); //释放当前节点 temp = psave; //前进至下一个节点 } } //局部函数定义 //把一个项拷贝到节点中 static void CopyToNode(Item item, Node *pnode) { pnode->item = item; //拷贝结构 }
//使用抽象数据类型(ADT)风格的链表 #include <stdio.h> #include <stdlib.h> #include <string.h> #include "list.h" void showmovies(Item item); char *s_gets(char *str, int n); int main() { List movies; Item temp; //初始化 InitializeList(&movies); if (ListIsFull(&movies)) { fprintf(stderr, "没有可用的内存! 再见!\n"); exit(EXIT_FAILURE); } //获取用户输入并储存 puts("输入电影标题:"); while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0') { puts("输入你的评级<0-10>:"); scanf_s("%d", &temp.rating); while (getchar() != '\n') continue; if (AddItem(temp, &movies) == false) { fprintf(stderr, "分配内存问题\n"); break; } if (ListIsFull(&movies)) { puts("名单已经满了."); break; } puts("输入下一个电影标题[空行停止]:"); } //显示 if (ListIsEmpty(&movies)) printf("没有输入数据."); else { printf("这是电影列表:\n"); Traverse(&movies, showmovies); } printf("你输入了 %d 部电影.\n", ListItemCount(&movies)); //清理 EmptyTheList(&movies); printf("完成\n"); system("pause"); return 0; } void showmovies(Item item) { printf("电影: %s 评级: %d\n", item.title, item.rating); } char *s_gets(char *str, int n) { char *ret_val, *find; ret_val = fgets(str, n, stdin); if (ret_val) { find = strchr(str, '\n'); if (find) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; }
3.
假设list.h(程序清单17.3)如下定义列表: #define MAXSIZE 100 typedef struct list { Item enteries[MAXSIZE]; /*项目数组*/ int items; /*列表中项目的个数*/ } List; 根据这个定义,重写list.c(程序清单17.5)函数,并用films3.c(程序清单17.4)测试结果代码。
#ifndef LIST_H_ #define LIST_H_ #include <stdbool.h> #define MAXSIZE 100 //特定程序的声明 #define TSIZE 45 struct film { char title[TSIZE]; int rating; }; //一般类型的定义 typedef struct film Item; typedef struct list { Item entries[MAXSIZE]; //内含项的数组 int items; //list中的项数 } List; //函数原型 void AddItem(Item item, Item *plist); #endif
#include <stdio.h> #include <stdlib.h> #include "list.h" //局部函数原型 static void CopyToNode(Item item, Item *pnode); //接口函数 void AddItem(Item item, Item *plist) { CopyToNode(item, plist); } //局部函数定义 //把一个项拷贝到节点中 static void CopyToNode(Item item, Item *pnode) { *pnode = item; //拷贝结构 }
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "list.h" void showmovies(Item item); char *s_gets(char *str, int n); int main() { List movies; Item temp; int i = 0; int j = 0; //获取用户输入并储存 puts("输入电影标题:"); while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0') { puts("输入你的评级<0-10>:"); scanf_s("%d", &temp.rating); while (getchar() != '\n') continue; AddItem(temp, &movies.entries[i]); i++; movies.items = i; if (i == MAXSIZE) { puts("名单已经满了."); break; } puts("输入下一个电影标题[空行停止]:"); } //显示 if (i == 0) printf("没有输入数据.\n"); else { printf("这是电影列表:\n"); while (j < i) { showmovies(movies.entries[j]); j++; } printf("你输入了 %d 部电影.\n", movies.items); } printf("完成\n"); system("pause"); return 0; } void showmovies(Item item) { printf("电影: %s 评级: %d\n", item.title, item.rating); } char *s_gets(char *str, int n) { char *ret_val, *find; ret_val = fgets(str, n, stdin); if (ret_val) { find = strchr(str, '\n'); if (find) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; }
4. 重写mall.c(程序清单17.9(图书印的是17.7,应该是印刷错误))使其使用两个队列模拟两个摊位。
#ifndef _QUEUE_H_ #define _QUEUE_H_ #include <stdbool.h> //在这里插入Item类型的定义 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
#include <stdio.h> #include <stdlib.h> #include "queue.h" //局部函数 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) { fputs("错误: 分配内存失败.\n", stderr); exit(EXIT_FAILURE); } CopyToNode(item, pnew); pnew->next = NULL; if (QueueIsEmpty(pq)) pq->front = pnew; //项位于队列首端 else pq->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; return true; } //清空队列 void EmptyTheQueue(Queue *pq) { Item dummy; while (!QueueIsEmpty(pq)) DeQueue(&dummy, pq); } //局部函数 static void CopyToNode(Item item, Node *pn) { pn->item = item; } static void CopyToItem(Node *pn, Item *pi) { *pi = pn->item; }
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "queue.h" #define MIN_PER_HR 60.0 #define SIZE 2 bool newcustomer(double x); //是否有新顾客到来 Item customertime(long when); //设置顾客参数 int main() { Queue line[SIZE]; Item temp[2]; //新的顾客数据 int hours; //模拟小时数 int perhour; //每小时平均多少位顾客 long cycle; //分钟 long cyclelimit; //总分钟 long turnaways = 0; //因团队已满被拒的顾客数量 long customers[SIZE] = { 0,0 }; //加入队列的顾客数量 long served[SIZE] = { 0,0 }; //在模拟期间咨询过Sigmund的顾客数量 long sum_line = 0; //累计队列总长 int wait_time[SIZE] = { 0,0 }; //从当前到Sigmund空闲所需的时间 double min_per_cust; //顾客到来的平均时间 long line_wait[SIZE] = { 0,0 }; //队列累计的等待时间 int i; for (i = 0; i < SIZE; i++) InitializeQueue(&line[i]); srand((unsigned int)time(0));//随机种子 puts("案例研究:Sigmund Lander的建议展位\n输入模拟小时数:"); scanf_s("%d", &hours); cyclelimit = (long)(MIN_PER_HR * hours); //小时转换为分钟 puts("输入每小时的平均客户数量:"); scanf_s("%d", &perhour); min_per_cust = MIN_PER_HR / perhour; //平均几分钟来一个顾客 for (cycle = 0; cycle < cyclelimit; cycle++) { if (newcustomer(min_per_cust)) { if (QueueIsFull(&line[0]) || QueueIsFull(&line[1])) turnaways++; else { if (line[0].items > line[1].items) { temp[1] = customertime(cycle); EnQueue(temp[1], &line[1]); customers[1]++; } else { temp[0] = customertime(cycle); EnQueue(temp[0], &line[0]); customers[0]++; } } } if (wait_time[0] <= 0 && !QueueIsEmpty(&line[0])) { DeQueue(&temp[0], &line[0]); wait_time[0] = temp[0].processtime; line_wait[0] += cycle - temp[0].arrive; served[0]++; } if (wait_time[1] <= 0 && !QueueIsEmpty(&line[1])) { DeQueue(&temp[1], &line[1]); wait_time[1] = temp[1].processtime; line_wait[1] += cycle - temp[1].arrive; served[1]++; } if (wait_time[0] > 0) wait_time[0]--; if (wait_time[1] > 0) wait_time[1]--; sum_line += QueueItemCount(&line[0]) + QueueItemCount(&line[1]); } for (i = 0; i < SIZE; i++) { if (customers[i] > 0) { puts("************************"); printf("摊位 %d:\n", i + 1); printf("顾客到来: %ld\n", customers[i]); printf("顾客咨询: %ld\n", served[i]); printf("平均等待时间: %.2f 分钟\n", (double)line_wait[i] / served[i]); } else { printf("摊位 %d:", i + 1); puts("没有顾客!"); } } if (customers[0] > 0) { puts("************************"); printf("总拒绝顾客: %ld\n", turnaways); printf("平均队列大小: %.2f\n", (double)sum_line / cyclelimit); puts("************************"); EmptyTheQueue(&line[0]); EmptyTheQueue(&line[1]); } puts("再见!"); system("pause"); return 0; } //x是顾客到来的平均时间(单位:分钟) //如果1分钟内有顾客到来,则返回true bool newcustomer(double x) { if (rand()*x / RAND_MAX < 1) return true; else return false; } //when 是顾客到来的时间 //该函数返回一个Item结构,该顾客到达的时间设置为when //咨询时间设置为1-3的随机值 Item customertime(long when) { Item cust; cust.processtime = rand() % 3 + 1; cust.arrive = when; return cust; }
5. 编写一个程序,让您输入一个字符串。改程序将此字符串中的字符逐个地压入一个栈(请参见复习题5),然后弹出这些字符并显示。结果是将字符串按逆序显示。
#ifndef _STACK_H_ #define _STACK_H_ #include <stdbool.h> #define MAXSTACK 100 typedef char Item; typedef struct stack { Item items; struct stack *next; } Stack; typedef struct list { Stack *head; int count; Stack *end; } List; //初始化栈 void InitializeStack(List *ps); //检查栈是否已满 bool FullStack(const List *ps); //检查栈是否为空 bool EmptyStack(const List *ps); //把项压入栈顶 bool Push(Item item, List *ps); //从栈顶删除项 bool Pop(Item *pitem, List *ps); #endif
#include <stdio.h> #include <stdlib.h> #include "stack.h" //初始化栈 void InitializeStack(List *ps) { ps->head = ps->end = NULL; ps->count = 0; } //检查栈是否已满 bool FullStack(const List *ps) { return ps->count == MAXSTACK; } //检查栈是否为空 bool EmptyStack(const List *ps) { return ps->count == 0; } //把项压入栈顶 bool Push(Item item, List *ps) { Stack *temp; temp = (Stack *)malloc(sizeof(Stack)); if (temp == NULL) return false; temp->items = item; temp->next = NULL; if (ps->head != NULL) temp->next = ps->head; if (ps->end == NULL) { ps->end = temp; ps->head = temp; } else ps->head = temp; ps->count++; return true; } //从栈顶删除项 bool Pop(Item *pitem, List *ps) { Stack *temp; if (EmptyStack(ps)) return false; *pitem = ps->head->items; temp = ps->head->next; free(ps->head); ps->head = temp; ps->count--; return true; }
#include <stdio.h> #include "stack.h" int main() { Item temp; List str; //初始化 InitializeStack(&str); puts("请输入字符串:"); while ((temp = getchar()) != '\n') { if (!Push(temp, &str)) //入栈 { puts("错误: 栈已满!"); break; } } //出栈 if (!EmptyStack(&str)) { while (Pop(&temp, &str)) printf("%c", temp); } puts("\n完成"); system("pause"); return 0; }
6. 写一个接受3个参数的函数。这3个参数为:存有已排序的整数的数组名,数组元素个数和要查找的整数。如果该整数在数组中,函数返回1;否则返回0。函数用二分查找法实现。
#include <stdio.h> #include <stdbool.h> #define SIZE 100 //二分查找法 bool find(int ar[], int n, int num); int count = 0; int main() { int n[SIZE]; int i; int num; for (i = 0; i < SIZE; i++) n[i] = i + 1; puts("********二分查找系统********"); puts("请输入你要查找的整数:"); while (scanf_s("%d", &num) == 1) { if (find(n, SIZE, num)) printf("结果: 存在\n查找次数: %d\n", count); else printf("结果: 不存在\n查找次数: %d\n", count); count = 0; puts("****************************"); puts("请输入下一个整数[q退出]:"); } puts("再见"); puts("pause"); return 0; } //二分查找法 bool find(int ar[], int n, int num) { int half; int min = 0; int max = n; while (1) { count++; half = (min + max) / 2; if (ar[half] > num) { max = half; } else { min = half; } if (ar[half] == num) return true; if (max == 0 || min == n - 1) return false; if (min == max - 1) return false; } }
7. 编写一个程序,能打开、读入一个文本文件并统计文件中单词出现的次数。用改进的二叉搜索树存储单词及其出现的次数。程序读入文件后,会提供一个有三个选项的菜单。第一个选项为列出所有的单词连同其出现的次数。第二个选项为让您输入一个单词,程序报告该单词在文件中出现的次数。第三个选项为退出。
#ifndef _TREE_H_ #define _TREE_H_ #include <stdbool.h> #define SLEN 20 typedef struct item { char words[SLEN]; int count; } Item; #define MAXITEMS 10 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 TreeIsEmpty(const Tree *ptree); //确定树是否已满 bool TreeIsFull(const Tree *ptree); //确定树的项数 int TreeItemCount(const Tree *ptree); //在树中添加一个项 bool AddItem(const Item *pi, Tree *ptree); //在树中查找一个项 void InTree(const Item *pi, const Tree *ptree); //显示树 void ShowTree(const Tree *ptree); //释放树 void DeleteTree(Tree *ptree); #endif
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" //局部数据类型 typedef struct pair { Trnode *parent; //指向根 Trnode *child; //指向子 } Pair; //局部函数原型 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 Pair SeekItem(const Item * pi, const Tree * ptree); static void DeleteAllNodes(Trnode * ptr); static void ShowAll(Trnode * root); //把树初始化为空 void InitializeTree(Tree *ptree) { ptree->root = NULL; ptree->size = 0; } //确定树是否为空 bool TreeIsEmpty(const Tree *ptree) { return ptree->size == 0; } //确定树是否已满 bool TreeIsFull(const Tree *ptree) { return ptree->size == MAXITEMS; } //确定树的项数 int TreeItemCount(const Tree *ptree) { return ptree->size; } //在树中添加一个项 bool AddItem(const Item *pi, Tree *ptree) { Trnode *temp; Trnode *Temp; if (TreeIsFull(ptree)) { fprintf(stderr, "树已满\n"); return false; /* 提前返回 */ } if (TreeItemCount(ptree) > 0) { if ((Temp = SeekItem(pi, ptree).child) != NULL) { Temp->item.count++; return true; } } temp = (Trnode *)malloc(sizeof(Trnode)); if (temp == NULL) { fprintf(stderr, "无法创建节点\n"); return false; /* 提前返回 */ } else { temp->item = *pi; temp->left = temp->right = NULL; } if (TreeIsEmpty(ptree)) ptree->root = temp; else AddNode(temp, ptree->root); ptree->size++; return true; } //添加节点 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); } } //对比左子树 static bool ToLeft(const Item * i1, const Item * i2) { if (strcmp(i1->words, i2->words) < 0) return true; else return false; } //对比右子树 static bool ToRight(const Item * i1, const Item * i2) { if (strcmp(i1->words, i2->words) > 0) return true; else return false; } //查找 static Pair SeekItem(const Item * pi, const Tree * ptree) { Pair temp; temp.parent = NULL; temp.child = ptree->root; if (temp.child == NULL) return temp; while (temp.child != NULL) { if (ToLeft(pi, &(temp.child->item))) { temp.parent = temp.child; temp.child = temp.child->left; } else if (ToRight(pi, &(temp.child->item))) { temp.parent = temp.child; temp.child = temp.child->right; } else break; } return temp; } //在树中查找一个项 void InTree(const Item *pi, const Tree *ptree) { Trnode *Temp; if ((Temp = SeekItem(pi, ptree).child) != NULL) { puts("结果: 找到"); printf("单词: %s\n出现次数: %d\n", Temp->item.words, Temp->item.count); } else puts("结果: 未找到"); } void DeleteAll(Tree * ptree) { DeleteAllNodes(ptree->root); ptree->root = NULL; ptree->size = 0; } static void DeleteAllNodes(Trnode * root) { Trnode * pright; if (root != NULL) { pright = root->right; DeleteAllNodes(root->left); free(root); DeleteAllNodes(pright); } } static void ShowAll(Trnode * root) { Trnode * pright; if (root != NULL) { printf("单词: %s \t出现次数: %d\n", root->item.words, root->item.count); pright = root->right; ShowAll(root->left); ShowAll(pright); } } void DeleteTree(Tree *ptree) { if (!TreeIsEmpty(ptree)) DeleteAll(ptree); } //显示树 void ShowTree(const Tree *ptree) { if (!TreeIsEmpty(ptree)) ShowAll(ptree->root); }
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include "tree.h" void menu(); char *s_gets(char *st, int n); int main() { errno_t err; FILE *fp; Item temp; Tree file; char ch; int i = 0; int num; if ((err = fopen_s(&fp, "text.dat", "r")) != 0) { fputs("错误: 打开文件失败\n", stderr); exit(EXIT_FAILURE); } InitializeTree(&file); while ((ch = getc(fp)) != EOF) { if (isgraph(ch)) { temp.words[i] = ch; i++; } else { if (temp.words[i - 1] == ',' || temp.words[i - 1] == '.') temp.words[i - 1] = '\0'; else temp.words[i] = '\0'; i = 0; temp.count = 1; if (!AddItem(&temp, &file)) break; } } menu(); while (scanf_s("%d", &num) == 1 && num != 3) { while (getchar() != '\n') continue; if (num == 1) { ShowTree(&file); printf("总共添加了 %d 个单词\n", file.size); } else if (num == 2) { puts("请输入你要查找的单词:"); s_gets(temp.words, SLEN); InTree(&temp, &file); } else { puts("错误: 请输入正确的选项"); continue; } menu(); } //释放树 DeleteTree(&file); //关闭文件 fclose(fp); system("pause"); return 0; } char *s_gets(char *st, int n) { char *ret_val, *find; ret_val = fgets(st, n, stdin); if (ret_val) { find = strchr(st, '\n'); if (find) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; } void menu() { puts("*********二叉树文件单词统计*********"); puts("1. 显示所有单词 \t2. 查找单词"); puts("3. 退出"); puts("************************************"); }
8. 修改宠物俱乐部程序,使所有同名的宠物存储在相同节点中的一个列表中。当用户选择查找一个宠物时,程序要求用户给出宠物名,而后列出所有具有此名字的宠物(连同它们的种类)。此题目只有2个要求我顺便把其他功能也一起修改了。
#ifndef _TREE_H_ #define _TREE_H_ #include <stdbool.h> //根据具体情况重新定义Item #define SLEN 20 typedef struct item { char petname[SLEN]; //宠物名字 char petkind[SLEN][SLEN]; //宠物种类 int count; //同名个数 } Item; #define MAXITEMS 10 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 TreeIsEmpty(const Tree *ptree); //确定树是否已满 bool TreeIsFull(const Tree *ptree); //确定树的项数 int TreeItemCount(const Tree *ptree); //在树中添加一个项 bool AddItem(const Item *pi, Tree *ptree); //在树中查找一个项 void 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); //显示树中数量 void CountAll(Tree *ptree); #endif
#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 bool TypePet(const Item * i1, 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); static void CountAllNodes(Trnode * root); 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; Trnode *temp; if (TreeIsFull(ptree)) { fprintf(stderr, "树已满\n"); return false; /* 提前返回 */ } if ((temp = SeekItem(pi, ptree).child) != NULL) { strcpy_s(temp->item.petkind[temp->item.count], SLEN, pi->petkind[0]); temp->item.count++; return true; /* 提前返回 */ } new_node = MakeNode(pi); /* 指向新节点 */ if (new_node == NULL) { fprintf(stderr, "无法创建节点\n"); return false; /* 提前返回 */ } /* 成功创建了一个新节点 */ ptree->size++; if (ptree->root == NULL) /* 情况 1: 树为空 */ ptree->root = new_node; /* 新节点为树的根节点 */ else /* 情况 2: 树不为空 */ AddNode(new_node, ptree->root); /* 在树中添加新节点 */ return true; } void InTree(const Item * pi, const Tree * ptree) { Trnode *temp; int i; if ((temp = SeekItem(pi, ptree).child) != NULL) { printf("查询结果: 找到如下会员\n"); for (i = 0; i < temp->item.count; i++) printf("宠物: %-19s 种类: %-19s\n", temp->item.petname, temp->item.petkind[i]); } else printf("查询结果: 未找到如下会员\n宠物: %-19s \n", pi->petname); } bool DeleteItem(const Item * pi, Tree * ptree) { Pair look; Trnode *temp; look = SeekItem(pi, ptree); if (look.child == NULL) return false; temp = look.child; if (temp->item.count > 1) { if (TypePet(pi, &temp->item)) return true; else return false; } else { 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; } /* 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 CountAllNodes(Trnode * root) { Trnode * pright; extern Count; if (root != NULL) { Count += root->item.count; pright = root->right; CountAllNodes(root->left); CountAllNodes(pright); } } 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, "位置错误 AddNode()\n"); exit(1); } } static bool ToLeft(const Item * i1, const Item * i2) { if (strcmp(i1->petname, i2->petname) < 0) return true; else return false; } static bool TypePet(const Item * i1, Item * i2) { int i, j; for (i = 0; i < i2->count; i++) { if (strcmp(i1->petkind[0], i2->petkind[i]) == 0) { if (i < i2->count) { for (j = i + 1; j < i2->count; j++) { strcpy_s(i2->petkind[i], SLEN, i2->petkind[j]); i++; } i2->count--; return true; } else { i2->count--; i2->petkind[i][0] = '\0'; return true; } } } return false; } static bool ToRight(const Item * i1, const Item * i2) { if (strcmp(i1->petname, i2->petname) > 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; /* 提前返回 */ 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; /* look.child 目标项的节点 */ } return look; /* 成功返回 */ } //显示树中数量 void CountAll(Tree *ptree) { extern Count; CountAllNodes(ptree->root); printf("%d 只宠物在俱乐部\n", Count); } static void DeleteNode(Trnode **ptr) /* ptr 时指向目标节点的父节点指针成员的地址 */ { 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 /* 被删除的节点有2个子节点 */ { /* 找到重新连接右子树的位置 */ for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right) continue; temp->right = (*ptr)->right; temp = *ptr; *ptr = (*ptr)->left; free(temp); } }
#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 Count = 0; 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': CountAll(&pets); Count = 0; break; case 'd': droppet(&pets); break; default: puts("切换错误"); } putchar('\n'); } DeleteAll(&pets); puts("Bye."); return 0; } char menu(void) { int ch; puts("******Nerfville 宠物俱乐部会员计划******"); puts("输入您选择的相应字母:"); puts("a) 添加一只宠物 \tl) 显示宠物列表"); puts("n) 宠物数量 \t\tf) 查找宠物"); puts("d) 删除一只宠物 \tq) 退出"); puts("****************************************"); while ((ch = getchar()) != EOF) { while (getchar() != '\n') /* 处理输入行的剩余内容 */ continue; ch = tolower(ch); if (strchr("alrfndq", ch) == NULL) puts("请输入 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("俱乐部没有空间!"); else { puts("请输入宠物的名字:"); s_gets(temp.petname, SLEN); puts("请输入宠物类型:"); s_gets(temp.petkind[0], SLEN); uppercase(temp.petname); uppercase(temp.petkind[0]); temp.count = 1; AddItem(&temp, pt); } } void showpets(const Tree * pt) { if (TreeIsEmpty(pt)) puts("没有条目!"); else Traverse(pt, printitem); } void printitem(Item item) { int i; for (i = 0; i < item.count; i++) printf("宠物: %-19s 种类: %-19s\n", item.petname, item.petkind[i]); } void findpet(const Tree * pt) { Item temp; if (TreeIsEmpty(pt)) { puts("没有条目!"); return; /* 如果树为空,则退出该函数 */ } puts("请输入你想查找的宠物的名字:"); s_gets(temp.petname, SLEN); uppercase(temp.petname); InTree(&temp, pt); } void droppet(Tree * pt) { Item temp; if (TreeIsEmpty(pt)) { puts("没有条目!"); return; /* 如果树为空,则退出该函数 */ } puts("请输入您希望删除的宠物名称:"); s_gets(temp.petname, SLEN); puts("请输入宠物种类:"); 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("从俱乐部删除.\n"); else printf("不是会员.\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) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; }