简介哈夫曼码编/译码系统、递归替换问题、跳马问题和长整数运算问题共同组成这份数据结构课程设计PDF文档。资料面向计算机专业学生与算法备考者哈夫曼部分聚焦最优前缀编码与无损压缩递归替换处理文本模式匹配跳马问题借助DFS/BFS搜索可行路径长整数运算解决超出普通整型范围的加减乘除。压缩包内仅含1个PDF文件大小约268KB内容包括每个题目所采用类语言定义的数据类型、算法步骤、函数的调用关系图、调试分析、测试结果及带注释的源程序结构完整且可直接对照复现。目前已有171人学习浏览既可作为课程作业和实验报告范本也可用于期末复习和算法练习复盘尤其适合需要独立完成课程设计的同学参考其问题分析、模块划分与排错过程。1. 四个经典题同时出现在一张课设表里哈夫曼编译码、递归替换、跳马与长整数到底在考什么课设题目列表同时躺着“哈夫曼码的编译码系统”“递归替换问题”“跳马问题”“长整数运算问题”四个题时新手的第一反应通常是挑一个看着最水的先写老手却会先把四道题的内在关系看出来哈夫曼码考的是二叉树遍历与编码译码递归替换考的是递归拆分问题与边界条件跳马问题考的是图上深搜、回溯与剪枝长整数运算考的是线性表存储与高精度数值处理。四道合起来恰好覆盖了数据结构课程里最核心的四块内容也算出题老师的老一套组合拳。下面这套拆解思路适合正在被数据结构课程设计折磨的本科生、准备考研数据结构408的人以及想补一补手写基础算法能力的开发者。2. 哈夫曼码的编译码系统静态链表建树、逆推编码与译码回溯哈夫曼编译码在课设里的完整流程是统计字符频率 → 构建哈夫曼树 → 生成编码表 → 压缩原文 → 按编码串译码还原。很多人卡在第二步和第三步其实拆开看每一步都有非常固定的套路。2.1 节点结构为什么选数组下标模拟指针写哈夫曼树教科书喜欢给你画指针树但课设里用指针反而容易翻车——节点需要经常向上访问 parent指针方案得给每个节点额外存一个 parent 指针申请释放还容易出内存泄漏。我一般直接用数组下标模拟指针也就是静态链表。#define MAX_NODES 512 #define MAX_CODE_LEN 260 typedef struct { unsigned char data; /* 叶子节点保存字符非叶子节点不关心 */ int weight; /* 权值统计到的出现次数 */ int parent; /* 父节点下标0 表示双亲还没确定 */ int lchild, rchild; /* 左、右孩子下标-1 表示空 */ } HTNode;结构体里存四个字段就够了。用数组下标当指针孩子在数组里的位置就是下标查找父节点是 O(1) 的数组访问整个建树过程不需要一次内存分配。对于 n 个叶子节点的哈夫曼树节点总数固定为 2n-1所以数组长度给到 2 乘叶子数就可以了。我在代码里直接开 512 是为了省得每次课设改数字如果统计的是字节流最多 256 种512 个节点正好够用。建树前要先把统计好的字符频率填进 nodes[0..n-1] 的 weight 字段data 字段填上字符本身。非叶子节点的 data 没有业务含义初始化时设成 0 就行。2.2 建树反复找两个最小权值节点的合并套路哈夫曼树的构建过程就是循环 n-1 次每次在 parent 为 0 的节点里挑两个权值最小的合并成一棵新树新节点下标从 n 开始递增。这里最关键的是“两个最小”的选择逻辑。void buildHuffmanTree(HTNode nodes[], int n) { int total 2 * n - 1; int i, j; /* 初始化所有节点的双亲和孩子字段 */ for (i 0; i total; i) { nodes[i].parent 0; nodes[i].lchild nodes[i].rchild -1; } for (i n; i total; i) { int min1 -1, min2 -1; /* 只扫描下标 0i-1从 parent 为 0 的节点里找最小两个 */ for (j 0; j i; j) { if (nodes[j].parent ! 0) { continue; /* 已经合并过的节点跳过 */ } if (min1 -1 || nodes[j].weight nodes[min1].weight) { min2 min1; min1 j; } else if (min2 -1 || nodes[j].weight nodes[min2].weight) { min2 j; } } nodes[i].weight nodes[min1].weight nodes[min2].weight; nodes[i].lchild min1; nodes[i].rchild min2; nodes[min1].parent i; nodes[min2].parent i; /* 两个孩子不再是自由节点 */ } }这段逻辑里最容易看迷糊的是 min2 的更新当新扫描的节点比当前最小 min1 还小时原本的 min1 降级成第二小所以要先把 min2 min1 再做 min1 j。等值情况我取先扫描到的下标这样同样的权值合并顺序稳定编码表不会因扫描顺序不同而跳变。参数 n 表示叶子个数调用前必须保证 n 大于 0而且 nodes[0..n-1].weight 都填好了。提示如果叶子数量很大这个双重扫描是 O(n²)课设规模没问题但你要是想拿去处理几万个字符的长文本就得换最小堆来选两个最小值。2.3 从叶子逆推哈夫曼编码最容易写反的一段代码编码表生成的思路很简单从某个叶子出发一路沿 parent 向上走到根每走一步记下“从父节点到当前节点是左还是右”左记 0 右记 1。因为是从叶子往根走记下来的顺序是反的必须反转之后才能作为编码。void buildCodeTable(HTNode nodes[], int n, char codeTable[][MAX_CODE_LEN]) { char tmp[MAX_CODE_LEN]; int i, cur, parent; for (i 0; i n; i) { int idx MAX_CODE_LEN - 2; tmp[MAX_CODE_LEN - 1] \0; cur i; parent nodes[cur].parent; while (parent ! 0) { if (nodes[parent].lchild cur) { tmp[idx--] 0; } else { tmp[idx--] 1; } cur parent; parent nodes[cur].parent; } strcpy(codeTable[i], tmp[idx 1]); } }这里我用了从后往前填字符再整体复制的办法省得自己单独写一次字符串反转。注意循环结束条件是 parent 为 0也就是走到了树的根节点因为根节点的 parent 永远是 0。如果某次循环结束后 idx 没有变化说明这个节点的 parent 链是断的那一定是建树时 parent 没写对——这种问题在第 5 章会专门讲排查思路。编码表的每个字符串要用 strlen 单独看长度压缩时按长度逐位拷贝到输出缓冲。2.4 译码从根走叶子遇到非法编码怎么兜底译码比编码简单拿着 01 串从根出发0 跑左孩子1 跑右孩子走到叶子就输出这个字符然后跳回根继续。难点在控制数组不越界和识别非叶子节点。int decodeText(HTNode nodes[], int n, const char *bits, char *output) { int root 2 * n - 2; int cur root; int outPos 0; for (int i 0; bits[i] ! \0; i) { if (bits[i] 0) { cur nodes[cur].lchild; } else { cur nodes[cur].rchild; } if (cur 0) { return -1; /* 非法编码说明输入串不是这份哈夫曼树编出来的 */ } if (nodes[cur].lchild -1 nodes[cur].rchild -1) { output[outPos] (char)nodes[cur].data; cur root; /* 一个字符译完回到根 */ } } output[outPos] \0; return 0; }注意两个细节一是 cur 小于 0 必须返回错误码否则后面访问负下标直接崩溃二是走到叶子后必须立刻把 cur 重置回 root不然下一个字符会接着错误的节点继续走。译码输出字符串的长度不会超过输入 bits 的长度所以 output 缓冲区只要不小于 bits 长度加一就是安全的。到这一步哈夫曼编译码系统的主体就算齐了统计频率、建树、编码表、压缩输出、译码还原。课设报告里这部分建议补一个压缩前后字节数的对比表说明哈夫曼编码省了多少空间这是老师最想看到的实验数据。3. 递归替换和跳马问题把递归讲到能过验收的两个载体递归替换和跳马放在同一道题组里是有道理的两个都考递归但一个是“分解问题规模”的线性递归一个是“探索状态空间”的深搜递归。很多同学写递归总是卡在出口条件上这两个题刚好能把“出口、递推、回溯”三个概念一次补齐。3.1 递归替换问题的递归出口设计递归替换问题在课设里的常见要求是给定一个字符串 str查找其中的目标子串 target找到就替换成 replacement重复这个过程直到不存在 target。听起来简单但把“重复”直接拿到递归里做写出来的代码很容易陷入死循环。/* target、replacement 为全局字符串变量len 是 str 长度 */ void replaceOnce(const char *str, char *out, int pos, int *outIdx) { int len strlen(str); int targetLen strlen(target); int replLen strlen(replacement); if (pos len) { out[*outIdx] \0; return; } if (strncmp(str pos, target, targetLen) 0) { memcpy(out *outIdx, replacement, replLen); *outIdx replLen; replaceOnce(str, out, pos targetLen, outIdx); } else { out[(*outIdx)] str[pos]; replaceOnce(str, out, pos 1, outIdx); } }这段代码只递归一次替换过程把 target 替换成 replacement 后从替换内容之后的位置继续往后扫描。注意每一次递归要么前进 targetLen 位要么前进 1 位递归深度等于字符串长度栈不会爆。真正的坑是“替换结果又被替换”的场景比如把“a”换成“aa”那 out 的增长是指数级的缓冲区很快越界。课设要求里如果写了“反复替换直到不存在 target”你得明确说明这种行为不做或有次数上限否则验收时输入一个这种用例直接翻车。3.2 跳马问题方向数组、回溯与 Warnsdorff 剪枝跳马问题在棋盘上模拟国际象棋“马”的走法每次沿日字跳横坐标变化 2 纵坐标变化 1或反过来要求在 N×M 棋盘上从起点出发经过每个格子恰好一次。这就是经典的骑士巡游问题裸深搜在 5×5 以上基本跑不完所以我一般会先教大家写方向数组再教剪枝。#define N 8 #define M 8 int board[N][M]; int found 0; /* 全局标志找到解后置 1 */ const int dx[8] {2, 1, -1, -2, -2, -1, 1, 2}; const int dy[8] {1, 2, 2, 1, -1, -2, -2, -1}; void knightTour(int x, int y, int step) { if (step N * M) { found 1; return; } for (int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx N || ny 0 || ny M) { continue; /* 越界剪枝 */ } if (board[nx][ny] ! 0) { continue; /* 已访问剪枝 */ } board[nx][ny] step 1; knightTour(nx, ny, step 1); if (found) return; /* 找到解直接跳出不要再探索其他分支 */ board[nx][ny] 0; /* 回溯恢复棋盘状态 */ } }回溯的核心理念就一句话先尝试一步递归下去不行再退回来把这一步的影响抹掉。这里最容易忘的是 board[nx][ny] 0 这行漏掉它之前的试探路径永远留在棋盘上后面的搜索会被误导成无解。方向数组的顺序也有一点讲究按 dx 从大到小排列让马优先往远处跳对 8 格内的棋盘会更快命中解你要是想再稳一点可以按 Warnsdorff 规则对 8 个方向排序优先走下一步可用格数最少的位置。我做一个最简的 Warnsdorff 实现每次递归前先计算每个候选位置的下一步分支数再把分支数小的排前面。int degree(int x, int y) { int cnt 0; for (int k 0; k 8; k) { int nx x dx[k], ny y dy[k]; if (nx 0 nx N ny 0 ny M board[nx][ny] 0) { cnt; } } return cnt; } void knightTourW(int x, int y, int step) { int order[8] {0, 1, 2, 3, 4, 5, 6, 7}; /* 冒泡排序degree 小的方向优先尝试 */ for (int i 0; i 8; i) { for (int j i 1; j 8; j) { if (degree(x dx[order[j]], y dy[order[j]]) degree(x dx[order[i]], y dy[order[i]])) { int t order[i]; order[i] order[j]; order[j] t; } } } for (int i 0; i 8; i) { /* 后续逻辑与裸 DFS 一致按 order 顺序尝试候选位置 */ } }注意 degree 函数里也要做越界和已访问判断这个判断条件跟主 DFS 里一样否则排序时把非法位置排进候选后面还是得逐个判断。Warnsdorff 不是教科书里必讲的但课设报告里写一句“使用 Warnsdorff 启发式剪枝搜索节点数下降约 90%”老师会觉得你做的是有思考的工程而不是背模板。这里的 order 数组排序时degree 计算是 O(8) 的8 次也就是常量级真正贵的是后面递归。实际跑 6×6 棋盘裸 DFS 可能要十几秒加了 Warnsdorff 基本是毫秒级就能出解。不过它不保证一定有解路径所以代码里仍然保留 found 标志做兜底找不到就让程序明确输出“无解”不要在终端里空转。3.3 递归转非递归的边界什么时候必须自己维护栈课设有的老师会加一道要求把跳马的递归改成非递归用显式栈模拟。这个改动不是为了炫技而是让你理解递归调用栈和手工栈其实是同一回事。常见做法是准备一个数组当栈每个栈元素保存 {x, y, step, nextDir}入栈代表进入一层的状态出栈代表回溯恢复状态。手工栈的好处是不受系统栈深度限制棋盘再大也能跑代价是代码复杂度明显上升。如果课设没强制要求我不建议主动把跳马改成非递归递归版配合 Warnsdorff 已经足够演示知识点但要是验收老师问“递归会不会爆栈”你得能答上来系统栈深度默认在 MB 级8×8 的深搜递归深度最多 64 层完全不会爆。4. 长整数运算问题用“万进制”数组解决加减乘除的存储与进位长整数运算也叫大整数运算解决的是 C 语言里 int、long long 都装不下的超大数运算。课设常见要求是实现两个几百位整数的加减乘除和取模输出。存储结构选链表还是数组决定了这个模块的工作量和调试难度。4.1 存储结构为什么用 BASE10000 而不是 10我先说结论顺序数组加 BASE10000也就是“万进制”是我做课设时最顺手的一套方案。进制每位取值范围数组长度10000位十进制数进位次数显示处理十进制0~9约10000个元素多无需补零千进制0~999约3334个元素较少中间位按%03d输出万进制0~9999约2500个元素更少中间位按%04d输出选万进制的原因很实际数组里每一个元素能存 0 到 9999正好填满 int 的一个安全区间乘法时两个 9999 相乘约等于 10⁸还在 int 范围内。要是选十万进制两个十万相乘等于 10¹⁰超过 int 上限进位处理必须用 long long代码里到处是强制转换容易看漏。万进制下进位最多 1加法逻辑干净很多。数据放在数组里从低位到高位顺序存储data[0] 是最低位每一位的值用 0~9999 表示len 记录数组有效长度。4.2 加法和乘法的核心实现定义一个结构体封装符号、位长和 digits 数组运算函数统一返回结果。#define MAX_DIGITS 1000 #define BASE 10000 typedef struct { int sign; /* 0 表示正数1 表示负数 */ int len; /* 有效元素个数即万进制位数 */ int d[MAX_DIGITS * 2]; /* 低位在前d[0] 是个位数组给乘法结果留足空间 */ } BigInt; void addBigInt(const BigInt *a, const BigInt *b, BigInt *c) { int carry 0; int i; int maxLen (a-len b-len) ? a-len : b-len; for (i 0; i maxLen; i) { int ai (i a-len) ? a-d[i] : 0; int bi (i b-len) ? b-d[i] : 0; int sum ai bi carry; c-d[i] sum % BASE; carry sum / BASE; } if (carry 0) { c-d[i] carry; } else { i maxLen; } c-len i; }逻辑说明低位对齐直接逐位相加缺位补零这样不用单独处理两个数长度不同的情况。c 的每一位是 sum 对 BASE 取余carry 是整除结果。万进制下 ai、bi 最大 9999两个加一起加进位最多 19999carry 只会是 0 或 1所以进位判断写成 if (carry 0) 就行。这个函数里没有处理符号实际使用时可以先比较绝对值大小再决定调用加法还是减法符号单独设置。乘法稍微麻烦一点得两层循环处理每位相乘结果的偏移void mulBigInt(const BigInt *a, const BigInt *b, BigInt *c) { int i, j; long long tmp[MAX_DIGITS * 2] {0}; /* 用 long long 累积防止中间结果溢出 */ for (i 0; i a-len; i) { for (j 0; j b-len; j) { tmp[i j] (long long)a-d[i] * b-d[j]; } } int carry 0; int total a-len b-len; for (i 0; i total; i) { tmp[i] carry; c-d[i] tmp[i] % BASE; carry (int)(tmp[i] / BASE); } while (carry 0) { c-d[i] carry % BASE; carry / BASE; i; } c-len i; while (c-len 1 c-d[c-len - 1] 0) { c-len--; /* 去掉最高位的多余 0 */ } }乘法的核心是 tmp[i j] 的偏移a 的第 i 位和 b 的第 j 位相乘结果落在第 ij 位上这是手算竖式的数组版。我特意把 tmp 声明成 long long因为 9999×9999≈10⁸两层循环叠加累计多次后一个位置可能累积到 10¹² 量级int 根本装不下。这是第 5 章要重点讲的翻车点int 乘法结果先溢出再赋值给 long long等于白转型。进位和加法稍有不同乘法每轮 carry 可能大于 1所以要用 while 循环处理 carry 一直除到 0。最后的去前导零循环必须保留否则输出会变成“00123”这种怪样子。4.3 输出格式与符号处理的三个细节大整数输出有三个高频翻车细节符号、前导零、中间位补零。符号必须在打印数字前先打印否则两个正数相乘变成负数谁也看不懂前导零要 remove 掉不然计算结果长度永远不对中间位要用 %04d 格式化输出让每一万进制位占满 4 位比如 10000 进制的实际数值 10001在数组里是 d[0]1, d[1]1输出时先打印最高位 d[1]再对低位枚举打印 %04d。void printBigInt(const BigInt *n) { if (n-sign) { printf(-); } printf(%d, n-d[n-len - 1]); /* 最高位不补零 */ for (int i n-len - 2; i 0; i--) { printf(%04d, n-d[i]); /* 其余位必须补零到 4 位 */ } printf(\n); }这个函数在所有运算模块都要复用建议把它放在单独的一个文件里头文件里声明好课设报告里也可以直接引用。减法、除法我建议在搞懂加法和乘法之后再写减法要先比较绝对值大小用大减小再决定符号除法最推荐做“逐位试商”也就是从高位到低位模拟长除法性能较差但逻辑直观适合演示。如果课设只要求加减乘除的其中两个尽量选加法、乘法它们最容易在验收时讲清楚。5. 数据结构课设验收避坑哈夫曼乱码、跳马死循环、长整数溢出的排查记录四个模块分别写完不等于课设能过验收。下面这五条是我实际做课设辅导时遇到频率最高的问题每一条都按现象、原因、解决的顺序写清楚读者可以直接对照排查。5.1 哈夫曼译码全是乱码现象用编码表把原文转成 01 串再把 01 串喂给译码函数输出的字符和原文完全对不上而且长度都对不上。原因编码表生成时方向写反了。从叶子逆向走到根存下来的是从叶子到根的路径必须先反转才是真正的编码很多同学直接把 tmp 数组正序拷贝进 codeTable导致每个编码都是反向的。另一个常见原因是叶子节点 data 字段没填译码时输出的是节点的下标数字而不是字符。解决用第 2 章给的 codeTable 写法tmp 数组从尾部往前填最后复制 tmp[idx1]同时在译码时输出 nodes[cur].data 而不是 cur。5.2 跳马程序跑很久不结束现象跳马程序在 5×5 或 8×8 棋盘上运行几十秒甚至几分钟没结果看起来像死循环。原因裸回溯在状态空间很大的情况下分支爆炸8×8 骑士巡游的搜索空间是超指数级别没有任何启发式的话找一条完整路径可能要遍历上亿个状态。另一个隐性原因是方向数组里的越界判断写成了 nx N等于把最后一行的格子全判成越界导致搜索永远填不满棋盘。解决先用小棋盘5×5验证 DFS 本身正确再换大棋盘时加 Warnsdorff 剪枝。方向判断统一写成 nx 0 || nx N || ny 0 || ny M别漏边界。5.3 长整数乘法结果突然变成负数现象两个正数相乘结果输出成了一个负数或者明显溢出成奇怪的值。原因乘法临时数组用了 int 而不是 long long。万进制下单个乘法 9999×9999≈10⁸int 还在承受范围内但累积到 tmp[ij] 的时候多个乘积叠加很容易超过 2³¹-1此时再做赋值和取余全部出错。解决把临时累积数组声明成 long long乘法里每一项也先转 long long 再相乘输出前再取模回到 int。这个问题的另一个信号是调试时 printf 打印 tmp[i] 出现负数说明溢出已经发生。5.4 递归替换缓冲区越界崩溃现象递归替换程序在输入某个特定字符串时崩溃报错指向 memcpy 或 out 数组越界。原因替换结果里又包含了目标串比如把“a”换“aa”字符串长度指数增长而 out 缓冲区长度是固定的写到最后就越界了。另一个隐蔽原因是 replacement 比 target 长很多单次替换就会把 out 写超。解决在 replaceOnce 里每次写入前判断 outIdx 替换长度是否超过缓冲区上限超过就报错终止。课设答辩时主动说明“做了替换次数上限超过 1000 次强制终止”比等着被测试用例打脸强。5.5 验收演示只准备一个用例现象验收现场老师让你输入第二个测试用例程序直接出错或者结果不对只能尴尬地被问住。原因平时没有做交叉测试代码只对“写代码时心里想的那个输入”成立。比如哈夫曼只测了全字母文本没测空串、单字符、所有字符同频率的边界长整数只测了正数相加没测结果为零、最高位进位、符号组合。解决每个模块准备 3 类测试用例正常用例、极端用例最小输入、最大长度、相同权值、非法用例空串、越界输入、负数组合。把这些用例连同预期结果写进课程设计报告就构成了“测试报告”这一节老师看到这个会很快认可你做的工程完整度。6. 把四个模块组装成完整课设工程自动化验证与三个进阶改进模块单独跑通以后我做课设的最后一步是把四个题放进同一个主菜单程序里输入数字 1/2/3/4 分别进入四个系统退出之后可以继续换下一个。这个交互层没什么技术含量但一个统一风格的菜单比四个孤零零的控制台程序看起来完成度高得多。验证上我会写一个批处理脚本预先把测试输入放在 txt 里用重定向批量跑程序输出文件再和期望结果做 diff。哈夫曼的验证方式最简单也最有效写一个小工具把编码结果再交给译码函数还原还原后的字符串必须和原文逐字节相同这就是“往返测试”。跳马的验证是检查输出的路径数组里有没有重复格子、有没有越界可以写个 20 行的校验函数遍历一遍路径就够。长整数可以用 Python 算一遍同样的表达式当基准把 C 程序的输出和 Python 的结果做 diff我当年就这么干批量生成 50 组随机大数对拍比人工验算靠谱得多。三个值得做的进阶改进按性价比排序第一个把哈夫曼从“字符级编码”升级到“任意文件字节级压缩”。做法是把文件读成字节流统计 256 种字节的出现次数再建树这样任何文件都能压缩课设报告的含金量立刻上一个档次。注意输出压缩文件时要保存字节频率表否则解压端没法重建同一棵哈夫曼树。第二个给跳马加一个可视化输出。不追求图形界面但至少把棋盘路径用二维表格打印出来数字从 1 到 N×M验收时一眼能看到“马按顺序走完了所有格子”。视觉效果对课设分数的影响比想象中大老师看三秒钟生成的路径表比看十行递归代码直观。第三个长整数模块支持 10 进制字符串输入和万进制内部存储的自动转换。把输入解析成 BigInt 需要处理前导零、空串、正负号这部分代码短但边界情况多写进报告里可以作为“输入合法性校验”的体现。我自己做课设时吃过最大的亏就是调通之后不验证边界就急着打包。后来养成的习惯是每天提交一次代码每次提交前必跑一遍已准备好的测试用例这个习惯让我在验收前没再翻过车。希望这四个模块的拆分思路和排查记录对你有帮助照着这套结构做数据结构课设没你想的那么难熬。本文还有配套的精品资源点击获取