简介这是一份沈阳航空航天大学计算机学院的数据结构课程设计报告题目为实现哈夫曼编码和译码器。报告面向计算机科学与技术专业学生也适合需要完成同类课程设计、或想理解数据压缩编码原理的读者参考。内容依次覆盖题目分析、系统功能需求、程序模块结构、数据结构说明、函数接口设计与算法描述重点讲解了字符频率统计、哈夫曼树构建、字符-哈夫曼编码对照表生成以及编码与译码的完整实现流程。文中还给出程序测试结果与附录代码便于按步骤复现。资源为1个PDF文档大小619KB目录清晰总篇幅适中可快速通读整份设计思路。目前已有280人学习下载无论是用于答辩准备、课程实验报告参考还是复习哈夫曼编码算法都能从中获取可落地的设计方法和代码实现细节。1. 哈夫曼编码译码器一份能跑通完整编解码闭环的数据结构课程设计哈夫曼编码是数据结构课程设计里最能把二叉树、链表和文件操作串起来的题目也是少有的做完能直接看到压缩效果的综合实验。这份沈阳航空航天大学的课程设计报告实现的是一个完整的哈夫曼编码译码器读入字符集和出现频率构造哈夫曼树生成字符到编码的对照表然后分别对明文字符串编码、对二进制密文译码。整套代码用 C 语言写成按功能拆成用户输入获取、哈夫曼树构造、对照表构造、编码、译码五个模块测试用例是 a、b、c 三个字符加对应频率流程完整。适合正在写数据结构实验报告、准备考研数据结构机试或者想弄懂树和链表怎么配合使用的读者。我会把报告里的结构体设计、建树算法和编解码逻辑拆开讲一遍再把实际跑代码时踩过的坑列出来。2. 数据结构选型三个结构体与双向链表为什么多数人在这里翻车这份报告里数据结构的组织方式值得先看清楚。它用了二叉树和链表两种结构三个核心结构体分别对应程序运行中三个不同阶段的数据哈夫曼树结点、建树时的待选字符容器、编码完成后的对照表。理解了这三个结构体后面所有函数都只是在它们之间搬运数据。2.1 三个结构体结点、容器、编码表的职责划分typedef struct _NODE { char word; // 字符内部结点用 -1 标记 int value; // 字符出现频率权值 _NODE *left, *right; // 左右孩子 } Node, *LPNode; typedef struct _CONTAINER { LPNode v; // 指向哈夫曼树结点 struct _CONTAINER *last, *next; // 双向链表前驱和后继 } Container, *LPContainer; typedef struct _CODENODE { char word; // 字符 char code[100]; // 编码字符串如 00 struct _CODENODE *next; // 单链表后继 } CodeNode, *LPCodeNode;三个结构体对应三个生命周期。Node 是哈夫曼树的骨架叶子结点里 word 是真实字符内部结点由两个子树合并产生word 统一置成 -1用这个值区分「叶子」和「内部结点」。Container 是一个套壳结构里面只存一个指向 Node 的指针不直接嵌 Node 本身这种做法的好处是链表结点的增删完全不影响哈夫曼树结点的存在合并子树时可以自由释放 Container 而不误删 tree 节点。CodeNode 是最后生成字符-哈夫曼编码对照表时用的单链表结点code 是字符串形式的 0/1 序列不是真正的二进制位。参数细节上有几个点要注意。word 用的是 char 类型内部结点填 -1正常 ASCII 字符不会和 -1 冲突所以这个标记是安全的。value 是 int合并时两个子树 value 直接相加理论上根节点的 value 等于所有字符频率之和。code 数组固定 100 字节字符集规模小的时候够用但如果输入几百个不同字符编码长度可能超过 100这是后面要防的一个坑。_CONTAINER 的 last 和 next 构成双向链表配合哨兵结点实现有序插入_CODENODE 的 next 是单链表插入时走头插法所以最终打印对照表时看到的顺序跟遍历顺序相反。2.2 为什么用双向链表而不是最小堆构建哈夫曼树的核心操作是反复取最小和第二小的子树这本是最小堆的标准应用场景。这份报告没有用堆而是用双向链表按权值升序维护所有待选结点每次取链表头两个结点就是当前最小和第二小。插入新结点时从尾部往前找位置维护链表的升序。从复杂度看链表方案是 O(n²)最小堆是 O(nlogn)但课程设计里字符集规模通常只有几个到几十个性能差异完全感知不到链表的优势在于每一步状态都可见调试时能打印出整个链表确认排序是否正确。二叉堆的 siftDown 和 siftUp 边界条件写起来容易出问题一旦出错很难定位链表插入的边界问题相对直观最多就是指针指错断点一打就能看出来。常见做法是课程设计用链表交差考研手写算法题时用堆两种情况考核点不同不必觉得链表方案低一档。2.3 insert 函数哨兵结点与插入边界的细节void insert(LPContainer list, LPContainer node) { LPContainer p; p list-last; // 从尾部开始往前找 while (node-v-value p-v-value) { p p-last; } node-last p; // 插到第一个 value 新结点的位置后面 node-next p-next; p-next-last node; p-next node; }这个函数的逻辑是从链表尾部向前扫描遇到第一个权值小于等于新结点权值的位置插到它后面。list 是带头哨兵的双向循环链表哨兵的 value 初始化为 0这很关键。循环条件 node-v-value p-v-value 意味着只要 p 指向的结点权值比新结点大就继续往前挪当 p 挪到哨兵时哨兵 value 为 0只要所有输入字符的权值都大于 0比较就会停下哨兵天然充当了边界挡板防止指针越界。有个细节值得注意插入时遇到相等权值不会继续往前跳所以相同频率的字符按「先来后到」的顺序排列。这保证了编码生成过程在相同输入下是稳定的不会因为结点相对顺序变化导致每次跑出不同的编码结果。如果哪天你改了排序方式比如把小于号改成小于等于那相同频率字符的编码就会互换整个编码表全变但译码仍然正确——只要编码表和树是同一批生成的。3. 从字符集到哈夫曼树建树流程与插入排序的边界问题建树是整份报告的算法核心也是代码里最容易写死循环的地方。GetInput 负责收集用户输入的字符和频率createHuffmanTree 负责把双向链表里的结点两两合并直到只剩根两个函数接力完成哈夫曼树的构造中间任何一个环节对指针的处理出现问题程序都会直接卡死或者崩掉。3.1 GetInput读字符集时的换行符陷阱LPNode GetInput() { Container list; LPContainer p; LPNode head; int i, num; printf(输入字符集规模); scanf(%d, num); list.v (LPNode)malloc(sizeof(Node)); list.v-word -1; list.v-value 0; list.v-left list.v-right NULL; list.next list; list.last list; for (i 0; i num; i) { p (LPContainer)malloc(sizeof(Container)); p-v (LPNode)malloc(sizeof(Node)); p-v-left p-v-right NULL; getchar(); // 吸收上一个 scanf 遗留的换行符 printf(输入字符); scanf(%c, p-v-word); printf(输入该字符的权值); scanf(%d, p-v-value); insert(list, p); } printf(正在构造哈夫曼树……\n); head createHuffmanTree(list); printf(哈夫曼树创建成功!\n); free(list.v); return head; }这段代码容易踩的坑在 getchar() 上。scanf(%d) 读完整数后输入缓冲区里会残留一个换行符如果下一轮直接 scanf(%c) 读字符读到的就是这个换行符而不是用户输入的字母。报告里在每轮循环开始调用 getchar() 吸掉残留的换行实测能跑通但有个隐患如果输入流的格式跟预期不一致比如上一轮输完数字后没有换行getchar() 会吞掉一个有效输入字符。更稳妥的做法是把 scanf(%c, p-v-word) 写成 scanf( %c, p-v-word)格式串里加一个空格让 scanf 自动跳过空白字符这样就不依赖 getchar 的时机了。3.2 createHuffmanTree合并最小两棵子树直到只剩根LPNode createHuffmanTree(LPContainer list) { LPContainer p; LPNode left, right, t; while (list-next-next ! list-last) { // 有效结点数大于 1 时继续 // 取出链表头两个有效结点 p list-next; list-next p-next; p-next-last list; left p-v; free(p); p list-next; list-next p-next; p-next-last list; right p-v; free(p); // 合并两个子树生成新结点 t (LPNode)malloc(sizeof(Node)); t-word -1; t-value left-value right-value; t-left left; t-right right; // 新结点重新挂进链表保持升序 p (LPContainer)malloc(sizeof(Container)); p-v t; insert(list, p); } // 链表只剩一个有效结点取出作为根 p list-next; list-next p-next; list-next-last list; left p-v; free(p); return left; }合并过程遵循哈夫曼树的经典构造逻辑每次取权值最小的两棵子树合并成新树新树的权值是两个子树的权值之和然后放回集合。重复直到集合里只剩一棵树这棵树就是最终的哈夫曼树。代码里有几个边界必须说清楚。循环条件我写的是 list-next-next ! list-last意思是「链表里至少有两个有效结点时才继续」。报告附录里写的是 while(list-next ! list-last)这个条件在只剩一个有效结点时仍然为真会多循环一轮把最后的根结点当成 left 取走再取 right 时取到的就是哨兵自身逻辑直接错乱。取下结点时 free 掉的是 Container 结构体left 和 right 指针指向的哈夫曼树结点必须保留这个区分要记住很多人 debug 半天发现树结点没了其实是 free 了不该 free 的东西。新生成的内部结点 word 置 -1只有这样 dfs 遍历时才能识别出它不是叶子。3.3 合并顺序决定编码唯一性为什么左右子树不能随便换哈夫曼编码有一个容易被误解的性质编码结果不是唯一的。两棵子树谁放左、谁放右生成的编码就互为镜象。报告里取链表头两个结点时left 是权值较小的那个所以左分支 0 始终对应较小频率的子树。如果两个字符频率相等链表插入顺序决定了谁先被取出相同输入在不同运行轮次可能得到不同的编码表。这个不唯一性不影响正确性。译码时只需要同一棵树编码表和树是一起生成的树的形态定下来编码就定下来译码按树走回去自然能还原。真正会导致翻车的做法是编码用一棵树译码时又根据频率重新建了一棵树。因为插入顺序、相等频率的处理方式都可能不同第二棵树和第一棵树结构不一致译码必然出错。这个在后面编解码章节还会再强调。4. 编码表与编解码实现DFS 生成对照表编码译码必须共用同一棵树字符-哈夫曼编码对照表的生成用的是深度优先搜索递归遍历。遍历过程中往递归函数传一个字符串参数记录从根到当前结点的路径左分支追加 0右分支追加 1。到达叶子时把这个字符和路径字符串存进 CodeNode 单链表。整个过程代码量不大但字符串处理和递归时机的细节很容易写错。4.1 dfs 遍历左0右1的编码生成与字符串副本void dfs(LPNode t, char *code, LPCodeNode list) { LPCodeNode p; char l[100], r[100]; if (t-word ! -1) { // 到达叶子结点 p (LPCodeNode)malloc(sizeof(CodeNode)); p-word t-word; strcpy(p-code, code); // 保存当前路径字符串 p-next list-next; list-next p; return; } strcpy(l, code); // 复制一份路径追加左分支 strcat(l, 0); dfs(t-left, l, list); strcpy(r, code); // 再复制一份追加右分支 strcat(r, 1); dfs(t-right, r, list); }递归的核心是字符串副本的处理。code 是调用方传入的一个缓冲左右两个分支都要基于它追加字符不能直接 strcat(code, 0) 再递归左、再 strcat(code, 1) 递归右——如果这样写左分支递归时已经把 code 改掉了右分支拿到的是被污染过的字符串。所以要先用 strcpy 把当前 code 复制到 l 和 r 两个独立数组里各自追加后再递归。这是递归字符串处理的典型写法也是报告附录里最容易抄错的地方。参数说明t 是当前访问的哈夫曼树结点根节点由 createHuffmanTree 返回code 是路径缓冲初始调用时传空字符串 list 是 CodeNode 链表的哨兵头每次插入新结点都挂到 list-next 前面所以对照表的打印顺序和遍历顺序是反的这个现象是正常的不是 bug。4.2 createCodeList 与编码查表写出密文LPCodeNode createCodeList(LPNode root) { LPCodeNode list (LPCodeNode)malloc(sizeof(CodeNode)); list-next NULL; char code[100] ; dfs(root, code, list); return list; } void code(LPNode root, LPCodeNode codeList, FILE *in, FILE *out) { char ch; LPCodeNode p; while ((ch fgetc(in)) ! EOF) { // 逐字符读明文 p codeList-next; while (p ! NULL p-word ! ch) // 查表 p p-next; if (p ! NULL) fputs(p-code, out); // 把编码字符串写入密文文件 } }createCodeList 只是对 dfs 的一层包装先分配一个哨兵头结点调 dfs 从根开始遍历返回链表。编码函数 code 做的事情很直接从源文件读一个字符在对照表里线性查找找到就把对应的编码字符串写入目标文件。查表是 O(n) 扫描字符集几十个字符时完全够用如果哪天字符集扩到几千可以换成哈希表课程设计阶段不需要考虑。这里有个细节fgetc 返回的是 int 不是 char因为要区分字符和 EOFEOF 是 -1。写法上先判断是否等于 EOF 再转成 char 赋给 ch顺序不能反。如果直接 char ch fgetc(in) 然后跟 EOF 比较某些编译器会把 char 当作无符号处理-1 变成 255EOF 判断永远为假循环不会结束。4.3 uncode 译码按位走树落叶子输出字符void uncode(LPNode root, FILE *in, FILE *out) { LPNode p root; char ch; while ((ch fgetc(in)) ! EOF) { if (ch 0) p p-left; // 0 走左子树 else if (ch 1) p p-right; // 1 走右子树 if (p-word ! -1) { // 到达叶子输出字符 fputc(p-word, out); p root; // 重置回根开始译下一个字符 } } }译码过程和编码过程是完全对称的。编码是查表替换译码是在树上按位走读到一个 0 就往左子树走读到 1 就往右子树走走到叶子说明一个字符译码完成输出该字符然后把指针重置回根节点继续读下一位。因为哈夫曼编码是前缀码任何一个字符的编码都不是另一个字符编码的前缀所以沿着树走不会出现歧义走到的叶子一定唯一对应一个字符。参数上要注意 root 是同一个哈夫曼树指针编码用的哪棵树译码就必须用哪棵。前面 3.3 提到过如果译码时根据同样的频率重新构建哈夫曼树由于插入顺序和相等频率字符的相对位置可能不同树的形态会变同一个二进制串走出来的字符就完全对不上。实际工程里做到编码时把树的形态或者每个字符的编码写进压缩文件头部译码先读表不依赖重新建树。5. 常见问题排查五个高频踩坑记录与完整验算这一章把报告自带的测试用例完整走一遍再列出我从这份代码里实际踩过的五个坑。这些都是能在几分钟内让程序卡死或者输出错乱的问题提前知道能省掉大量 debug 时间。5.1 用 a10/b3/c5 手工验算整个闭环报告里的测试用例是三个字符 a、b、c频率分别是 10、3、5。建树过程b(3) 和 c(5) 先合并生成权值 8 的内部结点a(10) 再和这个内部结点合并生成根节点权值 18。按左0右1 的规则左侧是权值较小的子树得到的编码表如下。字符频率哈夫曼编码编码长度a1011b3002c5012带权路径长度 WPL 3×2 5×2 10×1 26。如果不用哈夫曼编码三个字符固定用 2 位二进制表示同样这组数据需要 2×(3510) 36 位哈夫曼编码省掉了 10 位压缩率约 72%。报告测试里用明文 bcaacb 做编码对照编码表逐字符替换得到 00 01 1 1 01 00拼接成二进制串 0001110100一共 10 位。把这串二进制再交给译码函数00 走左左输出 b01 走左右输出 c1 走右输出 a以此类推最终还原出 bcaacb闭环成立。5.2 避坑五个高频踩坑记录坑 1程序一运行就卡死没有输出现象执行后终端停在原地没有提示像死循环。原因报告附录里 createHuffmanTree 的第一行写的是 while(list-next ! list-last){}while 后面直接跟了分号循环体为空程序在这里空转。就算去掉分号这个条件本身也不对链表只剩一个有效结点时它仍然为真会把根结点当 left 取走后面逻辑全乱。解决把循环条件改成 list-next-next ! list-last同时把合并逻辑写进循环体里。这个坑血的教训是抄代码前先扫一遍有没有空循环体别让肉眼骗过去。坑 2编码表里只有一路 0没有 1现象生成的对照表每个编码都是 0、00、000 这种全是 0 的形态。原因dfs 里只递归了左子树右子树的递归调用漏掉了或者写成两个 strcat 共用一个缓冲导致右子树拿到的字符串已经被左分支污染。解决右分支必须基于 code 的复制品再追加 1不能沿用左分支用过的数组。按 4.1 的写法l 和 r 各管各的互不干扰。坑 3输入字符时读进来的是换行符现象GetInput 输入完一个字符后下一个字符自动变成回车编码表里出现 \n 项。原因scanf(%d 后残留的换行符没处理下一轮 scanf(%c) 读到了它。解决把读取字符的语句改成 scanf( %c, p-v-word)格式串前加空格跳过所有空白字符。这一行代码能省掉 20 分钟的调试时间。坑 4字符集只有一个字符时编码为空现象输入字符集规模为 1程序输出的编码是空的译码也译不出东西。原因哈夫曼树只有一个根节点没有路径可走dfs 到叶子时 code 字符串是空串。解决单独处理单字符情况编码时直接输出空串或者约定一个固定编码译码时遇到任何输入都输出这个字符。这个问题在报告里没有覆盖但实际测试很容易遇到。坑 5译码结果末尾多一个字符或丢一个字符现象密文译回明文后最后一个字符不对或者少了。原因EOF 判断时机不对或者读到 EOF 时指针恰好在叶子结点上还没输出。解决fgetc 的返回值先跟 EOF 比较不是 EOF 才进入循环体走完一个完整字符、输出完再重置指针。按照 4.3 的写法就不会有这个问题。6. 把课程设计改成可用工具编码表持久化与逐位写出课程设计交差容易真正把哈夫曼编码用到实际压缩场景里还差两步编码表要跟着压缩文件一起存这样解压时不依赖重新建树编码结果要按位打包成二进制字节而不是把 0 和 1 当成两个字符写进文件。先解决编码表持久化。压缩文件头部按固定格式写入字符总数、每个字符的 word、value、code 字符串。解压时先读头部恢复字符-编码对照表直接查表译码不用重建哈夫曼树。这样还顺带解决了 3.3 讲的「两棵树不一致」问题——反正不建树了也就不存在第二棵树。再解决逐位写出。0 和 1 是字符每个占 1 字节而真正的二进制信息只需要 1 位。把 encoding 字符串按位拼进一个字节满 8 位写一次文件输出体积立刻缩小 8 倍void pack_bits(FILE *in, FILE *out) { int buf 0, bit_count 0, c; while ((c fgetc(in)) ! EOF) { if (c 0 || c 1) { buf (buf 1) | (c - 0); // 位拼进缓冲区 if (bit_count 8) { // 满 8 位写一个字节 fputc(buf, out); buf 0; bit_count 0; } } } if (bit_count 0) // 末尾不足 8 位左移补零 fputc(buf (8 - bit_count), out); }最后一位的处理是关键。如果编码串长度不是 8 的倍数最后一个字节右半部分是补的零译码时必须知道有效位数否则会把补的零当成真实密文多译出字符。常见做法是在文件头部用一个字节记录末尾补了多少位译码时读到最后一个字节先去掉补位再走树。从那以后我每次写哈夫曼编码都会强制先跑一遍 a10/b3/c5 的编码-译码闭环确认对照表、逐位写出、补位记录三个环节都对得上再继续加别的新功能。这组最小用例能挡住八成以上的低级错误希望帮到你。本文还有配套的精品资源点击获取