数据结构哈夫曼树.doc
《数据结构哈夫曼树.doc》由会员分享,可在线阅读,更多相关《数据结构哈夫曼树.doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、如有侵权,请联系网站删除,仅供学习与交流数据结构哈夫曼树【精品文档】第 5 页数据结构实验报告1. 问题描述已知n个字符在原文中出现的频率,求它们的哈夫曼编码。2. 问题分析求哈夫曼编码,首先要根据字符出现的频率,即权值,构建哈夫曼树,然后根据哈夫曼树求出哈夫曼编码。3. 算法设计创建哈夫曼树:对n个权值,创建2n-1个节点,parent都默认为0,然后进行循环查找,每次循环都从所有节点中找出parent为0且weight最小的两个节点,序号分别为s1和s2,将s1节点和s2节点作为本节点的lchild和rchild,构建出一颗哈夫曼树,循环2n-1次,最后只剩下一颗哈夫曼树,即所要求的哈夫曼
2、树。哈夫曼编码:从叶子节点出发,寻找双亲节点,若没有则说明已经到根节点;若有双亲节点,如果本节点是双亲节点的左孩子,则编码为0,右孩子编码为1,依次寻找直到走到根节点。最后将所求编码倒序输出即为哈夫曼编码。4. 测试数据测试数据为8个字符,权值分别为:5,29,7,8,14,23,3,11。测试结果:5. 总结建立哈夫曼树的时候,是逆向构建,即先创建叶节点,再创建根节点,从下往上创建。求哈夫曼编码的时候也是一样,从叶子节点不断找该节点的根节点,直到找到该哈夫曼树的根节点。6. 附录#include #include #include #define ERROR 0#define OK 1/-赫
3、夫曼树和赫夫曼编码的存储表示-typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,* HuffmanTree;typedef char * HuffmanCode;/-赫夫曼算法-void Select(HuffmanTree HT, int n, int &min1, int &min2)unsigned int m1,m2;m1=m2=-1;/随意确定两个权值为最小for(int i=1;i=n;i+)if(m2!=-1)break;if(HTi.parent=0)if(m1=-1)m1=HT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 哈夫曼树
限制150内