数据结构_实验报告四__赫夫曼编码的应用

1、实验课程名称 数据结构课程设计 专 业 班 级 学 生 姓 名 学 号 指 导 教 师 2012 至 2013 学年第 一 学期第 1 至 18 周目录一、 概 述21.1课程设计的背景21.2 赫夫曼树21.3 课程设计目的2二、系统分析32.1 课程设计的主要内容32.2功能设计3三、概要设计43.1 设计思想43.2 函数间的关系4四、详细设计5五、运行于测试8六、总结与心得11附录：程序代码12试验题目：赫夫曼编码的应用一、 概 述1.1课程设计的背景当下，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络传送时间已越来越引起人们的重视，赫夫曼编码正是一种运用广泛且非常有效的

2、数据压缩技术。1.2 赫夫曼树 赫夫曼编码就是利用赫夫曼树求得用于通信的二进制编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示为“0码”，指向右子树的分支表示为“1”码，取每条路径上的“0”和“1”的序列作为和各个叶子对应的字符的编码，这就是所谓的赫夫曼编码。1.3 课程设计目的本试验就是通过先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。二、系统分析2.1 课程设计的主要内容本实验要求完成发送端对等待传送数据的编码和接收端对传送来的数据的译码。要实现五个功能：接受原始数据、编码、译码、输出编码、译码存档。通过系统的提示要建立赫夫曼树并对载入的原

3、文件进行编码，并保存到txtfile.tet文件中，同时输出到屏幕。最后将建立的赫夫曼树用某种的存储方式存储后输出。 2.2功能设计（1）初始化（initialization） 从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。并将它存放于文件htmtree.tx中。 （2）编 码（encoding） 利用已经建立好的赫夫曼树（如不在内存，则从文件hfmtree.txe中读入，对文件tobetree.txt中的正文进行编码。然后将结果存在文件codefile.txt中。 （3）译 码（decoding） 利用已经建立好的赫夫曼树将文件codefile.txt中的代码进行译码，将结果

4、存入文件textfile.txt中。 （4）输出译码（print） 将文件codefile.txt以紧凑格式显示在终端上。同时将字符型式写入到文件codeprint.txt中。 （5）显示赫夫曼树（treeprint） 将已经在内存中的赫夫曼树以直观的方式显示在屏幕上，同时将此字符型的赫夫曼树写入文件treeprint.txt中。三、概要设计 3.1 设计思想 赫夫曼树用邻接矩阵来作为存储结构，借助静态链表来实现遍历。3.2 函数间的关系 四、详细设计1赫夫曼树的抽象数据类型定义ADT HuffmanCoding数据对象 T：具有相同特征的数据元素的集合数据关系 R：满足最优二叉树的关系基本操

5、作 P：Init （&t）操作结果：构造一个空赫夫曼树t。Encode（）操作结果：利用赫夫曼树进行编码Decode（）操作结果：利用赫夫曼进行译码2主函数void mian（）打印表头：while（选择选项不为0）输入选项：switch(选择项)case 1：初始化；break；case 2：输入编码字符；break；case 3：编码字符；break；case 4：译码操作；break；case 5：输出译码；break；case 6：显示赫夫曼树；break；default ：输入错误，重新选择；3求赫夫曼编码if(tj.weight<k&&tj.paren

6、t=0) k=tj.weight,flag=j; /flag为标志符，为不小于可能的值tflag.parent=1;4新建赫夫曼树HTs1.parent=HTs2.parent=i;/将选好的两个结点设置成有同一个双亲结点 HTi.lchild=s1;/左孩子的权值 HTi.rchild=s2;/右孩子的权值HTi.weight=HTs1.weight+HTs2.weight;/将两个权值相加作为新的权值 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/为赫夫曼代码分配空间5将赫夫曼编码写入文件用fputs(HCi,htmTree); fputs(r,ht

7、mTree);fclose(htmTree) 这些函数来实现编码写入文件;6完成译码功能并将译码写入文件因为赫夫曼树建好后是左孩子结点旁标上0，右孩子结点上标上1 所以碰到1是用左孩子结点，2是用右孩子结点，可以用条件语句来实现。 if(i2='0') m=HTm.lchild; if(i2='1') m=HTm.rchild; fputs(outext,txtfile);/将译码写入文件五、运行于测试1.程序运行后，出现如下主界面：2.执行其它操作之前必须进行初始化，选择“1”执行，并输入结点数3.依次按提示输入字符集并输入相应的权值,输入后会自动写入根目录下

8、htmTree.txt文件中。4输入要编码的字符，如下图：6编码，对目录下tobetran.txt文件进行编码，编码完成后将写入目录下codefile.txt文件中。7.译码，即对目录下codefile.txt文件中的字符进行译码，译码完成后，内容将会被写入到目录下txtfile.txt文件中。 8输出译码，即将CodePrint.txt中的编码字符。9显示赫夫曼树：六、总结与心得 通过两个学期对数据结构课程设计的学习，从中认识到怎样将知识迁移运用，深刻的知道了理论应用和实际相互间的密切联系，感受到了理论知识的重要，在今后的学习中一定会更加努力，认真，并且将理论与实践相结合。在做这个课程设计论

