神秘博客

C Primer Plus [第六版]第17章编程练习题答案

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", &current->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;
}

 

 

版权说明:
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

觉得文章有用就请我吃包辣条吧

微信扫一扫打赏