简介一份面向C数据结构课程设计学生的完整项目合集涵盖飞机票管理系统、Trie树与后缀树应用、交通咨询系统设计和简单搜索引擎四大模块。资源共1398个文件压缩包约10.5MB除大量索引数据文件idx外还包含17个头文件、16个C源文件、Qt界面文件ui、工程配置pro/json及说明文档其中idx文件承载检索索引数据h/cpp为各模块算法实现ui/json对应界面与工程配置整体目录适合按模块拆解学习。已有81人学习下载。项目中Trie树用于航班检索与自动补全后缀树支撑字符串模式匹配和搜索引擎索引构建交通咨询系统则涉及动态路线规划。通过阅读源码与工程文件可直观掌握各类数据结构的实际选型、封装方式及C多文件协作流程尤其适合需要完成期末课程设计或准备数据结构进阶项目的学生参考借鉴。1. 期末课程设计拿到手先别慌四个 C 题目的一张地图每年期末的数据结构课程设计翻来覆去就是那么几类题图论应用、字符串检索、文件管理与查询。这次拆的这个资源包正好把最典型的四个方向打包在了一起——飞机票管理系统、Trie 树和后缀树的应用、交通咨询系统设计、简单搜索引擎全部用 C 实现。说白了这是一套拿来就能跑的课程设计源码不是那种只有空壳的演示工程。它的价值在于把「数据结构怎么落到实际系统里」这件事讲透了航班查询是图的最短路径搜索引擎的底层是倒排索引前缀匹配靠 Trie 树复杂子串问题靠后缀树。如果你正被课设卡住或者想看看别人怎么把一本书的散知识点串成四个能答辩的项目这份资源值得花一个晚上拆开来看。2. 飞机票管理系统迪杰斯特拉与弗洛伊德怎么选、代码怎么落2.1 航班系统本质是一张带权图邻接矩阵怎么建课程设计里的飞机票管理系统剥掉菜单和界面外壳核心就是一个带权无向图如果考虑单程航线也可以是有向图。城市是顶点航线是边票价或者飞行时间就是边上的权重。最常见的做法是用邻接矩阵存因为城市数量在课设规模下不会超过 20 个用矩阵反而比邻接表更直观答辩时画图也好讲。const int MAXN 20; const int INF 0x3f3f3f3f; // 用这个值而不是 INT_MAX防止加法溢出 int graph[MAXN][MAXN]; // 全局邻接矩阵 int vertexCount; // 城市数量从文件读入 void initGraph(int n) { vertexCount n; for (int i 0; i n; i) for (int j 0; j n; j) graph[i][j] (i j) ? 0 : INF; } // 读入航班数据后建边 void addFlight(int cityA, int cityB, int price) { graph[cityA][cityB] min(graph[cityA][cityB], price); graph[cityB][cityA] min(graph[cityB][cityA], price); // 双向航线 }0x3f3f3f3f是 C 竞赛里常用的 INF 值约等于 10 亿两个 INF 相加不会溢出 int 范围这是很多新手最容易忽略的点——用INT_MAX做无穷大迪杰斯特拉松弛时两个 INT_MAX 一加直接变成负数路径全乱。建边时取min是为了防重边实际航班数据里两家航司可能飞同一航线价格还不一样程序里只保留最便宜那条。2.2 选迪杰斯特拉还是弗洛伊德单源查询与答辩友好度飞机票管理系统最常见的功能是「查询两个城市之间的最低票价路径」。这一步选算法有个很现实的问题迪杰斯特拉是单源最短路径一次只能查一个起点到所有终点的最短路径弗洛伊德是全源最短路径一次计算出所有城市对之间的最短路径。我的建议是课设里两个都写但明确它们的定位// 迪杰斯特拉适合用户反复查询「从 A 城出发到任意城市」 void dijkstra(int src, vectorint dist, vectorint pre) { vectorbool visited(vertexCount, false); dist.assign(vertexCount, INF); pre.assign(vertexCount, -1); dist[src] 0; for (int round 0; round vertexCount - 1; round) { int u -1; for (int i 0; i vertexCount; i) { if (!visited[i] (u -1 || dist[i] dist[u])) u i; } if (u -1 || dist[u] INF) break; // 剩余城市不可达 visited[u] true; for (int v 0; v vertexCount; v) { if (!visited[v] graph[u][v] INF dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; pre[v] u; // 记录前驱城市用于回溯路径 } } } }这段代码每次从未访问的顶点里挑一个距离最小的u这个「挑最小」的过程在课设规模下用线性扫描就够了不用写堆优化。因为城市数撑死 20 个堆优化带来的性能提升在这里毫无存在感写了复杂堆结构答辩反而容易被追问。// 弗洛伊德一次把所有城市对的路径都算出来代码极短答辩好讲 int dist[MAXN][MAXN]; int path[MAXN][MAXN]; // path[i][j] 记录 i 到 j 路径上的中间点 void floyd() { for (int i 0; i vertexCount; i) for (int j 0; j vertexCount; j) { dist[i][j] graph[i][j]; path[i][j] -1; // 表示 i 直达 j } for (int k 0; k vertexCount; k) for (int i 0; i vertexCount; i) for (int j 0; j vertexCount; j) if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; path[i][j] k; } }弗洛伊德最让人舒服的一点是三重循环写完不像迪杰斯特拉还要维护 visited 数组。我一般会跟答辩老师说这个系统的城市规模小弗洛伊德的 O(n³) 在 n20 时没任何压力换来的是实现简单和不容易写错。实际选型给了个对比参考场景适合算法时间复杂度答辩讲解难度单次查询一个起点到各城市迪杰斯特拉O(n²)中要讲贪心思想查询任意两城市间的票价弗洛伊德O(n³)低三重循环一句话讲完城市数几十万级的真实航司场景堆优化迪杰斯特拉O((nm)log n)高不推荐课设选2.3 路径怎么回溯pre 数组与 path 矩阵很多人的课设代码能算出最短票价但打印不出「北京 → 上海 → 广州」这条路径问题就出在回溯逻辑上。迪杰斯特拉的回溯靠pre数组从终点往前倒着找前驱弗洛伊德的回溯靠path矩阵需要递归处理。// 弗洛伊德路径回溯利用 path 矩阵递归打印 void printPathRecursive(int i, int j) { if (path[i][j] -1) { cout i 1 → j 1 ; return; } int k path[i][j]; printPathRecursive(i, k); // 先打印 i 到 k 这一段 cout ( k 1 ); // 再打印中间顶点 printPathRecursive(k, j); // 再打印 k 到 j 这一段 }这里有个细节要注意dist[i][j]等于dist[i][k] dist[k][j]时才对path[i][j]赋值不能只判断小于。因为等于的情况也可能需要更新中间点否则路径可能不是最短的那条。我见过不少同学只写最后打印出来的路径长度对得上但中间绕了远路答辩时被老师一追问就露馅。3. Trie 树与后缀树字符串检索从课堂到课设的实现边界3.1 Trie 树一个节点放什么、26 个指针的坑Trie 树是一个经典得不能再经典的课设题目它的应用场景很明确给定一组单词快速判断某个前缀下面有哪些词或者判断某个词是否存在。核心做法是把每个单词的字符拆成从根到叶子的一条链。struct TrieNode { bool isEnd false; // 标记从根到当前节点是否构成一个完整单词 TrieNode* children[26]; // 26 个小写字母的指针数组 TrieNode() { memset(children, 0, sizeof(children)); } }; class Trie { private: TrieNode* root; public: Trie() { root new TrieNode(); } void insert(const string word) { TrieNode* cur root; for (char c : word) { int idx c - a; if (cur-children[idx] nullptr) cur-children[idx] new TrieNode(); cur cur-children[idx]; } cur-isEnd true; } bool startsWith(const string prefix) { TrieNode* cur root; for (char c : prefix) { int idx c - a; if (cur-children[idx] nullptr) return false; cur cur-children[idx]; } return true; } bool search(const string word) { TrieNode* cur root; for (char c : word) { int idx c - a; if (cur-children[idx] nullptr) return false; cur cur-children[idx]; } return cur-isEnd; // 这里要判断 isEnd不能只按前缀判断 } };这段代码里最该注意的坑有两个。第一children[26]定长数组在数据稀疏时非常浪费每个节点不论有没有那么多子节点都占了 26 个指针的内存。课设里如果字典有几千个单词这个开销还算能扛但如果你定义的是 TrieNode 对象数组而不是指针数组每个节点里 26 个 TrieNode 对象会连锁创建内存直接爆炸。第二search和startsWith的区别就差在最后的isEnd判断上。很多同学把这两个函数写成一样的查询单词app时字典里只有apple也返回存在这显然不对。如果不想写定长数组换unordered_mapchar, TrieNode*是更好的选择。它按需分配子节点内存省很多代码也不复杂struct TrieNode { bool isEnd; unordered_mapchar, TrieNode* children; TrieNode() : isEnd(false) {} };缺点是每个节点多存了一个哈希表的结构开销在小写字母字典场景下定长数组访问更快。两种做法各有取舍课设里我会推荐先写数组版本答辩时再补充说「如果字符集扩大可以换成哈希表」这本身就是一个加分的扩展点。3.2 后缀树课堂能听懂、课设怎么写后缀树是字符串题里最让人头疼的一个结构因为 Ukkonen 算法的在线构建逻辑极其绕涉及 suffix link后缀链接、active point活动点、剩余后缀数这些概念。课堂上一个小时能听懂课设里自己写的时候往往会翻车——不是段错误就是建出来的树不对。先明确一件事后缀树的应用价值在哪。给定一个长文本后缀树可以在 O(m) 时间内判断某个模式串是不是它的子串还能在线性时间内找出最长重复子串、最长公共子串。搜索引擎里的关键词过滤、生物信息学里的基因序列比对底层都是这类思想。但课设的边界是什么如果你只是要完成「后缀树的应用」这个题目我不建议硬写 Ukkonen。更务实的路线是先用朴素方法建立后缀 Trie把每个后缀插入 Trie 树虽然 O(n²) 的空间和时间在长文本下扛不住但课设的演示文本只有几百个字符完全够用// 简化后缀树把字符串的所有后缀插入 Trie本质是朴素后缀 Trie void buildSuffixTrie(const string text) { for (int i 0; i text.size(); i) { insertSuffix(root, text.substr(i)); // 插入从 i 开始的后缀 } } // 查询某个子串是否存在 bool containsSubstring(const string pattern) { return searchPrefix(root, pattern); }这个版本的优点是思路直接答辩时你能清晰讲出「后缀树是把所有后缀压进一颗树里能快速回答子串存在性」缺点是你得主动跟老师承认这是朴素后缀 Trie不是压缩后的真后缀树。如果要写真后缀树我建议你读一下 Ukkonen 算法的三个关键点隐式后缀树的维护、suffix link 的用途、最后一个字符的扩展规则任何一点抄错都会导致建树结果不一致而且极难调试。4. 交通咨询系统与简单搜索引擎图的存储与倒排索引一次打通4.1 交通咨询系统邻接表建图最小生成树做路网规划交通咨询系统的代码骨架和飞机票管理系统很像都是图论在交通场景里的落地。区别在于交通咨询往往要考虑「修路成本最低的连通方案」也就是最小生成树问题。邻接矩阵在这种场景里依然能用但交通路网通常比航班网络稀疏——不是每两个城市都有直连公路——所以更合理的做法是邻接表。struct Edge { int to; // 另一端的城市编号 int weight; // 距离或费用 Edge(int t, int w) : to(t), weight(w) {} }; vectorvectorEdge adj; // 邻接表 void addUndirectedEdge(int u, int v, int w) { adj[u].push_back(Edge(v, w)); adj[v].push_back(Edge(u, w)); } // Prim 最小生成树从顶点出发逐步扩张 int prim(int start) { int totalCost 0; vectorint minCost(adj.size(), INF); vectorbool inTree(adj.size(), false); minCost[start] 0; for (int round 0; round adj.size(); round) { int u -1; int minW INF; for (int i 0; i adj.size(); i) { if (!inTree[i] minCost[i] minW) { minW minCost[i]; u i; } } if (u -1) return -1; // 图不连通 inTree[u] true; totalCost minW; for (const Edge e : adj[u]) { if (!inTree[e.to] e.weight minCost[e.to]) { minCost[e.to] e.weight; } } } return totalCost; }Prim 算法的代码逻辑一句话就能讲明白每次从「已选顶点集合」的邻接边里挑一条权重最小的边把对应新顶点加进来。注意minCost数组记录的是「每个顶点到已选集合的最小距离」不是到起点的距离这是和迪杰斯特拉最大的区别。写的时候别把两个算法的 minCost 语义搞混我见过有人把 Prim 的minCost写成了迪杰斯特拉的距离数组结果跑出来的生成树是错的。另一个常见的实现分歧是 Kruskal 算法它的思路是「把边按权排序从小到大一条条尝试加入用并查集判环」。如果你课设选的题是「公路修建方案」我建议两个都写因为老师特别爱问「Prim 和 Kruskal 分别适合什么场景」——Prim 适合稠密图Kruskal 适合稀疏图交通路网恰好是稀疏图Kruskal 的实际表现更好。4.2 简单搜索引擎切词、倒排索引、查询排序搜索引擎这个题目很多同学以为难点在网页爬取但实际上课设级别的搜索引擎根本不需要爬虫。题目给你的是一堆本地文本文件你要做的是建索引、响应查询并提供排序结果。底层结构核心是倒排索引——一个从词到文档列表的映射。// 倒排索引构建docId 是文档编号每个文档正文先做简单切词 unordered_mapstring, vectorint invertedIndex; unordered_setstring stopWords; // 停用词表的、了、是、在…… void buildIndex(const vectorstring docs) { for (int docId 0; docId docs.size(); docId) { vectorstring words split(docs[docId]); // 按空格/标点切词 unordered_setstring seen; // 当前文档去重标记 for (const string w : words) { string key toLower(w); // 统一转小写 if (stopWords.count(key)) continue; // 跳过停用词 if (seen.insert(key).second) { // 同一个 docId 只记一次 invertedIndex[key].push_back(docId); } } } } // 查询输入词返回包含该词的文档列表 vectorint queryWord(const string word) { auto it invertedIndex.find(toLower(word)); if (it invertedIndex.end()) return {}; return it-second; } // 多词查询取两个词对应文档列表的交集 vectorint queryAnd(const string w1, const string w2) { vectorint a queryWord(w1); vectorint b queryWord(w2); vectorint result; size_t i 0, j 0; while (i a.size() j b.size()) { if (a[i] b[j]) { result.push_back(a[i]); i; j; } else if (a[i] b[j]) { i; } else { j; } } return result; }我挑三个最容易翻车的点强调一下。第一切词后同一个词在同一个文档里出现多次索引里如果不做 docId 去重查询结果里会有大量重复项。上面的代码用seen集合在构建时去重比查询时再去重要省事得多。第二中文分词别在这里自己硬写课设文本里如果是中文直接在代码里放一个基本的分词词典或者把文本换成英文/拼音数据源否则你会陷入「切词不对导致索引全废」的泥潭。第三排序不能只看词频至少要做一个简单的 TF 排序——关键词在文档里出现次数越多排越前这个逻辑用vectorpairint,int就能实现第一维存词频第二维存 docId按词频降序输出。5. 避坑排查四个模块里反复出现的六个翻车点5.1 迪杰斯特拉跑出负数路径INF 加法溢出现象最短路径计算结果出现负数或者明明有路径的顶点输出 INF。原因用INT_MAX做无穷大松弛判断dist[u] graph[u][v] dist[v]时两个大数相加溢出成负数把dist[v]错误更新成了一个很小的负数。解决全局用0x3f3f3f3f做 INF两个 INF 相加约等于 20 亿小于 int 上限 21.4 亿不会溢出。所有涉及 INF 的初始化、判断都统一用这个常量不要一边用 0x3f3f3f3f 一边用 INT_MAX。5.2 Trie 树内存不降反升节点数组的连锁初始化现象插入几百个单词后程序内存占用飙升到几百 MB甚至直接崩溃。原因TrieNode 里如果定义的是TrieNode children[26]而不是指针数组构造一个节点时会递归构造 26 个子节点每个子节点又构造 26 个孙节点——这不是树是爆炸的满 26 叉树。解决节点里只声明TrieNode* children[26]子节点用new按需创建。如果内存还是紧张换unordered_mapchar, TrieNode*。课设规模下指针数组 new 是标准写法。5.3 后缀树建树结果不对Ukkonen 的 suffix link 没初始化现象按教材抄的 Ukkonen 代码能跑但查询子串时结果东拼西凑或者某些后缀插入后树里找不到。原因Ukkonen 算法的 suffix link 在内存中要预先指向一个虚拟根节点很多模板里只设了root-link nullptr插入新后缀时沿 suffix link 跳转就访问了空指针或跳错位置。解决要么严格按论文级的模板把所有 link 初始化到位要么放弃 Ukkonen改用朴素后缀 Trie 并在文档里主动声明「演示级实现」。「承认简化」比「拿着跑不通的复杂代码硬撑」在答辩里体面得多。5.4 搜索引擎查询结果全乱同文档重复词未去重现象查询一个词返回 18 条结果但文档只有 6 篇每篇出现三次。原因构建倒排索引时没有检查当前词是否已经在当前 docId 里出现过同一个 word-doc 对插入了多次。解决构建索引时维护一个unordered_setstring记录当前文档已出现的词或者更高效的做法是在索引的 vector 末尾比对back() ! docId时再 push_back。注意前提是 docId 按顺序遍历递增。5.5 文件读入乱码或漏行分隔符不统一现象航班信息用cin 读能读对换成getline后城市名变乱码或者最后一行数据读不到。原因航班文件里混合了空格和 Tab 或者换行符\r\ngetline默认按\n分割Windows 下\r残留到字符串末尾。解决统一用ifstream配合getline读每行然后用stringstream按空格或 Tab 再做二次拆分注意清理每行末尾的\r。5.6 答辩被问「为什么不用堆优化」答不上来现象老师问迪杰斯特拉为什么不用优先队列时间复杂度多少你愣住。原因代码里用的是线性扫描找最小顶点你没有准备复杂度相关的解释。解决明确记住课设规模的 n 只有几十个点线性扫描 O(n²) 完全够用如果换优先队列是 O((nm)log n)但代码复杂度上升、调试成本提高在 n 极小场景下反而是过度设计。回答思路是「先正确再优化当前规模下没必要」。6. 把四个课设串成一个骨架公共数据结构与后续扩展拆完这四个模块你会发现它们之间其实可以共享一套代码骨架。图的邻接矩阵和邻接表封个类字符串处理的工具函数放一个文件文件读取统一用一个带错误处理的函数这样四个课设不要各写一套重复代码。我一般会新建一个utils.h把所有公共头文件、INF 常量、分割字符串、读取文件、计时函数都放进去。进一步说如果你想把这套课设的含金量往上提有两条可走的路。第一条是把交通咨询系统的 Prim 和飞机票管理系统的迪杰斯特拉都封装成同一个「图搜索算法」类的成员函数用枚举区分算法类型这样代码复用性更强答辩时能讲面向对象设计第二条是在搜索引擎里加入布尔查询和 TF-IDF 排序不只是输出文档列表还按相关度打分这就是从「能跑」到「像产品」的差别。我自己的血泪经验是课设代码写完一定要在答辩前一天把每个模块的输入文件、运行截图、算法复杂度整理成一个 README把每个函数的功能和入参出参写成注释不是给老师看是给你自己看的——因为答辩现场你盯着自己两周前写的代码十有八九会突然想不起来path矩阵里存的是什么。从那以后我每次交付代码都强制走一遍「跑通 → 补注释 → 写 README → 准备两个追问答案」的流程希望帮到你。本文还有配套的精品资源点击获取