数据结构课设实战：航班信息查询与检索的折半查找与哈希表设计

简介：一份数据结构课程设计报告，以航班信息查询与检索为题，面向计算机相关专业学生及需要完成《数据结构》课程设计的读者。文档从课程设计任务书入手，完整介绍航班记录的数据类型定义、基数排序法处理航班号、二分查找法实现按航班号快速查询，以及按起点站、终点站、起飞时间等次关键字的顺序查找方法；包含系统分析、概要设计、详细设计、测试数据、收获与体会、参考文献和附录源程序等模块。资源共1个doc文件，约218KB，结构完整可直接参照。已有334人学习下载，适合用于理解数据结构算法落地、撰写课程设计报告或准备答辩。

1. 课程设计到底考什么：航班信息查询与检索背后的数据结构题

如果你在《数据结构》课程设计任务书里看到“航班信息查询与检索”这个题目，别以为它只是要求你写一个查航班的App。这个题目的核心，是考察你能否把线性表、查找、排序、哈希表这些理论结构落到一个具体业务场景里。换句话说，评委想看的是：给你一堆航班记录，你怎么组织它们，让“按航班号查”“按起飞城市查”“按日期查”这些操作又快又不乱。

这个题适合两类人：一类是正在被课设折磨的大学生，另一类是准备数据结构机考或面试的从业者。虽然标题是个.doc文档，但实际做起来完全是一个可运行的C语言或Java项目。下面我会按照最常见的课程设计验收标准，把从数据结构选型到代码实现的全过程拆开讲，包括那些你调试到凌晨三点才发现是边界条件写错的坑。

2. 先把航班数据想清楚：存储结构选型与信息组织

2.1 航班信息的字段设计：从需求文档到结构体

课设文档里通常会要求字段包含航班号、起点站、终点站、起飞时间、到达时间、班期（周几有班）、机型，有的还要求票价和余票。先把这些字段固化成结构体，后面所有排序和查找都基于这个结构体。

#define MAX_AIRLINE_LEN 8 #define MAX_CITY_LEN 32 typedef struct Flight { char flight_id[MAX_AIRLINE_LEN]; // 航班号，如 CA1301 char start_city[MAX_CITY_LEN]; // 起点城市 char end_city[MAX_CITY_LEN]; // 终点城市 int dep_hour, dep_minute; // 起飞时间点 int arr_hour, arr_minute; // 到达时间点 int day_mask; // 用二进制的7位表示周几有航班 int seats_left; // 余票数 } Flight;

字段设计时有一个容易忽略的点：时间尽量拆成 hour 和 minute 两个整型，不要存成"08:30"这种字符串。因为后续如果你要按起飞时间排序或查找某个时间段内的航班，字符串比较会带来乱序问题——"08:30"和"08:9"这种格式一变就出错。用整型存，比较dep_hour * 60 + dep_minute即可。

day_mask 按二进制的 bit0~bit6 表示周一到周日是否有航班，这个字段在很多人看来多余，但我在课设里加了它，最后做"查询每周一早上从北京出发的航班"这种需求时，一条位运算就能过滤，评委一看就明白你懂得用空间换表达。

2.2 选线性表还是哈希表：不同查询频率下的取舍

数据结构课设最核心的评分点不是界面多漂亮，而是你能否说明白"为什么用这个数据结构"。航班查询的典型场景有两类：

• 按航班号精确查询，比如用户输入 CA1301，要立刻返回这一条记录。这种场景下哈希表时间复杂度 O(1)，顺序表折半查找 O(log n)，线性表顺序查找 O(n)。
• 按起点城市查询，比如查所有从北京出发的航班。这时无法用航班号做索引，往往要遍历整个表，线性表和哈希表差别不大。

实话说，课设模板里最常要求的是"按航班号查询、按起点城市查询、按终点城市查询"这三个功能。按航班号用折半或哈希，按城市用遍历，这是最直接的组合。下表是我在设计时权衡的依据：

我的建议是：先实现顺序表折半查找，至少保证基本功能跑通；再单独给航班号建立哈希表作为一个模块，这样答辩时你能对比两种结构的实际耗时。

2.3 用带头结点的单链表存储航班：最小可行方案

很多课设要求文件读写航班信息，读入后就地建表。如果你还没有十足把握写红黑树，那就用带头结点的单链表。它插入方便，删除也直观，用来应付"读入N条航班记录并查询"这类需求完全够。

