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