9、文的时候，我遇到过许多的问题，比如说，写程序以及调试程序时，有很多地方的错误都搞不懂，不过在同学的帮助下，我成功的调试出了程序，并运行出了结果，当时我感觉非常有成就感。还有就是论文格式上，之前都没有学习过，不过通过老师讲解以及网上百度，最终我还是把它搞懂了，总之，觉得这门课程我收获了很多课堂外不能学到的东西。非常让我受益匪浅！ 通过这门课程的学习，我也确实体会到了自己的知识还有很多不足之处和个人能力的十分有限，只有通过同学、老师间的密切配合才能完成一项不错的工作。 不过从中我也体会到了在学习中也有无限的乐趣，可以将现实生活中某一问题用程序编写出来并将以调试，得出结果。 在这里也要感谢老师和同学

10、们对我的帮助，有你们的帮助，我才会学得更好。附录：程序代码#include <iostream.h> #include <iomanip.h> #include <string.h> #include <malloc.h>#include <stdio.h> typedef int TElemType; const int UINT_MAX=999;typedef struct int weight; /权值 int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点 HTNode,* HuffmanTree

11、; typedef char *HuffmanCode; /-全局变量- HuffmanTree HT; /代表赫夫曼树 HuffmanCode HC; /代表赫夫曼编码 int *w,i,j,n; char *z; int flag=0; int numb=0; / -求赫夫曼编码- void line()cout<<"n=n" int min(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; / 取k为不小于可能的值 for(j=1;j<=i;j+) if(tj.weight<k&&

12、tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag; /返回标识符 /- void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); s2=min(t,i); if(s1>s2)/ s1为最小的两个值中序号小的那个 j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,s

13、tart; 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->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) / 建赫夫曼树 select(HT,i-1,

14、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*); 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)

15、cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); /-初始化赫夫曼链表- void init() flag=1; int num; int num2; cout<<"赫夫曼链表初始化完成 !"<<endl<<"=n"<<"请输入结点数：" cin>>num; n=num; line

