数据结构-哈夫曼树的实验报告

河南师范大学软件学院软件学院设计性实验报告专业：网络工程年级/班级：2013—2014学年第一学期课程名称数据结构指导教师本组成员学号姓名实验地点实验时间项目名称哈夫曼编/译码系统的设计与实现实验类型设计性一、实验目的理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。二、实验仪器或设备学院提供公共机房，1台/学生微型计算机。三、总体设计（设计原理、设计方案及流程等）1．问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2．一个完整的系统应具有以下功能：1）初始化（Initialzation）。从数据文件DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.dat中的文本进行编码形成报文，将报文写在文件Code.txt中；3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.dat中的代码进行解码形成原文，结果存入文件Textfile.txt中；4）输出（Output）:输出DataFile.dat中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.dat及其报文Code.txt；输出CodeFile.dat及其原文Textfile.txt；要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.dat、ToBeTran.dat和CodeFile.dat三个文件，以保证系统的通用性。四、实验步骤（包括主要步骤、代码分析等）1）编写C语言程序#includestring.h#includemalloc.h#includestdio.h#includeiostream.h#includemath.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0河南师范大学软件学院#defineINFEASIBLE-1typedefstruct{chardata;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,char*d,int*w,intn)//构造哈弗曼函数HT，构造编码HC{voidselect(HuffmanTreeHT,intn,int&s1,int&s2);intm,c,f,j;HuffmanTreep;inti,s1,s2,start;char*cd;m=2*n-1;//m为结点数，n为叶子数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));p=HT;p++;for(i=1;i=n;i++,p++)//将叶子的值输入HT中{p-data=d[i];//={*d,*w,0,0,0};p-weight=w[i];p-parent=0;p-lchild=0;p-rchild=0;}for(i=n+1;i=m;i++,p++)//={'#',0,0,0,0}{p-data='#';p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;}s1=1;s2=2;for(i=n+1;i=m;i++)//构建哈夫曼树{河南师范大学软件学院select(HT,i-1,s1,s2);HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;HT[s1].parent=i;HT[s2].parent=i;}HC=(HuffmanCode)malloc((n+1)*sizeof(HuffmanTree));//开辟空间，编码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]);printf(%c的编码是：,HT[i]);puts(HC[i]);}free(cd);}voidselect(HuffmanTreeHT,intn,int&s1,int&s2)//求最小两数{inti,t;s1=1;s2=2;while(HT[s1].parent!=0)s1++;while((HT[s2].parent!=0)||(s1==s2))s2++;/*for(i=1;i=n;i++)河南师范大学软件学院{if(HT[s1].weightHT[i].weight&&HT[i].parent==0&&s2!=i)s1=i;}if(HT[s1].weightHT[s2].weight){t=s1;s1=s2;s2=t;}for(i=1;i=n;i++){if(s1!=i){if(HT[s2].weightHT[i].weight&&HT[i].parent==0)s2=i;}}*/for(i=1;i=n;i++){if(s1!=i&&i!=s2){if(HT[i].weightHT[s1].weight&&HT[i].parent==0&&i!=s2){if(HT[s1].weightHT[s2].weight)s2=s1;s1=i;}elseif(HT[i].weightHT[s2].weight&&HT[i].parent==0&&s1!=i)s2=i;}}}voidtranslation(HuffmanTreeHT,intnum){charstr[20];inti,t=num;printf(请输入由0或1组成的编码：);cinstr;河南师范大学软件学院//t=HT;//t为树的指向各节点的指针for(i=0;i(strlen(str));i++){if(str[i]=='0')t=HT[t].lchild;elseif(str[i]=='1')t=HT[t].rchild;else{printf(编码输入错误);break;}if(!(HT[t].lchild&&HT[t].rchild)){printf(%c,HT[t].data);t=num;}}printf(\n);}voidmain(){voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,chard[],intw[],intn);voidtranslation(HuffmanTreeHT,intnum);HuffmanTreeHT=NULL;HuffmanCodeHC=NULL;chardata,n,*p,*d;int*w,wei,i,num;printf(pleaseintputcharacternumber:);scanf(%d,&n);d=(char*)malloc((n+1)*sizeof(char));w=(int*)malloc((n+1)*sizeof(int));printf(请输入Huffman树中的字符：\n);for(i=1;i=n;i++){cindata;d[i]=data;}printf(请输入%d次位权\n:,n);河南师范大学软件学院for(i=1;i=n;i++){cinwei;w[i]=wei;}num=2*n-1;HuffmanCoding(HT,HC,d,w,n);translation(HT,num);}2）程序分析此实验是构造哈夫曼树，求出哈夫曼编码然后输出构造哈夫曼树的算法操作时选出两棵根节点的权值最小的一颗树的左右子树，且置新树的根节点的权值为其左右子树上根节点的权值之和，根据哈夫曼树求出带权路径的算法操作是用递归调用的方法。在此实验的操作过程中要注意构造哈夫曼树的方法，因为在此操作的过程中用的的指针变量特别多，容易混淆。3）运行结果举例五、结果分析与总结1)在做这个实验时前期要做很多准备，因为这个实验操作很复杂，虽然老师已经讲过了大致构思和算法思想，课本上也有相关算法及其伪代码，但翻译成C语言的过程要注意语法等原因，所以要查找一些资料。2）对于不懂得地方要像其他同学虚心请教。3）哈夫曼编码很考验编程者的细心程度，而且涉及的问题也很复杂，培养河南师范大学软件学院了我们的细心和耐心。教师签名：年月日