没有合适的资源?快使用搜索试试~ 我知道了~
实验五哈夫曼编码与译码的设计与实现.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 109 浏览量
2021-10-04
22:11:26
上传
评论
收藏 216KB DOC 举报
温馨提示
试读
22页
实验五哈夫曼编码与译码的设计与实现.doc
资源推荐
资源详情
资源评论
.
实验五 哈夫曼编码与译码的设计与实现
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,
降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,
在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信
息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发编写一
个哈夫曼码的编/译码系统。
基本要求:
(1)接收原始数据:从终端读入字符集大小 n,以与 n 个字符和 n 个
权值,建立哈夫曼树,并将它存于文件 nodedata.dat 中。
( 2 ) 编 码 : 利 用 已 建 好 的 哈 夫 曼 树 ( 如 不 在 存 , 则 从 文 件
nodedata.dat 中读入),对文件中的正文进行编码,然后将结果存入文件
code.dat 中。
(3)译码:利用已建好的哈夫曼树将文件 code.dat 中的代码进行译
码,结果存入文件 textle.txt 中。
(4)打印编码规则:即字符与编码的一一对应关系。
(5)打印哈夫曼树:将已在存中的哈夫曼树以直观的方式显示在终端
上。
二、数据结构设计
1、
构造哈夫曼树时,使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时,设计一个结构体数组 HuNode 保存哈夫曼树中各结
点的信息,根据二叉树的性质可知,具有 n 个叶子结点的哈夫曼树共有 2n-1
个结点,所以数组 HuNode 的大小设置为 2n-1,描述结点的数据类型为:
typedefstruct
{
int weight;
int parent;
int lchild;
int rchild;
char inf;
}HNodeType;
2.求哈夫曼编码时使用一维结构数组 HuCode 作为哈夫曼编码信息的存
储。
求哈夫曼编码实际上就是在已建立的哈夫曼树中,从叶子结点开始,沿结
点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼的一个分支,从而
得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子
结点所经过的路径上各分支所组成的 0、1 序列,因此先得到的分支代码为所
求编码的低位码,后得到的分支代码为所求的高位码。所以设计如下数据类型:
#dene MaxBit 10
struct HcodeType
{
1 / 22
.
int bit[MaxBit];
int start;
};
3、文件 nodedata.dat、code.dat、textle.txt
三、功能函数设计
1、初始化功能模块
此功能模块的功能为从键盘接受字符集大小 n,以与 n 个字符和 n 个权值。
2、建立哈夫曼编码的功能模块
此模块功能为使用 1 中得到的数据按照教材中的构造哈弗曼的算法构造哈
弗曼树,即将 HuNode 数组中的各个位置的各个域都填上相关的值,并将这
个结构体数组存于文件 nodedata.dat 中。
函数原型为:
void Creat_Hamantree(int &n)
{
HNodeType *HaNode=new HNodeType[2*n-1];
int i,j;
int m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
HaNode[i].weight=0;
HaNode[i].parent=-1;
HaNode[i].lchild=-1;
HaNode[i].rchild=-1;
HaNode[i].inf='0';
}
for(i=0;i<n;i++)
{
cout<<"请输入字符"<<endl;
cin>>HaNode[i].inf;
cout<<"请输入该字符的权值"<<endl;
cin>>HaNode[i].weight;
}
for(i=0;i<n-1;i++)//构造哈夫曼树
{
m1=m2=Maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)//选取最小和次小
{
if(HaNode[j].parent==-1&&HaNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HaNode[j].weight;
x1=j;
2 / 22
.
}
else
{
if(HaNode[j].parent==-1&&HaNode[j].weight<m2)
{
m2=HaNode[j].weight;
x2=j;
}
}
}
//将找出的最小和次小合并,创造其父母结点
HaNode[x1].parent=n+i;
HaNode[x2].parent=n+i;
HaNode[n+i].weight=HaNode[x1].weight+HaNode[x2].weight;
HaNode[n+i].lchild=x2;
HaNode[n+i].rchild=x1;
HaNode[n+i].inf=NULL;
}
cout<<"显示存储的哈弗曼树信息:"<<endl;
cout<<"权值左孩子右孩子双亲"<<endl;
for(i=0;i<2*n-1;i++)
{
cout<<HaNode[i].inf<<" ";
cout<<HaNode[i].weight<<" ";
cout<<HaNode[i].lchild<<" ";
cout<<HaNode[i].rchild<<" ";
cout<<HaNode[i].parent<<endl;
}
//写入文件
fstream outle1;
outle1.open("E:\\nodedata.dat",ios::out|ios::trunc|
ios::binary);//建立进行写入的文件
if(!outle1) //没有创建成功则显示相应信息
{
cout<<"nodedata.dat文件不能打开"<<endl;
abort();
}
for(i=0;i<2*n-1;i++) // 将 存 中 从 HaNode[i] 地 址 开 始 的
sizeof(HaNode[i])的容写入文件中
outle1.write((char*)&HaNode[i],sizeof(HaNode[i]));
outle1.close ();//关闭文件
3 / 22
.
delete []HaNode;
}
3、建立哈弗曼编码功的功能模块
此模块功能是从文件 nodedata.dat 中读入相关的字符信息进行哈弗曼编
码,然后将结果存入 code.dat 中,同时将字符与 0 和 1 代码串的一一对应关
系显示到屏幕上。
函数原型为:
void HaCode(int &n)//哈夫曼编码
{
HNodeType *HaNode=new HNodeType[Maxnode];
HcodeType *HaCode=new HcodeType[Maxleaf];
HcodeType cd;
int i,j,c,p;
fstream in("E:\\nodedata.dat",ios::in|ios::binary);
in.read((char*)HaNode,(2*n-1)*sizeof(HNodeType));
in.close();
fstream outle;
outle.open("E:\\codedata.dat",ios::out|ios::binary);// 建 立进 行
写入的文件
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HaNode[c].parent;
while(p!=-1)
{
if(HaNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HaNode[c].parent;
}
for(j=cd.start+1;j<n;j++)
HaCode[i].bit[j]=cd.bit[j];
HaCode[i].start=cd.start;
}
for(i=0;i<n;i++)
{
outle<<HaNode[i].inf;
for(j=HaCode[i].start+1;j<n;j++)
4 / 22
.
outle<<HaCode[i].bit[j];
}
cout<<"字符信息--编码信息"<<endl;
for(i=0;i<n;i++)
{
cout<<HaNode[i].inf<<"---";
for(j=HaCode[i].start+1;j<n;j++)
cout<<HaCode[i].bit[j];
cout<<endl;
}
outle.close ();
cout<<"请输入要编码的字符串,基本元素为(";
for(i=0;i<n;i++)
cout<<HaNode[i].inf<<",";
cout<<")"<<endl;
char inf[100];
cin>>inf;
int f=strlen(inf);
fstream outle1;
outle1.open("E:\\code.dat",ios::out|ios::binary);//建立进行写入
的文件
if(!outle1)
{
cout<<"code.dat文件不能打开!"<<endl;
abort();
}
else
{ cout<<endl;
cout<<"字符串编码后为:";
for(int x=0;x<f;x++)
{
for(i=0;i<n;i++)
{
if(inf[x]==HaNode[i].inf)
{
for(j=HaCode[i].start+1;j<n;j++)
{
outle1.write((char*)&HaCode[i].bit[j],sizeof(HaCode[i].bit[j]));
cout<<HaCode[i].bit[j];
}
}
}
5 / 22
剩余21页未读,继续阅读
资源评论
huayuya123
- 粉丝: 26
- 资源: 31万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功