哈夫曼编译码器

1、数据结构课程设计目录1问题描述第2页2. 系统设计第2页3. 数据结构与算法描述第5页4. 测试结果与分析第6页5总结第10页6.参考文献第10页附录程序源代码第11页共18页第17页课程设计题目1. 问题描述 利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成 本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行 译码（复原）。对于双工信道（既可以双向传输信息的信道） ，每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2.1 基本要求一个完整的系统应具有以下功能：1） I :初始化（Initializati

2、on）。从终端读入字符集大小n,以及n个字符和n个权 值，建立哈夫曼树， 并将它存于文件 hfmTree 中。输出哈夫曼树， 及各字符对应的编码。2）W输入（In put ）。从终端读入需要编码的字符串s,将字符串s存入文件 Tobetran.txt 中。3）E：编码（Encoding）与译码（Decoding ）。编码（Encoding ）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile中的代码进行译码， 结果存入文件 Tex

3、tFile 中。打印代码文件（ Print ）。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个 代码。同时将此字符形式的编码写入文件 CodePrint 中。4） T：打印哈夫曼树（Tree Printing ）。将已在内存中的哈夫曼树以直观的方式（树 或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。5）Q:退出程序。返回WINDOWS面。2.2 设计思想哈夫曼编码（Huffman Coding）是一种编码方式，以哈夫曼树一即最优二叉树，带 权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符 （例如某文件中的一

4、个符号）进行编码。这种方法是由 David.A.Huffman 发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一 篇英文进行压缩时，e极有可能用一个位（bit）来表示，而z则可能花去25个位（不是 26）。用普通的表示方法时，每个英文字母均占用一个字节（byte ），即8个位。二者相 比，e使用了一般编码的1/8的长度，z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。2.3系统模块划分mai n()prin ti ng()图2-3哈夫曼编/解码器的程序结构图2.3.1 初始化算法：程序从文件a

5、bc.txt中获取26个英文字母的权值。2.3.2 编码算法：(1) 对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化 为权值w1,w2,wN构成n棵二叉树的集合F=T1,T2,Tn把它们保存到结构 体数组HTn中,其中Ti是按它们的ASCH码值先后排序。其中每棵二叉树Ti中只有一 个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。(2) 在HT1.i中选取两棵根结点的权值最小且没有被选过的树作为左右子树 构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之 和。(3) 哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。2.3.3 译

6、码算法：译码的过程是分解电文中字符串，从根出发，按字符 0',或'1'确定找左孩子 或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。3. 数据结构与算法描述3-1typedef struct int weight;int pare nt,lchild,rchild;HTNode,* Huffma nTree;/动态分配数组存储赫夫曼树 typedef char *Huffma nCode; /动态分配数组存储赫夫曼编码表3-2int min(HuffmanTree t,int i)/求赫夫曼编码3-3 void select(HuffmanTree t

7、,int i,int &s1,int &s2) /-sleet 函数-3-4void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode & HC,i nt *w,i nt n)/ w存放n个字符的权值(均0)，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC3-5 void In itializati on()3-6 void In putCode()3-7 void En cod in g()3-8 void Decodi ng()3-9 void Code_pri nting()/初始化赫夫曼链表-/获取报文并写入

8、文件/编码函数/译码函数-/打印编码的函数3-19 void coprint(HuffmanTree start,HuffmanTree HT)/打印赫夫曼树的函数3-20 void main()/主函数4. 测试结果与分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1表4-1 abc.txt文件中的字母和权值声明：程序预先将Huffman编码解码所需的26个字母和权值保存在根目录下的abc.txt 文件下。4-1.按照程序提示输入i对Huffman进行初始化。4-2.初始化后程序对abc

9、.txt文件中的数据进行读取并运行编码函数进行哈夫曼编码。 然后将字母、权值和哈夫曼编码存在根目录下的htmTree.txt文件中。在屏幕显示出字符、权值、编码。4-3.输入w进入待编码字符输入窗口，并键入字符串（注意单词间无空格）“ I”happynewyear。57劎入何漪朗斷子诃逬布囁码，译码、打印编码 <3打印赫天曼树3熏升<"初妬化赫<w><c>赫夫曼編码解码養 宇符, 一行編码、译码、打印编列 打印旃夫曼树3违开文件中。4-4.可以看出所获得的字符串已经存入根目录下的tobetra n.txt4-5.输入e进行编码、译码和打印编码功能。

