简介面向高校学生的2025年数据结构期末课程设计综合包基于C完成飞机票管理系统、Trie树与后缀树应用、交通咨询系统设计、简单搜索引擎四个典型项目。资源覆盖字符串检索、图算法、通信与界面交互适合正在完成课设或通过完整案例巩固数据结构知识的学生。压缩包共1398个文件大小10.5MB以idx索引文件为主另有h头文件、cpp源文件、ui界面、json配置、pro工程等包含可编译源码、项目配置与运行资料。已有82人学习下载。内容整合客户端与服务端源码、图结构与界面设计能展示Trie树在自动补全和快速检索中的作用、后缀树在字符串匹配中的应用、交通咨询中的路径规划及搜索引擎的查询流程可作为课程设计实现的完整参照。1. 期末课程设计“四大件”这份 zip 里装的是同一套数据结构题期末周拿到这份 zip里面其实是四个相互独立的子系统飞机票管理系统、Trie 树和后缀树的应用、交通咨询系统设计、简单搜索引擎。很多人不理解为什幺一次课程设计要同时出现这么多东西——因为考试不让只考一个点。飞机票管理考线性表和图的结合交通咨询考最短路径和最小生成树Trie 树和后缀树考字符串数据结构搜索引擎则是把查找和排序揉在一起。对正在做数据结构期末复习的人来说这一套正好覆盖了期末卷子上最容易出大题的几个方向对只差一份实验报告交差的同学四个子系统随便挑两个做透也能保住分数。我下面按自己做过这类课程设计的习惯来拆先讲每个子系统的数据结构和算法选型再给能直接跑的代码骨架最后把最容易翻车的几个坑单独拎出来。这套东西本身不难难的是别把文件读写、指针和中文编码这几个老问题拖进答辩现场。2. 飞机票管理系统用链表维护航班用 Dijkstra 求最便宜中转2.1 数据结构选型航班用链表、航线用邻接矩阵飞机票管理系统在最常见课程设计里的定位是“基础 CRUD 一个图算法”。航班信息是典型的业务数据用户要添加航班、删除航班、按票价排序、查余票数据量在几十条级别不存在随机访问需求所以用单链表比顺序表更贴合实际场景——删除中间节点不用搬动数据插入新航班也不用担心扩容。航线和票价关系则单独抽象成一张图城市是顶点两个城市之间有直飞航班就有一条边边的权值是票价或飞行时间。图的顶点数通常不超过 20用邻接矩阵最省心权值查询是 O(1)实现 Dijkstra 时也不用去遍历邻接表。typedef struct Flight { char no[16]; // 航班号例如 CA1501 char from[32]; // 出发城市 char to[32]; // 到达城市 int price; // 票价 int seats; // 余票 struct Flight *next; // 链表后继 } Flight;这段定义是整个航班管理的基础。航班号用char [16]而不是char *因为文件读进来的字符串需要固定空间承载char *只存指针指向的内容随时可能失效。城市字段开 32 字节是为了给四个字的中文城市名留足 UTF-8 空间一个汉字三字节四个字 12 字节加结束符32 字节不浪费。2.2 航班链表插入与按票价排序的落地写法航班录入通常要求“航班号不重复按航班号有序”。头插法最简单但会打乱顺序我一般写成按航班号比较后插到合适位置这样展示列表时天然有序不用再调排序。void insertFlight(Flight **head, Flight *nf) { Flight *cur *head, *prev NULL; while (cur strcmp(cur-no, nf-no) 0) { prev cur; cur cur-next; } if (prev NULL) { // 新节点最小插到头部 nf-next *head; *head nf; } else { // 插到 prev 和 cur 之间 nf-next cur; prev-next nf; } }参数Flight **head必须传二级指针因为新节点可能成为头节点函数内部要改写外部变量的值只传Flight *head改不动调用者手里的头指针。strcmp返回负、零、正对应小于、等于、大于用strcmp(cur-no, nf-no) 0判断“当前节点的航班号小于新航班号”保证正序插入。读文件时每一行对应一个航班用fscanf按格式读。这里有个血泪经验判断文件结束不要用feof要用fscanf的返回值具体原因在避坑章节展开。按票价排序时如果链表已经有序插入直接遍历输出即可题目要求“按票价从低到高显示”可以单独写一个冒泡或者选择排序。课程设计对性能没要求别去写归并选择排序配合交换price字段就够。void sortByPrice(Flight *head) { for (Flight *p head; p p-next; p p-next) { Flight *minp p; for (Flight *q p-next; q; q q-next) if (q-price minp-price) minp q; if (minp ! p) { char tmpNo[16], tmpFrom[32], tmpTo[32]; int tmpP p-price, tmpS p-seats; // 字段逐个交换最笨也最好懂 strcpy(tmpNo, p-no); strcpy(p-no, minp-no); strcpy(minp-no, tmpNo); strcpy(tmpFrom, p-from); strcpy(p-from, minp-from); strcpy(minp-from, tmpFrom); strcpy(tmpTo, p-to); strcpy(p-to, minp-to); strcpy(minp-to, tmpTo); p-price minp-price; minp-price tmpP; p-seats minp-seats; minp-seats tmpS; } } }这里交换的是节点内数据不是交换指针。交换指针会让链表顺序混乱交换数据字段则保持节点位置不变。minp记录从当前节点到末尾的最小票价节点走完内层循环再交换一趟确定一个位置的最终值。2.3 用 Dijkstra 求“最便宜中转”边权就是票价航线的图模型是城市是顶点直飞边权为票价。题目要求查“从 A 到 B 最便宜的走法”即使没有直飞也可以中转这就是单源最短路径问题。航班价格都是正数Dijkstra 是标准答案Floyd 也能做但单源场景下 Dijkstra 更贴合教材考点。#define INF 999999 void dijkstra(int n, int src, int dest, int cost[][MAX], int prev[]) { int dist[MAX], visited[MAX]; for (int i 0; i n; i) { dist[i] cost[src][i]; prev[i] src; visited[i] 0; } dist[src] 0; visited[src] 1; for (int k 0; k n; k) { int u -1, min INF; for (int i 0; i n; i) if (!visited[i] dist[i] min) { min dist[i]; u i; } if (u -1) break; visited[u] 1; if (u dest) break; for (int v 0; v n; v) if (!visited[v] dist[u] cost[u][v] dist[v]) { dist[v] dist[u] cost[u][v]; prev[v] u; } } }cost是邻接矩阵cost[i][j]为INF表示 i、j 之间没有直飞dist保存起点到每个城市的最低票价prev记录当前城市的前驱城市用于回溯完整路线。松弛条件dist[u] cost[u][v] dist[v]的意思是“从起点到 u再从 u 到 v 比之前到 v 的方案更便宜就更新”。回溯路线时从 dest 开始不断当前城市 prev[当前城市]直到回到 src把经过的城市压栈再输出就是正序路径。这个算法的前提是边权非负航班票价显然满足。如果课程设计里加了“特价机票为负”这种不现实设定直接用 Dijkstra 会得到错误答案需要换成 Bellman-Ford。提示INF不要设成INT_MAX因为松弛时dist[u] cost[u][v]会溢出成负数结果反而被当成更短路径。设成 999999 这种比最大合理路径大一个数量级的数更安全。3. 交通咨询系统设计Floyd 全源最短路与最小生成树双模型3.1 城市网的邻接矩阵加载与文件格式约定交通咨询系统的数据模型和飞机票的航线图很像但需求侧重点不同它不只问“某个城市到另一个城市的最短路径”还要回答“任意两个城市之间的最短距离”甚至“如果要保证所有城市通公路最少修多少公里”。所以交警系统的标准配置是 Floyd Prim 或 Kruskal。城市数量和城市名之间的映射一般用数组存城市编号从 0 开始。文件格式可以用最朴素的“第一行城市数后面每行三个值起点城市、终点城市、距离”加载时对称填充矩阵。int loadGraph(const char *filename, int cost[][MAX], int *n) { FILE *fp fopen(filename, r); if (!fp) return -1; fscanf(fp, %d, n); // 第一行是城市数量 for (int i 0; i *n; i) for (int j 0; j *n; j) cost[i][j] (i j) ? 0 : INF; int u, v, w; while (fscanf(fp, %d%d%d, u, v, w) 3) { cost[u][v] w; // 无向图 cost[v][u] w; } fclose(fp); return 0; }无向图必须把对称位置也填上否则后续 Floyd 只沿一个方向计算从 v 到 u 会找不到路。fscanf(fp, %d%d%d, u, v, w) 3这个判断是读取三成功次才进入循环比while (!feof(fp))可靠。城市名不需要保存进算法因为 Floyd 只跟编号打交道。交互层把用户输入的“北京 上海”映射成 0 和 5查完编号再映射回名称输出。有些课程设计把城市名写死在程序里不是好习惯答辩老师一问“换一组城市数据怎么办”就卡住了。3.2 Floyd 全源最短路一次算完所有点对多个咨询请求任意起点终点同时出现的场景Floyd 比反复跑 Dijkstra 更适合。算法核心是三重循环把每一个顶点当作中间点逐个尝试看经过它会不会让原来的路径更短。void floyd(int n, int cost[][MAX], int path[][MAX]) { for (int i 0; i n; i) for (int j 0; j n; j) path[i][j] (cost[i][j] INF i ! j) ? i : -1; for (int k 0; k n; k) // 中间点 for (int i 0; i n; i) // 起点 for (int j 0; j n; j) // 终点 if (cost[i][k] cost[k][j] cost[i][j]) { cost[i][j] cost[i][k] cost[k][j]; path[i][j] path[k][j]; } }这里cost被原地修改最终cost[i][j]就是 i 到 j 的最短距离。path[i][j]存的是“从 i 到 j 的最短路径上j 的前一个顶点”用path[k][j]而不是path[i][k]因为路径是从 k 到 j 的那一段。回溯时void printPath(int path[][MAX], int i, int j) { if (path[i][j] -1) { printf(%d , i); return; } printPath(path, i, path[i][j]); printf(%d , j); }递归在这里很顺手先递归打印 i 到前驱的路径再打印当前终点。顶点数在 30 以内时递归深度不会爆栈。Floyd 的时间复杂度是 O(n^3)对交通咨询这种城市数量不超过 50 的场景毫无压力如果你的数据有几千个点就该考虑 Dijkstra 堆优化加多源预计算了。3.3 Prim 求最小生成树修路预算问题的标准答案“在所有城市之间修公路保证每两个城市都能连通总里程最短”这是最小生成树的经典表述。Prim 和 Kruskal 都能做区别在于Prim 适合边稠密的图Kruskal 适合边稀疏的图。交通网络这种每两个城市之间都可能直接连通的数据用 Prim 正好而且它和 Dijkstra 的代码结构很像两个算法放在同一份报告里对比性强。void prim(int n, int cost[][MAX]) { int lowcost[MAX], closest[MAX]; for (int i 1; i n; i) { lowcost[i] cost[0][i]; closest[i] 0; } for (int i 1; i n; i) { int u -1, min INF; for (int j 1; j n; j) if (lowcost[j] lowcost[j] min) { min lowcost[j]; u j; } printf(edge %d-%d\n, closest[u], u); lowcost[u] 0; // 0 表示已并入生成树 for (int j 1; j n; j) if (cost[u][j] lowcost[j]) { lowcost[j] cost[u][j]; closest[j] u; } } }lowcost[j]存的是“生成树到顶点 j 的最小边权”closest[j]记录这条最小边是从哪个顶点连过来的。lowcost[j] 0表示 j 已经属于生成树避免自己连自己。每次找一圈里最小lowcost输出一条生成树边再用它去更新所有不在树里的点。你会发现这个更新过程和 Dijkstra 的松弛几乎一样区别只是 Dijkstra 累加路径Prim 比较单条边权。4. Trie 树和后缀树的应用自动补全、词频统计与最长重复子串4.1 Trie 节点定义孩子数组用 26 个还是哈希表Trie 树在课程设计里最常见的身份是“搜索引擎的前置组件”或“单词自动补全器”。它的核心优势是共享公共前缀空间换查询时间插入和查询都是 O(单词长度)。节点定义最关键的是一个数组或哈希表来存孩子。如果是纯英文文本开next[26]最省事数组下标就是 c - a如果数据里混了大小写、数字、下划线就得把字符集扩大到 128 或 256直接拿 ASCII 码当下标。处理中文时一个汉字在 UTF-8 里是三个字节单纯用字符数组就不成立了常见做法是每次取一个完整汉字做 key但那种实现比英文 Trie 繁琐得多。课程设计用英文单词文本最稳。typedef struct TrieNode { int childCount; // 有多少个非空孩子遍历用 struct TrieNode *next[26]; // 英文字母节点 int pass; // 经过该节点次数词频用 int end; // 有多少单词在此结束 } TrieNode; TrieNode *newNode() { TrieNode *p (TrieNode *)calloc(1, sizeof(TrieNode)); return p; }pass和end是词频统计的两把尺子插入单词时每经过一个节点pass在末尾end查询一个单词出现次数就读end查询有多少单词以某前缀开头就读pass。用calloc分配会自动把所有指针和整数清零省去手动初始化的麻烦也是避坑里“指针未初始化”的正解。4.2 自动补全与词频统计两条最常用操作自动补全的思路很直接先沿输入前缀走到对应节点然后递归遍历该节点下的所有子树收集全部终止节点就是所有以该前缀开头的单词。课程设计里“输入 app提示 apple、application、apply”就是这个逻辑。void collect(TrieNode *node, char prefix[], int depth) { if (!node) return; if (node-end) { char full[64] {0}; strncpy(full, prefix, depth); printf(%s (%d)\n, full, node-end); } for (int i 0; i 26; i) { if (node-next[i]) { prefix[depth] a i; collect(node-next[i], prefix, depth 1); prefix[depth] \0; } } } void autocomplete(TrieNode *root, const char *pre) { TrieNode *p root; for (int i 0; pre[i]; i) { p p-next[pre[i] - a]; if (!p) return; } char buf[64] {0}; strcpy(buf, pre); collect(p, buf, strlen(pre)); }collect的depth变量同时有两个作用它既是当前前缀的长度也是写入prefix的下标。递归进入next[i]之前先写入对应字母回溯时用\0截断这样prefix始终是当前路径上的完整单词。参数里char prefix[]在 C 语言中是值传递但数组退化为指针递归过程中修改的是同一块内存所以打印前必须用strncpy复制出来否则输出会被后续递归覆盖。词频统计更进一步建立好含end和pass的 Trie 后遍历一次把所有终止节点的单词和次数输出就是一份“词频表”。这个功能经常被要求配合文本文件输入读入一篇文章按空格/标点切出英文单词全部 insert 到 Trie再 collect 一次。实现简单效果直观同时也把“读文件—处理字符串—用新数据结构存结果”这条链路完整走了一遍。4.3 后缀树课后题为什么我用后缀数组代替后缀树后缀树在理论上是强大的一个字符串的所有后缀都放进压缩前缀树里可以查询子串是否存在、统计子串出现次数、求最长重复子串。代价是构造算法复杂教材里说的 Ukkonen 线性构造算法光active point和suffix link两个概念就够劝退大部分学生。课程设计阶段我一般建议直接用后缀数组替代。后缀数组记录的是每个后缀的起始位置排序后相邻后缀的最长公共前缀就是最长重复子串的候选结论成立的关键是任何重复出现的子串一定出现在两个相邻后缀的公共前缀里。暴力排序的复杂度是 O(n^2 log n)对几千字节的文本完全够用不碰 Ukkonen 也能把原理讲清楚。int buildSuffixArray(const char *s, int *sa) { int n strlen(s); for (int i 0; i n; i) sa[i] i; // 直接比较两个后缀的字典序规模小足够 for (int i 0; i n; i) for (int j i 1; j n; j) if (strcmp(s sa[i], s sa[j]) 0) { int t sa[i]; sa[i] sa[j]; sa[j] t; } return n; } void longestRepeat(const char *s, int *sa, int n, char *out) { int maxlen 0, pos 0; for (int i 0; i n - 1; i) { int len 0; while (s[sa[i] len] s[sa[i] len] s[sa[i 1] len]) len; if (len maxlen) { maxlen len; pos sa[i]; } } strncpy(out, s pos, maxlen); out[maxlen] \0; }strcmp(s sa[i], s sa[j])比较的是从这两个位置开始的两个后缀字符串C 语言里运算符优先级高于指针解引用所以写成s[sa[i] len]比*(s sa[i] len)清晰。while循环里先判断当前字符不是\0再判断相等顺序不能反否则越界读。strncpy(out, s pos, maxlen)精确截取最长重复子串最后手动补\0是因为strncpy在不足长度时补零但恰好截满maxlen时不会补结束符。后缀树的题还有另一个常见分支最长公共子串求两个字符串的共同最长片段。那个需要把两个串拼成s1 # s2再建后缀数组保证公共前缀跨过拼接点且字符不同。如果课程设计文档里写的是“后缀树应用”后缀数组能应对绝大多数查询类问题但要是题目强制要求“画出后缀树”那就只能按图论手工建一棵再把程序里的含义对应上去。5. 课程设计避坑指南文件指针、内存管理、中文编码5.1 用 feof 判断文件结尾最后一条航班记录凭空消失现象读航班文件时终端输出少了一条记录有时又多输出一条乱码数据。原因feof(fp)只有在读取操作已经越过文件末尾之后才会返回真。用while (!feof(fp))判断时循环体会先执行一次再判断是否结束。最后一个有效数据正好读到EOF边界时条件还认为是假于是又进入循环读一次要么读到垃圾数据要么因为读取失败用了未更新的变量。解决改用读取函数的返回值判断。fscanf返回成功读取的字段数fgets返回非 NULL 表示读到了内容。航班文件用while (fscanf(fp, %s%s%d%d, no, from, price, seats) 4)就能准确控制循环次数。这是文件读取里最经典的一个“玄学”bug所有数据类型都受影响写完代码先跑一遍包含末行数据的用例是基本原则。5.2 free 一个没申请过的指针程序崩得莫名其妙现象程序启动正常执行删除操作时崩溃或者退出时在free(head)处报“double free or corruption”。原因链表节点创建用了Flight *p; p-price 100;只管了指针没分配内存p指向野地址写字段时已经破坏堆另一种更隐蔽的情况是head被局部指针直接赋值函数内部free(cur)时把原本属于其他节点或者栈区的地址释放了。解决所有节点必须经过malloc或calloc分配后使用且free之后要将原指针置为NULL。删除单链表节点时必须保存前驱节点把prev-next cur-next先接好再free(cur)顺序反过来会导致后继节点丢失。我习惯每次分配后马上判空Flight *nf (Flight *)calloc(1, sizeof(Flight)); if (!nf) { printf(memory error\n); exit(1); }calloc比malloc多做了一个清零动作对结构体里的指针字段特别友好能避免“结构体里夹杂随机值导致链表断链”的隐性翻车。5.3 中文乱码Windows ANSI 和 Linux UTF-8 的互相伤害现象源文件在 Windows 下用记事本写的中文注释乱码或者程序运行后界面里的中文变成“锟斤拷”。更离谱的是代码里if (strcmp(flight-from, 北京) 0)在 Windows 上正常放到 Linux 上编译后永远匹配不上。原因Windows 简体中文版默认用 GBK/ANSI 编码保存文本Linux 下用 UTF-8。同样一串“北京”字节序列两种编码下的字节完全不同字符串比较自然失败。解决整个项目从源码到数据文件统一用 UTF-8并且打开方式要写明。在 Windows 上用 Visual Studio 时可以在源码开头插入#pragma execution_character_set(utf-8)或者把命令行和编辑器都切到 UTF-8数据文件包含中文时写文件用fprintf(fp, %s %s %d\n, from, to, price)不涉及编码转换只要原始数据是 UTF-8 就没有问题。最省心的是把城市名、机场名改成英文或者拼音课程设计没有强制要求中文界面答辩时口头解释“中文是展示层问题不影响算法”也能通过。5.4 Dijkstra 只算“最短”回答不了“最多转两次”现象交通咨询系统里用户问“从 A 到 B最多转两次车哪个方案最近”直接跑 Dijkstra 得到的结果可能包含三次中转被老师当场指出与需求不符。原因Dijkstra 的目标是最短路径不会约束跳数中转次数。它把路径长度当作唯一优化目标一旦找到最短路径即使需要转很多次也不会再找次优解。课程设计题目如果明确写了“限乘次数”那图模型就要加维度用 BFS 或者动态规划状态从“到达哪个城市”升级为“到达哪个城市且乘坐了几次”。解决先读题。只求“最短”用 Dijkstra/Floyd要求“中转次数最少”且边权为 1用 BFS要求“中转次数不超过 k 次且总距离最短”用带跳数约束的动态规划dp[k][v]。实现时把距离矩阵变成三维状态表转移时限制k不超上限。5.5 main.c 越写越长最后自己都不认识现象课程设计交卷前一周打开main.c里面两百行代码全是菜单打印和函数调用找不到算法在哪里加一个小功能要滚动半天。原因为了省事所有菜单逻辑、文件读取、算法实现全部堆在 main 函数里全局变量满天飞。当时觉得方便后来查 bug 时才发现函数之间通过全局变量传递数据一处改动处处报错。解决按子系统拆文件——flight.c、graph.c、trie.c、search.c、main.c头文件里只放接口声明。菜单逻辑单独一个menu.c从 main 里调用。模块拆分还有一个实际好处答辩演示时老师让你“只讲飞机票这部分”时你可以快速定位代码而不是在 main 里来回滚动找case 3。这也是从“能跑”到“像工程”的关键一步应聘实习时项目经验写这个也更有说服力。6. 简单搜索引擎倒排索引实现之外交差前还要过的三关6.1 倒排索引与中文分词的最小实现简单搜索引擎的课程设计核心考核点不是爬虫那个也不许你爬而是倒排索引从一组文档里提取词项建立“词项 - 文档列表 词频”的映射。查询时把用户输入拆成词项去倒排表里找并集或交集按相关度排序。数据结构上用哈希表或链表都行但既然做了 Trie 树更优雅的是直接用一棵 Trie 当词项字典每个终止节点挂一条文档链表。中文分词是最大的坎。一句“研究数据结构的应用”按空格切分只会得到一个整串。课程设计不需要上 jieba实现一个正向最大匹配足够词典里放一批常用词从句子开头尽量匹配最长的词匹配不到就按单字处理。int cutFMM(const char *line, char words[][32], int maxWords) { int len strlen(line), i 0, cnt 0; while (i len cnt maxWords) { int adv 1; // 尝试从当前字符开始匹配最长词假设最长 4 个汉字 for (int l 12; l 3; l - 3) { if (i l len matchDict(line i, l)) { strncpy(words[cnt], line i, l); words[cnt - 1][l] \0; i l; adv 0; break; } } if (adv) { // 没匹配到词当单字处理 words[cnt][0] line[i]; words[cnt - 1][1] \0; i; } } return cnt; }l按 3 的倍数递减是因为一个汉字在 UTF-8 里占 3 字节最长匹配 4 个汉字就是 12 字节。匹配成功就跳过l个字节继续匹配不到就落单字。这套实现只做演示工程级分词要比它复杂得多。倒排索引建立后查询就是“拆分查询串 - 到 Trie 里找每个词项的文档链表 - 按词频和文档频率计算一个简单打分”。6.2 交差前的三件事跑通、截图、写实验报告我自己的习惯是验收时按“测试用例 截图 报告”三件套来。先为四个子系统各准备一组测试数据航班文件 5 条以上、城市图 6 个顶点以上、英文文章 200 词以上、搜索语料 10 篇左右。每个子系统跑一遍核心功能把输入命令和输出结果存成 txt截图贴进实验报告。这一步看起来麻烦但能逼出大量边界问题——比如空文件、只有一个城市、查询词不在词典里。写报告时不要只贴代码要把每个子系统的数据结构设计理由写透为什么航班用链表不用顺序表为什么交通咨询用 Floyd 不用多次 Dijkstra为什么 Trie 的孩子数组开 26 而不开 128。老师看重的是你在取舍里有依据而不是代码跑起来就行。这也是整个课程设计真正的收获把线性表、图、树、查找排序四项核心内容在一套系统里织成网。希望你答辩前不用熬夜改 bug 改到凌晨——把文件编码、内存分配和边界条件这三关提前过一遍这份 zip 里的四个子系统都能稳稳落地希望帮到你。本文还有配套的精品资源点击获取