哈夫曼树Word文件下载.docx
- 文档编号:6307157
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:16
- 大小:17.89KB
哈夫曼树Word文件下载.docx
《哈夫曼树Word文件下载.docx》由会员分享,可在线阅读,更多相关《哈夫曼树Word文件下载.docx(16页珍藏版)》请在冰点文库上搜索。
//字符值数组
intflag=0;
//初始化标记
//**********************************************************************
//初始化函数
//函数功能:
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中
//函数参数:
//向量HT的前n个分量表示叶子结点,最后一个分量表示根结点,各字符的编码长度不等,所以按实际长度动态分配空间
voidSelect(HuffmanTreet,inti,int&
s1,int&
s2)
{//s1为最小的两个值中序号最小的那个
intj;
intk=ImpossibleWeight;
//k的初值为不可能达到的最大权值
for(j=1;
j<
=i;
j++)
{
if(t[j].weight<
k&
&
t[j].parent==0)
{k=t[j].weight;
s1=j;
}
}
t[s1].parent=1;
k=ImpossibleWeight;
s2=j;
t[s2].parent=1;
voidHuffmanCoding(HuffmanTree&
HT,HuffmanCode&
HC,int*w,intnum)//w存放n个字符的权值(均>
0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC
inti,m,c,s1,s2,start,f;
HuffmanTreep;
char*cd;
if(num<
=1)return;
m=2*num-1;
//m为结点数,一棵有n个叶子结点的哈夫曼树共有2n-1个结点,可以存储在一个大小为2n-1的一维数组中
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//0号单元未用
//--------初始化哈弗曼树-------
for(p=HT+1,i=1;
i<
=num;
i++,p++,w++)
p->
weight=*w;
parent=0;
lchild=0;
rchild=0;
for(i=num+1;
=m;
i++,p++)
weight=0;
//--------建哈夫曼树-------------
i++)
Select(HT,i-1,s1,s2);
//在HT[1...i-1]选择parent为0且weight最小的两个结点,其序号分别为s1和s2
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
//左孩子权值小,右孩子权值大
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//-------从叶子到根逆向求每个字符的哈弗曼编码--------
HC=(HuffmanCode)malloc((num+1)*sizeof(char*));
//指针数组:
分配n个字符编码的头指针向量
cd=(char*)malloc(n*sizeof(char*));
//分配求编码的工作空间
cd[n-1]='
\0'
;
//编码结束符
for(i=1;
=n;
i++)//逐个字符求哈弗曼编码
start=n-1;
//编码结束符位置
for(c=i,f=HT[i].parent;
f!
=0;
c=f,f=HT[f].parent)//从叶子到跟逆向求哈弗曼编码
if(HT[f].lchild==c)cd[--start]='
0'
//判断是左孩子还是右孩子(左为0右为1)
elsecd[--start]='
1'
HC[i]=(char*)malloc((num-start)*sizeof(char*));
//按所需长度分配空间
intj,h;
strcpy(HC[i],&
cd[start]);
free(cd);
//****************初始化函数******************
voidInitialization()
flag=1;
//标记为已初始化
inti;
w=(int*)malloc(n*sizeof(int));
//为26个字符权值分配空间
info=(char*)malloc(n*sizeof(char));
//为26个字符分配空间
ifstreaminfile("
ABC.txt"
ios:
:
in);
if(!
infile)
cerr<
<
"
打开失败"
endl;
exit
(1);
for(i=0;
n;
infile>
>
info[i];
w[i];
infile.close();
cout<
读入字符成功!
HuffmanCoding(HT,HC,w,n);
//------------打印编码-----------
依次显示各个字符的值,权值或频度,编码如下"
字符"
setw(6)<
权值"
setw(11)<
编码"
setw(3)<
w[i]<
setw(12)<
HC[i+1]<
//---------将建好的哈夫曼树写入文件------------
下面将哈夫曼树写入文件"
ofstreamoutfile("
hfmTree.txt"
out);
outfile)
i++,w++)
outfile<
info[i]<
"
outfile.close();
已经将字符与对应的权值,编码写入根目录下文件hfmTree.txt"
//*****************输入待编码字符函数*************************
voidInput()
charstring[100];
ToBeTran.txt"
请输入你想要编码的字符串(字符个数应小于100),以#结束"
cin>
string;
for(inti=0;
string[i]!
='
if(string[i]=='
)break;
string[i];
获取报文成功"
------"
已经将报文存入根目录下的ToBeTran.txt文件"
//******************编码函数****************
voidEncoding()
inti,j;
char*string;
string=(char*)malloc(MaxN*sizeof(char));
下面对根目录下的ToBeTran.txt文件中的字符进行编码"
100;
if(string[i]!
#'
)
elsebreak;
CodeFile.txt"
for(j=0;
if(string[i]==info[j])
HC[j+1];
'
free(string);
编码完成------"
编码已写入根目录下的文件CodeFile.txt中"
}
//******************译码函数****************
voidDecoding()
intj=0,i;
char*code;
code=(char*)malloc(MaxC*sizeof(char));
下面对根目录下的CodeFile.txt文件中的代码进行译码"
for(i=0;
MaxC;
{infile>
code[i];
if(code[i]!
)
elsebreak;
intm=2*n-1;
code[i-1]!
if(HT[m].lchild==0)
string[j]=info[m-1];
j++;
m=2*n-1;
i--;
else
if(code[i]=='
m=HT[m].rchild;
m=HT[m].lchild;
string[j]='
TextFile.txt"
的译码为------"
cout<
------译码完成------"
译码结果已写入根目录下的文件TextFile.txt中"
free(code);
//*************打印编码函数****************
voidCode_printing()
下面打印根目录下文件CodeFile.txt中的编码"
CodePrin.txt"
code[i]!
------打印结束------"
该字符形式的编码文件已写入文件CodePrin.txt中"
//*************打印哈夫曼树函数****************
intnumb=0;
voidcoprint(HuffmanTreestart,HuffmanTreeHT)//start=ht+26这是一个递归算法
{
if(start!
=HT)
TreePrint.txt"
numb++;
//number=0该变量为已被声明为全局变量
coprint(HT+start->
rchild,HT);
//递归先序遍历
setw(5*numb)<
start->
weight<
//if(start->
rchild==0)cout<
info[start-HT-1]<
weight;
lchild,HT);
numb--;
voidTree_printing(HuffmanTreeHT,intnum)
p=HT+2*num-1;
//p=HT+26
下面打印赫夫曼树"
coprint(p,HT);
打印工作结束"
//*************主函数**************************
intmain()
charchoice;
do{
************哈弗曼编/译码器系统***************"
请选择您所需功能:
I>
初始化哈弗曼树"
W>
输入待编码字符串"
E>
利用已建好的哈夫曼树进行编码"
D>
利用已建好的哈夫曼树进行译码"
P>
打印代码文件"
T>
打印哈夫曼树"
Q>
退出"
if(flag==0)
请先初始化哈夫曼树,输入I"
系统将从根目录下的文件ABC.txt中读出26个字母并对字母进行编码>
choice;
switch(choice)
case'
I'
Initialization();
break;
W'
Input();
E'
Encoding();
D'
Decoding();
P'
Code_printing();
T'
Tree_printing(HT,n);
Q'
default:
cout<
输入的命令出错,请重新输入!
}while(choice!
);
free(w);
free(info);
free(HT);
free(HC);
system("
pause"
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树