简介这份数据结构课程设计资料以「航班查询与检索」为主题面向正在完成数据结构课程设计或需要算法实践案例的计算机专业学生。内容围绕结构体、链表、顺序表、队列等基础数据结构以及基数排序、二分法查询等算法展开完整呈现了从航班信息建模到多条件查询的实现思路。压缩包内仅含1个doc文档大小约217KB集中收录了课程设计报告、核心代码、算法流程图与程序输出结果便于对照理解各模块的衔接关系。文档中给出了航班号、起飞站、终点站、班期、起降时间与票价等字段的结构体定义并演示了按时间、航班号、地点和票价范围查询的流程同时包含基数排序与二分查找的具体代码片段。已有104人学习该资源适合作为课程设计参考模板帮助读者快速梳理数据结构选型、算法实现与实验报告撰写的完整脉络。1. 航班查询与检索从课程设计到能跑起来的完整方案课程设计最怕的不是题目难而是做完了讲不清。航班查询与检索这个题目表面看是“输入出发地、目的地、日期返回航班列表”但真正拉开差距的地方在于数据怎么组织、查找怎么加速、多条件组合怎么处理。我见过太多同学用三重循环硬扫几千条航班数据演示时输入一个“北京”要等三秒才出结果老师一问复杂度就露馅。这个方案解决的核心问题是用合理的数据结构把航班信息管起来让单条件查询接近 O(1) 或 O(log n)多条件组合查询也能在可接受时间内返回。适合正在做数据结构课程设计的本科生也适合想复习查找、排序、哈希、树结构的开发者。代码用 C 语言写因为严蔚敏那本教材的语境就是 C答辩时老师也认这套。下面从数据结构选型讲到完整实现再到流程图的画法和输出结果的整理每一步都能直接抄。2. 航班数据怎么存结构体设计、文件读写与内存布局2.1 航班信息该拆成哪几个字段先想清楚一条航班记录到底要存什么。最少要有航班号、出发城市、到达城市、起飞时间、到达时间、票价、剩余座位数。如果要做日期检索还得加一个执飞日期字段。我一般会这样定义#define MAX_CITY_LEN 32 #define MAX_FLIGHT_NO 16 #define MAX_FLIGHTS 2000 typedef struct { char flight_no[MAX_FLIGHT_NO]; // 航班号如 CA1234 char from_city[MAX_CITY_LEN]; // 出发城市 char to_city[MAX_CITY_LEN]; // 到达城市 char depart_time[8]; // 起飞时间 HH:MM char arrive_time[8]; // 到达时间 HH:MM char date[12]; // 执飞日期 YYYY-MM-DD float price; // 票价 int seats_left; // 剩余座位 } Flight;字段长度不要卡得太死。城市名用 32 字节看起来浪费但省去了后面处理“乌鲁木齐”“呼和浩特”这类长名字时截断的麻烦。航班号 16 字节足够国内航班号最长也就七八个字符。日期用字符串存而不是时间戳因为课程设计里日期比较就是字符串比较strcmp一把梭不需要引入time.h那套东西。注意seats_left用 int 而不是 unsigned因为后面排序时可能临时置为 -1 表示无效记录unsigned 会翻车。2.2 用文件做持久化读进来、写回去课程设计的数据一般放在 txt 或 csv 里。我习惯用 csv因为 Excel 能直接打开检查数据对不对。读取逻辑用fgets逐行读再用strtok按逗号切分int load_flights(const char *filename, Flight *flights, int *count) { FILE *fp fopen(filename, r); if (!fp) { printf(无法打开文件 %s\n, filename); return -1; } char line[256]; *count 0; // 跳过表头 fgets(line, sizeof(line), fp); while (fgets(line, sizeof(line), fp) *count MAX_FLIGHTS) { line[strcspn(line, \r\n)] \0; // 去掉换行 Flight *f flights[*count]; char *token strtok(line, ,); if (!token) continue; strncpy(f-flight_no, token, MAX_FLIGHT_NO - 1); token strtok(NULL, ,); strncpy(f-from_city, token, MAX_CITY_LEN - 1); token strtok(NULL, ,); strncpy(f-to_city, token, MAX_CITY_LEN - 1); token strtok(NULL, ,); strncpy(f-depart_time, token, 7); token strtok(NULL, ,); strncpy(f-arrive_time, token, 7); token strtok(NULL, ,); strncpy(f-date, token, 11); token strtok(NULL, ,); f-price atof(token); token strtok(NULL, ,); f-seats_left atoi(token); (*count); } fclose(fp); return 0; }这里有几个参数要盯住。line[256]是单行最大长度如果你的 csv 某行特别长比如加了备注字段要往上调。strcspn(line, \r\n)用来兼容 Windows 的\r\n和 Linux 的\n不处理的话最后一个字段会带换行符后面strcmp比较日期时就会玄学失败。strtok不是线程安全的但课程设计单线程跑无所谓。写回文件的逻辑对称用fprintf按同样格式输出即可。每次修改座位数或添加航班后调一次save_flights避免程序崩溃丢数据。2.3 内存布局为什么用数组而不是链表很多同学一上来就想用链表觉得“动态”更高级。但航班查询这个场景数据量在几千条以内数组的随机访问优势远大于链表的插入优势。查询时你要反复按索引访问、排序、二分查找链表每次都要从头遍历反而更慢。我一般直接用Flight flights[MAX_FLIGHTS]静态数组配合一个int count记录实际条数。内存占用大概是2000 * sizeof(Flight)算下来不到 200KB完全没压力。如果你非要用动态内存用malloc分配count * sizeof(Flight)也行但记得在程序退出前free否则答辩时老师问你内存泄漏就尴尬了。数组方案的好处是代码简单、调试方便、不需要处理分配失败课程设计阶段够用。3. 查询与检索的核心哈希、二分与多条件组合的实现3.1 按航班号查哈希表把 O(n) 压到 O(1)最基础的查询是按航班号精确查找。如果每次遍历整个数组n2000 时平均要比较 1000 次。用哈希表可以把这一步降到接近常数时间。哈希函数我一般用简单的 BKDR#define HASH_SIZE 4096 unsigned int bkdr_hash(const char *str) { unsigned int seed 131; // 31, 131, 1313 都可以 unsigned int hash 0; while (*str) { hash hash * seed (*str); } return hash % HASH_SIZE; } // 哈希表存的是航班在数组中的下标 int hash_table[HASH_SIZE];初始化时把所有hash_table[i]置为 -1然后遍历航班数组把hash_table[bkdr_hash(f-flight_no)] i。查询时算出哈希值取出下标再strcmp确认一次航班号是否真的相等处理哈希冲突。冲突用开放地址法的线性探测解决如果位置被占了且航班号不同就往后找下一个空位。参数说明HASH_SIZE取 4096 是因为航班总数不超过 2000负载因子约 0.5冲突概率低。seed取 131 是经典值对短字符串分布均匀。如果你把HASH_SIZE改成 2048冲突会变多查询虽然还是 O(1) 但常数变大实测差距在 2000 条数据下大概多 0.1ms感知不明显但答辩时你可以说“负载因子控制在 0.5 以下”。3.2 按城市查二分查找要先排序按出发城市或到达城市查询哈希就不太合适了因为城市名会重复一个城市对应多条航班。常见做法是先按城市名排序然后二分查找定位到第一条再往后扫描所有匹配项。排序用qsort比较函数按出发城市字典序int cmp_by_from_city(const void *a, const void *b) { const Flight *fa (const Flight *)a; const Flight *fb (const Flight *)b; return strcmp(fa-from_city, fb-from_city); } // 使用 qsort(flights, count, sizeof(Flight), cmp_by_from_city);二分查找定位左边界int binary_search_city(Flight *flights, int count, const char *city) { int lo 0, hi count - 1, pos -1; while (lo hi) { int mid lo (hi - lo) / 2; int cmp strcmp(flights[mid].from_city, city); if (cmp 0) { pos mid; hi mid - 1; // 继续往左找第一条 } else if (cmp 0) { lo mid 1; } else { hi mid - 1; } } return pos; // 返回第一条匹配的下标-1 表示没找到 }找到pos后从pos开始往后遍历直到城市名不等于目标城市为止把中间所有航班输出。这里有个坑qsort之后数组顺序变了如果你之前建了哈希表存下标哈希表就失效了。解决办法是哈希表存航班号到数组下标的映射排序后重建一次哈希表或者干脆哈希表里存指针。我一般选择排序后重建代码简单。3.3 多条件组合先过滤再排序的流水线实际查询往往是“从北京到上海日期是 2024-06-01价格低于 1500”。这种多条件组合最直接的做法是线性扫描加条件判断int query_flights(Flight *flights, int count, const char *from, const char *to, const char *date, float max_price, Flight *result) { int n 0; for (int i 0; i count; i) { Flight *f flights[i]; if (from strcmp(f-from_city, from) ! 0) continue; if (to strcmp(f-to_city, to) ! 0) continue; if (date strcmp(f-date, date) ! 0) continue; if (max_price 0 f-price max_price) continue; result[n] *f; } return n; }这段代码看起来是 O(n)但每个条件都是短路判断实际比较次数远小于 n 乘以条件数。2000 条数据下即使全条件扫描也就 2000 次循环耗时在微秒级。如果你非要优化可以先用哈希或二分缩小候选集再在候选集上做多条件过滤。但课程设计里除非数据量上万否则没必要。提示from、to、date传 NULL 表示该条件不启用。这样一套代码支持任意条件组合不用写多个函数。排序结果用qsort按价格或起飞时间排比较函数根据用户选择动态传int cmp_by_price(const void *a, const void *b) { float pa ((const Flight *)a)-price; float pb ((const Flight *)b)-price; return (pa pb) - (pa pb); }(pa pb) - (pa pb)这个写法避免直接返回浮点差值被截断成 int 导致排序不稳定是血泪经验。4. 流程图怎么画从主控流程到查询子流程的拆解4.1 主控流程图菜单驱动的主循环课程设计报告里流程图是必交项。主控流程用传统流程图符号画椭圆表示开始和结束矩形表示处理菱形表示判断平行四边形表示输入输出。主流程的逻辑是开始 → 加载航班数据 → 显示菜单 → 读取用户选择 → 判断选择类型 → 调用对应功能 → 判断是否退出 → 是则保存并结束否则回到显示菜单。画的时候注意菱形判断框要有两个出口分别标注“是”和“否”。菜单选项一般有1 按航班号查询、2 按城市查询、3 多条件查询、4 添加航班、5 删除航班、6 显示全部、0 退出。每个功能调用完回到菜单不要画成直线到底否则老师会问你“查完一次就退出了”4.2 查询子流程图二分查找的判断分支查询子流程单独画一张。以按城市查询为例输入城市名 → 对航班数组按城市排序 → 二分查找定位左边界 → 判断是否找到 → 没找到则输出“无匹配航班”并返回 → 找到则从该位置向后遍历 → 判断当前航班城市是否等于目标 → 是则输出该航班并继续 → 否则结束遍历并返回。这里的关键是二分查找的循环判断lo hi时继续mid位置比较后决定lo mid 1还是hi mid - 1。流程图上要体现这个循环回边否则画成一条直线就不叫二分了。4.3 流程图工具选择与输出规范画流程图可以用 Visio、Draw.io、ProcessOn甚至 Word 自带的形状。我一般用 Draw.io免费、导出 PNG 清晰、支持传统流程图符号。导出时选 300dpi 以上插入报告里不会糊。注意流程图的字体统一用宋体或黑体字号 10-12pt框与框之间对齐箭头不要交叉。如果学校要求用特定模板就按模板来别自己发挥。输出结果部分把程序运行时的截图贴上去主菜单、按航班号查询结果、按城市查询结果、多条件查询结果、无匹配时的提示。每张截图下面配一行说明比如“图 5 按出发城市‘北京’查询结果共返回 3 条航班”。截图要清晰命令行窗口背景建议用白色或浅色别用黑色背景打印出来看不清。5. 避坑与排查课程设计里最容易翻车的 5 个地方5.1 字符串比较用 而不是 strcmp现象查询“北京”时明明数据里有但程序说找不到。原因C 语言里字符串不能用比较比的是指针地址。解决所有字符串比较统一用strcmp(a, b) 0。这个坑几乎每个初学者都会踩一次代码评审时先全局搜一遍后面跟字符串变量的地方。5.2 文件读取时最后一个字段带换行符现象日期比较总是失败打印出来看日期是2024-06-01\n。原因fgets会把行尾换行符读进来strtok按逗号切分时最后一个字段包含了换行。解决在读入每行后立刻用line[strcspn(line, \r\n)] \0去掉换行再切分。或者用strtok的分隔符集写成,\r\n。5.3 qsort 比较函数返回差值导致溢出现象排序结果偶尔乱序尤其是价格相差很大时。原因比较函数写成return a-price - b-price浮点差值转 int 时可能溢出或截断。解决用(a b) - (a b)的写法返回 -1、0、1安全且稳定。整数比较同理别直接减。5.4 哈希表冲突处理不当导致覆盖现象按航班号查询时某些航班号查不到但数据确实存在。原因哈希冲突时直接覆盖了旧下标没有做线性探测。解决插入时如果目标位置已被占用且航班号不同就pos (pos 1) % HASH_SIZE继续找直到找到空位或航班号相同的位置。查询时同样要探测直到找到匹配或遇到空位为止。5.5 排序后忘记重建索引现象先按航班号查询正常再按城市查询后按航班号查询就失效了。原因qsort改变了数组元素顺序之前哈希表里存的下标指向了错误的航班。解决每次排序后重新遍历数组重建哈希表或者哈希表里存航班号字符串到指针的映射排序不影响指针有效性。我一般选择重建代码三行搞定。6. 让答辩加分的两个进阶技巧性能对比与边界测试6.1 用 clock() 做查询耗时对比答辩时老师最爱问“你这个查询效率怎么样”。与其空口说 O(1)不如现场跑一组对比数据。用time.h的clock()函数分别测线性扫描和哈希查找的耗时#include time.h clock_t start clock(); // 线性扫描查询 1000 次 for (int i 0; i 1000; i) { linear_search(flights, count, CA1234); } clock_t end clock(); printf(线性扫描 1000 次耗时: %f ms\n, 1000.0 * (end - start) / CLOCKS_PER_SEC); start clock(); // 哈希查询 1000 次 for (int i 0; i 1000; i) { hash_search(flights, count, CA1234); } end clock(); printf(哈希查询 1000 次耗时: %f ms\n, 1000.0 * (end - start) / CLOCKS_PER_SEC);2000 条数据下线性扫描 1000 次大概 2-5ms哈希查询大概 0.1-0.3ms差距肉眼可见。把这两行输出截图放进报告比写一堆复杂度分析更有说服力。注意clock()测的是 CPU 时间不是墙钟时间但课程设计够用了。6.2 边界测试用例清单程序能跑通正常数据不算本事边界情况不崩才是真功夫。我一般会准备这几组测试测试场景输入预期行为空数据查询数据文件为空提示“无航班数据”不崩溃不存在的城市出发城市“火星”输出“无匹配航班”日期格式错误输入“2024/06/01”按字符串比较无匹配不报错价格为 0max_price0视为不启用价格过滤座位数为 0查询到该航班正常显示但提示“已满”超长城市名输入 100 个字符截断到 31 字符不溢出把这些用例跑一遍截图附在报告附录里。老师看到你有边界意识印象分直接拉满。我当年做课程设计时就因为多附了一页边界测试答辩老师问了句“你考虑得挺全”然后就没怎么为难我。最后一个习惯每次改完代码先跑一遍全部测试用例再提交。别等到答辩前一天晚上才发现改了一个 bug 又引入三个新 bug。希望帮到你。本文还有配套的精品资源点击获取