文档介绍：哈夫曼树及其的应用一、实验目的 ,掌握对二叉树的一些其它操作的具体实现方法。。 3、熟练掌握哈夫曼树(最优二叉树)特征及其应用二、实验内容题目一、哈夫曼树和哈夫曼编码: 从终端输入若干个字符,统计(或指定)字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。设计要求: ⑴哈夫曼殊和哈夫曼编码的存储表示参考教材事例⑵在程序中构造四个子程序为①int freqchar (char *text, HTree *t) /*统计字符出现的频率*/ ②int createhtree(HTree *t) /* 根据字符出现的频率建立哈夫曼树*/ ③void coding(HTree *t,int head_i,char *code) /*对哈夫曼树进行编码*/ ④void printhtree(HTree *t,int head_i,int deep,int* path) /*中序打印树*/ 题目二、寻求最佳判断( ACM/ICPC 训练题) 例:试设计一个算法,用最少的比较,尽快地将 ~59 ———————————————————— bad 60~69 ———————————————————— pass 70~79 ———————————————————— general 80~89 ———————————————————— good 90~100 ———————————————————— excellent 题目三果子合并( ACM/ICPC 训练题): 有四堆果子,其数量分别是:10, 30, 15和100 ,试设计一种最佳方案,将果子合并为一堆,使得合并工作量最小。注:规定合并两堆果子的工作量是这两堆果子的数量之和。三、实验步骤㈠、数据结构与核心算法的设计描述 void Frequent()// 计算输入字母出现的频率 void Select(HuffmanTree HT,int i,int &s1,int &s2) //选择函数 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n){}w 存放 n 个权值, 构造哈夫曼树 p, 并求出哈夫曼编码 hc 并输出哈弗曼编码㈡、函数调用及主函数设计函数调用及主函数设计主函数 Frequen t()计算输入字母出现的频率 Select(Hu ffmanTree HT,int i,int &s1,int &s2) 选择函数 Huffman Coding( Huffman Tree&H T,Huffm anCode &HC,int *w,int n) 构造哈夫曼树 p, 并求出哈夫曼编码 hc 打印哈弗曼树表㈢程序调试及运行结果分析首先调用 Frequent() ,计算输入字母出现的频率,输入一串字符串,并以字符#号结束,运行结果如下: 然后根据输入字符的个数与出现的频率输入哈弗曼所要编码的个数,然后输入这几个字母的权值,即出现的频率,运行结果如下: 然后输出哈弗曼树的建立次序,哈弗曼树表以及哈弗曼编码, 结果如下: ㈣实验总结通过这次实验使我掌握了哈夫曼树与哈夫曼码的转换。对