哈夫曼编码/译码器

jquave · 发表于 2023-2-18 16:02

文章目录

一、设计任务及要求

哈夫曼编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。要求完成以下功能：

二、设计导向

1. 设计目的

(1) 巩固和加深对数据结构课程所学知识的理解，了解并掌握数据结构与算法的设计方法；
(2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
(3) 提高综合运用所学的理论知识和方法，独立分析和解决问题的能力；
(4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；
(5) 培养查阅资料，独立思考问题的能力。
2. 设计课题

哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中，通常需要将传送文字转换成由二进制字符0，1组成的二进制串，称之为编码。构建一个哈夫曼树，设定哈夫曼树中的左分支为0，右分支代表1，则从根结点到每个叶子节点所经过的路径组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可以有效缩短传送文字的总长度。哈夫曼树则是用于构造使编码总长最短，最节省空间成本的编码方案。
设计包含几个方面：
(1)哈夫曼树的建立
哈夫曼树的建立由哈夫曼算法的定义可知，初始森林中共有n课只含有根节点的二叉树，算法的第二步是：当前森林中两颗根节点权值最小的二叉树，合并为一个新的二叉树，每合并一次，森林中就减少一棵树，产生一个新节点，要进行n-1次的合并，共产生n-1个新节点，他们都是具有两个孩子的分支节点。由此可知，最终得到的哈夫曼树中一共有2n-1个节点，其中n个节点是由初始森林的n个孤立节点，哈夫曼树中没有度数为1的分支节点，我们可以利用一个大小为2n-1的一维数组来存储哈夫曼树中的节点。
(2)哈夫曼编码
首先定义哈夫曼编码类型，根据实际需要定义类型如下：

Typedef struct//结点的结构{unsignedint weight;unsignedint parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
Typedef char**HuffmanCode;//动态分配数组存储哈夫曼树

复制代码

(3)代码文件的译码
译码的思路是：读取文件中的编码，并与原先生成的哈夫曼编码表进行比较，遇到相等时，取出相应字符存入一个新字符串中。
3. 总体设计方案

设计哈夫曼编码译码器的总体思路:
(1)首先建立哈夫曼树，将哈夫曼树初始化，输入权值及字符建立哈夫曼树。
(2)输出哈夫曼的被编码的字符及对应的编码。
(3)输入要译码的哈夫曼编码字符串进行译码。

4. 详细设计

（1）建树模块
在建立哈夫曼树时需要录入字符及其权值。
（2）设计思路
在建立哈夫曼树时输入的字符及权值的个数不确定，因此采用了动态分配存储的方法。因为在后面要输出编码的字符及对应的哈夫曼编码，要统计输入了几个字符所以输入字符函数有一个返回值，返回所输入字符的个数。并且在选最初的两个结点时，要找两个权值最小的两个，则该两个结点从原来结点中删除，在此用了给它们赋最大权值。
（3）流程图

（4）编码模块
① 设计思路
在已建立的哈夫曼的基础上，逆向求哈夫曼编码。利用动态分配存储的方式，因为是逆向存储，所以也应逆向存储哈夫曼编码。
② 流程图

（5）译码模块
① 设计思路
动态分配存储输入的编码，遍历哈夫曼树，若编码等于0，向左遍历其左子树，并判断其左右孩子是否为零，若为都零则输出其data域中的字符并存储。并判断输入的编码是否读到‘\0’ ,是也退出循环，并判断退出时结点的左右孩子是否都为零，是则为完全译码否就为不完全译码。
② 流程图

5. 系统测试与结果分析

三、课程设计总结

通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。
通过本次数据结构的课设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必会顺利地做出来。
这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据,对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。

四、附录：源程序清单

#include<iostream>#include<string.h>#defineMAX_MA1000#defineMAX_ZF100
using namespace std;//哈夫曼树的顺序储存表示typedefstruct{int weight;//结点的权值int parent,lchild,rchild;//结点的双亲，左孩子，右孩子的下标} HTNode,*HuffmanTree;//动态分配数组来储存哈夫曼树的结点//哈夫曼编码表的储存表示typedefchar**HuffmanCode;//动态分配数组来储存哈夫曼编码//在哈夫曼树HT中选择两个双亲域为0且权值最小的两个结点，并返回它们在HT中的序号s1和s2voidSelect(HuffmanTree HT,int len,int&s1,int&s2){//len代表HT数组的长度int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值for(i=1; i<=len; i++){if(HT[i].weight<min1 && HT[i].parent==0){
min1=HT[i].weight;
s1=i;}}int temp=HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择
HT[s1].weight=0x3f3f3f3f;for(i=1; i<=len; i++){if(HT[i].weight<min2 && HT[i].parent==0){
min2=HT[i].weight;
s2=i;}}
HT[s1].weight=temp;//恢复原来的值}//构造哈夫曼树HTvoidCreatHuffmanTree(HuffmanTree &HT,int n){int s1,s2;if(n<=1)return;int m=2*n-1;//当n大于1时，n个叶子结点需要2*n-1个结点
HT=new HTNode[m+1];//0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点//将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0for(int i=1; i<=m;++i){
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;}
cout<<"请输入叶子结点的权值：";//输入前n个单元中叶子结点的权值for(int i=1; i<=n;++i){
cin>>HT[i].weight;}//通过n-1次的选择、删除、合并来创建哈夫曼树for(int i=n+1; i<=m;++i){//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2Select(HT,i-1,s1,s2);//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
HT[s1].parent=i;
HT[s2].parent=i;//s1,s2分别作为i的左右孩子
HT[i].lchild=s1;
HT[i].rchild=s2;//i的权值为左右孩子权值之和
HT[i].weight=HT[s1].weight+HT[s2].weight;}}//哈夫曼编码voidHuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
HC=new char*[n+1];//分配n个字符编码的编码表空间（头指针矢量）char*cd=new char[n];//分配临时存放编码的动态数组空间
cd[n-1]='\0';//编码结束符//从叶子开始逐个字符求哈夫曼编码for(int i=1; i<=n;++i){int start=n-1;//start开始时指向最后，即编码结束符位置int c=i;int f=HT[i].parent;//f是指向结点c的双亲结点//从叶子结点开始向上回溯，直到根结点while(f!=0){--start;//回溯一次，start向前指向一个位置//判断是结点c是f的左孩子还是右孩子if(HT[f].lchild==c){
cd[start]='0';//结点c是f的左孩子，则生成代码0}else{
cd[start]='1';//结点c是f的右孩子，则生成代码1}
c=f;
f=HT[f].parent;//继续向上回溯}//求出第i个字符的编码
HC[i]=new char[n-start];//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中}
delete cd;//释放临时空间}//哈夫曼译码voidHuffmanDecoding(HuffmanTree HT,char a[],char zf[],char b[],int n){//a[]用来传入二进制编码，b[]用来记录译出的字符//zf[]是与哈夫曼树的叶子对应的字符，n是字符个数相当于zf[]数组的长度int q=2*n-1;//q初始化为根结点的下标int k=0;//记录存储译出字符数组的下标for(int i=0; a[i]!='\0'; i++){//for循环结束条件是读入的字符是结束符//判断读入的二进制字符是0还是1if(a[i]=='0'){//读入0，把根结点(HT[q])的左孩子的下标值赋给q，//下次循环的时候把HT[q]的左孩子作为新的根结点
q=HT[q].lchild;}elseif(a[i]=='1'){//读入1，把根结点(HT[q])的右孩子的下标值赋给q，//下次循环的时候把HT[q]的右孩子作为新的根结点
q=HT[q].rchild;}//判断HT[q]是否为叶子结点if(HT[q].lchild==0&& HT[q].rchild ==0){//如果读到一个结点的左孩子和右孩子都为0，是叶子结点，//说明已经译出一个字符，该字符的下标就是找到的叶子结点的下标
b[k++]=zf[q];//把下标为q的字符赋给字符数组b[]
q=2*n-1;//初始化q为根结点的下标}//继续译下一个字符的时候从哈夫曼树的根结点开始}//译码完成之后，用来记录译出字符的数组由于没有结束符输出的时候会报错，//所以紧接着把一个结束符加到数组最后
b[k]='\0';}voidmenu(){int n;//记录要编码的字符个数char a[MAX_MA];//储存输入的二进制字符char b[MAX_ZF];//存储译出的字符char zf[MAX_ZF];//储存要编码的字符
HuffmanTree HT=NULL;//初始化树为空树
HuffmanCode HC=NULL;//初始化编码表为空表
cout<<" =============================================================================\n";
cout<<"|| ★★★★★★★哈夫曼编码与译码★★★★★★★ ||\n";
cout<<"||============================================================================||\n";
cout<<"||============================================================================||\n";
cout<<"|| 【1】--- 创建哈夫曼树 ||\n";
cout<<"|| 【2】--- 进行哈夫曼编码 ||\n";
cout<<"|| 【3】--- 进行哈夫曼译码 ||\n";
cout<<"|| 【4】--- 退出程序 ||\n";
cout<<" ==============================================================================\n";
cout<<"请输入数字来选择对应的功能：";while(1){int num;if(!(cin>>num)){
cout<<"输入格式错误！请重新输入："<<endl;}else{switch(num){case1:
cout<<"请输入字符个数:";
cin>>n;
cout<<"请依次输入"<<n<<"个字符: ";for(int i=1; i<=n; i++)
cin>>zf[i];CreatHuffmanTree(HT,n);
cout<<endl;
cout<<"创建哈夫曼成功！下面是该哈夫曼树的参数输出："<<endl;
cout<<endl;
cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"双亲"<<"\t"<<"左孩子"<<"\t"<<"右孩子"<<endl;for(int i=1; i<=2*n-1; i++){
cout<<i<<"\t"<<zf[i]<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent <<"\t"<< HT[i].lchild<<"\t"<<HT[i].rchild<<endl;}
cout<<"请输入数字来选择对应的功能：";break;case2:HuffmanCoding(HT, HC, n);
cout<<"生成哈夫曼编码表成功！下面是该编码表的输出："<<endl;
cout<<endl;
cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"编码"<<endl;for(int i=1; i<=n; i++){
cout<<i<<"\t"<<zf[i]<<"\t"<<HT[i].weight<<"\t"<<HC[i]<<endl;}
cout<<"请输入数字来选择对应的功能：";break;case3:
cout<<"请输入想要翻译的一串二进制编码：";
cin>>a;HuffmanDecoding(HT,a,zf,b,n);
cout<<"译码成功！翻译结果为："<<b<<endl;
cout<<"请输入数字来选择对应的功能：";break;case4:
cout<<"\n\n";
cout<<"\n*************************************************"<<endl;
cout<<"\n****** ******"<<endl;
cout<<"\n****** 谢谢使用哈夫曼编码与译码程序 ******"<<endl;
cout<<"\n****** ******"<<endl;
cout<<"\n*************************************************"<<endl;exit(0);default:
cout<<"输入错误！没有此功能！请重新输入！"<<endl;
cout<<endl;}}}}intmain(){menu();return0;}

复制代码

		自动登录	找回密码
密码			立即注册

哈夫曼编码/译码器

本帖子中包含更多资源