问题描述与题目要求

问题描述： 假定某民航有M个航次的班机，每个航次都只到达一个地方。试为该机场售票处设计一个自动订票和退票系统，要求系统具有以下功能：
（1） 订票：若该航次余票大于等于乘客订票数，则在该航次的乘客表中，插入订票乘客的信息项，并修改该航次有关数据，否则给出相应信息。
（2） 退票：若该航次当前退票数小于等于乘客原订票数，则在相应的乘客表中找到该乘客项，修改该航次及乘客表中有关数据；当某乘客由于退票使订票数为零时，则从乘客表中撤消该数据项。

要求：

（1）描述对航次表和乘客表选用的数据结构。
（2）编程实现飞机票订票和退票系统。

模型假设

1.假设所有输入均为整数且在int类型的表示范围内
2.假设航次是从1到n的连续整数
3.假设每个乘客 ID 均唯一

数据结构的选用

联想到图中的邻接链表，采用相似的数据结构描述该问题
航次表： 用一个数组flight_info_list存储每个航次的乘客表，该数组下标即为航班航次，对应元素即为该航次相关信息（乘客表，航班编号及航班余票数）
乘客表： 用双向链表存储每个航次的乘客表passenger_info_list，每个结点存储乘客的 ID，订票数以及指向前、后结点的指针

编程实现(C语言实现)

/*
 * @Description: 模拟航班的订票系统
 * 模型假设:
 *   1. 飞机最大载客量为300人
 *   2. 共10个航次
 * 用双向链表存储乘客信息
 * 用array存储航班信息
 * @Author: Fishermanykx
 * @Date: 2019-09-29 10:32:56
 * @LastEditors: Fishermanykx
 * @LastEditTime: 2019-09-30 12:29:16
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_CAPACITY 300 // 假定飞机最大载客量为300
#define TOTAL_AIRLINE 10 // 假定不同航线最大数目为10
#define BOOK_TICKET 1
#define REFUND -1
#define EXIT_SYSTEM 0
#define PRINT_INFO 11
#define ROOT 123456

// 某航次航班
struct SingleFlight {
 int flight_id;    // 航班编号，从1开始，到TOTAL_AIRLINE为止
 int remain_tickets; // 该航班余票数
 struct SinglePassenger* passenger_info_list; // 该航班乘客表
};

// 某航次航班的某个乘客的信息
struct PassengerInfo {
 int passenger_id;  // 乘客id
 int ticket_number; // 该乘客购买票数
};

// 乘客表中的一个结点
struct SinglePassenger {
 struct PassengerInfo passenger_info;   // 乘客信息
 struct SinglePassenger* prev_passenger; // 指向前一个乘客的指针
 struct SinglePassenger* next_passenger; // 指向后一个乘客的指针
};

typedef struct SingleFlight SingleFlight;
typedef struct SinglePassenger SinglePassenger;

// 订票操作
SingleFlight* BookTicket(SingleFlight flight_info_list[]);
SinglePassenger* GetNewPassenger(const int new_passenger_id,
                 const int book_ticket_number);
SinglePassenger* AddNewPassenger(SinglePassenger* head,
                 const int new_passenger_id,
                 const int book_ticket_number);

// 退票操作
SingleFlight* Refund(SingleFlight flight_info_list[]);
SinglePassenger* RemovePassenger(SinglePassenger* head, const int passenger_id);
// 判断操作
bool IsPassengerExist(SinglePassenger* head, const int passenger_id);
// 打印操作
void PrintCurrentAirlineInfo(SingleFlight flight_info_list[]);
void PrintPassengerList(SinglePassenger* head, SingleFlight* flight_info_list,
            int airline_id);

int main(void) {
 int order, exit_loop = 1;

 // 初始化航班信息
 SingleFlight* flight_info_list;
 flight_info_list =
   (SingleFlight*)malloc(TOTAL_AIRLINE * sizeof(SingleFlight));
 for (int i = 0; i < TOTAL_AIRLINE; ++i) {
  flight_info_list[i].flight_id = i + 1;
  flight_info_list[i].remain_tickets = MAX_CAPACITY;
  flight_info_list[i].passenger_info_list = NULL;
 }

 /* 登录界面 */
 printf("您好，欢迎使用此系统！\n\n");
 printf("使用说明：\n");
 printf("1. 本程序所有输入均为整数\n");
 printf("2. 可供选择的航次编号为1-%d, 每架次最大载客量为%d\n", TOTAL_AIRLINE,
     MAX_CAPACITY);
 printf(
   "3. 若订票，请输入1；若退票，请输入-1；若退出系统，请输入0; "
   "若要以root用户登录，请输入root密码\n");
 printf("使用说明到此结束，祝您使用愉快！\n");

 // 判断是否以root登录
 int log_in_as_root, root_key;
 bool is_root = false;

 printf("-------------------------------------------------------------\n\n");
 printf("是否以root用户登录？若是，请输入1，否则请输入0:");
 scanf("%d", &log_in_as_root);

 if (log_in_as_root) printf("请输入root密码(按0退出root登录程序)：");
 while (log_in_as_root) {
  scanf("%d", &root_key);
  if (!root_key) {
   break;
  } else if (root_key != ROOT) {
   printf("输入密码错误！请重新输入或按0退出root登录程序：");
  } else {
   is_root = true;
   break;
  }
 }
 // 欢迎界面
 if (is_root)
  printf("欢迎，root用户！输入11可查看当前航次表\n");
 else
  printf("欢迎，普通用户！\n");
 printf("-------------------------------------------------------------\n");

 // 主循环
 while (true) {
  if (is_root)
   printf("请输入1, 0, -1或11中的一个数字: ");
  else
   printf("请输入1, 0, -1中的一个数字: ");

  scanf("%d", &order);
  switch (order) {
   case BOOK_TICKET:
    flight_info_list = BookTicket(flight_info_list);
    break;
   case REFUND:
    flight_info_list = Refund(flight_info_list);
    break;
   case EXIT_SYSTEM:
    exit_loop = 0;
    break;
   case PRINT_INFO:
    printf(
      "-------------------------------------------------------------\n");
    PrintCurrentAirlineInfo(flight_info_list);
    break;
   default:
    printf("非法输入！\n");
    break;
  }
  if (!exit_loop) break;
 }

 return 0;
}

