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-check=full ./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); }
