哈夫曼编译码器_

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

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

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

4、来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。2.3 系统模块划分main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_printing()打印编码函数Tre

5、e_printing()打印哈夫曼树图2-3 哈夫曼编/解码器的程序结构图2.3.1 初始化算法： 程序从文件abc.txt中获取26个英文字母的权值。2.3.2 编码算法：    （1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值w1,w2,，wN构成n棵二叉树的集合F=T1,T2,，Tn把它们保存到结构体数组HTn中,其中Ti是按它们的ASC码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。   （2）在HT1.i中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树

6、，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。   （3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。 2.3.3 译码算法：     译码的过程是分解电文中字符串，从根出发，按字符'0',或'1'确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。3. 数据结构与算法描述3-1typedef struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; /动态分配数组存储赫夫曼树  t

7、ypedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表3-2 int min(HuffmanTree t,int i) / -求赫夫曼编码-3-3 void select(HuffmanTree t,int i,int &s1,int &s2) /-slect函数-3-4 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/ w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC3-5 void Initialization(

8、) /-初始化赫夫曼链表-3-6 void InputCode() /-获取报文并写入文件-3-7 void Encoding() /-编码函数-3-8 void Decoding() /-译码函数-3-9 void Code_printing() /-打印编码的函数-3-19 void coprint(HuffmanTree start,HuffmanTree HT) /-打印赫夫曼树的函数-3-20 void main() /-主函数-4. 测试结果与分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W1

9、8X1Y16Z1表4-1 abc.txt文件中的字母和权值声明：程序预先将Huffman编码解码所需的26个字母和权值保存在根目录下的abc.txt文件下。4-1.按照程序提示输入i对Huffman进行初始化。4-2.初始化后程序对abc.txt文件中的数据进行读取并运行编码函数进行哈夫曼编码。然后将字母、权值和哈夫曼编码存在根目录下的htmTree.txt文件中。在屏幕显示出字符、权值、编码。4-3.输入w进入待编码字符输入窗口，并键入字符串（注意单词间无空格）“happynewyear”。4-4.可以看出所获得的字符串已经存入根目录下的tobetran.txt文件中。4-5.输入e进行编码

10、、译码和打印编码功能。4-6.输入t打印哈夫曼树。由于哈夫曼树过于巨大，一次截屏无法完全显示，使用两次截屏。以上两幅图显示出来程序编出的哈夫曼树的形状。打印出来的图形与教科书上的常见哈夫曼树略有不同，左边的数是右边数的父节点。4-7.输入q退出程序。5. 总 结5-1、用户界面设计为“菜单”模式，使人们更加容易使用。5-2、在程序的一次执行过程中，第一次执行e命令之后，哈夫曼树已经在内存了，不必再读入。5-3.在编程中使用了很不规范的编程方法，应用了一些临时变量来实现功能，而大量临时变量在代码中没有很好地进行命名。这给程序的阅读和维护带来了极大的困难。5-4.本程序仅能对26个小写字母构成的字

11、符串进行处理，并不具有对汉字等的编码处理能力。5-5.设计中得到了老师和广大同学的帮助，并参考了网络上的优秀论文和纸质文件，使我的程序设计能够较为顺利的进行下去。在此我衷心感谢我的老师同学和对以上资源的作者。五、心得体会通过这次课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环，最后的解决

12、方式是把main函数里的一个dowhile循环去掉。在程序中，我还另外加了一个功能-输出哈夫曼树的存储结构的初态和终态。这使得我更加的明白了哈夫曼到底是怎么存储信息的。6. 参考文献 A：书籍资料 1 严蔚敏 吴伟民数据结构（C语言版）北京：清华大学出版社2 苏仕华 数据结构 课程设计 北京：机械工业出版社B：网络资料1 哈夫曼编/译码器(课程设计)2 哈夫曼编码附录 程序源代码 /哈夫曼编/译码器(课程设计) 2008/5/21#include <iostream.h>#include <fstream.h>#include <iomanip.h>#inc

13、lude <string.h>#include <malloc.h>#include <stdio.h>#include <iomanip.h> const int UINT_MAX=10000;typedef struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; /动态分配数组存储赫夫曼树  typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表/-全局变量-HuffmanTree HT;HuffmanCode HC;