10、输夫打印哈曼树入4-6.t0316115301£121571145721?1034185199481?31213111824134723?447札印工作结束X M：JC6e iC J * ：M JC KJBKKXXXE赫夫曼编码解码由于哈夫曼树过于巨大，一次截屏无法完全显示，使用两次截屏。以上两幅图显示出来程序编出的哈夫曼树的形状。打印出来的图形与教科书上的常 见哈夫曼树略有不同，左边的数是右边数的父节点。4- 7.输入q退出程序。5总结5- 1、用户界面设计为“菜单”模式，使人们更加容易使用。5-2、在程序的一次执行过程中，第一次执行 e命令之后，哈夫曼树已经在内存了， 不必再读入

11、。5-3.在编程中使用了很不规范的编程方法，应用了一些临时变量来实现功能，而大量临时变量在代码中没有很好地进行命名。这给程序的阅读和维护带来了极大的困难。5-4.本程序仅能对26个小写字母构成的字符串进行处理， 并不具有对汉字等的编码 处理能力。5-5.设计中得到了老师和广大同学的帮助，并参考了网络上的优秀论文和纸质文件, 使我的程序设计能够较为顺利的进行下去。在此我衷心感谢我的老师同学和对以上资源 的作者。五、心得体会通过这次课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我 更加明白哈夫曼编码译码在信息技术中的重要性和地位。开始的时候，代码中有许多的 错误，特别是有一个“无法

12、找到文件”的错误让我束手无策，最后还是屏蔽了定义的四 个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对 文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环，最后的 解决方式是把main函数里的一个dowhile循环去掉。在程序中，我还另外加了一个 功能-输出哈夫曼树的存储结构的初态和终态。这使得我更加的明白了哈夫曼到底是 怎么存储信息的。6.参考文献A :书籍资料1严蔚敏 吴伟民数据结构（C语言版）北京：清华大学出版社2苏仕华数据结构 课程设计北京：机械工业出版社B :网络资料1 哈夫曼编/译码器（课程设计） ng/blog/item/d30236

13、7a65804eed2e73b32bhtml2 哈夫曼编码 附录程序源代码哈夫曼编/译码器（课程设计）2008/5/21#i nclude <iostream.h>#in clude <fstream.h>#i nclude <ioma nip.h>#in clude <stri ng.h>#i nclude <malloc.h>#in clude <stdio.h>#i nclude <ioma nip.h>con st i nt UINT_MAX=10000;typedef structint weight

14、;int parent,lchild,rchild;HTNode,* HuffmanTree;/ 动态分配数组存储赫夫曼树typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表/ 全局变量 HuffmanTree HT;HuffmanCode HC;int *w,i,j;const int n=26;char *z;int flag=0;int numb=0;/ 求赫夫曼编码 int min(HuffmanTree t,int i) / 此函数将要被 void select() 调用int j,flag;int k=UINT_MAX; / 取 k 为不小于可能的

15、值 for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0) k=tj.weight,flag=j;tflag.parent=1; return flag;/slect 函数 void select(HuffmanTree t,int i,int &s1,int &s2) / s1 为最小的两个值中序号小的那个int j;s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;/ 参考课本算法 6.12void HuffmanCoding(HuffmanTree &

16、;HT,HuffmanCode &HC,int *w,int n)HC / w存放n个字符的权值(均>0),构造赫夫曼树 HT,并求出n个字符的赫夫曼编码 int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(n<=1)return;/ 检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0 号单元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p-&g

17、t;lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0;for(i=n+1;i<=m;+i) / 建赫夫曼树 / 在 HT1i-1 中选择 parent=0 且 weight 最小的两个结点 ,其序号分别为 s1 和 s2 select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/ 从叶子到根逆向求每个字符的赫夫曼编码 HC=(HuffmanCode)mal

18、loc(n+1)*sizeof(char*);/ 分配 n 个字符编码的头指针向量 (0不用 ) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1='0' / 编码结束符 for(i=1;i<=n;i+) / 逐个字符求赫夫曼编码start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*

