数据结构实验报告.doc

一、 课题的主要功能1、程序的功能 首先，这里介绍一下在赫夫曼的来源及原理。 赫夫曼的来源：传送电文时，希望总长尽可能地短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。如果设计A、 B、C、D的编码分别为0、00、1和01，则上述七个字符的电文可转换成总长为9的字符串000011010。但是，这样的电文无法翻译，例如传送过去的字符串中前四个字符的子串，0000就可有多种译法，或是AAAA，或是ABA，也可以是BB，等。因此，若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。 赫夫曼的原理：可以利用二叉树来设计二进制的前缀编码。假设有一棵如图6.25所示的二叉树，其四个叶子结点分别表示A、B、C、D四个字符，且约定左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。读者可以证明，如此得到的必为二进制前缀编码。如由图1所得A、B、C、D的二进制前缀编码分别为0、10、110和111。A 0 1B 1 0 CD 0 1 图1假设每种字符在电文中出现的次数为wi；，其编码长度为li，电文中只有n种字符，则电文总长为wili。对应到二叉树上，若置wi为叶子结点的权，li恰为从根到叶子的路径长度。则wili恰为二叉树上带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。 而本程序的功能就是：对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。2、输入输出的要求： 首先要求输出一个用户界面，让用户好进行操作。其次，用户如果想实现赫夫曼编码就必须先初始化，键盘输入字符集大小n，n个字符和n个权植，程序将根据用户输入建立赫夫曼树。求树中两个结点之间的路径，由于赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫磁共振夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。因为在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需知孩子结点的信息。然后可以选择输出编码和译码，并保存到文件夹 其中字符和频度如下： 字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116二、 课题的功能模块的划分1、 程序的主要模块组成int min(HuffmanTree t,int i) 接收原始数据：从终端读入字符集大小i，n个字符和n个权值。建立赫夫曼树存于文件以供htmtree.datmitHuffman()函数调用。（2）select函数 把输入的字符权值从小到大排序，排出最小的权值供HuffmanCoding（）调用，并且根据根结点的权值等于它的左右孩子的权值和。求赫夫曼编码void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)初始哈夫曼树，处理Inputhuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数调用了select()函数。void Decoding()编码功能函数：利用已经建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入）对文件中的正文进行编码，然后将结果存入文件codefile.dat中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。void Decoding(Huffman Hfm)译码功能函数：利用以建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入textfile.dat中。void Code_printing()打印功能函数;输出哈夫曼树，字符，权值，以及对应的编码。主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树结构，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。2、 模块之间的层次结构、各模块的调用关系fput()Initialization() fclose()Inputcode()fprint()Code-printing()主函数Decoding()fprint()Code-printing()Tree-printing()copprint()copprint()3、 课题涉及的数据结构和数据库结构为了建立哈夫曼树以及实现哈夫曼编译及译码，因此我们选择了节点结构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来记录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼树构造哈夫曼树的过程，是从n颗一个根结点的树组成森林开始的。为了实现哈夫曼树的建树运算，定义程序的哈夫曼树类HfmTree,它包括如下两个私有成员tree和weight：其中，tree是一个二叉树。Weight是树的权值。三、 主要功能的实现哈夫曼编码实现C语言定义相关的数据类型int m,i,s1,s2,start;unsigned c,f;int c,f;HuffmanTree p;char *cd;模块的类C码算法if(n=1)返回检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用for(p=HT+1,i=1;i=n;+i,+p,+w)初始化哈夫曼树for(i=n+1;i=m;+i) 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2select(HT,i-1,s1,s2); 从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char); 分配求编码的工作空间 编码结束符for(i=1;iparentl.childHci.code-Hci.start=1Hci.code-Hci.start=0 p=p-next i=n 结束四、 程序调试当程序敲完后，运行时发现有很多需改善的地方，还有的是错误的。譬如当我输入结点数是1时。因为由于赫夫曼树中没有度为1的结点，所以在要求输出哈夫曼树时，就无法输出。改正后运行如下：输入i后输入字符和权值哈夫曼树五、 总结 这次课设让我感受颇多，拿到课题开始，我觉得很难入手，不知道怎么做，一点思路也没有，甚至连哈夫曼编译码器是什么东东也不清楚。后来我就拿着教材看了看熟悉一下哈夫曼编译码器的原理，并把关于哈夫曼的知识章节看了一遍。书上关于哈夫曼算法的代码很少，于是我就上网查资料，看到了一个经典的算法，于是把它弄懂，在自己稍做了些改变。在进行近一周的实验中，我感触良多，深感自己能力的不足和认识的欠缺。综观种种，我总结了几点。一、尽可能的多占有校内资源在这次实验中，我做的是哈夫曼编译码器课题。在开始的两天，在前期准备工作中，我觉得向老师咨询有用资源是很有帮助的。除此之外，我们还利用了网上资源，图书馆资源等等。二、学会思考做这次实验之前，我的思考角度一直处在被老师带着走的状态。但通过实践，分析和处理实验过程的问题、提出解决问题的方案以及实施解决过程，我感觉自己的脑子突然开阔，也许我知识领会了一点点，实验不仅仅是做出来的，也是想出来的。我长那么大，受到各种条条框框的影响，思考问题的角度和深度几乎停留在一个阶段，并且没有继续前进的趋势。但现实生活不需要这样的我。通过这次，我想我应该好好的反省自己，给自己一个更积极更全新的定位和思考。三、感谢老师在做实验中，刘老师给了我很大的帮助和鼓励。在做课设过程中，我很感动，感动于老师的亲切和关爱。 零零星星的几点，也许还不能总结为我的总结。很多来自心底的感动和心底的声音不易用语言描述，只此几笔，一带而过。 为期两周的数据结构课程设计马上就要结束了，现在我来总结一下这周课程设计的内容以及心得体会。 通过本次数据结构课程设计，也让我更加明白实践的重要性，如果整天的学习课本上的理论知识而不拿来用，那么所学的知识是很不牢固的，再者学习理论知识的目的还是要拿来运用，通过实践来巩固所学的理论知识。总之，这次数据结构课程设计让我收益匪浅，我不但收获了知识，提高了能力，而且学到了很多道理。对于今后的学习起到了很好的引导作用，学会在实践中发现问题，并及时解决，让自己更上一层楼。六、 附件原程序清单# include # include # include # include /typedef int TElemType;const int UINT_MAX=1000;typedef structint weight; /赫夫曼树的权值int parent,lchild,rchild; /树的母亲左孩子和右孩子HTNode,* HuffmanTree; /定义赫夫曼树，和赫夫曼指针typedef char *HuffmanCode;/-全局变量-HuffmanTree HT;HuffmanCode HC;int *w,i,j,n;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个字符的赫夫曼编码HCint m,i,s1,s2,start;unsigned c,f;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) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2select(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;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/ 为第i个字符编码分配空间strcpy(HCi,&cdstart); / 从cd复制编码(串)到HCfree(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);/-打印编码-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);doif(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(