/**
 * @description: 一次订票操作的模拟
 * @param {type}
 * flight_info_list {SingleFlight *}: 航班信息表(航次表)
 * @return:
 */
SingleFlight* BookTicket(SingleFlight flight_info_list[]) {
 /* 获取乘客预定航次 */
 int target_airline;
 printf("可供选择的航次对应的编号为: 1 - %d\n", TOTAL_AIRLINE);
 printf("请输入您想预定的航次(输入0时退出订票程序): ");
 // 判断输入合法性
 while (true) {
  scanf("%d", &target_airline);
  if (target_airline < 0 || target_airline > TOTAL_AIRLINE) {
   printf("您要预定的航次不存在！\n");
   printf("请重新输入一个正确的航次，或按0退出订票程序：");
  } else if (target_airline == 0) {
   printf("-------------------------------------------------------------\n");
   return flight_info_list;
  } else
   break;
 }

 /* 获取乘客id */
 int passenger_id;
 int modify_tickets;
 printf("若您原先已经订票，且想增加您的订票数，请输入1，否则请输入0: ");
 // 判断输入合法性
 while (true) {
  scanf("%d", &modify_tickets);
  if (modify_tickets != 1 && modify_tickets != 0) {
   printf("您输入的是非法命令，请重新输入0(原先未订票)或1(原先已经订票)：");
  } else
   break;
 }
 printf("请输入您的ID: ");
 // 若原先未订票
 while (!modify_tickets) {
  scanf("%d", &passenger_id);
  if (IsPassengerExist(
      flight_info_list[target_airline - 1].passenger_info_list,
      passenger_id)) {
   printf("该ID已存在，请输入一个新的ID: ");
  } else
   break;
 }
 // 若原先已经订票
 if (modify_tickets) {
  scanf("%d", &passenger_id);
  if (!IsPassengerExist(
      flight_info_list[target_airline - 1].passenger_info_list,
      passenger_id)) {
   printf("您原先并未预订该航次的票！\n");
   printf("-------------------------------------------------------------\n");
   return flight_info_list;
  }
 }

 /* 获取乘客预定票数 */
 // 获取当前航次余票数
 int remain_tickets;

 remain_tickets = flight_info_list[target_airline - 1].remain_tickets;
 printf("当前航次余票数为: %d\n", remain_tickets);
 // 若该乘客想修改票数，显示此乘客此前预订的票数
 if (modify_tickets) {
  SinglePassenger* head =
    flight_info_list[target_airline - 1].passenger_info_list;
  while (head->passenger_info.passenger_id != passenger_id) {
   head = head->next_passenger;
  }
  printf("您此前预订的票数为%d张\n", head->passenger_info.ticket_number);
 }
 // 获取乘客想预定的票数
 int target_ticket_num;

 printf("请输入您想预定(或增订)的票数: ");
 // 判断输入合法性
 while (true) {
  scanf("%d", &target_ticket_num);
  if (target_ticket_num > remain_tickets) {
   printf("您想预定的票数为%d, 但当前航次余票数仅为%d, 余票不足！\n",
       target_ticket_num, remain_tickets);
   printf("请输入您想预定的票数，或按0退出订票程序: ");
  } else if (target_ticket_num == 0) {
   printf("-------------------------------------------------------------\n");
   return flight_info_list;
  } else {
   break;
  }
 }

 /* 修改航次余票数 */
 flight_info_list[target_airline - 1].remain_tickets -= target_ticket_num;

 /* 修改乘客表中对应的项 */
 // 判断该乘客原先是否存在
 if (modify_tickets) {
  // 若存在，找到该乘客并修改他的订票项
  SinglePassenger* tmp =
    flight_info_list[target_airline - 1].passenger_info_list;
  while (tmp->passenger_info.passenger_id != passenger_id) {
   tmp = tmp->next_passenger;
  }
  tmp->passenger_info.ticket_number += target_ticket_num;
  printf("增订成功！您现在共预订%d张航次%d的票\n",
      tmp->passenger_info.ticket_number, target_airline);

 } else {
  // 若不存在，则在该航次的乘客列表中增加该乘客及其对应信息
  flight_info_list[target_airline - 1].passenger_info_list = AddNewPassenger(
    flight_info_list[target_airline - 1].passenger_info_list, passenger_id,
    target_ticket_num);
  printf("预订成功！您现在共预订%d张航次%d的票\n", target_ticket_num,
      target_airline);
 }
 printf("-------------------------------------------------------------\n");

 return flight_info_list;
}

