哈弗曼树实验报告.doc

? 哈夫曼树及其的?应用 一、实验目的? 1．在二叉树基本操?作的基础上，掌握对二?叉树的一些其它操作的?具体实现方法。 2.?掌握构造哈夫曼树以及?哈夫曼编码的方法。 ?3、熟练掌握哈夫曼树?（最优二叉树）特征及?其应用 二、实验内容? 题目一、哈夫曼树?和哈夫曼编码： ? 从终端输入若干个?字符，统计（或指定）?字符出现的频率，将字?符出现的频率作为结点?的权值，建立哈夫曼树?，然后对各字符进行哈?夫曼编码。最后打印哈?夫曼树和对应的哈夫曼?编码。 设计要求： ?⑴ 哈夫曼殊和哈夫曼?编码的存储表示参考教?材事例 ⑵ 在程序中?构造四个子程序为 ①? int freqc?har(char *?text, HTre?e *t) //?统计字符出现的频率 ?② int crea?tehtree(HT?ree *t) //?根据字符出现的频率建?立哈夫曼树 ③ vo?id coding(?HTree *t,i?nt head_i,?char *code?)//对哈夫曼树进行?编码 ④ void ?printhtree?(HTree *t,?int head_i?,int deep,?int* path)? ///中序打印树 ? 三、实验步骤? ㈠、数据结构与核心?算法的设计描述 vo?id Frequen?t()//计算输入字?母出现的频率 voi?d Select(H?uffmanTree? HT,int i,?int s1,in?t s2) //选?择函数 voidHu?ffmanCodin?g(HuffmanT?reeHT,Huf?fmanCodeH?C,int *w,i?nt n) //?w存放n个权值, 构?造哈夫曼树p, 并求?出哈夫曼编码hc并输?出哈弗曼编码 ㈡、函?数调用及主函数设计 ?主函数 主函数 Frequent( )计算输入字母出现的频率 Select(HuffmanTree HT,int i,int s1,int s2)选择函数 HuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int *w,int n) 构造哈夫曼树p, 并求出哈夫曼编码hc 打印哈弗曼树表 ㈢ 程序调试及?运行结果分析 首先调?用Frequent(?)，计算输入字母出现?的频率，输入一串字符?串，并以字符#号结束?，运行结果如下： 然?后根据输入字符的个数?与出现的频率输入哈弗?曼所要编码的个数，然?后输入这几个字母的权?值，即出现的频率，运?行结果如下： 然?后输出哈弗曼树的建立?次序，哈弗曼树表以及?哈弗曼编码,结果如下?： ㈣ 实验总结? 通过这次实验使我掌?握了哈夫曼树与哈夫曼?码的转换。其中就是要?求的函数不能正确的写?出来，这次没按照实验?要求的函数写，弄了很?长时间也没弄出来，就?这样把几个函数放在一?起啦。 四、主要算法?流程图及程序清单 ? 1、主要算法流程?图： 主函数 主函数 开始界面 统计频率 构造哈夫曼树p 输出哈夫曼编码 打印哈弗曼树表 选择函数 主函数 输出数据 结束 2、程序?清单 #inclu?deiostrea?m.h #incl?udeiomani?p.h #incl?udestdlib?.h #inclu?destring.?h #includ?estdio.h? #define ?maxsize 10?0 struct f?requence//?统计频率 { ch?ar a;//存放字?符 int ?n; //该字符出现?的次数 }; typ?edef struc?t { unsig?ned int we?ight;// 用来?存放各个结点的权值 ? unsigned ?int parent?,lchild,rc?hild;//指向双?亲、 孩子结点的指针? }HTNode,*?HuffmanTre?e;//动态分配数组?存储赫夫曼树 typ?edef char ?**HuffmanC?ode;//动态分配?数组存储赫夫曼编码表? void Freq?uent() { ?frequence ?ch[27];//2?6个英文字母，0号位?置不存储字符，用来存?储总共的字符个数,多?次出现的只记一次 ?int i=0; ?for(;i=26?;i++)//初始化?结构体数组 { ? ch[i].n=0?; } cout?请输入各个字符?（输入#键结束输入）?：; char ?c; cinc?; bool fl?ag; while?(c!=#) ?{ i=1; ? flag=fals?e; for(;?i=ch[0].n?;i++) { ? if(c