typedef struct Node { Flight data; struct Node *next; } ListNode; ListNode* create_list() { ListNode *head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; return head; } void insert_tail(ListNode *head, Flight flight) { ListNode *p = head; while (p->next) p = p->next; ListNode *new_node = (ListNode*)malloc(sizeof(ListNode)); new_node->data = flight; new_node->next = NULL; p->next = new_node; }

create_list返回一个带头结点的空链表，头结点不存数据，这样无论链表是否为空，插入和删除的逻辑都是同一套。insert_tail每次都从头遍历到尾部，如果数据量大（几千条）会慢一点，但课设规模通常不超过几百条，完全够用。注意每次malloc后要检查是否分配失败，演示时可能看不出问题，但匿名函数测试员会专门输入大文件来考验你，这种小细节能救你一命。

3. 用顺序表加折半查找做航班查询：从排序到二分

3.1 按航班号排序：基于关键字的稳定排序

折半查找的前提是序列有序。航班号是字符串，比如"CA1301"、"MU570"，你要按字典序排。C语言里直接用strcmp做比较。排序算法我建议用快速排序，虽然冒泡代码短，但课设评审问到"你的排序时间复杂度"时，快排的 O(n log n) 明显更说得出口。

void quick_sort(Flight arr[], int left, int right) { if (left >= right) return; int i = left, j = right; Flight pivot = arr[left]; while (i < j) { while (i < j && strcmp(arr[j].flight_id, pivot.flight_id) >= 0) j--; arr[i] = arr[j]; while (i < j && strcmp(arr[i].flight_id, pivot.flight_id) <= 0) i++; arr[j] = arr[i]; } arr[i] = pivot; quick_sort(arr, left, i - 1); quick_sort(arr, i + 1, right); }

这里用的strcmp >= 0和<= 0是刻意写成这样，为了皮亚诺式的稳定性——保证相等的元素不分向两侧乱跑。如果写成> 0和< 0，航班号相等时也会交换，排序不稳定，虽然不影响折半，但影响后续按城市分组输出的稳定性。我实际调的时候吃过这个亏：排序后同航班号的记录顺序和输入顺序不一致，测试用例里的期望输出就按输入顺序，直接翻车。

3.2 折半查找的边界条件：用这三个参数防死循环

折半查找的代码人人都能背，但一写就错的地方在于边界处理。常见的错法是while (low <= high)里mid = (low + high) / 2，然后low = mid或high = mid，导致死循环。正确的标准写法是：

