文档介绍：设计性综合性实验实验课题名称:静态查找院系:数统专业:数应双学位课程:数据结构 教师:焦翠珍学号:103122001姓名:刘纯德(组长)任务:哈夫曼树静态查找学号:103122011姓名:张琛玉任务:队列实现学号:103122012姓名:胡云鹏任务:AOE网关键路径学号:103122013姓名:黄开杰任务:线性表实现2011至2012学年度第一学期实验名称:哈夫曼树实验性质: 设计性(*) 综合性(*)实验器材:PC机并装有VC++:熟悉哈夫曼树,哈夫曼编码应用实验任务:描述哈夫曼问题,设计思路,构造哈夫曼树,求得哈夫曼编码,调试运行并进行算法分析。实验内容、过程及结果:问题描述在数据传送时,需要将字符转换为二进制的字符串。例如,假设要传送的电文是ABDAACDA,电文中有A、B、C、D四种字符,如果规定A、B、C和D的编码分别为00、01、10和11,则上面的电文代码为00011**********,总共16个二进制数。在传送电文时,要求电文的代码尽可能的短。如果按照每个字符进行长度不等进行编码,将出现频率高的字符采用尽可能短的编码,则电文的代码长度就会减少。设计思路哈夫曼编码常应用于数据通信中,可以利用哈夫曼树对电文进行编码,假设需要编码的字符集合为{c1,c2,…cn},相应的,字符在电文中的出现次数为{w1,w2,…wn},以字符c1,作为叶子结点,以w1,w2,…wn为对应叶子结点的权值构造一颗二叉树,规定哈夫曼树的左孩子分支为0,右孩子分支为1,从根结点到每个叶子结点经过的分支组成的0和1序列就是结点对应的编码。定义一个类型为HuffmanCode的变量HT,用来存放每一个叶子结点的哈夫曼编码。初始时,将每一个叶子结点的双亲结点域、,则非叶子结点有n-1个,所以总共结点数是2*n-1个。同时也要将剩下的n-1个双亲结点域初始化为0,依次选择两个权值最小的结点,分别作为左子树结点和右子树结点,修改它们的双亲结点域,使他们指向同一个双亲结点,同时修改双亲结点的权值,使其等于两个左、右子树结点权值的和,并修改左、右孩子结点域,使其分别指向左、右孩子结点。重复执行以上操作n-1次,即求出n-1个非叶子结点的权值。这样就得到了一颗哈夫曼树。解决问题假设一个字符序列为{A,B,C,D},对应的权值为{1,3,6,9}。设计一个哈夫曼树,并输出相应的哈夫曼编码。在实现哈夫曼的算法时,为了设计的方便,利用一个二维数组实现。需要保存字符的权重、双亲结点的位置、左孩子结点位置和右孩子结点位置,因此需要设计n行四列。、voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)初始化哈夫曼树,处理InputHuffman(HuffmanHfm)函数得到的数据,按照哈夫曼规则建立2叉树。此函数块调用了Select()函数。2、voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函数,选出HT树到a为止,权值最小且parent为0的2个节点2、intmain()主函数:利用已建好的哈夫曼树(如不在内存,)对文件中的正文进行编码,。如果正文中没有要编码的字符,则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容,将编码好的哈夫曼编码存储到CodeFile中。3、Encoding编码功能:对输入字符进行编码4、Decoding译码功能:,。Print()打印功能函数:输出哈夫曼树,字符,权值,以及它对应的编码。,主函数主要设计的是一个分支语句,,然后分别调用统计频数函数,排序函数,建立哈夫曼函数,编码函数,译码函数来实现功能。下面是源代码:/*包含头文件*/#include<>#include<>#include<>#include<>#defineinfinity10000 /*定义一个无限大的值*//*哈夫曼树类型定义*/typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchi