没有合适的资源?快使用搜索试试~ 我知道了~
哈夫曼树实验报告.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 76 浏览量
2021-10-10
20:16:12
上传
评论
收藏 96KB DOC 举报
温馨提示
试读
14页
哈夫曼树实验报告.doc
资源推荐
资源详情
资源评论
.. -
数据构造实验报告
实验名称:实验三哈夫曼树
学生:
班 级:
班序号:
学 号:
日 期:
程序分析:
2.1 存储构造:二叉树
2.2 程序流程:
template <class T>
class BiTree
{
public:
BiTree(); //构造函数,其前序序列由键盘输入
~BiTree(void); //析构函数
BiNode<T>* Getroot(); //获得指向根结点的指针
protected:
BiNode<T> *root; //指向根结点的头指针
};
//声明类 BiTree 及定义构造 BiNode
Data:
二叉树是由一个根结点和两棵互不相交的左右子树构成
二叉树中的结点具有一样数据类型及层次关系
. . word.zl-
.. -
示意图: root
lchild parent rchild
哈夫曼树类的数据域,继承节点类型为 int 的二叉树
class Hu'manTree:public BiTree<int>
data:
HCode* HCodeTable;//编码表
int tSize; //编码表中的总字符数
二叉树的节点构造
template <class T>
struct BiNode //二叉树的结点构造
{
T data; //记录数据
T lchild; //左孩子
T rchild; //右孩子
T parent; //双亲
};
示意图:
编码表的节点构造
struct HCode
{
char data; //编码表中的字符
char code[100]; //该字符对应的编码
};
示意图:
待编码字符串由键盘输入,输入时用链表存储,链表节点为
struct Node
{
char character; //输入的字符
unsigned int count;//该字符的权值
. . word.zl-
T data T lchild T rchild T parent
char data char code[100]
.. -
bool used; //建立树的时候该字符是否使用过
Node* next; //保存下一个节点的地址
};
示意图:
2.3 关键算法分析:
1.初始化函数〔void HumanTree::Init(string Input)〕
算法伪代码:
1.初始化链表的头结点
2.获得输入字符串的第一个字符,并将其插入到链表尾部,n=1(n 记录的是
链表中字符的个数)
3.从字符串第 2 个字符开场,逐个取出字符串中的字符
3.1 将当前取出的字符与链表中已经存在的字符逐个比拟,如果当前取出
的字符与链表中已经存在的某个字符一样,那么链表中该字符的权值加
1。
3.2 如果当前取出的字符与链表中已经存在的字符都不一样,那么将其参
加到链表尾部,同时 n++
4.tSize=n(tSize 记录链表中字符总数,即哈夫曼树中叶子节点总数)
5.创立哈夫曼树
6.销毁链表
源代码:
void Hu'manTree::Init(string Input)
{
Node *front=new Node; //初始化链表的头结点
if(!front)
throw exception("堆空间用尽");
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //获得第一个字符
Node* New1=new Node;
if(!New1)
throw exception("堆空间用尽");
New1->character=ch; //将第一个字符插入链表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符一样的
. . word.zl-
char character unsigned int count bool used Node* next
剩余13页未读,继续阅读
资源评论
wsbhm62
- 粉丝: 7
- 资源: 22万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功