哈弗曼树实验报告.doc

哈夫曼树及其的应用一、,掌握对二叉树的一些其它操作的具体实现方法。。3、熟练掌握哈夫曼树(最优二叉树)特征及其应用二、实验内容题目一、哈夫曼树和哈夫曼编码:从终端输入若干个字符,统计(或指定)字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。设计要求:⑴哈夫曼殊和哈夫曼编码的存储表示参考教材事例⑵在程序中构造四个子程序为①intfreqchar(char*text,HTree*t)//统计字符出现的频率②intcreatehtree(HTree*t)//根据字符出现的频率建立哈夫曼树③voidcoding(HTree*t,inthead_i,char*code)//对哈夫曼树进行编码④voidprinthtree(HTree*t,inthead_i,intdeep,int*path)///中序打印树三、实验步骤㈠、数据结构与核心算法的设计描述voidFrequent()//计算输入字母出现的频率voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)//选择函数voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//w存放n个权值,构造哈夫曼树p,并求出哈夫曼编码hc并输出哈弗曼编码㈡、函数调用及主函数设计主函数Frequent()计算输入字母出现的频率Select(HuffmanTreeHT,inti,int&s1,int&s2)选择函数HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)构造哈夫曼树p,并求出哈夫曼编码hc打印哈弗曼树表㈢程序调试及运行结果分析首先调用Frequent(),计算输入字母出现的频率,输入一串字符串,并以字符#号结束,运行结果如下:然后根据输入字符的个数与出现的频率输入哈弗曼所要编码的个数,然后输入这几个字母的权值,即出现的频率,运行结果如下:然后输出哈弗曼树的建立次序,哈弗曼树表以及哈弗曼编码,结果如下:㈣实验总结通过这次实验使我掌握了哈夫曼树与哈夫曼码的转换。其中就是要求的函数不能正确的写出来,这次没按照实验要求的函数写,弄了很长时间也没弄出来,就这样把几个函数放在一起啦。四、主要算法流程图及程序清单1、主要算法流程图:主函数开始界面统计频率构造哈夫曼树p输出哈夫曼编码打印哈弗曼树表选择函数主函数输出数据结束2、程序清单#include<>#include<>#include<>#include<>#include<>#definemaxsize100structfrequence//统计频率{ chara;//存放字符intn; //该字符出现的次数};typedefstruct{ unsignedintweight;//用来存放各个结点的权值 unsignedintparent,lchild,rchild;//指向双亲、孩子结点的指针}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar*