哈夫曼树的构造、编码生成与带权路径长度计算——基于C语言的实验实现与分析 P12114068王勇豪

P12114068 王勇豪摘要哈夫曼树是数据结构中基于贪心算法构建的最优二叉树由其生成的哈夫曼编码是一种经典的前缀无损压缩编码广泛应用于文件压缩、图像编码等领域。本文以课程实验题目为研究对象首先阐述哈夫曼树、哈夫曼编码、带权路径长度 WPL 的基础理论结合题目给定的构造规则与样例输入完成完整的手工推导基于实验所用 C 语言代码详细分析结构体设计、节点选择、树构建、编码回溯、WPL 计算的核心逻辑针对代码中存在的兼容性问题进行修复最后通过样例验证程序正确性分析代码优缺点并给出改进方向。一、理论原理1.1 基本概念路径与路径长度在二叉树中从根节点到某一叶子节点所经过的边的数量称为该叶子的路径长度。带权路径长度WPL所有叶子节点的权值×路径长度之和公式(WPLsum_{i1}^n w_i cdot l_i)其中(w_i)为字符权值(l_i) 为对应路径长度。WPL越小编码整体压缩效率越高。哈夫曼树给定一组带权叶子节点通过每次合并权值最小的两个节点最终得到的WPL最小的二叉树又称最优二叉树。哈夫曼编码从根到叶子左分支记0、右分支记1得到的二进制编码天然满足前缀码特性无编码互为前缀可直接用于无损编码。1.2 题目规定的哈夫曼树构造规则1.每次选取森林中权值最小的两个节点合并为新父节点父节点权值为两子节点权值之和2.权值较小的节点作为左孩子编码0权值较大作为右孩子编码13.若权值相同先输入先出现的节点优先作为左孩子。1.3 哈夫曼算法核心思想哈夫曼算法属于贪心算法每一步只做当前局部最优选择合并最小两个权值最终得到全局最优解WPL最小。二、样例推导过程2.1 样例输入plaintext5A 5B 9C 12D 13E 162.2 哈夫曼树手工构建初始叶子节点A (5)、B (9)、C (12)、D (13)、E (16)第1次合并最小两个 A (5)、B (9) → 父节点 N1 (14)左 A (0)右 B (1)第2次合并剩余 C (12)、D (13)、N1 (14)、E (16)最小 C (12)、D (13) → 父节点 N2 (25)左 C (0)右 D (1)第3次合并剩余 N1 (14)、E (16)、N2 (25)最小 N1 (14)、E (16) → 父节点 N3 (30)左 N1 (0)右 E (1)第4次合并剩余 N2 (25)、N3 (30)合并为根节点 N4 (55)左 N2 (0)右 N3 (1)2.3 字符编码推导C根→0→0 → 00D根→0→1 → 01A根→1→0→0 → 100B根→1→0→1 → 101E根→1→1 → 112.4 WPL 计算begin{align} WPL 5times3 9times3 12times2 13times2 16times2 1527242632 124 end{align}与样例输出WPL124完全一致。三、C 语言代码实现与分析3.1 原代码整体结构程序分为6个核心部分结构体定义哈夫曼树节点Select函数选出权值最小的两个节点CreateHuff函数构建哈夫曼树GetCode函数回溯生成哈夫曼编码GetWPL函数计算带权路径长度main函数输入、调度、输出。3.2 原实验完整代码#includestdio.h#includestring.h#defineMAXSIZE200typedefstruct{chardata;intweight;intparent,lch,rch;}HTNode,HuffTree[MAXSIZE];charcode[MAXSIZE][MAXSIZE];intn;voidSelect(HuffTree T,intend,int*s1,int*s2){inti;// 变量提前定义intmin19999,min29999;*s1*s2-1;for(i0;iend;i){if(T[i].parent-1T[i].weightmin1){min1T[i].weight;*s1i;}}for(i0;iend;i){if(T[i].parent-1i!*s1T[i].weightmin2){min2T[i].weight;*s2i;}}}voidCreateHuff(HuffTree T){intm2*n-1,s1,s2,i;// i放开头for(i0;im;i){T[i].parent-1;T[i].lch-1;T[i].rch-1;}for(in;im;i){Select(T,i-1,s1,s2);T[s1].parenti;T[s2].parenti;T[i].lchs1;T[i].rchs2;T[i].weightT[s1].weightT[s2].weight;}}voidGetCode(HuffTree T,intleaf){intcurleaf,fa,len0,i,j;// i,j提前定义chartmp[MAXSIZE];while(T[cur].parent!-1){faT[cur].parent;if(T[fa].lchcur)tmp[len]0;elsetmp[len]1;curfa;}tmp[len]\0;j0;for(ilen-1;i0;i--){code[leaf][j]tmp[i];}code[leaf][j]\0;}intGetWPL(HuffTree T){intsum0,i;for(i0;in;i){sumT[i].weight*strlen(code[i]);}returnsum;}intmain(){HuffTree T;inti,wpl;// main内所有变量放最前面scanf(%d,n);getchar();for(i0;in;i){scanf(%c %d,T[i].data,T[i].weight);getchar();}CreateHuff(T);for(i0;in;i){GetCode(T,i);}for(i0;in;i){printf(%c: %s\n,T[i].data,code[i]);}wplGetWPL(T);printf(WPL %d\n,wpl);return0;}3.3 代码逐模块分析结构体 HTNodetypedefstruct{chardata;// 存储字符intweight;// 权值频率intparent;// 父节点下标intlch,rch;// 左右孩子下标}HTNode,HuffTree[MAXSIZE];采用静态数组存储哈夫曼树这是课程实验最常用的实现方式结构清晰、简单易懂。2. Select 函数选择最小两个节点• 第一次遍历选出权值最小的节点 s1• 第二次遍历选出剩余中最小的节点 s2• 天然满足题目要求权值小的先被选中作为左孩子权值相同则下标小先输入优先完全匹配题目规则。3. CreateHuff 函数构建哈夫曼树• 哈夫曼树总节点数固定为 (2n-1)• 循环 (n-1) 次合并节点• s1 固定为左孩子0s2 为右孩子1严格遵守题目编码规则。4. GetCode 函数回溯生成编码• 从叶子向上走到根沿途记录 0/1• 因为是逆序使用 strrev 反转字符串得到从根到叶子的正确编码。原代码扣分点strrev 不是标准 C 库函数仅 VC 可用GCC 编译报错。5. GetWPL 函数计算带权路径长度直接套用公式权值 × 编码长度路径长度累加求和逻辑简单准确。四、实验结果与分析4.1 运行结果输出与题目样例完全一致程序逻辑正确。4.2 算法复杂度分析时间复杂度O(n^2)每次Select需要遍历数组空间复杂度O(n)使用静态数组存储节点适合课程实验小规模数据工业级实现一般使用最小堆优化至 O(n*log n)。五、总结本文完整梳理了哈夫曼树与哈夫曼编码的理论原理,通过手工推演验证了样例的正确性,完整沿用实验编写的 C 语言代码对每个函数进行详细逻辑分析同时修复了兼容性缺陷。该程序能够正确生成每个字符的哈夫曼编码并计算 WPL。哈夫曼算法作为贪心算法的经典案例既加深了对二叉树的理解也体现了最优编码在数据压缩中的实际价值。