赫夫曼编译码器数据结构设计

赫夫曼编\译码器摘要本次课程设计过程中我主要根据课本中的实现思想及算法编写程序，体现以课本知识的应用为主，在学习了线性表、栈、队列、二叉树、树和图等结构的基础上，以能够更加熟练的应用所学知识，并能结合一些著名算法来实现对一些实际问题的应用，例如，赫夫曼树等，从而更为深刻理解数据结构的内涵，熟悉它们各自的应用场合及方法。有些在平时课程中并没有掌握的内容在这次课程设计中都是先通过看课本学懂了，然后再在课程设计中加深印象，实现算法的应用和扩展。这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。程序设计设计语言采用C++,程序运行平台为WindowsXP。赫夫曼编\译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成哈夫曼编码后进行译码。赫夫曼编译系统分为五个功能模块：原始数据载入，打印编码规则、编码、译码。以二叉树的应用为基础，包括统计信息，并通过构建赫夫曼树、对信息进行赫夫曼编码，将编码信息等存入文档。关键字数据结构栈和队列赫夫曼树赫夫曼编码目录1引言………………….11.1课程设计目的……………….11.2课程设计背景……………….11.3课程设计主要内容………….12需求分析…………….33概要设计…………43.1设计思想……………………43.2函数间的关系………………43.3数据结构与算法设计………44详细设计…………….64.1赫夫曼的主要结构…………..65调试分析…………..86测试并列出测试结果……………..96.1测试方式……………………96.2测试结果……………………..97总结………………13致谢…………………..14参考文献……………..14附录…………………..15PAGEPAGE341引言当今社会，计算机技术和通信技术已不断发展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。1.1课程设计目的本课程设计是为了让同学们了解数据结构的作用和意义。数据结构是计算机科学与技术专业、计算机信息管理与应用专业和电子商务的专业的基础课，是十分重要的课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，想要更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题，想要有效地使用计算机，充分发挥它的性能，还必须学习和掌握好数据结构的有关知识，打好数据结构这门课的扎实基础，对于学习计算机专业的其他课程，如操作系统、软件工程、编译原理、人工智能等十分有益。1.2课程设计背景当今社会，计算机技术和通信技术已不断发展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。在这信息量发达的时代，随着社会的进步，信息不断地增多和更新，为了使信息更加快速、准确有的传递。需要一个程序来完成。1.3课程设计主要内容本课程设计要求完成发送端对待传送数据的编码和接收端对传送来的数据的译码。要实现五个功能:接受原始数据、编码、译码、打印编码规则、将编码、译码存档。通过系统的提示要建立哈夫曼树并对载入的原文件进行编码，并保存到txtfile.txt文件中，同时输出到屏幕。最后将建立的赫夫曼树用某种树的储存方式储存后输出。

