哈夫曼树及其操作-数据结构实验报告

./电子科技大学实验报告课程名称：数据结构与算法学生：*浩学号：*************点名序号：***指导教师：钱**实验地点：基础实验大楼实验时间：2015.5.72014-2015-2学期信息与软件工程学院实验报告<二>学生：**浩学号：*************指导教师：钱**实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—树三、实验学时：4四、实验原理：霍夫曼编码〔HuffmanCoding是一种编码方式,是一种用于无损数据压缩的熵编码〔权编码算法。1952年,DavidA.Huffman在麻省理工攻读博士时所发明的。在计算机数据处理中,霍夫曼编码使用变长编码表对源符号〔如文件中的一个字母进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特〔不是26。用普通的表示方法时,每个英文字母均占用一个字节〔byte,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度〔若根结点为0层,叶结点到根结点的路径长度为叶结点的层数。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=<W1*L1+W2*L2+W3*L3+...+Wn*Ln>,N个权值Wi〔i=1,2,...n构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li〔i=1,2,...n。可以证明霍夫曼树的WPL是最小的。五、实验目的：本实验通过编程实现赫夫曼编码算法,使学生掌握赫夫曼树的构造方法,理解树这种数据结构的应用价值,并能熟练运用C语言的指针实现构建赫夫曼二叉树,培养理论联系实际和自主学习的能力,加强对数据结构的原理理解,提高编程水平。六、实验容：〔1实现输入的英文字符串输入,并设计算法分别统计不同字符在该字符串中出现的次数,字符要区分大小写；〔2实现赫夫曼树的构建算法；〔3遍历赫夫曼生成每个字符的二进制编码；〔4显示输出每个字母的编码。七、实验器材〔设备、元器件：PC机一台,装有C或C++语言集成开发环境。八、数据结构与程序：/**********************************************************************程序名称：哈夫曼树的相关操作****程序容：生成哈夫曼树及其编码表、对字符串进行编码等****编写作者：家浩****完成时间：2015.5.15********************************************************************/#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE10000charfile_address[100];//全局通用文件地址typedefstructhnode//哈夫曼树的节点结构定义{intweight;intlchild,rchild,parent;}THNode,*TpHTree;typedefstructhuffman_code//哈夫曼编码表的元素结构定义{intweight;//编码对应的权值char*pcode;//指向编码字符串的指针}THCode,*TpHcodeTab;//*************************************************************//****声明函数//*************************************************************TpHcodeTabbuild_codesheet<TpHTreepht,intleaves_num>;//根据哈夫曼树得到编码表TpHTreecreate_huffman_tree<intweights[],intn>;//构造哈夫曼树voidselect_mintree<TpHTree,int,int*,int*>;//从森林中选择权值最小的两棵子树voiddestroy_codesheet<TpHcodeTabcodesheet,intn>;//销毁哈夫曼编码表intread_file<charfile_address[100],char*message>;//从文本文件读入字符串intcalc_freq<chartext[],int**freq,char**dict,intn>;//统计字符串text中字符出现的频率//*************************************************************//****主函数//*************************************************************intmain<void>{ inti,msg_num,choose; chars;//清空缓存 intleaves_num=0; do { TpHTreepht=NULL;//建立树根 TpHcodeTabcodesheet;//建立编码表 charmsg[MAXSIZE];//建立信息数组 int*weights=NULL;//建立频率数组 char*dict=NULL;//建立字符数组 printf<"\n""哈夫曼树\n""">; printf<"\n读取文件还是手动输入信息？\n""1：手动输入信息\n""2：读取文件\n""请选择：">; scanf<"%d",&choose>; if<choose==1> { printf<"请输入信息：\n">; scanf<"%c",&s>;//清理键盘缓存 gets<msg>; msg_num=strlen<msg>; } else { printf<"输入文件地址〔例如：F:\\\\filename.txt:\n">; scanf<"%c",&s>;//清理键盘缓存 gets<file_address>;//输入文件地址 msg_num=read_file<file_address,msg>;//读取文本文件 } leaves_num=calc_freq<msg,&weights,&dict,msg_num>;//统计文本串中的字符频率,同时得到哈夫曼树的叶节点数 pht=create_huffman_tree<weights,leaves_num>;//创建哈夫曼树 codesheet=build_codesheet<pht,leaves_num>; //构造哈夫曼编码表 printf<"\n字符频率编码表\n">; printf<"符号--频率--编码\n">; for<i=0;i<leaves_num;i++> printf<"%4c--%-3d--%-6s\n",dict[i],codesheet[i].weight,codesheet[i].pcode>; printf<"\n">; destroy_codesheet<codesheet,leaves_num>;//销毁哈夫曼编码表 if<pht> //释放所有临时空间 free<pht>; if<dict> free<dict>; if<weights> free<weights>; printf<"\n\t0：结束\n\t1：继续\n""\t请选择：">; scanf<"%d",&choose>; }while<choose>; return0;}//*************************************************************//****构造哈夫曼编码表//*************************************************************TpHcodeTabbuild_codesheet<TpHTreepht,intleaves_num>{ inti,cid,pid,cursor,len; TpHcodeTabsheet; char*pch=<char*>malloc<leaves_num+1>; if<!pch>{ printf<"申请空间失败！">; exit<0>; } memset<pch,0,<leaves_num+1>>;//清零新分配的空间 sheet=<TpHcodeTab>malloc<sizeof<THCode>*leaves_num>; if<!sheet>{ printf<"申请编码表存空间失败！">; exit<0>; } for<i=0;i<leaves_num;++i>{ sheet[i].weight=pht[i].weight; } for<i=0;i<leaves_num;++i>{ cursor=leaves_num; cid=i; pid=pht[cid].parent; while<pid!=-1>//不为根节点{ if<pht[pid].lchild==cid> pch[--cursor]='0';//左分支编码为'0' else pch[--cursor]='1';//右分支编码为'1' cid=pid; pid=pht[cid].parent; } len=leaves_num-cursor+1; sheet[i].pcode=<char*>malloc<len>; if<!sheet[i].pcode>{ printf<"为节点%d的编码申请存空间失败！",i>; exit<0>; } memset<sheet[i].pcode,0,len>; strncpy<sheet[i].pcode,&pch[cursor],strlen<&pch[cursor]>>; } free<pch>; returnsheet;}//*************************************************************//****构造哈夫曼树//*************************************************************TpHTreecreate_huffman_tree<intweights[],intn>{ TpHTreepht; intminA,minB;//用于保存权值最小的两棵子树的序号 inti,a=0; if<n<1>{ printf<"没有叶子节点！\n">; return0; } a=<2*n>-1; pht=<TpHTree>malloc<sizeof<THNode>*a>; if<!pht>{ printf<"分配数组空间失败！\n">; exit<0>; } for<i=0;i<a;++i> //哈夫曼数组初始化{ pht[i].weight=<i<n>?weights[i]:0; pht[i].lchild=-1; pht[i].rchild=-1; pht[i].parent=-1; } for<i=n;i<a;++i>{ select_mintree<pht,<i-1>,&minA,&minB>; pht[minA].parent=i; pht[minB].parent=i; pht[i].lchild=minA; pht[i].rchild=minB; pht[i].weight=pht[minA].weight+pht[minB].weight; } returnpht;}//*************************************************************//****选出权值最小的两棵子树//*************************************************************voidselect_mintree<TpHTreepht,intn,int*minA,int*minB>{ intid,min1=-1,min2=-1;//最小值,次小值 intmaxa=10000,maxb=10000; for<id=0;id<=n;id++>{ if<pht[id].parent==-1>{ if<pht[id].weight<maxa>{ min2=min1; min1=id; maxa=pht[id].weight; } elseif<pht[id].weight<maxb>{ min2=id; maxb=pht[id].weight; } } } *minA=min1; *minB=min2; return;}//*************************************************************//****销毁哈夫曼编码表//*************************************************************voiddestroy_codesheet<TpHcodeTabsheet,intn>{inti;for<i=0;i<n;++i>free<sheet[i].pcode>;free<sheet>;return;}//*************************************************************//****读取文本文件//*************************************************************intread_file<charfile_address[100],char*message>{ intstr_len;//字符串长度 FILE*pFile=NULL; pFile=fopen<file_address,"r">; //打开文件 if<!pFile> { printf<"打开文件失败!\n">; exit<0>; } else{ printf<"打开文件成功!\n">; } memset<message,0,MAXSIZE>; //清除缓冲 if<fgets<message,MAXSIZE,pFile>==NULL>{ printf<"fgetserror\n">; exit<0>; } else{ printf<"成功读取文件,容如下：\n%s\n",message>; } str_len=strlen<message>; fclose<pFile>; returnstr_len;}//*************************************************************//****统计字符出现的频率//*************************************************************intcalc_freq<chartext[],int**freq,char**dict,intn>//n为字符串长度{ inti,k; intchar_num=0; int*chars;//不同种类的字符 char*fre; //字符的出现频率 inttimes[256]={0}; for<i=0;i<n;++i> //各个字符出现的频率 times[