int binary_search(Flight arr[], int n, const char* key) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; int cmp = strcmp(arr[mid].flight_id, key); if (cmp == 0) { return mid; // 找到，返回下标 } else if (cmp < 0) { low = mid + 1; // key 更大，去右半 } else { high = mid - 1; // key 更小，去左半 } } return -1; }

三个参数low、high、mid是这条代码的生命线：low始终指向当前区间第一个可能的位置，high指向最后一个可能的位置，mid 每次用low + (high - low) / 2而不是(low + high) / 2，是为了防止 high 很大时 low+high 溢出整型范围——虽然课设数组不至于那么大，但这是习惯。每轮必须让low变成mid + 1或high变成mid - 1，只有这样才能保证区间在收缩，不会出现 low 永远等于 high 的死循环。

3.3 处理按起点终点查询：字符串匹配的笨办法也够用

按起点城市查，航班号有序帮不上忙，因为城市没序。最直接的办法是顺序遍历整个数组，用strcmp判断。

void search_by_city(Flight arr[], int n, const char* city) { int found = 0; for (int i = 0; i < n; i++) { if (strcmp(arr[i].start_city, city) == 0) { print_flight(&arr[i]); found = 1; } } if (!found) printf("没有从%s出发的航班\n", city); }

时间复杂度 O(n)。可能有同学想用哈希给城市也建索引，但课设里我不建议。很多同学觉得哈希很厉害，但城市查询的需求是"返回所有匹配项"，哈希只能给每个城市挂一个链表，如果每条城市-航班列表的维护没做对，反而因为又要管理多个 hashtable 而 bug 频出。顺序遍历在几百条数据上的耗时几乎为零，你要做的是在答辩时诚实说"这里根据数据规模选择了顺序查找，如果数据量大，可以改成二级哈希索引"，这就是一个加分的演进思路，而不是逞能去写一个你不可控的复杂结构。

4. 把哈希表引入航班检索：O(1)查询与冲突处理的取舍

4.1 航班号的哈希函数设计：取模与冲突

如果你的课程设计要求中额外有一条"按航班号查找要求尽可能高效"，那就要动哈希表。航班号由字母和数字组成，常见做法是把每个字符的 ASCII 码累加，再对表长取余。注意取余时最好用质数表长，比如 137，能减少冲突。

#define HASH_SIZE 137 int hash_key(const char* flight_id) { unsigned int sum = 0; while (*flight_id) { sum = (sum * 31 + (*flight_id)) % HASH_SIZE; flight_id++; } return (int)sum; }

这里乘 31 是模仿 Java 字符串哈希的做法，31 是经验选出来的质数，冲突率在同规模下明显小于直接累加。最后% HASH_SIZE把结果压到 0~136。当我解释这个为什么用 31 时，答辩老师会认为你不是照抄的，而是真的理解哈希函数的散列性要求。

4.2 用链地址法处理冲突，保留全部航班

哈希表每个槽位挂一个链表，也叫链地址法。冲突的航班号都存到同一个链表中。插入和查找的代码可以实现得很干净：

typedef struct HashNode { Flight data; struct HashNode *next; } HashNode; HashNode* table[HASH_SIZE]; void hash_insert(Flight flight) { int idx = hash_key(flight.flight_id); HashNode *node = (HashNode*)malloc(sizeof(HashNode)); node->data = flight; node->next = table[idx]; table[idx] = node; // 头插法 } Flight* hash_search(const char* flight_id) { int idx = hash_key(flight_id); HashNode *p = table[idx]; while (p) { if (strcmp(p->data.flight_id, flight_id) == 0) { return &(p->data); } p = p->next; } return NULL; }

插入用头插法，不需要遍历到链表尾部，新记录挂在最前面，插入复杂度 O(1)。查找时先算哈希值，再在链表中线性找。假设每个链表平均长度约等于总航班数 / HASH_SIZE，只要表长足够，每个链表长度会很小，查找稳定在接近 O(1)。

但哈希表有坑：一旦航班数据动态增加，而 HASH_SIZE 固定不变，链表会越来越长。所以这个方案只适合课设这种“一次性读入、之后只查不改”的场景。如果你的文档要求“增加航班”功能，频繁 insert 后哈希质量下降，你需要在答辩时说明这一点，否则就是给自己埋雷。

4.3 对比：什么时候哈希表比折半查找更值得

我做一个跑过真实数据的对比，用 500 条航班记录，分别用顺序表折半查找、单链表顺序查找、哈希表查找同一航班号，各执行 1000 次，耗时结果如下（单位毫秒，不同机器有波动但趋势一致）：

结论：如果你只是应付课设，折半查找已经足够，它代码短，不容易错。哈希表可以作为加分项单独封装一个模块，在界面上做一个“用哈希查找”的功能，让用户看到输入航班号后秒出结果。这样你既演示了顺序结构，又演示了哈希结构对同一问题的不同解法，评委对“为什么用这个结构”的追问你也能给出数据支撑。

5. 避坑：数据结构课程设计中航班查询的常见问题与排查

5.1 现象：运行到输入航班号后直接闪退或报错

现象是编译通过，输入数据也正常，但一输入航班号查找程序就崩溃。

原因有三个高频来源：一是存储航班号的 char 数组长度不够，比如flight_id[8]却存进了"CA1301-XYZ"这种更长的字符串，导致越界覆盖了其他变量；二是折半查找的数组没有排序，直接二分访问了错误下标；三是strcmp传入的指针是 NULL，比如哈希表查询没找到就返回 NULL，你却直接拿来strcmp。

解决方法是先给程序加一层防御：在访问数组元素前检查下标范围，在strcmp前判断指针非空。另外用调试器逐步看是崩溃在哪一行，比瞎猜快得多。我一般会把所有从外部读人的字符串都做一个长度校验函数，超过数组容量就拒绝。

5.2 现象：折半查找返回 -1，但记录明明存在

现象是输入一个肯定存在的航班号，折半查找却返回未找到。

原因通常是排序函数没有排正确。比如你按航班号升序排，但比较函数写成了strcmp(a, b) > 0返回一个负数，导致排序结果逆序。还有一种是中途插入了新航班，但没有重新排序，而折半查找又要求有序，就会在这个新数据附近彻底找偏。

解决办法：查完排除逻辑错误后，先打印排序后的数组验证升序。我常用的土办法是写一个冒烟测试，生成 10 条航班号乱序的测试数据，排序后逐个用折半查找查每一条，全部命中才算通过。这个小脚本能让你在十分钟内戒掉边写边猜的毛病。

5.3 现象：哈希表查询效率反而不如顺序遍历

现象是你的哈希表查询时间没有明显优势，甚至更慢。

原因多半是哈希函数写得太简单，比如直接把航班号的 ASCII 码相加后取余，导致几乎所有航班号都聚集到少数哈希槽位上。如果某条链上挂了几十条，查找就成了线性找，自然快不起来。

解决方法是重新设计哈希函数。上面我给的乘 31 循环版本是实测比较好的。你可以再验证一种更好的：字符串哈希中的 DJB2 函数，初始哈希值为 5381，每处理一个字符hash = hash * 33 + c。在数据量 500 条、表长 137 的情况下，DJB2 的冲突数远少于简单累加。这个函数也是业界常用，用在课设里完全拿得出手。

5.4 现象：查询“某个城市的航班”时少输出同行一天多班的情况

现象是有多条航班都是同一城市出发，但只显示一条，另一条死活查不出来。

原因是我之前提的 day_mask 字段没有参与筛选，或者你在城市匹配后没有继续用后续条件过滤。另一个常见原因是两人同名的航班号，比如CA1301和CA1302，你存成单个变量覆盖了。这也暴露出主键设计缺失：以航班号作为唯一标识在现实业务中并不充分，因为同一航班号对应的是固定航线，比如 CA1301 每周一和周三各一班，你如果只按航班号存一条，就丢了班期信息。

解决方法是把主键定为航班号 + 星期几，或者干脆用一个自增 id 作为内部主键，查询城市时不对主键做任何假设。我后来做课设都是给结构体加了一个int unique_id，两者都能准确区分。

5.5 现象：从文件读入数据后用fwrite写回，再读出来乱码

现象是程序第一次运行时能正常读数据，关掉再打开，读出的航班号打印出来是一串乱码或者直接负数。

原因大概率是你用了文本模式打开二进制数据文件，或者反过来用了二进制模式打开文本文件。Windows 下fopen的"r"和"rb"是完全不同的处理方式。在文本模式下读取时遇到\n会被映射成\r\n，导致 fread 读出的字节数和写入时不匹配，结构体内部的指针被存成了数值，再被解释成地址自然乱。

解决方法是统一用"rb"和"wb"模式读写，不要混用。如果要可读的存档，用fscanf/fprintf按列读写文本，更稳妥一点。我自己的习惯是，课设里为了省事直接生成一个flights.txt，每次启动都重新读取，不纠结读回写回的格式问题，这样能少踩至少两个坑。

6. 让课设超出预期：多级检索加排序的进阶验证

如果基础功能都跑通了，建议你多加两个大多数人不会做的步骤：组合查询和性能对比。组合查询的意思是用户可以选择“起点城市 + 起飞时间区间 + 周几有班”来筛选。这也是我把 day_mask 设计成二进制的原因，筛选时直接用位运算判断。

// 假设用户要求查找周一(day=1)、从北京出发、8点到12点之间的航班 for (int i = 0; i < flight_count; i++) { Flight *f = &flights[i]; if (strcmp(f->start_city, "北京") == 0 && (f->day_mask & (1 << 0)) && (f->dep_hour * 60 + f->dep_minute) >= 8 * 60 && (f->dep_hour * 60 + f->dep_minute) <= 12 * 60) { print_flight(f); } }

筛选结果出来后，我按起飞时间做了一次快排输出，用户看到的是按时间有序的列表，这个体验远超“列出来就行”的要求。而且这里用到的排序可以和前面按航班号排序复用一个排序框架，通过一个compare_fn函数指针切换比较逻辑，代码改造量不大。

验证方面，我建议你准备一个 500 条航班数据的小文件，分别跑顺序查找、折半查找、哈希查找，记录clock()时间差，打印出来。这个动作在答辩时效果出奇好——老师看到你能用数据证明自己的选择，而不是空口说“我的算法很快”，基本不会刁难你。

最后说一个我自己的教训。当年我第一次做这个题，图省事只用了顺序查找，答辩时老师随口问“为什么不用哈希？”我答不上来。第二次做我加上了哈希表，虽然代码量多了不少，也踩了冲突处理的坑，但调试的过程反而让我彻底搞懂了链地址法。从那之后我养成了一个习惯：无论课设多简单，都要试着用两种以上的结构去解决同一个问题，然后比较它们。这比抱着一种结构写一百遍都有用，希望帮到你。

本文还有配套的精品资源，点击获取