19、)malloc(n-start)*sizeof(char);/ 为第 i 个字符编码分配空间 strcpy(HCi,&cdstart); / 从 cd 复制编码 (串 )到 HCfree(cd); / 释放工作空间/ 初始化赫夫曼链表 void Initialization()flag=1;int num2;cout<<" 下面初始化赫夫曼链表 "<<endl; w=(int*)malloc(n*sizeof(int); / 为第 26 个字符权值分配空间 z=(char*)malloc(n*sizeof(char); / 为第 26 个字符

20、分配空间 cout<<"n 依次显示 "<<n<<" 个字符与其权值和编码 n"<<endl; char base2;/?ifstream fin("abc.txt");for(i=0;i<n;i+)fin>>base;*(z+i)=*base;/?fin>>num2;/ 上面 123 行*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/ 打印编码 cout<<" 字符 "<<setw(6

21、)<<" 权值 "<<setw(11)<<" 编码 "<<endl; for(i=1;i<=n;i+)cout<<setw(3)<<*(z+i-1); cout<<setw(6)<<*(w+i-1)<<setw(12)<<HCi<<endl;/ 将赫夫曼编码写入文件 cout<<" 下面将赫夫曼编码写入文件 "<<endl<<""<<

22、;endl;FILE *htmTree;char r=' ','0'if(htmTree=fopen("htmTree.txt","w")=NULL)cout<<" 不能打开文件 "<<endl;return;for(i=0;i<n;i+)fputc(*(z+i),htmTree);fputs(r,htmTree);for(i=0;i<n;i+)fprintf(htmTree,"%6d",*(w+i);fputs(r,htmTree);for(i=

23、1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmTree);fclose(htmTree);cout<<" 已将字符与对应编码写入根目录下文件htmTree.txt 中 "<<endl<<endl;/ 获取报文并写入文件 void InputCode()FILE *tobetran;char str100;if(tobetran=fopen("tobetran.txt","w")=NULL)cout<<" 不能打开文件 "&l

24、t;<endl;return;cout<<" 请输入你想要编码的字符 "<<endl;/ 字符个数应当小于 100gets(str);fputs(str,tobetran);cout<<" 获取报文成功 "<<endl; fclose(tobetran);cout<<""<<endl<" 报文存入根目录下的 tobetran.txt 文件中 "<<endl;/ 编码函数 void Encoding()cout<&l

25、t;" 下面对目录下文件 tobetran.txt 中的字符进行编码 "<<endl;FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL)cout<<" 不能打开文件 "<<endl; if(codefile=fopen("codefile.txt","wb")=NULL)cout<<" 不能打开文件 "<<e

26、ndl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99) if(fgets(tran,100,tobetran)=NULL) cout<<" 不能打开文件 "<<endl; break; for(i=0;*(tran+i)!='0'i+)for(j=0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,COdefile);if(j>n)!"<<endl;COut<<" 字符错

27、误，无法编码break;"<<endl ;COdefile.txt 中 "<<endl<<endl;COUt<<"编码完成cout<<" 编码写入目录下的 fClOse(tObetran); fClOse(COdefile); free(tran);/ 译码函数 vOid DeCOding()COut<<" 下面对根目录下文件 COdefile.txt 中的字符进行译码 "<<endl;FILE *COdef,*txtfile; if(txtfile=

28、fOpen("Textfile.txt","w")=NULL) COut<<" 不能打开文件 "<<endl;txtfile=fOpen("Textfile.txt","w");if (COdef=fOpen("COdefile.txt","r")=NULL)COut<<" 不能打开文件 "<<endl;codef=fopen("codefile.txt","

29、r");char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000; work=(char*)malloc(length*sizeof(char);fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!='0'i+) i2=*(work+i);if(HTi3.lchild=0) *(work2+i4)=*(z+i3-1); i4+; i3=2*n-1;i-;else if

30、(i2='0') i3=HTi3.lchild;else if(i2='1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile);cout<<"译码完成"<<endl ;cout<<"内容写入根目录下的文件textfile.txt中"<<endl<<endl;free(work);/释放工作区free(work2);/释放工作区fclose(txtfile);/关闭文件 txtfile.txt

31、fclose(codef); /关闭文件 codef.txt/ 打印编码的函数 void Code_printing()cout<<" 下面打印根目录下文件 CodePrin.txt 中编码字符 "<<endl; FILE * CodePrin,* codefile;if(CodePrin=fopen("CodePrin.txt","w")=NULL)cout<<" 不能打开文件 "<<endl;return;if(codefile=fopen("codef

32、ile.txt","r")=NULL)cout<<" 不能打开文件 "<<endl;return;char *work3;work3=(char*)malloc(51*sizeof(char); if(fgets(work3,51,codefile)=NULL)cout<<" 不能读取文件 "<<endl;elsedofputs(work3,CodePrin);puts(work3);while(strlen(work3)=50&&fgets(work3,51,

33、codefile)!=NULL); free(work3);cout<<" 打印结束 "<<endl<<endl;fclose(CodePrin);fclose(codefile);/ 打印赫夫曼树的函数 void coprint(HuffmanTree start,HuffmanTree HT)/start=ht+26 这是一个递归算法if(start!=HT)FILE * TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<

34、;<" 创建文件失败 "<<endl;return;numb+; /number=0 该变量为已被声明为全局变量 coprint(HT+start->rchild,HT);/ 递归先序遍历cout<<setw(5*numb)<<start->weight<<endl; fprintf(TreePrint,"%dn",start->weight);coprint(HT+start->lchild,HT);numb-;fclose(TreePrint);void Tree_printing(HuffmanTree HT,int w)HuffmanTree p;p=HT+w; /p=HT+26cout<<" 下面打印赫夫曼树 "<<endl;coprint(p,HT); /p=HT+26 cout<<&qu