数据结构赫夫曼编译码器.doc

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 2008 课程名称： 学 号： 姓 名： 指导教师： 2010年6月 2日年级2008班号01学号专业计算机科学与计术姓名实验名称哈弗曼编/译码器实验类型设计型综合型创新型实 验目的或要求一个完整的系统应具有以下功能：（1） I:初始化。从终端读入字符集大小n， n个字符和n个权值,建立哈弗曼树,并将它存于文件hfmTree.（2） E:编码。利用已建好的树，对文件ToBeTran中的正文进行编码，然后将结果存入CodeFile中。（3） D:译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P:印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的哈夫曼树写入文件TreePin中。（5） T:印哈弗曼树。将哈夫曼树以直观的方式显示在终端上，同时将此树写入文件TreePrint中。实验原理（算法流程）一算法流程建立HuffmanTreevoid HaffmanTree:Haffman(int weight,HaffmanTree HT)a.查找哈夫曼链表中两个权值最小的节点： b.创建哈弗曼树开始初始化哈夫曼链表且有2n-1个节点i=1Iweight=countip=p-nextfor(i=n;iParent=HT2-Parent=pp-LChild=HT1p-RChild=HT2p-weight=HT1-weight+HT2-weight结束哈夫曼编码和译码void HaffmanTree:HaffmanCode(HaffmanTree haffTree, HaffmanTree HaffCode,char ch,string s)开始将字符存入哈夫曼编码结构体数组的字符单元中if(q=q-Parent-LChild)HCi.code-HCi.start=0HCi.code-HCi.start=1p=p-nextI=n 时结束解码函数：DeCoding(char code,HFMTree HT,char str,char) s开始Root指向根节点P!=rootcodei=0p=p-LChildp=p-RChildp-LChild=NULL&p-RChild=NULLsk+=strjp=root结束二哈夫曼编码的算法 （1）字符集编码的存储结构及其算法描述 typedef struct char ch； /存储字符 char bitsn+1； /存放编码位串 CodeNode； typedef CodeNode HuffmanCoden； void CharSetHuffmanEncoding(HuffmanTree T，HuffmanCode H) /根据哈夫曼树T求哈夫曼编码表H int c，p，i;/c和p分别指示T中孩子和双亲的位置 char cdn+1； /临时存放编码 int start； /指示编码在cd中的起始位置 cdn=0； /编码结束符 for(i=0，i=0)/直至上溯到Tc是树根为止 /若Tc是Tp的左孩子，则生成代码0；否则生成代码1 cd-start=(Tp).1child=C)?0：1； c=p； /继续上溯 strcpy(Hi.bits，&cdstart)； /复制编码位串 /endfor /CharSetHuffmanEncoding三文件的编码和解码 有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，若Hi.ch=c，则将字符c转换为Hi.bits中存放的编码串。 对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点(即Tm-1)出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子Ti时便译出相应的字符Hi.ch。然后重新从根出发继续译码，直至文件结束。实验结果分析及心得体会测试数据：利用教科书例6-2中的数据调试程序，并设第1到第8个字符为 a，b，c，d，e，f，g，h。运行结果图： 运行结果分析：通过调试发现该程序满足哈弗曼树，哈弗曼编码与译码的基本要求，满足课程设计任务的基本功能与要求。在以后的学习中希望能将程序进一步优化，思想更简单明了，使程序变得更完善。心得体会通过一周的编程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。 通过对数据结构和课程设计的学习，使我们能够以问题求解方法、程序设计方法以及一些典型的数据结构算法为研究对象，分析数据对象的特征，掌握数据组织的方法和在计算机中的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，使我们初步掌握了算法的时间、空间复杂度的分析技巧，并逐步培养了良好的程序设计风格以及进行复杂程序设计的技能。数据结构一科的重要内容和主要难点是让我们理解、习惯和熟悉算法构造性思维方法。在设计过程中，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，构建最小代价生成树时，一个细微的循环控量的错误都能影响到程序的正确性，而所有的代码机制都是为一个目标的实现而运作的，所以，细致是实现算法和程序准确性必不可少的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，能有效地节约时间。成绩评定教师签名： 年 月 日（注：源码附后）#include #include #include #include #include const int UINT_MAX=1000;typedef struct int weight; /权值 int parent,lchild,rchild;HTNode,* HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表/-全局变量-HuffmanTree HT; /w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC.HuffmanCode HC;int *w,n,i,j; 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.weights2) 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; char *cd; if(n=1) return; /检测结点数是否可以构成树 m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1.i-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)malloc(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; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间/-初始化赫夫曼链表-void Initialization() flag=1; int num; int num2; cout下面初始化赫夫曼链表endlnum; n=num; w=(int*)malloc(n*sizeof(int); z=(char*)malloc(n*sizeof(char); coutn请依次输入n个字符(字符型)n注意:必须以回车结束：endl; char base2; for(i=0;in;i+) cout第i+1个字符:endl; gets(base); *(z+i)=*base; for(i=0;i=n-1;i+) coutsetw(6)*(z+i); coutn请依次输入n个权值(n注意:必须以回车结束)：endl; for(i=0;i=n-1;i+) coutendl第i+1num2; *(w+i)=num2; HuffmanCoding(HT,HC,w,n); /开始构造对应的赫夫曼树及这n个字符的赫夫曼编码/-打印编码- cout字符对应的编码为:endl; for(i=1;i=n;i+) /cout字符*(z+i-1)的编码; puts(HCi); /-将赫夫曼编码写入文件- cout下面将赫夫曼编码写入文件endl.endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) coutcan not open fileendl; return; fputs(z,htmTree); for(i=0;in+1;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中endlendl;/-获取报文并写入文件-void InputCode()/cout请输入你想要编码的字符endl;FILE *tobetran;char str100;if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打开文件endl; return;cout请输入你想要编码的字符endl;gets(str);fputs(str,tobetran);cout获取报文成功endl;fclose(tobetran);/-编码函数-void Encoding() 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); while(i=99) if(fgets(tran,100,tobetran)=NULL) cout不能打开文件endl; break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) cout字符错误，无法编码!endl; break; cout编码工作完成endl编码写入目录下的codefile.txt中endlendl; fclose(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,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,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i)!=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译码完成endl内容写入根目录下的文件txtfile.txt中endlendl;free(work);free(work2); fclose(txtfile); fclose(codef);/-打印编码的函数-void Code_printing() cout下面打印根目录下文件CodePrin.txt中编码字符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(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout不能读取文件endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3);/* int iNum=2,num=2; while(num=fscanf(codefile,%d,iNum)!=NULL) printf(%d,iNum); fprintf(CodePrin,%d,iNum); */ cout打印工作结束endlendl; fclose(CodePrin); fclose(codefile);/-打印赫夫曼树的函数-void coprint(HuffmanTree start,HuffmanTree HT) if(start!=HT) FILE * TreePrint; if(TreePrint=fopen(TreePrint.txt,a)=NULL) cout创建文件失败rchild,HT); coutsetw(