2需求分析一套完整的编码译码系统应该具有以下功能：（1）I：初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。并将他存于文件hfmtree.txt中。(2)E：编码（encoding）。利用已经建立好的赫夫曼树（如不在内存，则从文件hfmtree.txt中读入），对文件tobetree.txt中的正文进行编码。然后将结果存入文件codefile.txt文件中。(3)D：译码（decoding）。利用已经建立好的赫夫曼树将文件codefile.txt中的代码进行译码，将结果存入文件textfile.txt中。（4）P：印代码文件（print）。将文件codefile.txt以紧凑格式显示在终端上。每行50个代码。同时将字符形式的编码文件写入到文件codeprin.txt中。（5）T：印赫夫曼树（treeprint）。将已在内存中的赫夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的赫夫曼树写入文件treeprin.txt中。3概要设计3.1设计思想赫夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。3.2函数间的关系函数间的关系如图3.1所示：主函数主函数显示表头初始化树输入字符编码译码打印编码打印赫夫曼树选最小两个权值Select()图3.1函数间的关系3.3数据结构与算法设计赫夫曼编\译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。其主要流程图如图3.2所示。开始开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I++编码为1结束否否否右子是否为空是是否否是是是图3.2赫夫曼树编\译码器流程图4详细设计赫夫曼树编、译码设计功能如下：1．赫夫曼树抽象数据类型定义ADTHuffmanCoding{数据对象T：具有相同特性的数据元素的集合数据关系R：满足最优二叉树的关系基本操作P：Init（&t）操作结果：构造一个空赫夫曼树t。encode()操作结果：利用赫夫曼树进行编码Decode（）操作结果：利用赫夫曼树进行译码}2.主函数Voidmian（）{打印表头；While(选择项不为q){输入选择项；Switch(选择项){Casei：初始化；break;Casew：输入要编码的字符；break；Casee：编码字符；break；Cased；译码操作；break；Casep；打印代码；break；Caset；打印赫夫曼树；break；Default：输入错误，重新选择；}3.求赫夫曼编码[5]if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;//flag为标志符，为不小于可能的值t[flag].parent=1;4.建赫夫曼树HT[s1].parent=HT[s2].parent=i;//将选好的两个结点设置成有同一个双亲结点HT[i].lchild=s1;//左孩子的权值HT[i].rchild=s2;//右孩子的权值HT[i].weight=HT[s1].weight+HT[s2].weight;//将两个权值相加作为新的权值}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//为赫夫曼代码分配空间5.将赫夫曼编码写入文件用fputs(HC[i],htmTree);fputs(r,htmTree);fclose(htmTree)这些函数来实现编码写入文件;6.完成译码功能并将译码写入文件因为赫夫曼树建好后是左孩子结点旁标上0，右孩子结点上标上1所以碰到1是用左孩子结点，2是用右孩子结点，可以用条件语句来实现。if(i2=='0')m=HT[m].lchild;if(i2=='1')m=HT[m].rchild;fputs(outext,txtfile);//将译码写入文件5调试分析1．本程序要执行首先要初始化一个赫夫曼树，按照用户设定的字符集大小，输入每个字符及其对应的出现概率即权值。分别存放在w和z这两个变量中。再利用这两个变量构造赫夫曼树。2．执行输入字符命令时，程序将用户输入的字符存入文件tobetran.txt中。以便执行下一步编码操作时自己从文件调用。3．编码时，程序直接从tobetran.txt中读取字符，依次和字符数组变量z中元素项比较，找到之后，将编码表HC中对应编号的代码添加到分配的工作区间中，全部字符编码完成后将代码写入文件codefile.txt中。4．译码时，程序从codefile中读取代码，按照代码从树根开始向叶子节点查找对应的字符，直到全部代码译码完成，再将译好的字符写入文件txtfile.txt中5．打印编码操作，即从codefile.txt中读取代码，按要求输出到屏幕上。6测试并列出测试结果6.1测试方式1．程序运行环境为DOS，执行文件为：胡江英的程序设计.exe2．程序运行后，出现的界面如图6.1所示：图6.1界面图3．首先须进行初始化，按“i”执行，输入字符集数，对应的字符和权值，初始化赫夫曼树。然后才能进行后续的操作。4．选择“w”，输入要编码的字符。5．选择“e”，对刚输入的字符进行编码。6．选择“d”，对刚编码出的代码再译码回去。7．选择“p”，打印编码出的代码。8．选择“t”，代印赫夫曼树9．选择“q”，退出程序。6.2测试结果1.初始化的内容如表6.1所示：表6.1初始化的内容“”ABCDEFGHIJKLMN1866413223210321154757153220NOPQRSTUVWXYZ5763151485802381811612.初始化的结果如图6.2所示:图6.2初始化的结果3.将字符对应编码写入htmtree.txt,如图6.3所示：图6.3将字符写入文件4.字符对应的编码如图6.4所示：图6.4字符对应的编码5.输入要编码的字符如图6.5所示：图6.5要编码的字符6.译码：文件textfile.txt中内容：THISPROGRAMISMYFAVORIT其操作如图6.6所示：图6.6译码操作7.打印赫夫曼树如图6.7所示：图6.7赫夫曼树7总结通过将近两周的课设练习，认识到知识的迁移运用，理论应用实际和相互间的密切联系，感受到理论知识的重要，在今后的学习中一定会更加努力，认真。体会到自己知识有所缺乏，和个人能力的有限，只有通过同学、老师间的密切配合才能完成一项不错的工作。从中也体会到了学习中的乐趣，可以自由的创作自己喜欢的东西并自己调试。致谢在课程设计过程中遇到了很多问题，不过在陈倩诒老师和和同学们的帮助下大部分都得以解决，首先要对他们表示感谢。同时，我们也要感谢学校为我们提供了大量的图书，通过看书我们也学到了很多课堂上学不到的东西。通过此次课程设计我最大的收获是学会了自主学习，也增加了与老师和同学们的交往、增进了相互之间的感情。参考文献[1]严蔚敏，吴伟民.数据结构：C语言版.北京：清华大学出版社,1997[2]王昆仑,李红.数据结构与算法.北京：中国铁道出版社[3]周霭如，林伟健.C++程序设计基础.北京：电子工业出版社,2005[4]耿国华.数据结构.北京：高等教育出版社,2005[5]王卫东.数据结构辅导课.西安:电子科技大学出版社,2001年[6]赵文静.数据结构辅导.西安：交通大学出版社,1999年附录：#include<iostream.h>#include<iomanip.h>#include<string.h>#include<malloc.h>#include<stdio.h>//typedefintTElemType;constintUINT_MAX=1000;typedefstruct{intweight;//权值intparent,lchild,rchild;//父节点，左孩子结点，右孩子结点}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//全局变量HuffmanTreeHT;//代表赫夫曼树HuffmanCodeHC;//代表赫夫曼编码int*w,i,j,n;char*z;intflag=0;intnumb=0;//求赫夫曼编码voidline(){cout<<"\n\n";}intmin(HuffmanTreet,inti){intj,flag;intk=UINT_MAX;//取k为不小于可能的值for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;returnflag;//返回标识符}//voidselect(HuffmanTreet,inti,int&s1,int&s2){intj;s1=min(t,i);s2=min(t,i);if(s1>s2)//s1为最小的两个值中序号小的那个{j=s1;s1=s2;s2=j;}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start;intc,f;HuffmanTreep;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,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}//初始化赫夫曼链表voidinit(){//flag=1;intnum;intnum2;cout<<"下面初始化赫夫曼链表"<<endl<<"请输入结点的个数n：";cin>>num;n=num; line();w=(int*)malloc(n*sizeof(int));//weightz=(char*)malloc(n*sizeof(char));//wordcout<<"\n请依次输入"<<n<<"个字符(字符型)\n注意:必须以回车结束："<<endl;chartemp[2];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<<"第"<<i+1<<"个字符的权值:";cin>>num2;*(w+i)=num2; } //输入部分结束HuffmanCoding(HT,HC,w,n);//打印编码line(); cout<<"字符对应的编码为:"<<endl;for(i=1;i<=n;i++){//cout<<"字符"<<*(z+i-1)<<"的编码";puts(HC[i]);}//将赫夫曼编码写入文件line(); cout<<"下面将赫夫曼编码写入文件"<<endl<<""<<endl;FILE*htmTree;charr[]={'','\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(HC[i],htmTree);fputs(r,htmTree);}fclose(htmTree);cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl; }//init//获取字符并写入文件voidinputcode(){//cout<<"请输入你想要编码的字符"<<endl;FILE*virttran,*tobetran;charstr[100];if((tobetran=fopen("tobetran.txt","w"))==NULL){cout<<"不能打开文件"<<endl;return;}cout<<"请输入你想要编码的字符"<<endl;gets(str);fputs(str,tobetran);cout<<"获取字符成功"<<endl;fclose(tobetran);}//voidencode()//完成译码功能{cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl;FILE*tobetran,*codefile;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){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(HC[j],codefile); puts(HC[j]);if(j>n){cout<<"字符错误，无法编码!"<<endl;break;}}}}}cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);}//voiddecode()//完成译码功能{cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;FILE*codef,*txtfile;if((txtfile=fopen("Textfile.txt","w"))==NULL){cout<<"不能打开文件"<<endl;}if((codef=fopen("codefile.txt","r"))==NULL){cout<<"不能打开文件"<<endl;}char*tbdc,*outext,i2;intio=0,i,m;unsignedlonglength=10000;tbdc=(char*)malloc(length*sizeof(char));//分配空间fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char));//分配空间m=2*n-1;for(i=0;*(tbdc+i)!='\0';i++)//进入循环{i2=*(tbdc+i);if(HT[m].lchild==0){*(outext+io)=*(z+m-1);io++;m=2*n-1;i--;}elseif(i2=='0')m=HT[m].lchild;elseif(i2=='1')m=HT[m].rchild;}*(outext+io)='\0';fputs(outext,txtfile);cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl;free(tbdc);free(outext);fclose(txtfile);fclose(codef);}//voidprintcode()//打印代码{cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl<<"\n";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(51*sizeof(char));do{if(fgets(work3,51,codefile)==NULL){cout<<"不能读取文件"<<endl;break;}fputs(work3,CodePrin);puts(work3);}while(strlen(work3)==50);free(work3);line(); cout<<"打印工作结束"<<endl<<endl;fclose(CodePrin);fclose(codefile);}//打印赫夫曼树的函数voidcoprint(HuffmanTreestart,HuffmanTreeHT){chart='';if(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)<<start->weight<<t<<endl;fprintf(TreePrint,"%d\n",start->weight);coprint(HT+start->lchild,HT);numb--;fclose(TreePrint);}}voidprintree(HuffmanTreeHT,intw)//打印赫夫曼树{HuffmanTreep;p=HT+w;cout<<"下面打印赫夫曼树"<<endl;//输出“打印赫夫曼树”语句 line();coprint(p,HT); line();cout<<"打印工作结束"<<endl;//输出“打印工作结束”}voidprinthead(){ cout<<"===============================================================================\n";cout<<"\t数据结构\t课程设计\t计-0503杨天心29号\n"; cout<<"\n"; cout<<"\n\t\t"; cout<<"┏━━━━━━━━━━━━━━━━━━━━┓\n\t\t";cout<<"┃欢迎使用赫夫曼编码解码系统┃\n\t\t"; cout<<"┡━━━━━━━━━━━━━━━━━━━━┩\n\t\t"; cout<<"│i.初始化赫夫曼链表│\n\t\t"; cout<<"│w.编码字符│\n\t\t