实验五哈夫曼编码与译码的设计与实现Word文档下载推荐.docx
- 文档编号:1546974
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:34
- 大小:155.48KB
实验五哈夫曼编码与译码的设计与实现Word文档下载推荐.docx
《实验五哈夫曼编码与译码的设计与实现Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《实验五哈夫曼编码与译码的设计与实现Word文档下载推荐.docx(34页珍藏版)》请在冰点文库上搜索。
}HNodeType;
2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码实际上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼的一个分支,从而得到一位哈夫曼编码值。
由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求的高位码。
所以设计如下数据类型:
#defineMaxBit10
structHcodeType
intbit[MaxBit];
intstart;
};
3、文件nodedata.dat、code.dat、textfile.txt
三、功能函数设计
1、初始化功能模块
此功能模块的功能为从键盘接受字符集大小n,以及n个字符和n个权值。
2、建立哈夫曼编码的功能模块
此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树,即将HuffNode数组中的各个位置的各个域都填上相关的值,并将这个结构体数组存于文件nodedata.dat中。
函数原型为:
voidCreat_Haffmantree(int&
n)
HNodeType*HaffNode=newHNodeType[2*n-1];
inti,j;
intm1,m2,x1,x2;
for(i=0;
i<
2*n-1;
i++)
{
HaffNode[i].weight=0;
HaffNode[i].parent=-1;
HaffNode[i].lchild=-1;
HaffNode[i].rchild=-1;
HaffNode[i].inf='
0'
;
}
n;
cout<
<
"
请输入字符"
endl;
cin>
>
HaffNode[i].inf;
请输入该字符的权值"
HaffNode[i].weight;
n-1;
i++)//构造哈夫曼树
m1=m2=Maxvalue;
x1=x2=0;
for(j=0;
j<
n+i;
j++)//选取最小和次小
{
if(HaffNode[j].parent==-1&
&
HaffNode[j].weight<
m1)
{
m2=m1;
x2=x1;
m1=HaffNode[j].weight;
x1=j;
}
else
if(HaffNode[j].parent==-1&
m2)
{
m2=HaffNode[j].weight;
x2=j;
}
}
//将找出的最小和次小合并,创造其父母结点
HaffNode[x1].parent=n+i;
HaffNode[x2].parent=n+i;
HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;
HaffNode[n+i].lchild=x2;
HaffNode[n+i].rchild=x1;
HaffNode[n+i].inf=NULL;
}
cout<
显示存储的哈弗曼树信息:
权值左孩子右孩子双亲"
HaffNode[i].inf<
"
HaffNode[i].weight<
HaffNode[i].lchild<
HaffNode[i].rchild<
HaffNode[i].parent<
//写入文件
fstreamoutfile1;
outfile1.open("
E:
\\nodedata.dat"
ios:
:
out|ios:
trunc|ios:
binary);
//建立进行写入的文件
if(!
outfile1)//没有创建成功则显示相应信息
nodedata.dat文件不能打开"
abort();
i++)//将存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的容写入文件中
outfile1.write((char*)&
HaffNode[i],sizeof(HaffNode[i]));
outfile1.close();
//关闭文件
delete[]HaffNode;
}
3、建立哈弗曼编码功的功能模块
此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码,然后将结果存入code.dat中,同时将字符与0和1代码串的一一对应关系显示到屏幕上。
voidHaffCode(int&
n)//哈夫曼编码
HNodeType*HaffNode=newHNodeType[Maxnode];
HcodeType*HaffCode=newHcodeType[Maxleaf];
HcodeTypecd;
inti,j,c,p;
fstreamin("
in|ios:
in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));
in.close();
fstreamoutfile;
outfile.open("
\\codedata.dat"
cd.start=n-1;
c=i;
p=HaffNode[c].parent;
while(p!
=-1)
if(HaffNode[p].lchild==c)
cd.bit[cd.start]=0;
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HaffNode[c].parent;
for(j=cd.start+1;
j++)
HaffCode[i].bit[j]=cd.bit[j];
HaffCode[i].start=cd.start;
outfile<
for(j=HaffCode[i].start+1;
outfile<
HaffCode[i].bit[j];
字符信息--编码信息"
---"
for(j=HaffCode[i].start+1;
outfile.close();
请输入要编码的字符串,基本元素为("
"
)"
charinf[100];
cin>
inf;
intf=strlen(inf);
\\code.dat"
outfile1)
code.dat文件不能打开!
abort();
else
{cout<
字符串编码后为:
for(intx=0;
x<
f;
x++)
if(inf[x]==HaffNode[i].inf)
for(j=HaffCode[i].start+1;
outfile1.write((char*)&
HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));
cout<
编译后的代码串已经存入code.dat文件中!
outfile1.close();
delete[]HaffNode;
delete[]HaffCode;
4.此模块功能为接收需要译码的0、1代码串,按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件textfile.dat,同时将翻译的结果在屏幕上打印输出。
接受0、1代码串有两种形式,一种是直接输入,一种是从文件中读取。
voiddecode(int&
n)//解码
inti;
fstreaminfile1;
infile1.open("
//读出哈夫曼树
infile1)
infile1.read((char*)&
HaffNode[i],sizeof(HNodeType));
infile1.close();
inttempcode[100];
intnum=0;
100;
tempcode[i]=-1;
HcodeType*Code=newHcodeType[n];
请选择要做的操作:
输入串解码,请按4"
从文件中解码,请按5"
intq;
q;
while(q>
5||q<
4)
输入错误请重新输入"
switch(q)
case4:
请输入要解码的0,1串(按其他键结束输入):
i=0;
tempcode[i];
while(tempcode[i]==0||tempcode[i]==1)
i++;
num=i;
输入的编码为:
num;
intm=2*n-2;
译码后为:
\\textfile.txt"
out);
outfile)
textfile.txt文件不能打开!
while(i<
num)//小于字符串的长度
while(HaffNode[m].lchild!
=-1&
HaffNode[m].rchild!
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
elseif(tempcode[i]==1)
m=HaffNode[m].rchild;
HaffNode[m].inf;
m=2*n-2;
outfile.close();
译码后的结果已经存入textfile.txt中!
break;
case5:
fstreaminfile2;
//读编码
infile2.open("
while(!
infile2.eof())
infile2.read((char*)&
tempcode[num],sizeof(tempcode[num]));
num++;
infile2.close();
num--;
从文件中读出的编码为"
译码后为:
四.编码实现
#include"
stdafx.h"
#include<
iostream>
fstream>
string.h>
stdlib.h>
usingnamespacestd;
#defineMaxvalue100//应该大于权重之和
#defineMaxleaf100
#defineMaxnodeMaxleaf*2-1
Haff
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 五哈夫曼 编码 译码 设计 实现