赫夫曼树的实现数据结构实验报告

软件学院设计性实验报告专业：.NET年级/班级：2012—2013学年第一学期课程名称数据结构指导教师本组成员学号姓名实验地点实验时间第十二、十三、十四周项目名称哈夫曼编/译码系统的设计与实现实验类型设计性1．问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2．一个完整的系统应具有以下功能：1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；4）输出（Output）:输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data和CodeFile.data三个文件，以保证系统的通用性。一、实验目的1、掌握哈夫曼编码原理；2、熟练掌握哈夫曼树的生成方法；3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。四、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HTNode对象中的data属性，即每一个HTNode对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HTNode，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。五、实验流程①初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；②根据符号概率的大小按由大到小顺序对符号进行排序；③把概率最小的两个符号组成一个节点；④重复步骤（2）（3），直到概率和为1；⑤从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”；⑥从根节点开始，对符号进行编码；⑦译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。六、实验程序数据结构：下面是编译码系统中所用的数据结构。在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：程序中用到的头文件、类型定义及主要的函数原型如下：#includestdio.h#includemalloc.h#includestdlib.h#includestring.htypedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;unsignedcharch;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表charstr[9]={'','a','b','c','d','e','f','g','h'};intm;voidSelect(HuffmanTree&HT,inti,int&s1,int&s2){intj,min1,min2;for(j=1;j=i;j++)if(HT[j].parent==0)if(HT[j].weights1||HT[j].weights2){if(s1=s2){s1=HT[j].weight;min1=j;}else{s2=HT[j].weight;min2=j;}}s1=min1;s2=min2;}voidPrint1(HuffmanTreeHT){inti;printf(建立好的赫夫曼树的存储情况：\n);printf(存储单元字符权值双亲左孩子右孩子\n);for(i=1;i=m;i++)printf(%-4d%c%-4d%-4d%d%d\n,i,HT[i].ch,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);}voidPrint2(HuffmanCodeHC){inti;printf(各个字符的编码如下：\n);for(i=1;i=8;i++)printf(%c的编码：%s\n,str[i],HC[i]);}voidInitialzation(int*w){FILE*fp;chara;inti;intn=0;if((fp=fopen(DataFile.data,wb))==NULL){printf(cannotopenflie\n);return;}printf(请输入数据字符（a-h）以#结束:\n);a=getchar();for(i=0;a!='#';i++){fprintf(fp,%c,a);n++;switch(a){case'a':w[1]++;break;case'b':w[2]++;break;case'c':w[3]++;break;case'd':w[4]++;break;case'e':w[5]++;break;case'f':w[6]++;break;case'g':w[7]++;break;case'h':w[8]++;}a=getchar();}fclose(fp);printf(输入的字符及其权值：\n);for(i=1;i=8;i++)printf(%c,%d,str[i],w[i]);printf(\n);}voidEnCoding(HuffmanCodeHC){printf(原文为：\n);chars[100],a;inti,n=0;a=getchar();for(i=0;a!='#';i++){s[i]=a;n++;a=getchar();}printf(报文为：\n);for(i=0;in;i++){switch(s[i]){case'a':printf(%s,HC[1]);break;case'b':printf(%s,HC[2]);break;case'c':printf(%s,HC[3]);break;;case'd':printf(%s,HC[4]);break;;case'e':printf(%s,HC[5]);break;;case'f':printf(%s,HC[6]);break;;case'g':printf(%s,HC[7]);break;;case'h':printf(%s,HC[8]);}}printf(\n);}voidDe(HuffmanTreeHT){printf(报文为：\n);chars[100],a;inti,j,n=0;a=getchar();for(i=0;a!='#';i++){s[i]=a;n++;a=getchar();}for(i=1;i=m;i++)if(HT[i].parent==0)j=i;HT[0]=HT[j];printf(译文为：\n);for(i=0;in;i++)if(HT[0].lchild!=NULL&&HT[0].rchild!=NULL){if(s[i]=='0')HT[0]=HT[HT[0].lchild];if(s[i]=='1')HT[0]=HT[HT[0].rchild];}else{printf(%c,HT[0].ch);HT[0]=HT[j];i--;}printf(%c\n,HT[0].ch);}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w){//w存放n个字符的权值（均0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCinti,start,c,f;intn=8;ints1,s2;HuffmanTreep;char*cd;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1,p=HT+1,w=w+1;i=n;i++,p++,w++){p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;p-ch=str[i];}for(;i=m;i++){p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;p-ch='';p++;}printf(初始化后的赫夫曼树的存储情况：\n);printf(存储单元字符权值双亲左孩子右孩子\n);for(i=1;i=m;i++)printf(%-4d%c%-4d%-4d%d%d\n,i,HT[i].ch,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);for(i=n+1;i=m;i++)//建立赫夫曼树{//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2s1=100;s2=100;Select(HT,i-1,s1,s2);HT[s1].parent=i;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*));//分配n个字符编码的头指针向量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));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码（串）到HC}free(cd);}//HuffmanCodingvoidmain(){HuffmanTreeHT;HuffmanCodeHC;intw[9]={0},x;//存放权值for(;;){printf(\n*********************************\n);printf(1.****输入字