16、(); w=(int*)malloc(n*sizeof(int);/weight z=(char*)malloc(n*sizeof(char);/word cout<<"n请依次输入"<<n<<"个字符(字符型)n按Enter结束：<<endl; char temp2; line(); for(i=0;i<n;i+) cout<<"第"<<i+1<<"个字符:"<<endl; gets(temp); *(z+i)=*temp

17、; line(); for(i=0;i<=n-1;i+) cout<<setw(6)<<*(z+i); line(); cout<<"n请依次输入"<<n<<"个权值n按Enter结束："<<endl; line(); for(i=0;i<=n-1;i+) cout<<endl<<"第"<<i+1<<"个字符的权值:" cin>>num2; *(w+i)=num2; /输入

18、部分结束- HuffmanCoding(HT,HC,w,n); line(); cout<<"字符对应的编码为:"<<endl; for(i=1;i<=n;i+) /cout<<"字符"<<*(z+i-1)<<"的编码" puts(HCi); /-将赫夫曼编码写入文件- line(); /cout<<"下面将赫夫曼编码写入文件"<<endl<<"."<<endl; FILE *htm

19、Tree; char r=' ','0' if(htmTree=fopen("htmTree.txt","w")=NULL) cout<<"文件打开失败"<<endl; return; fputs(z,htmTree); for(i=0;i<n+1;i+) fprintf(htmTree,"%6d",*(w+i); fputs(r,htmTree); for(i=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmT

20、ree); fclose(htmTree); cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl; /init /-获取字符并写入文件- void inputcode() /cout<<"请输入你想要编码的字符"<<endl; FILE *virttran,*tobetran; char str100; if(tobetran=fopen("tobetran.txt","w")=NULL) cout<&

21、lt;"不能打开文件"<<endl; return; cout<<"请输入你想要编码的字符"<<endl; gets(str); fputs(str,tobetran); cout<<"获取字符成功"<<endl; fclose(tobetran); void encode() /完成译码功能 cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl; FILE *tobetran,*codefile;

22、if(tobetran=fopen("tobetran.txt","rb")=NULL) cout<<"不能打开文件"<<endl; if(codefile=fopen("codefile.txt","wb")=NULL) cout<<"不能打开文件"<<endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); /为tuan分配100个字节 while(i=99)

23、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); puts(HCj); if(j>n) cout<<"字符错误，无法编码!"<<endl; break; cout<<"编码工作完成"<<end

24、l<<"编码写入目录下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose(codefile); free(tran); void decode() /完成译码功能 cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("Textfile.txt","w")=NULL) cout<&l

25、t;"不能打开文件"<<endl; if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; char *tbdc,*outext,i2; int io=0,i,m; unsigned long length=10000; tbdc=(char*)malloc(length*sizeof(char); /分配空间 fgets(tbdc,length,codef); outext=(char*)malloc(le

26、ngth*sizeof(char); /分配空间 m=2*n-1; for(i=0;*(tbdc+i)!='0'i+) /进入循环 i2=*(tbdc+i); if(HTm.lchild=0) *(outext+io)=*(z+m-1); io+; m=2*n-1; i-; else if(i2='0') m=HTm.lchild; else if(i2='1') m=HTm.rchild; *(outext+io)='0' fputs(outext,txtfile); cout<<"译码完成"&l

27、t;<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl; free(tbdc); free(outext); fclose(txtfile); fclose(codef); void printcode() /打印代码 cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl<<"=n" FILE * CodePrin,* codefile; if(CodePrin=fopen("Co

28、dePrin.txt","w")=NULL) cout<<"不能打开文件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout<

29、;<"不能读取文件"<<endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); line(); cout<<"打印工作结束"<<endl<<endl; fclose(CodePrin); fclose(codefile); /-打印赫夫曼树的函数- void coprint(HuffmanTree start,HuffmanTree HT) char t=' ' if(

30、start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePrint.txt","a")=NULL) cout<<"创建文件失败"<<endl; return; numb+;/该变量为已被声明为全局变量 coprint(HT+start->rchild,HT); if(start->lchild!=NULL&&start->rchild!=NULL) t='<' cout<<setw(5*numb

31、)<<start->weight<<t<<endl; fprintf(TreePrint,"%dn",start->weight); coprint(HT+start->lchild,HT); numb-; fclose(TreePrint); void printree(HuffmanTree HT,int w) /打印赫夫曼树 HuffmanTree p; p=HT+w; cout<<"下面打印赫夫曼树"<<endl; / 输出“打印赫夫曼树”语句 line(); copr

32、int(p,HT); line(); cout<<"打印工作结束"<<endl; /输出“打印工作结束” void printhead() cout<<"ntt" cout<<"*ntt" cout<<" 欢迎使用赫夫曼编、译码系统 ntt" cout<<"*ntt" cout<<" 1.初始化赫夫曼链表 ntt" cout<<" 2.输入编码字符 ntt" c

33、out<<" 3.编 码 ntt" cout<<" 4.译 码 ntt" cout<<" 5.输出译码 ntt" cout<<" 6.显示赫夫曼树 ntt" cout<<" 0.退 出 ntt" cout<<" nt " cout<<"*n" if(flag=0)cout<<"n请先输入'1'初始化赫夫曼链表"<<

34、endl<<"n" cout<<"请选择你要进行的操作:" /*2主程序*/ void main() char choice; while(choice!='0') printhead(); cin>>choice; switch(choice) case '1': init(); /按下i则进行初始化赫夫曼链表, break; case '2': /按下2编码字符 inputcode(); break; case '3': /按下3编码 encode()

35、; break; case '4': /按下4译码 decode(); break; case '5': /按下5输出译码 printcode(); break; case '6': /按下6显示赫夫曼树 printree(HT,2*n-1); break; case '0': /按下0退出 break; default: cout<<"输入错误，请重新选择"<<endl; free(z); /释放z结点 free(w); /释放w结点 free(HT); /释放HT结点 实验完成情况：

36、完成 基本完成 未完成 #include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>/typedef int TElemType;const int UINT_MAX=1000;typedef struct int weight; /权值 int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点HTNode,* HuffmanTree;typedef char *Huffma

37、nCode;/-全局变量-HuffmanTree HT; /代表哈夫曼树HuffmanCode HC; /代表哈夫曼编码int *w,i,j,n;char *z;int flag=0;int numb=0;/ -求哈夫曼编码-void line()cout<<"n-n"int min(HuffmanTree t,int i) 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;

38、 tflag.parent=1; return flag; /返回标识符/-void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); s2=min(t,i); if(s1>s2)/ s1为最小的两个值中序号小的那个 j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTree p; char

39、 *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) / 建哈夫曼树 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i;

40、 HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); 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' else cd-start

41、='1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd);/-初始化哈夫曼链表-void init() /- flag=1; int num; int num2; cout<<"下面初始化哈夫曼链表"<<endl<<"请输入结点的个数n：" cin>>num; n=num;line(); w=(int*)malloc(n*sizeof(int);/weight z=(char*)mallo

42、c(n*sizeof(char);/word cout<<"n请依次输入"<<n<<"个字符(字符型)n注意:必须以回车结束："<<endl; char temp2; line();for(i=0;i<n;i+) cout<<"第"<<i+1<<"个字符:"<<endl; gets(temp); *(z+i)=*temp; line();for(i=0;i<=n-1;i+) cout<<setw(6)<<*(z+i); line();cout<<"n请依次输入"<<n<<"个权值(n注意:必须以回车结束)："<<endl; line();for(i=0;i<=n-1;i+) cout<<endl<<&