C Primer Plus 第6版 编程练习 chapter 17
发布时间：2024年01月23日
文章目录
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",¤t->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",¤t->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 结果显示
文章来源:https://blog.csdn.net/Bell_corp/article/details/135685350
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 单目相机标定理论及张正友标定法总结
- Apple Find My「查找」认证芯片找哪家，认准伦茨科技ST17H6x芯片
- inner join / left join / right join
- 七款网工在线画拓扑工具
- 游戏找不到emp.dll，无法运行的5种解决方法
- Abp vNext（四）运行项目
- PHP 读取excel输入为HTML
- C Primer Plus（第六版）13.11 编程练习 第12题
- 编程领域新巨头：Phind-CodeLlama-34B-v2的技术优势揭秘
- Docker 如何删除所有没有名字的镜像