哈夫曼树.docx
- 文档编号:3889493
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:16
- 大小:17.89KB
哈夫曼树.docx
《哈夫曼树.docx》由会员分享,可在线阅读,更多相关《哈夫曼树.docx(16页珍藏版)》请在冰点文库上搜索。
哈夫曼树
#include
#include
#include
#include
usingnamespacestd;
#defineMaxN100//初始设定的最大结点数
#defineMaxC1000//最大编码长度
#defineImpossibleWeight10000//结点不可能达到的权值
#definen26//字符集的个数
//-----------哈夫曼树的结点结构类型定义-----------
typedefstruct//定义哈夫曼树各结点
{
intweight;//权值
intparent;//双亲结点下标
intlchild;//左孩子结点下标
intrchild;//右孩子结点下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表
//-------全局变量--------
HuffmanTreeHT;
HuffmanCodeHC;
int*w;//权值数组
//constintn=26;//字符集的个数
char*info;//字符值数组
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].weight; s1=j;} } t[s1].parent=1; k=ImpossibleWeight; for(j=1;j<=i;j++) { if(t[j].weight {k=t[j].weight; 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; p->parent=0; p->lchild=0; p->rchild=0; } for(i=num+1;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } //--------建哈夫曼树------------- for(i=num+1;i<=m;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;i<=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<<"打开失败"< exit (1); } for(i=0;i { infile>>info[i]; infile>>w[i]; } infile.close(); cout<<"读入字符成功! "< HuffmanCoding(HT,HC,w,n); //------------打印编码----------- cout<<"依次显示各个字符的值,权值或频度,编码如下"< cout<<"字符"< for(i=0;i { cout< cout< } //---------将建好的哈夫曼树写入文件------------ cout<<"下面将哈夫曼树写入文件"< ofstreamoutfile("hfmTree.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } for(i=0;i { outfile< outfile< outfile< } outfile.close(); cout<<"已经将字符与对应的权值,编码写入根目录下文件hfmTree.txt"< } //*****************输入待编码字符函数************************* voidInput() { charstring[100]; ofstreamoutfile("ToBeTran.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } cout<<"请输入你想要编码的字符串(字符个数应小于100),以#结束"< cin>>string; for(inti=0;string[i]! ='\0';i++) { if(string[i]=='\0')break; outfile< } cout<<"获取报文成功"< outfile.close(); cout<<"------"<<"已经将报文存入根目录下的ToBeTran.txt文件"< } //******************编码函数**************** voidEncoding() { inti,j; char*string; string=(char*)malloc(MaxN*sizeof(char)); cout<<"下面对根目录下的ToBeTran.txt文件中的字符进行编码"< ifstreaminfile("ToBeTran.txt",ios: : in); if(! infile) { cerr<<"打开失败"< exit (1); } for(i=0;i<100;i++) { infile>>string[i]; } for(i=0;i<100;i++) if(string[i]! ='#') cout< elsebreak; infile.close(); ofstreamoutfile("CodeFile.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } for(i=0;string[i]! ='#';i++) { for(j=0;j { if(string[i]==info[j]) outfile< } } outfile<<'#'; outfile.close(); free(string); cout<<"编码完成------"; cout<<"编码已写入根目录下的文件CodeFile.txt中"< } //******************译码函数**************** voidDecoding() { intj=0,i; char*code; code=(char*)malloc(MaxC*sizeof(char)); char*string; string=(char*)malloc(MaxN*sizeof(char)); cout<<"下面对根目录下的CodeFile.txt文件中的代码进行译码"< ifstreaminfile("CodeFile.txt",ios: : in); if(! infile) { cerr<<"打开失败"< exit (1); } for(i=0;i {infile>>code[i]; if(code[i]! ='#') { cout< } elsebreak; } infile.close(); intm=2*n-1; for(i=0;code[i-1]! ='#';i++) { if(HT[m].lchild==0) { string[j]=info[m-1]; j++; m=2*n-1; i--; } else if(code[i]=='1') m=HT[m].rchild; else if(code[i]=='0') m=HT[m].lchild; } string[j]='#'; ofstreamoutfile("TextFile.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } cout<<"的译码为------"< for(i=0;string[i]! ='#';i++) { outfile< cout< } outfile<<'#'; outfile.close(); cout<<"------译码完成------"< cout<<"译码结果已写入根目录下的文件TextFile.txt中"< free(code); free(string); } //*************打印编码函数**************** voidCode_printing() { inti; char*code; code=(char*)malloc(MaxC*sizeof(char)); cout<<"下面打印根目录下文件CodeFile.txt中的编码"< ifstreaminfile("CodeFile.txt",ios: : in); if(! infile) { cerr<<"打开失败"< exit (1); } for(i=0;i { infile>>code[i]; if(code[i]! ='#') cout< elsebreak; } infile.close(); cout< ofstreamoutfile("CodePrin.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } for(i=0;code[i]! ='#';i++) { outfile< } outfile.close(); free(code); cout<<"------打印结束------"< cout<<"该字符形式的编码文件已写入文件CodePrin.txt中"< } //*************打印哈夫曼树函数**************** intnumb=0; voidcoprint(HuffmanTreestart,HuffmanTreeHT)//start=ht+26这是一个递归算法 { if(start! =HT) { ofstreamoutfile("TreePrint.txt",ios: : out); if(! outfile) { cerr<<"打开失败"< exit (1); } numb++;//number=0该变量为已被声明为全局变量 coprint(HT+start->rchild,HT);//递归先序遍历 cout< //if(start->rchild==0)cout< outfile< coprint(HT+start->lchild,HT); numb--; outfile.close(); } } voidTree_printing(HuffmanTreeHT,intnum) { HuffmanTreep; p=HT+2*num-1;//p=HT+26 cout<<"下面打印赫夫曼树"< coprint(p,HT);//p=HT+26 cout<<"打印工作结束"< } //*************主函数************************** intmain() { charchoice; do{ cout<<"************哈弗曼编/译码器系统***************"< cout<<"请选择您所需功能: "< cout<<": 初始化哈弗曼树"< cout<<" 输入待编码字符串"< cout<<" 利用已建好的哈夫曼树进行编码"< cout<<" 利用已建好的哈夫曼树进行译码"< cout<<" : 打印代码文件"< cout<<" 打印哈夫曼树"< cout<<" 退出"< if(flag==0) { cout<<"请先初始化哈夫曼树,输入I"< cout<<"<系统将从根目录下的文件ABC.txt中读出26个字母并对字母进行编码>"< } cin>>choice; switch(choice) { case'I': Initialization();break; case'W': Input();break; case'E': Encoding();break; case'D': Decoding();break; case'P': Code_printing();break; case'T': Tree_printing(HT,n);break; case'Q': ;break; default: cout<<"输入的命令出错,请重新输入! "< } }while(choice! ='Q'); free(w); free(info); free(HT); free(HC); system("pause"); return0; }:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树
![提示](https://static.bingdoc.com/images/bang_tan.gif)