题目：姓名：学号：班级：C语言程序设计实践
哈夫曼编码与费诺编码 苏斌斌 通信工程170x
兰州交通大学 电子与信息工程学院
通信工程系
2018 年 6 月 25 日
哈夫曼编码与费诺编码
《C语言程序设计实践》任务书
课程名称 题目 姓名 苏斌斌 1）哈夫曼编码 哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。 2）费诺(Fano)编码 费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率达，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。通过采用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码长，以及编码的传输效率进行了求解，利用C语言实现费诺编码。 C语言程序设计实践 哈夫曼编码与费诺编码 学号 2017xxx 班级 通信工程170x 设 计 任 务 程序质量： 设 计 要 求 1．符合课题要求，实现相应功能；可以加以其他功能或修饰，使程序更加完善、合理。 2．代码应适当缩进，并给出必要的注释，以增强程序的可读性。 3．程序调试完后需生成可执行文件。 课程设计书面报告： 课程结束后，上交课程设计书面报告和源程序。课程设计书面报告的内容及格式参见课程设计要求。 指导教师 签字 2
兰州交通大学C语言课程设计实践
《C语言程序设计实践》评分表
课程设计题目：哈夫曼编码与费诺编码 姓名 学院 项目 评价指标 苏斌斌 电子与信息工程学院 学号 专业 指标内涵 选题难度分为两个等级，A类选题为一级，B类选选题难度 题为二级。对于A类选题，能将C语言作为开发工具，使用相关技术解决问题；为今后搭建与专业相关的仿真实验环境，开展仿真实验提供基础知识 工 作 量 设计完成情况 设计水平与实际能力 书面报告撰写 答辩 思路清晰，语言流畅，回答问题准确。 考勤 按时出勤，不迟到早退，以每次点名为准 20 10 文档质量 能够按照给定格式排版，页面美观 写作水平 工作量饱满，工作认真、严谨，遵守纪律，与同学团结协作、协调能力强，能按时完成设计任务 综合运用知识能力强，能系统地运用有关理论与知综合运用 识解决实际问题。能够独立查阅文献资料，从事调知 识 查研究；具有收集、整理、加工各种信息及获取新知识的能力 能独立开展设计工作，能熟练掌握和运用所学基本理论、基本知识和基本技能分析解决相关理论和实际问题，设计方案合理可行，界面友好，符合课题要求，实现相应功能；可以加以其他功能或修饰，使程序更加完善、合理；操作方便易行 语言表达清晰，报告内容详实，能对本人所做工作进行详细论述 30 30 10 2017xxx 通信工程 分值 评分 选题情况 成绩 3
评阅时间： 2018年 月 日 哈夫曼编码与费诺编码
目录
1、哈夫曼编码 ............................................................. 1
(1)需求分析 ........................................................... 1 (2)概要设计 ........................................................... 1 (3)详细设计 ........................................................... 2 (4)程序代码 ........................................................... 5 (5)调试分析 .......................................................... 11 (6)用户使用说明 ...................................................... 11 (7)测试结果 .......................................................... 13 (8)参考文献 .......................................................... 14 2、费诺编码 .............................................................. 15
(1)需求分析 .......................................................... 15 (2)概要设计 .......................................................... 15 (3)详细设计 .......................................................... 15 (4)程序代码 .......................................................... 19 (5)调试分析 .......................................................... 22 (6)用户使用说明 ...................................................... 23 (7)测试结果 .......................................................... 23 (8)参考文献 .......................................................... 23
4
兰州交通大学C语言课程设计实践
1、哈夫曼编码
(1)需求分析
程序设计任务：
设计一个哈夫曼编码压缩与解压缩程序，对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件，反过来，可将编码文件译码还原为文本文件。 程序相关规定：
输入的形式：整型和字符型；
输入值的范围：MAXBIT 100 MAXVALUE 10000； 输出的形式：二进制编码形式输出；
程序所能达到的功能：实现对一个ASCII编码的文本文件字符进行哈夫曼编码以及将编码文件译码还原为文本文件。
(2)概要设计
模块设计
本程序包含三个模块：主程序模块，哈夫曼编码模块，，选择模块，其调用关系如下图所示：
图1.2.1模块调用关系
图1.2.2哈夫曼编码（译码）模块设计
1
哈夫曼编码与费诺编码
图1.2.3主程序模块
采用结构体保存过程数据.通过定义两个结构类型，分别记录二叉树的信息和编码的信息。输出结果.将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数print，将结果回显。 求解Huffman的编码
通过对已经建立好的数进行循环遍历，向左路径记录为0，向右记录为1，直到所有结点访问到。 数据类型的定义
哈夫曼树类型 Typedef struct{//构造树 Char value；//结点权值 int weight //权重 int parent//双亲结点 int lchild//左孩子结点 int rchild//右孩子结点 }HNodeType 求哈夫曼编码类型 typedef struct {int bit[MAXBIT]; int start;
} HCodeType;
(3)详细设计
第一部分：建立哈夫曼树
构建结点结构体数组HuffNode；初始化结构体数组HuffNode；输入结点及其权值；循环构造HuffmanTree;每次循环运算得到权值最小的两个结点，并合成一棵小型HuffmanTree;循环结束，所有的小型HuffmanTree合成最终的Huffman。
2
兰州交通大学C语言课程设计实践
3
哈夫曼编码与费诺编码
图1.3.1
第二部分：构建解码（decodeing）函数
图1.3.2
构建新的数组num：循环判断数组string中的每个元素，并逐个存放到数组num中；构建指针nump指向数组num的首元素地址；循环解码；每次循环，如果节点是父结点，且满足条件：其子结点都为叶结点，则循环结束；循环输出相应的叶结点的解码（所求），解码完成。 第三部分：主函数
调用HuffmanTree函数；循环编码。每次循环，得到一个叶结点的编码；得到所有叶结点的编码循环结束；循环保存每个叶节点的哈夫曼编码和编码起始位；输出每个叶节点的哈夫曼编码和编码起始位；调用decodeing函数，可以进行字符或字符串的解码；程序结束。
4
兰州交通大学C语言课程设计实践
图1.3.2
(4)程序代码
#include #define MAXBIT 100 /*最大编码长度*/ 5 哈夫曼编码与费诺编码 #define MAXVALUE 10000 /*最大值*/ #define MAXLEAF 30 /*最大叶子数n*/ #define MAXNODE MAXLEAF*2 -1 /*最大结点数（2n-1）*/ typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; /*权重*/ int parent; /*父结点*/ int lchild; /*左子结点*/ int rchild; /*右子结点*/ char value; /*叶子结点*/ } HNodeType; /* 结点结构体 */ /* 构造一颗哈夫曼树 */ void HuffmanTree (HNodeType HuffNode[MAXNODE], int n) { /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ for (i=0; i<2*n-1; i++) { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=' '; //实际值，可根据情况替换为字母 } /* end for */ /* 输入 n 个叶子结点的权值 */ 6 兰州交通大学C语言课程设计实践 for (i=0; i scanf (\"%c\ } /* end for */ for (i=0; i /* 循环构造 Huffman 树 */ for (i=0; i /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */ for (j=0; j m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j; } else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } } /* end for */ 7 哈夫曼编码与费诺编码 /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; printf (\"x1.weight and x2.weight in round %d: %d, %d\\n\i+1, HuffNode[x1].weight, HuffNode[x2].weight); printf (\"\\n\"); } /* end for */ } /* end HuffmanTree */ //解码 void decodeing(char string[],HNodeType Buf[],int Num) { int i,tmp=0,code[1024]; int m=2*Num-1; char *nump; char num[1024]; for(i=0;i num[i]=1; } i=0; nump=&num[0]; while(nump<(&num[strlen(string)])) {tmp=m-1; while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1)) { 8 兰州交通大学C语言课程设计实践 if(*nump==0) { tmp=Buf[tmp].lchild ; } else tmp=Buf[tmp].rchild; nump++; } printf(\"%c\ } } int main(void) { HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF], cd; int i, j, c, p, n; char pp[100]; printf (\"Please input n:\\n\"); scanf (\"%d\ HuffmanTree (HuffNode, n); for (i=0; i < n; i++) { cd.start = n-1; c = i; p = HuffNode[c].parent; while (p != -1) /* 父结点存在 */ { if (HuffNode[p].lchild == c) cd.bit[cd.start] = 0; else /* 定义一个结点结构体数组 */ /* 定义一个编码结构体数组， 同时定义一个临 时变量来存放求解编码时的信息 */ 9 哈夫曼编码与费诺编码 cd.bit[cd.start] = 1; cd.start--; /* 求编码的低一位 */ c=p; p=HuffNode[c].parent; /* 设置下一循环条件 */ } /* end while */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ for (j=cd.start+1; j printf (\"%d\ } printf(\" start:%d\ printf (\"\\n\"); } printf(\"Decoding?Please Enter code:\\n\"); scanf(\"%s\ decodeing(pp,HuffNode,n); getchar(); return 0; } 10 兰州交通大学C语言课程设计实践 (5)调试分析 在调试哈夫曼编码程序中，出现了无法解码信息的情况，在经过上网查询资料，同伴讨论之后，改正了某些错误，并确定了函数本身语法的正确性，并对函数语句进行了顺序上的改变解决了这个问题 ，并完成本程序。 这个过程中，体会到了什么叫做细节决定成败，编写程序中查询错误耗时最长，也是这时最煎熬，程序很多时候牵一发而动全身，一些细节上的小问题会使整个程序的运行出现问题，使得无法得到想要得到的结果，因此，编程过程中细节决定成败，可能不经意间一举动会浪费大量时间来排错。 (6)用户使用说明 搭建好可执行.c.文件的环境 打开huffman.c 图1.6.1 点击ctrl+F5 输入待编码的字符数 图1.6.2 11 哈夫曼编码与费诺编码 依次输入待编码的字符 图1.6.3 依次输入待编码的字符的权重 图1.6.4 等待程序执行输出结果 图1.6.5 12 兰州交通大学C语言课程设计实践 输入需要转换成字符的机器码 图1.6.6 等待程序执行输出结果 图1.6.7 (7)测试结果 输入节点数11，输入节点分别为q、i、a、n、g 、 (空格)、e、 z、u、s、h,输入权值分别为10、20、30、40、50、60、70、80、90、100、110。 13 哈夫曼编码与费诺编码 图1.7.1哈夫曼测试 然后输出各二叉树，并输入代码解码得到信息。 图1.7.2 哈夫曼测试 (8)参考文献 [1]谭浩强.C语言程序设计[H].北京：清华大学出版社，2006. [2]王防修,周康.通过哈夫曼编码实现文件的压缩与解压[J].武汉工业学院学报,2008(04):46-49. 14 兰州交通大学C语言课程设计实践 2、费诺编码 (1)需求分析 程序的目的 费诺编码意在将输入的n个信源按照概率的大小从大到小进行了排序，然后将n个信源分为两组，使其两组的概率之和基本相等，并分别给予二进制码元0和1，再将两大组进行同样的分组，同样给予0和1，直到每一组中只有一个信源符号为止。 输入与输出 本程序输入的是信源符号的个数，输出的为各信源符号的码长和二元码字。 测试数据：本程序要求输入的信源符号概率总和无限接近1，否则将无法继续。 (2)概要设计 本程序主流程为一个简单的输入输出函数，使用了三个函数来实现了费诺编码。本程序所使用的数据类型为int型和float型，程序共使用三个函数，function1函数是为了求出分界点d。function2函数是为了对信源符号进行分组和计算码长、码字。而function3函数是调用了function1函数和function2函数。 (3)详细设计 输入信源符号，并将其排序 15 哈夫曼编码与费诺编码 图2.4.1 费诺编码流程图 16 兰州交通大学C语言课程设计实践 function1函数：求分界点 图2.4.2 费诺编码流程图 17 哈夫曼编码与费诺编码 function2函数：分组并求码长，码字 图2.4.3 费诺编码流程图 18 兰州交通大学C语言课程设计实践 function3函数 图2.4.4 费诺编码流程图 (4)程序代码 #include #define G 20 int function1(int c,int M); void function2(int c,int num1,int M,int cs); void function3(int c,int M); double a[G]={0},tmp=0,m[G]={0},k=0,H=0,num[G]={0},sum1=0,sum2=0; int K[G]={0},i,j,N,s[G][G],c,cs=0,num1=0,ks[G],zj[G],zh[]; void main() 19 哈夫曼编码与费诺编码 loop:printf(\"请输入信源符号个数N：\"); scanf(\"%d\for(i=0;i if(tmp<0.9999||tmp>1.0001) { printf(\"输入的数据不符合要求,请重新输入\\n\"); tmp=0; goto loop; } else { for(i=0;i } ///////////////////////////////////////////////////////////////////////////// function3(0,N); printf(\"信源消息符号ai 符号概率p(ai) 码长Ki for(i=0;i 20 二元码字\\n\"); %d \{ 兰州交通大学C语言课程设计实践 } } } printf(\"\\n\"); int function1(int c,int M)//求出分界点 { } void function2(int c,int num1,int M,int cs)//进行分组并计算码长、码字 { int d=c; for(i=c;i for(j=c;j for(i=c;i s[i][cs]=0; K[i]+=1; 哈夫曼编码与费诺编码 } for(j=num1;j void function3(int c,int M) { } num1=function1(c,M); function2(c,num1,M,cs); ks[cs]=c; zj[cs]=num1; zh[cs]=M; cs++; if((zj[cs-1]-ks[cs-1])>1) { } if((zh[cs-1]-zj[cs-1])>1) { } cs--; function3(zj[cs-1],zh[cs-1]); function3(ks[cs-1],zj[cs-1]); (5)调试分析 在此程序分析的过程中，对于费诺编码的理解并不深刻，在分组的时候遇到 大的问题，比如无法进行正确的分组使两组的概率之和近似相等，但是在网上查阅资料，并对程序的循环进行了多次核对，发现需要使用for循环的多次使用，在多次调试后，完成了对数据的分组，同时，还对函数的引用进行了整合，完成了本次程序。 22 兰州交通大学C语言课程设计实践 (6)用户使用说明 用户在使用本程序的时候，需要注意，输入的信源个数可以为单双数，但是必须为整数，并且输入的信源符号的概率必须是之和为1的一组概率，若不符合要求就会被提醒重新输入。输入完成后，你会得到每个信源符号的码长和每个信源符号所对应的二元码字，即费诺编码数。 (7)测试结果 图2.7.1费诺测试 图2.7.2费诺测试 (8)参考文献 [1]魏艳红.信源编码算法的研究及优化[J].福建电脑,2015,31(11):10+12. [2]余秀玲.信源编码的方法研究及应用[J].现代商贸工业,2018,39(16):176-177. 23 因篇幅问题不能全部显示，请点此查看更多更全内容