/**
 * @description: 查找乘客表(双向链表)中某乘客是否存在
 * @param {type}
 * head {SinglePassenger*}: 双向链表头结点
 * passenger_id {const int}: 待查找的键值
 * @return: 若存在，返回true；否则返回false
 */
bool IsPassengerExist(SinglePassenger* head, const int passenger_id) {
 SinglePassenger* tmp = head;
 bool exist = false;
 if (!head) {
  return false;
 }
 while (tmp) {
  if (tmp->passenger_info.passenger_id == passenger_id) {
   exist = true;
   break;
  }
  tmp = tmp->next_passenger;
 }

 return exist;
}

/**
 * @description: 初始化一个新结点
 * @param {type}
 * new_passenger_id {const int}: 新增加的乘客的id
 * book_ticket_number {const int}: 新增加乘客的订票数
 * @return: 初始化后的结点(前驱，后继均为空指针)
 */
SinglePassenger* GetNewPassenger(const int new_passenger_id,
                 const int book_ticket_number) {
 SinglePassenger* new_passenger =
   (SinglePassenger*)malloc(sizeof(SinglePassenger));

 new_passenger->passenger_info.passenger_id = new_passenger_id;
 new_passenger->passenger_info.ticket_number = book_ticket_number;
 new_passenger->next_passenger = NULL;
 new_passenger->prev_passenger = NULL;

 return new_passenger;
}

SinglePassenger* AddNewPassenger(SinglePassenger* head,
                 const int new_passenger_id,
                 const int book_ticket_number) {
 SinglePassenger* new_passenger =
   GetNewPassenger(new_passenger_id, book_ticket_number);
 if (!head) {
  head = new_passenger;
 } else {
  // 直接从头部插入
  new_passenger->next_passenger = head->next_passenger;
  if (head->next_passenger) {
   head->next_passenger->prev_passenger = new_passenger;
  }
  new_passenger->prev_passenger = head;
  head->next_passenger = new_passenger;
 }

 return head;
}

/**
 * @description: 一次退票操作的模拟
 * @param {type}
 * flight_info_list {SingleFlight *}: 航次表
 * @return: 修改后的航次表
 */