14、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为不小于可能的值 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(HuffmanTre

15、e 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.12-void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; int c,f; HuffmanTree p; cha

16、r *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->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最小的两个结点,

17、其序号分别为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)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1='0' / 编码结束符 for(i=1;i<=n

18、;i+) / 逐个字符求赫夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间/-初始化赫夫曼链表-void Initiali

19、zation() flag=1; int num2; cout<<"下面初始化赫夫曼链表"<<endl; w=(int*)malloc(n*sizeof(int); / 为第26个字符权值分配空间 z=(char*)malloc(n*sizeof(char); / 为第26个字符分配空间 cout<<"n依次显示"<<n<<"个字符与其权值和编码n"<<endl; char base2;/?ifstream fin("abc.txt"); fo

20、r(i=0;i<n;i+) fin>>base; *(z+i)=*base;/? fin>>num2;/上面123行 *(w+i)=num2; HuffmanCoding(HT,HC,w,n); /-打印编码- cout<<"字符"<<setw(6)<<"权值"<<setw(11)<<"编码"<<endl; for(i=1;i<=n;i+) cout<<setw(3)<<*(z+i-1); cout<

21、;<setw(6)<<*(w+i-1)<<setw(12)<<HCi<<endl; /-将赫夫曼编码写入文件- cout<<"下面将赫夫曼编码写入文件"<<endl<<"."<<endl; FILE *htmTree; char r=' ','0' if(htmTree=fopen("htmTree.txt","w")=NULL) cout<<"不能打开文件 &

22、quot;<<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=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<

23、endl<<endl;/-获取报文并写入文件-void InputCode() FILE *tobetran; char str100; if(tobetran=fopen("tobetran.txt","w")=NULL) cout<<"不能打开文件"<<endl; return; cout<<"请输入你想要编码的字符"<<endl; /字符个数应当小于100 gets(str); fputs(str,tobetran); cout<<&qu

24、ot;获取报文成功"<<endl; fclose(tobetran);cout<<"."<<endl<"报文存入根目录下的tobetran.txt文件中"<<endl;/-编码函数-void Encoding() cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl; FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","

25、rb")=NULL) cout<<"不能打开文件"<<endl; if(codefile=fopen("codefile.txt","wb")=NULL) cout<<"不能打开文件"<<endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) cout<<"不能打开文件"

26、<<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) cout<<"字符错误，无法编码!"<<endl; break; cout<<"编码完成"<<endl；cout<<"编码写入目录下的codefile.txt中"<<endl<<endl; fclo

27、se(tobetran); fclose(codefile); free(tran);/-译码函数-void Decoding() cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("Textfile.txt","w")=NULL) cout<<"不能打开文件"<<endl; txtfile=fopen("Textfile.txt"

28、,"w"); if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; codef=fopen("codefile.txt","r"); char *work,*work2,i2; int i4=0,i,i3; unsigned long length=10000; work=(char*)malloc(length*sizeof(char); fgets(work,length,c

29、odef); 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(i2='0') i3=HTi3.lchild; else if(i2='1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile); cout&l

30、t;<"译码完成"<<endl；cout<<"内容写入根目录下的文件textfile.txt中"<<endl<<endl; free(work); /释放工作区 free(work2); /释放工作区 fclose(txtfile); /关闭文件txtfile.txt fclose(codef); /关闭文件codef.txt/-打印编码的函数-void Code_printing() cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<

31、;endl; FILE * CodePrin,* codefile; if(CodePrin=fopen("CodePrin.txt","w")=NULL) cout<<"不能打开文件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; return; char *work3; work3=(char*)malloc(

32、51*sizeof(char);if(fgets(work3,51,codefile)=NULL) cout<<"不能读取文件"<<endl; else do fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50&&fgets(work3,51,codefile)!=NULL); free(work3); cout<<"打印结束"<<endl<<endl; fclose(CodePrin); fclose(codef

33、ile);/-打印赫夫曼树的函数-void coprint(HuffmanTree start,HuffmanTree HT) /start=ht+26这是一个递归算法 if(start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePrint.txt","a")=NULL) cout<<"创建文件失败"<<endl; return; numb+; /number=0 该变量为已被声明为全局变量 coprint(HT+start->rchild,HT); /

34、递归先序遍历 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+26 cout<<"下面打印赫夫曼树"<<endl; coprint(p,HT); /p=HT+26 cout<<"打印工作结束"<<