C语言数据结构课设航空订票系统链表与队列实战航空订票系统是数据结构课程设计的经典案例它完美融合了链表和队列这两种基础数据结构。本文将深入探讨如何用C语言实现一个功能完整的航空订票系统重点分析数据结构的选择依据、核心算法设计思路以及实际编码中的关键技巧。1. 系统架构设计1.1 需求分析与数据结构选择航空订票系统需要管理两类核心数据航班信息和乘客信息。每条航班包含以下字段起点站、终点站航班编号、飞机号飞行日期星期几总票数、余票量不同舱位的余票量如经济舱、商务舱乘客信息则需要记录姓名、身份证号订票数量、舱位等级飞行日期链表是管理航班信息的理想选择因为航班数量动态变化可能新增或取消航班需要频繁的插入和删除操作内存利用率高不需要预先分配固定空间队列则用于处理候补订票需求符合先到先服务的业务规则。当某航班票已售罄时后续请求进入候补队列有空余票时按顺序处理。1.2 核心数据结构定义// 乘客节点用于已订票乘客链表 typedef struct CNode { char name[20]; // 姓名 int num; // 订票数 char ID[20]; // 身份证 char day[20]; // 飞行日期 int dengji; // 舱位等级 struct CNode *next; // 下一乘客指针 } CNode, *CList; // 候补队列节点 typedef struct HbNode { char name[20]; // 姓名 char ID[20]; // 身份证 int num; // 预定数量 struct HbNode *next;// 下一候补指针 } QhbNode, *Phb; // 候补队列结构 typedef struct Queue { Phb front; // 队头指针 Phb rear; // 队尾指针 } LinkQueue; // 航班节点带头结点的单链表 typedef struct hangban { char qidian[20]; // 起点站 char zhongdian[20]; // 终点站 char hbID[20]; // 航班编号 char hbnum[20]; // 飞机号 char day[20]; // 飞行日期 int maxnum; // 总票数 int less; // 余票量 int lessgrade1; // 等级1余量 int lessgrade2; // 等级2余量 hangban *next; // 下一航班指针 CList cusLinkList; // 乘客链表头指针 LinkQueue wQgrade1; // 等级1候补队列 LinkQueue wQgrade2; // 等级2候补队列 } hangban, *Phangban;2. 核心功能实现2.1 航班链表管理航班链表采用带头结点的单链表结构方便统一处理插入和删除操作。初始化时需要创建头结点void initFlight() { pFlight (hangban *)malloc(sizeof(hangban)); if (pFlight NULL) exit(0); pFlight-next NULL; // 初始为空链表 }航班插入操作需要考虑航班编号的唯一性。通过遍历链表检查是否已存在相同编号int duibiFlight(hangban *flight, char ID[]) { hangban *p flight; while (p ! NULL) { if (!strcmp(ID, p-hbID)) return 0; // 编号重复 p p-next; } return 1; // 编号可用 }2.2 订票业务逻辑订票是系统最复杂的功能需要处理多种情况有余票时直接订票余票不足时询问是否候补候补队列管理void dingpiao() { hangban *info find(); // 查找航班 if (info NULL) { printf(不存在该航班\n); return; } // 获取用户输入 printf(请输入您想要定的票数:); int need; scanf(%d, need); printf(请输入您的票的舱位等级1或2:); int grade; scanf(%d, grade); // 检查余票 int num (grade 1) ? info-lessgrade1 : info-lessgrade2; if (need num) { // 有余票处理订票 char name[20], id[20], day[20]; printf(请输入您的姓名:); scanf(%s, name); printf(请输入您的身份证号码:); scanf(%s, id); printf(请输入你的飞行周期); scanf(%s, day); // 添加到乘客链表 CList head info-cusLinkList; addlink(head, need, name, id, day, grade); // 更新余票 info-less - need; if (grade 1) info-lessgrade1 - need; else info-lessgrade2 - need; printf(\n订票成功\n); } else { // 余票不足 printf(该等级的票不足\n); printf(是否排队等候(Y/N)); char r getch(); if (r Y || r y) { // 加入候补队列 char name[20], id[20]; printf(\n请输入您的姓名排队订票:); scanf(%s, name); printf(\n请输入您的身份证排队订票:); scanf(%s, id); if (grade 1) info-wQgrade1 enqueue(info-wQgrade1, name, need, id); else info-wQgrade2 enqueue(info-wQgrade2, name, need, id); printf(\n排队成功!\n); } } }2.3 退票与候补处理退票时需要检查乘客信息匹配并触发候补队列处理void tuipiao() { hangban *info find(); // 查找航班 if (info NULL) return; // 获取用户信息 char name[20], id[20], day[20]; printf(请输入你的姓名: ); scanf(%s, name); printf(请输入你的身份证号码: ); scanf(%s, id); printf(请输入飞行周期: ); scanf(%s, day); // 在乘客链表中查找 CNode *p1 info-cusLinkList-next; CNode *p2 info-cusLinkList; while (p1 ! NULL) { if (strcmp(name, p1-name)0 strcmp(id, p1-ID)0 strcmp(day, p1-day)0) break; p2 p1; p1 p1-next; } if (p1 NULL) { printf(退票信息不匹配\n); return; } // 执行退票 int grade p1-dengji; int num p1-num; p2-next p1-next; free(p1); // 恢复余票 info-less num; if (grade 1) info-lessgrade1 num; else info-lessgrade2 num; printf(%s 成功退票\n, name); // 处理候补队列 processWaitQueue(info, grade); }候补队列处理函数会检查队列头部乘客是否能满足订票需求void processWaitQueue(hangban *info, int grade) { LinkQueue *queue (grade 1) ? (info-wQgrade1) : (info-wQgrade2); int *less (grade 1) ? (info-lessgrade1) : (info-lessgrade2); while (!isQueueEmpty(queue) queue-front-next-num *less) { Phb node dequeue(queue); printf(通知候补乘客 %s已有余票请办理订票手续\n, node-name); *less - node-num; info-less - node-num; free(node); } }3. 关键算法优化3.1 航班查找优化原始实现中每次查找航班都需要遍历整个链表时间复杂度为O(n)。可以通过以下方式优化哈希表索引建立航班编号到节点指针的哈希映射排序链表保持链表按编号有序使用二分查找跳表结构构建多级索引加速查找// 哈希表优化示例 #define HASH_SIZE 100 hangban* hashTable[HASH_SIZE]; int hashFunc(char *id) { int sum 0; for (int i 0; id[i]; i) sum id[i]; return sum % HASH_SIZE; } void insertHash(hangban *node) { int index hashFunc(node-hbID); node-nextHash hashTable[index]; hashTable[index] node; } hangban* findHash(char *id) { int index hashFunc(id); hangban *p hashTable[index]; while (p ! NULL) { if (strcmp(p-hbID, id) 0) return p; p p-nextHash; } return NULL; }3.2 内存管理改进原始代码中频繁使用malloc/free可能导致内存碎片。可以考虑内存池技术预先分配大块内存自行管理分配释放对象池对常用结构体如乘客节点建立回收机制#define POOL_SIZE 1000 CNode nodePool[POOL_SIZE]; int nodeIndex 0; CNode* allocNode() { if (nodeIndex POOL_SIZE) return NULL; return nodePool[nodeIndex]; } void freeNode(CNode *node) { // 标记为可复用即可 }4. 系统测试与验证4.1 测试用例设计完整测试应覆盖以下场景测试类型测试用例预期结果正常订票有余票时订票订票成功余票减少边界测试订票数等于余票订票成功余票为0异常测试订票数超过余票提示余票不足询问是否候补退票测试有效退票退票成功余票增加候补测试退票后触发候补通知队列首位的候补乘客4.2 内存泄漏检查使用valgrind等工具检查内存泄漏valgrind --leak-checkfull ./airline_system常见内存问题包括节点删除后未free异常路径下资源未释放指针操作错误导致的内存越界5. 项目扩展方向5.1 持久化存储当前系统数据仅保存在内存中可以扩展文件存储功能void saveToFile(Phangban flight, const char* filename) { FILE *fp fopen(filename, wb); if (fp NULL) return; hangban *p flight-next; while (p ! NULL) { fwrite(p, sizeof(hangban), 1, fp); // 需要单独保存乘客链表和候补队列 p p-next; } fclose(fp); } void loadFromFile(Phangban flight, const char* filename) { FILE *fp fopen(filename, rb); if (fp NULL) return; hangban temp; while (fread(temp, sizeof(hangban), 1, fp)) { hangban *q (hangban *)malloc(sizeof(hangban)); *q temp; q-next flight-next; flight-next q; } fclose(fp); }5.2 多线程支持引入线程安全机制支持并发访问pthread_mutex_t flight_mutex PTHREAD_MUTEX_INITIALIZER; void safeDingpiao() { pthread_mutex_lock(flight_mutex); dingpiao(); pthread_mutex_unlock(flight_mutex); } void safeTuipiao() { pthread_mutex_lock(flight_mutex); tuipiao(); pthread_mutex_unlock(flight_mutex); }5.3 图形界面使用GTK或Qt添加图形界面// GTK简单示例 void create_main_window() { GtkWidget *window gtk_window_new(GTK_WINDOW_TOPLEVEL); gtk_window_set_title(GTK_WINDOW(window), 航空订票系统); GtkWidget *button gtk_button_new_with_label(查询航班); g_signal_connect(button, clicked, G_CALLBACK(query_flights), NULL); gtk_container_add(GTK_CONTAINER(window), button); gtk_widget_show_all(window); }