没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
哈夫曼编译码器
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,这要求在发送端通过一个编码系统对待传输预先编码,在接收端将传来的数据进行译码。对于双工通道,每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、概要设计
1. 哈夫曼树的定义:
在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。
2.哈夫曼树的构造:
假设有N个权值,则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1,W2,……….Wn,则哈夫曼树的构造规则为:
(1) 将W1,W2,……….Wn看成有N棵树的森林;
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左,右子树,且新树的根结点为其左,右子树结点权值之和;
(3) 从森林中删除选取取的两面三刀棵树,并将新树加入森林;
(4) 重复(2)(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。
在构造哈夫曼树的过程中,每次由两棵权值最小的树生成一棵新树时,新树的左子树和右子树可以任意安排,这样将会得到具有不同结构的多个哈夫曼树,但字们都具有相同的带权路径长度。为了歙 得到的哈夫曼树的结构尽量唯一,通常规定生成的哈夫曼树中每个结点的左子树根结点的权要小于等于右女树根结点的权。
3.构造哈夫曼树的算法实现:
假设哈夫曼树采用双亲孩子表示法存储,并增加权值域,构造哈夫曼树的叶子结点(树木的权)有N个,合并次数为N―1次,则森林中总共有2N―1棵树,(包含合并后删除的)。 存储结构描述为:
const int n=maxn //maxn表示叶子数目
const int m=2*n-1 //m为森林中树的棵数
class tree
{ public:
float weight; //权值
int parent; //双亲
int lch, rch; //左,右孩子
}
tree hftree[m+1]; //规定从第一个元素hftree[1]开始使用数组元素,故定义长度为m+1而不为m
4.结构类型:
typedef struct
{
char data;
int weight;
int parent;
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,这要求在发送端通过一个编码系统对待传输预先编码,在接收端将传来的数据进行译码。对于双工通道,每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、概要设计
1. 哈夫曼树的定义:
在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。
2.哈夫曼树的构造:
假设有N个权值,则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1,W2,……….Wn,则哈夫曼树的构造规则为:
(1) 将W1,W2,……….Wn看成有N棵树的森林;
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左,右子树,且新树的根结点为其左,右子树结点权值之和;
(3) 从森林中删除选取取的两面三刀棵树,并将新树加入森林;
(4) 重复(2)(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。
在构造哈夫曼树的过程中,每次由两棵权值最小的树生成一棵新树时,新树的左子树和右子树可以任意安排,这样将会得到具有不同结构的多个哈夫曼树,但字们都具有相同的带权路径长度。为了歙 得到的哈夫曼树的结构尽量唯一,通常规定生成的哈夫曼树中每个结点的左子树根结点的权要小于等于右女树根结点的权。
3.构造哈夫曼树的算法实现:
假设哈夫曼树采用双亲孩子表示法存储,并增加权值域,构造哈夫曼树的叶子结点(树木的权)有N个,合并次数为N―1次,则森林中总共有2N―1棵树,(包含合并后删除的)。 存储结构描述为:
const int n=maxn //maxn表示叶子数目
const int m=2*n-1 //m为森林中树的棵数
class tree
{ public:
float weight; //权值
int parent; //双亲
int lch, rch; //左,右孩子
}
tree hftree[m+1]; //规定从第一个元素hftree[1]开始使用数组元素,故定义长度为m+1而不为m
4.结构类型:
typedef struct
{
char data;
int weight;
int parent;
int lchild;
int rchild;
}huffnode;
typedef struct
{
char cd[MAX];
int start;
}huffcode;
5.主程序
int main()
{
初始化:输入字符代码以及权值.
编制哈夫曼码:根据权值建立二叉树, 输出相应的根节点到叶结点的路
径,便是哈夫曼编码.
编码:输入字符,输出哈夫曼码.
译码:输入哈夫曼,输出字符代码.
退出:结束进程,退出程序.
return 0;
}
三、详细设计
#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define MAX 25
typedef struct
{
char data;
int weight;
int parent;
int rchild;
}huffnode;
typedef struct
{
char cd[MAX];
int start;
}huffcode;
5.主程序
int main()
{
初始化:输入字符代码以及权值.
编制哈夫曼码:根据权值建立二叉树, 输出相应的根节点到叶结点的路
径,便是哈夫曼编码.
编码:输入字符,输出哈夫曼码.
译码:输入哈夫曼,输出字符代码.
退出:结束进程,退出程序.
return 0;
}
三、详细设计
#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define MAX 25
typedef struct
{
char data;
int weight;
int parent;
剩余17页未读,继续阅读
资源评论
Dibugger
- 粉丝: 3
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Nacos如何支持服务发现和注册-基于词频统计的分析.txt
- :基于java打造的深度学习框架,帮助你快速搭建神经网络,实现模型推理与训练,引擎支持自动求导,多线程与GPU运算
- 第九次作业(XY图,XY图显示,三维曲面,数字波形图)
- 微信小程序实战案例:打造高效便捷的在线书店.zip
- 1.0.5win(1)(1).exe
- ESP8266 WiFi模块入门教程:从连接到配置.zip
- 词频统计:从基础到实践的应用指南.zip
- 滑动窗口:深入理解与应用.zip
- WRF(Weather Research and Forecasting Model)模型:深入解析与实用操作指南.zip
- IngeekDK.json
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功