简介围绕哈夫曼编译码器展开的数据结构课程设计报告面向正在完成课设、需要参考完整实现思路的计算机相关专业学生开发环境为VC 6.0。文档从需求分析、总体设计到详细设计逐层展开覆盖初始化、编码、译码、打印代码文件、打印哈夫曼树和退出程序六个功能模块并给出系统框图、总流程图、函数列表及main、Init、Encoding、Decoding、CodePrint等主要函数的说明便于对照理解哈夫曼树的构建、字符频率统计、二进制编码生成与文本还原过程。压缩包共1个doc文件大小约2.76MB适合直接查阅排版完整的报告正文与目录结构。目前已有811人学习可作为课程设计选题、实验报告撰写和C数据结构练习的参考样本帮助读者梳理从频率统计、优先队列合并节点到编码存储与解码输出的完整链路。1. 哈夫曼编译码器一份课设报告里真正能跑起来的那套骨架拆过不少数据结构课设的压缩包绝大多数翻到第三页就开始贴流程图截图函数实现全靠附录一页半的源码撑着。这份哈夫曼编译码器的报告不一样的地方在于它把链式节点、数组编码表、五个磁盘文件、六键菜单这四件事捏成了一个能自洽运行的闭环而不是把 Huffman 算法的教科书推导抄一遍就交差。它要解决的真问题很具体给定 n 个字符和频度建树、出码表、把一段文本压成 01 串、再从 01 串原样还原全程状态可落盘、可重启。适合三类人——正在做哈夫曼题课设需要一份能对照调试的骨架的、想把变长编码从公式推到可执行代码的、以及带学生做课设需要一份哪一步最容易崩清单的。下面按存储结构、功能实现、文件链路、踩坑、验证五段往下走。2. 五域节点配数组表哈夫曼树的存储结构怎么选才不返工2.1 ch/weight/parent/lchild/rchild 这五个域各管什么报告里明确写了用链式存储构造哈夫曼树每个节点五个域ch 存字符、weight 存权值频度、parent 存双亲、lchild 和 rchild 存左右孩子而编码表、字符集这些辅助数据走顺序存储理由是方便查找。这个混搭不是随便定的。哈夫曼树是一棵严格二叉树n 个叶子节点必然对应 2n-1 个总节点建树过程中要反复找两个权值最小且还没挂双亲的节点这个动作需要随机访问任意下标用真正的 malloc 指针反而难在调试器里整片展开看。我一般写成下标式的静态链表0 号单元空着当空指针哨兵这样 parent 为 0 就等价于 NULL判断起来干净#define MAXLEAF 64 /* 字符集上限按实际 n 调 */ #define MAXNODE (2*MAXLEAF) /* 哈夫曼树最多 2n-1 个节点 */ typedef struct { char ch; /* 叶子字符非叶节点填 # 占位 */ int weight; /* 权值即该字符出现频度 */ int parent; /* 双亲下标0 表示尚未挂接 */ int lchild; /* 左孩子下标0 表示无 */ int rchild; /* 右孩子下标0 表示无 */ } HTNode; typedef HTNode HuffmanTree[MAXNODE]; /* 下标从 1 开始使用 */ typedef char *HuffmanCode[MAXLEAF]; /* HC[i] 指向第 i 个字符的 01 串 */用下标代替指针有三个实打实的好处。第一VC 6.0 的 watch 窗口能直接把整个 HuffmanTree 数组展开成一行行数字建树到第几步、哪个节点的 parent 还没填肉眼一眼看完不用顺着指针爬。第二HT[f].lchild c这种判断只比较两个 int不会出现野指针访问。第三落盘特别省事——把整个数组按下标 ch weight parent lchild rchild六列 fprintf 出去就是一张完整的树表下次读回来直接 fscanf 还原不需要任何序列化逻辑。参数上要注意 MAXLEAF 的取值。字符集大小 n 由用户在 Init 里输入但数组必须在编译期定长所以 MAXLEAF 要留足余量。课设场景 n 一般不超过 64取 64 或 128 都行取太小会在n MAXLEAF时静默越界写这是后面会讲的翻车点之一。2.2 Select() 一次扫描挑两个最小比较符号写错就是灾难建树的核心子过程是在 [1, end] 范围内找出两个 parent 为 0 且 weight 最小的节点。报告的函数表里把它单列为 Select()这个拆分是对的因为它是整个建树循环里唯一有分支风险的地方。最直观的写法是扫两遍但更稳的是一遍同时维护两个槽位void Select(HuffmanTree HT, int end, int *s1, int *s2) { int i; int min1 0x7fffffff, min2 0x7fffffff; *s1 *s2 0; for (i 1; i end; i) { if (HT[i].parent ! 0) continue; /* 已挂到别的双亲下跳过 */ if (HT[i].weight min1) { /* 比最小值还小 */ min2 min1; *s2 *s1; /* 原来的最小值降级为次小 */ min1 HT[i].weight; *s1 i; } else if (HT[i].weight min2) { /* 只比次小值小 */ min2 HT[i].weight; *s2 i; } } }逻辑本身很朴素min1/min2 维护当前扫过的两个最小权值s1/s2 记录它们对应的下标。关键是两次比较都必须用严格小于不能用。如果写成当树里存在两个权值完全相等的节点这在字符频度统计里极其常见比如两个字符各出现 1 次第二个等值节点会走else if分支吗不会——因为让第一个分支也成立min1 被更新成新节点旧 min1 挤到 min2但*s2 *s1那一步在下的语义就变了最终可能出现 s1 和 s2 指向同一个下标的情况。一旦 s1 s2接下来的建树代码就会把同一个节点同时挂成自己的左孩子和右孩子HT[i].lchild HT[i].rchild s1HT[s1].parent i被赋两次。后果是这棵树出现自环编码阶段从叶子回溯到根时f ! 0永远不成立程序卡死。血泪经验这个 bug 在 n 小于 8 的时候经常不自爆因为小数据下权值撞车的概率低等答辩现场老师随手输了一组等频数据直接白屏。参数说明end 是当前已使用节点的最大下标。建树第 i 步i 从 n1 到 2n-1时参与选择的节点范围是 [1, i-1]所以调用要写Select(HT, i - 1, s1, s2)。写成Select(HT, m, ...)m 为最终总数是另一个常见错误——此时数组尾部全是 0 权值的空节点会被当成最小权选出来树直接建歪。2.3 HuffmanCoding()先向上建树再向下回溯出码建树和生成编码其实是两个方向的遍历报告把它放在同一个函数里这个组织方式在 n 不大的时候是合理的。建树阶段是从叶子往上合每次取两个最小节点接到新的内部节点下面出码阶段则反过来从每个叶子往根爬边走边记 0/1void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n) { int m 2 * n - 1; int i, s1, s2, c, f, start; char *cd; /* --- 第一阶段自底向上合树 --- */ for (i 1; i m; i) { /* 初始化所有节点的双亲与孩子 */ HT[i].parent 0; HT[i].lchild HT[i].rchild 0; } for (i n 1; i m; i) { /* 第 i 个内部节点 */ Select(HT, i - 1, s1, s2); HT[s1].parent i; HT[s2].parent i; HT[i].lchild s1; HT[i].rchild s2; HT[i].weight HT[s1].weight HT[s2].weight; } /* --- 第二阶段自叶向根回溯逆序填码 --- */ cd (char *)malloc(n * sizeof(char)); /* 最长码 n-1 位 结束符 */ cd[n - 1] \0; for (i 1; i n; i) { start n - 1; for (c i, f HT[i].parent; f ! 0; c f, f HT[f].parent) cd[--start] (HT[f].lchild c) ? 0 : 1; HC[i] (char *)malloc((n - start) * sizeof(char)); strcpy(HC[i], cd[start]); } free(cd); }回溯这段的精髓在cd[--start]。因为是往上爬先拿到的是最低位所以要往数组尾部填、向前推进指针。循环结束后cd[start]到cd[n-2]就是完整编码cd[n-1]是预先放好的\0直接strcpy(HC[i], cd[start])就能拿到正序字符串。如果反过来从前往后填最后还得写一次 strrev多一个出错点。cd 数组长度取 n 而不是 2n这是有依据的n 个叶子的哈夫曼树最坏情况是退化成链每次合并都把新节点和下一个叶子合权值递增时会出现此时单条编码长度最多 n-1 位加一位结束符正好 n。参数上唯一要注意的是 n 必须等于实际输入字符数如果 Init 里读到的 n 和后面填权值的循环次数对不上建树会读到未初始化权值。2.4 编码表落盘HuffmanTree.txt 存什么、按什么顺序读报告里规定 D:\HuffmanTree.txt 同时存编译码表和哈夫曼树表这个设计让它具备了断点续跑的能力——进程退出再进来不做 Init 也能直接按 E 编码。文件格式要自己定得死板一点读写两头才不会打架我一般这么排行号内容示例第 1 行字符集大小 n8第 2 ~ n1 行字符 空格 该字符的 01 编码a 110第 n2 ~ 2n 行树表每行下标 ch weight parent lchild rchild9 # 28 0 4 5写的时候用fprintf(fp, %d\n, n)然后循环fprintf(fp, %c %s\n, HT[i].ch, HC[i])。有个坑要提前防如果用户输入的字符集里包含空格%c读回来会吞掉分隔空格导致字符错位。常见做法是 Init 阶段就拒绝空格字符或者把字符和编码之间的分隔符改成制表符\t并在读时用%c\t%s。读的时候顺序不能乱必须先读 n再按 n 决定后面循环多少次。见过不少版本的代码把 n 固定写成 26 或者 8换一组数据就崩。fscanf的返回值也要判读到 EOF 说明文件被截断上一次写的时候崩在半路这时候应该提示重新初始化而不是继续往下跑。3. 六个按键的实现骨架Init、Encoding、Decoding 逐层拆开3.1 main() 的 while 菜单和未初始化状态守卫报告 3.2.1 节把 main 描述成用 while 使调用每个功能之后都能循环回到菜单这个结构本身没问题但真正决定健壮性的是那个藏在 switch 外面的状态标志。需求里明确列了五种未先初始化就直接按 e/d/p/t的测试用例这些用例要能全部走通并给出正确提示靠的就是一个 int 型的 built 变量int main(void) { char choice; int built 0; /* 0 树还没建1 已初始化可用 */ while (1) { HCVision(); /* 打印六键菜单 */ scanf( %c, choice); /* 前导空格吃掉上次残留的回车 */ switch (choice) { case i: case I: Init(); built 1; /* 只有 Init 成功返回才置位 */ break; case e: case E: if (!built) { printf(请先执行 I 初始化!\n); break; } Encoding(); break; case d: case D: if (!built) { printf(请先执行 I 初始化!\n); break; } Decoding(); break; case p: case P: if (!built) { printf(请先执行 I 初始化和 E 编码!\n); break; } CodePrint(); break; case t: case T: if (!built) { printf(请先执行 I 初始化!\n); break; } HuffmanTreePrint(); break; case q: case Q: return 0; default: printf(输入有误自动返回菜单\n); } } }scanf( %c, choice)里那个前导空格是必须的。不加的话上一轮用户按回车产生的\n还留在输入缓冲区下一轮%c会立刻读到它表现为菜单闪一下就跳过去了。这个现象在报告 4.1.2 的测试记录里没写但只要在 VC 6.0 下实际跑一遍就会遇到。built 置位的位置也有讲究要放在 Init() 调用之后。如果 Init 内部因为文件打不开提前 return 了built 还是 1后面按 E 就会读到一张空表然后崩。更稳的做法是让 Init 返回 int成功返回 1、失败返回 0主函数里写built Init();。3.2 Encoding()逐字符查表拼串先拼完再落盘编码的输入路径在报告里是从终端读入字符串源串存 D:\ToBeTran.txt结果存 D:\Code.txt。核心动作就是两层循环外层扫输入串的每个字符内层在编码表里线性找匹配项找到就把对应的 01 串追加到输出。void Encoding(void) { FILE *fpSrc, *fpCode; char str[MAXTEXT]; char outbuf[MAXCODE]; /* 先攒在内存里 */ int i, j, pos 0, found; printf(请输入要编码的字符串: ); gets(str); /* VC 6.0 可用新编译器改 fgets(str, MAXTEXT, stdin) */ fpSrc fopen(D:\\ToBeTran.txt, w); if (fpSrc) { fprintf(fpSrc, %s, str); fclose(fpSrc); } for (i 0; str[i] ! \0; i) { found 0; for (j 1; j n; j) { if (HT[j].ch str[i]) { /* 命中 */ strcpy(outbuf pos, HC[j]); pos strlen(HC[j]); found 1; break; } } if (!found) { /* 有字符不在表里 */ printf(字符 %c 不在编码表中请重新输入\n, str[i]); return; /* 此时还没打开 Code.txt不会留半截文件 */ } } fpCode fopen(D:\\Code.txt, w); if (!fpCode) { printf(Code.txt 创建失败\n); return; } fprintf(fpCode, %s, outbuf); fclose(fpCode); printf(编码完成共 %d 位\n, pos); }这段代码里最值得说的是先拼完再打开 Code.txt 写。如果一边查表一边fputs写文件中途遇到一个表里没有的字符提前 returnCode.txt 已经被w模式截断成空文件、又只写了半截编码后面按 D 译码就会读到一段残缺的 01 串输出一堆乱码。这个坑报告正文没提但它是 4.1.2 里未初始化输入 e那组测试之外的第二种失败路径。参数上MAXTEXT 是明文长度上限、MAXCODE 是编码后长度上限后者要显著大于前者因为最坏情况下每个字符编出 n-1 位。粗略取 MAXCODE MAXTEXT * 8 比较安全。另外内层线性查找的复杂度是 O(n)n 小的时候完全够用如果字符集扩到 200 以上可以开一个 128 项的int idx[128]映射表Init 时把idx[字符] 下标一次填好编码时 O(1) 定位。3.3 Decoding()按各码长度截取子串靠前缀性质保证唯一解译码是整份课设里最容易被老师追问的一环。报告 3.2.4 的描述是把 h 数组按照编译码表中每个字符的编码长度取每个字符编码采用顺序表查找比较若相同就输出。翻成代码就是从当前位置 pos 出发遍历编码表里每个字符取其编码长度 L截buf[pos, posL)出来比对相同就输出该字符、pos 前进 L继续下一轮void Decoding(void) { FILE *fpIn, *fpOut; char buf[MAXCODE]; int pos, i, L, clen, ok; fpIn fopen(D:\\Code.txt, r); if (!fpIn) { printf(Code.txt 打开失败请先执行 E 编码\n); return; } if (fscanf(fpIn, %s, buf) ! 1) { fclose(fpIn); printf(Code.txt 为空\n); return; } fclose(fpIn); fpOut fopen(D:\\Decode.txt, w); if (!fpOut) { printf(Decode.txt 创建失败\n); return; } L (int)strlen(buf); pos 0; while (pos L) { ok 0; for (i 1; i n; i) { if (HC[i] NULL || HC[i][0] \0) continue; /* 空码跳过 */ clen (int)strlen(HC[i]); if (pos clen L) continue; /* 越界保护 */ if (strncmp(buf pos, HC[i], clen) 0) { fputc(HT[i].ch, fpOut); pos clen; ok 1; break; } } if (!ok) { printf(编码串在偏移 %d 处无法匹配请检查 Code.txt\n, pos); break; } } fclose(fpOut); }为什么第一个匹配上的就是唯一解因为哈夫曼编码天然满足前缀性质任何一条码都不是另一条码的前缀。这个性质来自建树过程——所有字符都在叶子上从根到叶的路径不可能被另一条根到叶的路径走过一半。所以遍历顺序不影响结果即使最长的码排在前面、最短的排在后面也不可能出现短码误配到长码前缀上的情况。这一点答辩时大概率会被问到你怎么保证不匹配错答前缀码三个字就够但最好能把为什么叶子节点保证前缀码一起说清楚。pos clen L这个越界检查非常关键。没有它当 Code.txt 末尾被人为截断或者上一次编码崩在半路strncmp会拿 buf 后面的随机内存去比运气好返回非零、运气差读越界内存直接崩。HC[i][0] \0的跳过则是防 Init 只填了一部分编码表就落盘的情况。3.4 CodePrint() 与 HuffmanTreePrint()50 字符换行和表格对齐打印编码的要求是每行 50 个代码同时写入 D:\CodePrint.txt看起来简单边界在最后一行。如果总长度正好是 50 的整数倍循环结束时会多打一个空行需要if (cnt % 50)补一次判断void CodePrint(void) { FILE *fi, *fo; char a[MAXCODE]; int i, cnt 0; fi fopen(D:\\Code.txt, r); if (!fi) { printf(请先执行 E 编码\n); return; } if (fscanf(fi, %s, a) ! 1) { fclose(fi); printf(Code.txt 为空\n); return; } fclose(fi); fo fopen(D:\\CodePrint.txt, w); if (!fo) { printf(CodePrint.txt 创建失败\n); return; } for (i 0; a[i] ! \0; i) { putchar(a[i]); fputc(a[i], fo); /* 终端和文件同步写 */ if (cnt % 50 0) { putchar(\n); fputc(\n, fo); } } if (cnt % 50 ! 0) { putchar(\n); fputc(\n, fo); } /* 补齐末行 */ fclose(fo); printf(共输出 %d 位编码\n, cnt); }putchar和fputc双写是报告里同时显示在终端和写入文件的直接实现。更好的做法是先拼到内存 buffer最后一次性 fputs 到两边避免终端重定向时两路输出不同步。HuffmanTreePrint 则是典型的表格打印用固定宽度格式串对齐void HuffmanTreePrint(void) { FILE *fo fopen(D:\\HuffmanTree.txt, a); /* 追加别覆盖前面的码表 */ int i; printf(%-6s%-6s%-8s%-8s%-8s\n, 下标, 字符, 权值, 双亲, 左右孩子); if (fo) fprintf(fo, %-6s%-6s%-8s%-8s%-8s\n, 下标, 字符, 权值, 双亲, 左右孩子); for (i 1; i 2 * n - 1; i) { printf(%-6d%-6c%-8d%-8d%-3d%-3d\n, i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild); if (fo) fprintf(fo, %-6d%-6c%-8d%-8d%-3d%-3d\n, i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild); } if (fo) fclose(fo); }注意这里用a而不是w。报告里 Init 和 T 都往 HuffmanTree.txt 写如果用w按完 T 之后原来的编码表会被整片覆盖掉再按 E 就读不到表了。这个细节报告正文没强调但它是 T 功能顺手就把文件毁了的直接原因。4. 五个 txt 的读写链路把内存状态托管给磁盘的代价4.1 文件清单与依赖关系谁先谁后不能乱报告 3.1.2 用一张表列了五个文件的地址和内容这张表其实就是整个程序的状态机。按写入先后串起来看依赖链非常清晰文件写入者读取者内容前置依赖D:\HuffmanTree.txtInit、TInit 恢复、E、D编码表 树表无最先生成D:\ToBeTran.txtE人工比对原始明文依赖编码表D:\Code.txtED、P01 编码串依赖 ToBeTran 处理完成D:\Decode.txtD人工比对还原后的明文依赖 Code.txtD:\CodePrint.txtP人工查看每行 50 位的格式化串依赖 Code.txt这条链意味着 I 是绝对的前置E 是 D 和 P 的前置。报告 4.1.2 里那五组未初始化直接按某键的测试本质就是在验证每一次操作前的依赖检查是否到位。实际写的时候我习惯把这条链画在纸上贴在屏幕边上每加一个功能就对照一遍我这个函数读了哪个文件、那个文件由谁保证存在。4.2 读写模式与 VC 6.0 下的三个路径陷阱fopen的第二个参数决定成败。写文件统一用w表示清空重写这符合 E 每次重新编码、P 每次重新打印的预期但 HuffmanTreePrint 必须用a理由第 3.4 节已经说过。读文件统一用r读之前必须判空。第一个陷阱是 D 盘根目录。课设机器上 D:\ 一般存在但如果把程序拷到只有 C 盘的机器上fopen(D:\\HuffmanTree.txt, w)直接返回 NULL后面fprintf(NULL, ...)立刻崩现象是程序刚进来按个 i 就闪退没有任何提示。稳妥的做法是每个 fopen 后面跟一句if (!fp) { printf(xxx 打开失败\n); return; }或者干脆把路径改成相对路径HuffmanTree.txt跟可执行文件放同一个目录换机器也不用改代码。第二个陷阱是中文路径。VC 6.0 默认多字节字符集fopen走的是窄字符接口路径里一旦出现中文在非中文区域设置的系统上会打开失败或创建出奇怪名字的文件。课设交付时把源码放在纯英文目录下能省掉一类莫名其妙的报错。第三个陷阱是w模式的截断时机。fopen(path, w)一调用就会立刻把文件清空即使后面一个字节都没写。所以凡是可能中途失败的写入流程都应该先把结果算在内存里确认全部成功后再 open→write→close。第 3.2 节 Encoding 里那个 outbuf 就是这个思路的落地。4.3 用文件代替内存的收益与代价把状态全部落盘好处很实在进程关掉重开Init 不用再做一遍按 E 直接就能编演示的时候可以当场退出再进证明数据真的持久化了调试时可以直接用记事本打开 HuffmanTree.txt 看码表对不对比在调试器里翻结构体快得多。代价是代码复杂度和错误面都上去了。每次 E 和 D 都要重新fopen、fscanf、解析格式文件格式一改就得同步改读写两头漏一处就是格式错位。更麻烦的是文件状态和内存状态可能不一致Init 建好树写进文件用户在菜单里又按了一次 I 输入了不同的字符集内存里的 n 变了文件也重写了但这时候如果 Code.txt 还是按旧树编的D 阶段就会拿新树去解旧串解出一堆乱码。我的处理办法是 Init 里顺手把 Code.txt 清零fopen(..., w)后立即 fclose让状态强制回到只有树、没有编码。另一个常被忽略的是文件句柄泄漏。每个fopen都必须配一个fclose包括那些提前return的错误分支。VC 6.0 下句柄上限不高连着按十几次 E 而每次都走错误分支就可能出现明明文件存在却打不开的怪现象。5. 避坑与排查答辩前最容易翻车的六处细节5.1 环境与文件层的三个坑现象一程序双击运行黑窗口一闪就没了。原因通常是fopen返回 NULL 后没做检查紧接着fprintf(NULL, ...)触发访问违例。也可能是 D:\ 根目录不存在或没有写权限。解决办法是把所有fopen后面统一加判空并打印具体是哪个文件失败同时把绝对路径 D:\xxx.txt 改成相对路径xxx.txt程序放到哪都能跑。验证方式很简单把程序拷到 U 盘里换台机器跑一遍如果还能正常初始化说明路径处理是干净的。现象二HuffmanTree.txt 用记事本打开是一堆看不懂的方块和乱码。原因是用了fwrite(HT, sizeof(HTNode), ...)直接写结构体二进制。结构体里有 char 有 int还有内存对齐填充字节写出来人眼不可读换编译器就废。解决办法是全程fprintf/fscanf文本格式按第 2.4 节那张表六列输出。文本格式的额外好处是老师翻你文件的时候能直接看到码表答辩印象分直接上来。现象三第二次按 E 之后 Code.txt 变成空文件。两种情况。一种是编码循环里遇到表中没有的字符提前 return 了而 Code.txt 已经被w截断。另一种是用户第一次按 E 输入了一串第二次按 E 直接按回车空串代码照样fopen(w)然后写入空串。解决办法是空串直接拒绝if (str[0] \0) { printf(输入不能为空\n); return; }有非法字符的情况按 3.2 节的先算后写处理。5.2 算法与逻辑层的三个坑现象四建树过程卡死不返回或者生成的编码表里出现空串。根因几乎必然是 Select 选出了同一个下标两次导致节点自己挂自己形成环。触发条件是两个待选节点权值相等且比较用了。排查方法是在 Select 返回后加一句if (*s1 *s2) printf(Select 冲突end%d\n, end);跑一组所有权值都设为 1 的数据一按 I 就能立刻复现。改法是把两次比较都改成严格小于并且在*s1 *s2 0初始化后加一句如果扫描完 s2 还是 0说明可用节点不足 2 个的防御。现象五译码输出比原文多几个字符或者末尾蹦出奇怪的符号。先看pos clen L这个越界检查有没有写。没写的话当 buf 末尾剩余的位数不够一条完整编码的长度时strncmp会拿\0之后的随机内存去比碰巧匹配上就多输出一个字符。再看编码表里有没有空串HC[i][0] \0空串的strlen是 0pos 0会让 while 循环完全不前进表现为死循环。最后确认 Code.txt 是不是被手动改过——有人为了测试一下往里面插了个空格fscanf(%s)读到空格就停剩下半截被丢掉译出来自然短一截。现象六菜单按一次键跳两级或者按键完全没反应。这是输入缓冲区的经典问题。scanf(%c, choice)不带前导空格时上一轮用户敲的回车\n会被下一轮直接吃掉switch 走到 default 分支打印输入有误然后重新显示菜单看起来就像跳了一下。改法就是第 3.1 节写的scanf( %c, choice)那个空格让 scanf 跳过所有前导空白字符。如果菜单里还混用了gets更要注意 gets 会把上一轮的换行当成一次空输入最好在 gets 之前统一用一次getchar()清缓冲或者干脆全部换成fgets 手动去换行符。6. 用平均码长反推树对不对三个自检动作跑通六个功能只是及格线真正决定这份课设能不能拿高分的是你能不能证明自己建的树是最优的。哈夫曼树的价值在于平均码长逼近信息熵这个性质可以直接拿来自检不用另外写测试用例。第一个动作是算平均码长。公式是Σ(weight_i × len_i) / Σ weight_i理论上这个值必须落在[H, H1)区间内H 是信源熵-Σ p_i × log2(p_i)。举个手算的例子四个字符权值分别 1、1、2、4总权值 8概率是 0.125、0.125、0.25、0.5熵 H ≈ 1.75 比特。如果你的树建对了码长应该是 3、3、2、1平均码长 (1×3 1×3 2×2 4×1) / 8 14/8 1.75正好等于熵——这说明频度刚好是 2 的幂次分布。换一组 1、1、1、1、2、2 的数据熵会略低于平均码长差距在 1 以内都算正常。如果算出来超过 H1基本可以断定 Select 选错了节点。第二个动作是检前缀性质。编码表里任意两条码不能有一条是另一条的前缀。这个检查写起来就十来行塞在 Init 末尾最合适/* 自检编码表前缀性质 平均码长Init 结束后调用 */ double SelfCheck(HuffmanTree HT, HuffmanCode HC, int n) { int i, j, conflict 0; double sum 0.0, wsum 0.0; for (i 1; i n; i) { for (j 1; j n; j) { if (i j) continue; /* 若 HC[i] 是 HC[j] 的前缀说明树结构有问题 */ if (strncmp(HC[i], HC[j], strlen(HC[i])) 0) { printf(前缀冲突: [%s] 是 [%s] 的前缀\n, HC[i], HC[j]); conflict 1; } } sum HT[i].weight * strlen(HC[i]); wsum HT[i].weight; } if (conflict) printf(警告编码表不满足前缀码性质\n); return (wsum 0) ? sum / wsum : 0.0; }参数说明HT 和 HC 就是建好的树与码表n 是叶子数。返回值是平均码长直接 print 出来跟手算的熵比一下。这段代码的复杂度是 O(n²×码长)n64 时毫秒级完全不影响体验但能在答辩现场当场自证我的树是对的。第三个动作是往返一致性。按 I → E → D 走一遍然后用记事本同时打开 ToBeTran.txt 和 Decode.txt 对比或者命令行fc D:\ToBeTran.txt D:\Decode.txt。注意 E 阶段用 gets 读入的明文如果末尾有空格写入时会被保留但 D 阶段逐字符 fputc 输出时也可能保留两边应该完全一致。如果不一致优先查 Encoding 里是不是漏了某个字符的映射其次查 Decoding 的 pos 有没有多加或少加。我第一次交这份课设的时候就吃过亏Select 里写的是测试数据全是精心挑的、权值各不相同的字符跑得漂亮得很交上去老师随手输了六个权值全是 1 的字符程序直接卡死。从那以后我每次交课设前都强制走一遍三件事——先用等权数据按一遍 I 看会不会卡再跑一遍前缀自检看有没有冲突最后 fc 比对往返文件。这三步加起来不到五分钟比答辩现场被问住强太多。希望帮到你。本文还有配套的精品资源点击获取