SingleFlight* Refund(SingleFlight flight_info_list[]) {
 /* 获取乘客预定航次 */
 int target_airline;

 printf("可供选择的航次对应的编号为: 1 - %d\n", TOTAL_AIRLINE);
 printf("请输入您想退订的航次(输入0时退出订票程序): ");
 // 判断输入合法性
 while (true) {
  scanf("%d", &target_airline);
  if (target_airline < 0 || target_airline > TOTAL_AIRLINE) {
   printf("您要退订的航次不存在！\n");
   printf("请重新输入一个正确的航次，或按0退出退票程序：");
  } else if (target_airline == 0) {
   printf("-------------------------------------------------------------\n");
   return flight_info_list;
  } else
   break;
 }

 /* 获取乘客ID并判断其合法性 */
 int passenger_id;

 printf("请输入您的ID: ");
 scanf("%d", &passenger_id);

 SinglePassenger* head =
   flight_info_list[target_airline - 1].passenger_info_list;

 if (!IsPassengerExist(head, passenger_id)) {
  printf("您并未预订此次航班！\n");
  printf("-------------------------------------------------------------\n");
  return flight_info_list;
 }

 /* 获取乘客退票数 */
 // 打印此乘客的预订票数
 SinglePassenger* tmp = head;

 while (tmp->passenger_info.passenger_id != passenger_id) {
  tmp = tmp->next_passenger;
 }
 printf("您当前预订的票数为: %d张\n", tmp->passenger_info.ticket_number);
 // 读入退票数
 int refund_ticket_num;

 printf("请输入您的退票数(输入0退出退票程序): ");
 scanf("%d", &refund_ticket_num);
 // 输入合法性检查
 int cur_ticket = tmp->passenger_info.ticket_number; // 当前该乘客预订的票数
 while (cur_ticket < refund_ticket_num) {
  if (!refund_ticket_num) {
   printf("-------------------------------------------------------------\n");
   return flight_info_list;
  }
  printf("您输入的退票数大于您当前预订的票数！");
  printf("请重新输入退票数(输入0退出退票程序): ");
  scanf("%d", &refund_ticket_num);
 }

 /* 退票 */
 // 更新航次表
 flight_info_list[target_airline - 1].remain_tickets += refund_ticket_num;
 // 更新乘客表
 if (cur_ticket > refund_ticket_num) {
  tmp->passenger_info.ticket_number -= refund_ticket_num;
  printf("您已成功退票，现在您%d航次的余票为%d张\n", target_airline,
      tmp->passenger_info.ticket_number);
 } else {
  flight_info_list[target_airline - 1].passenger_info_list =
    RemovePassenger(head, passenger_id);
  printf("您已成功退票，现在您%d航次的余票为%d张\n", target_airline, 0);
 }
 printf("-------------------------------------------------------------\n");

 return flight_info_list;
}

/**
 * @description: 从乘客表中删除某个结点
 * @param {type}
 * head {SinglePassenger *}: 乘客表
 * passenger_id {const int}: 待删除乘客的id
 * @return: 修改后的航次表
 */
SinglePassenger* RemovePassenger(SinglePassenger* head,
                 const int passenger_id) {
 SinglePassenger* tmp = head;

 while (tmp->passenger_info.passenger_id != passenger_id) {
  tmp = tmp->next_passenger;
 }
 // 若为头结点
 if (!tmp->prev_passenger) {
  head = head->next_passenger;
 }
 // 若为尾结点
 else if (!tmp->next_passenger) {
  tmp->prev_passenger->next_passenger = NULL;
 }
 // 若为中间某个结点
 else {
  tmp->prev_passenger->next_passenger = tmp->next_passenger;
  tmp->next_passenger->prev_passenger = tmp->prev_passenger;
 }

 return head;
}

/**
 * @description: 输出当前航次表
 * @param {type}
 * flight_info_list {SingleFlight *}: 航班信息表(航次表)
 * @return: void
 */
void PrintCurrentAirlineInfo(SingleFlight flight_info_list[]) {
 for (int current_airline_index = 1; current_airline_index <= TOTAL_AIRLINE;
    ++current_airline_index) {
  int remain_ticket_num =
    flight_info_list[current_airline_index - 1].remain_tickets;
  SinglePassenger* head =
    flight_info_list[current_airline_index - 1].passenger_info_list;
  // 输出
  PrintPassengerList(head, flight_info_list, current_airline_index);
  printf("-------------------------------------------------------------\n");
 }
}

/**
 * @description: 打印某航次的乘客表
 * @param {type}
 * head {SinglePassenger*}: 乘客表的头结点
 * flight_info_list {SingleFlight *}: 航次表
 * @return:
 */
void PrintPassengerList(SinglePassenger* head, SingleFlight* flight_info_list,
            int airline_id) {
 if (!head) {
  printf("%d航次无乘客订票！\n", airline_id);
 } else {
  printf("%d航次余票数为: %d, 其中：\n", airline_id,
      flight_info_list[airline_id - 1].remain_tickets);
 }
 while (head) {
  printf("ID为%d的乘客订票数为%d张\n", head->passenger_info.passenger_id,
      head->passenger_info.ticket_number);
  head = head->next_passenger;
 }
 printf("\n");
}