c语言哈夫曼树的构造_哈夫曼树的构造c语言代码

数据结构之哈夫曼树（C语言）
　　#include

　　#include

　　#include

　　#include

　　using namespace std;

　　# define MaxN 100//初始设定的最大结点数

　　# define MaxC 1000//最大编码长度

　　# define ImpossibleWeight 10000//结点不可能达到的权值

　　# define n 26//字符集的个数

　　//———–哈夫曼树的结点结构类型定义———–

　　typedef struct //定义哈夫曼树各结点

　　{

　　int weight;//权值

　　int parent;//双亲结点下标

　　int lchild;//左孩子结点下标

　　int rchild;//右孩子结点下标

　　}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树

　　typedef char**HuffmanCode;//动态分配数组存储哈夫曼编码表

　　//——-全局变量——–

　　HuffmanTree HT;

　　HuffmanCode HC;

　　int *w;//权值数组

　　//const int n=26;//字符集的个数

　　char *info;//字符值数组

　　int flag=0;//初始化标记

　　//**********************************************************************

　　//初始化函数

　　//函数功能： 从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中

　　//函数参数：

　　//向量HT的前n个分量表示叶子结点，最后一个分量表示根结点，各字符的编码长度不等，所以按实际长度动态分配空间

　　void Select(HuffmanTree t,int i,int &s1,int &s2)

　　{ //s1为最小的两个值中序号最小的那个

　　int j;

　　int k=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;

　　for(j=1;j<=i;j++)

　　{

　　if(t[j].weight0），构造哈夫曼树HT，并求出n个字符的哈弗曼编码HC

　　{

　　int i,m,c,s1,s2,start,f;

　　HuffmanTree p;

　　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;iweight=*w;

　　p->parent=0;

　　p->lchild=0;

　　p->rchild=0;

　　}

　　for(i=num+1;iweight=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)

　　else cd[–start]='1';

　　HC[i]=(char*)malloc((num-start)*sizeof(char*));//按所需长度分配空间

　　int j,h;

　　strcpy(HC[i],&cd[start]);

　　}

　　free(cd);

　　}

　　//****************初始化函数******************

　　void Initialization()

　　{

　　flag=1;//标记为已初始化

　　int i;

　　w=(int*)malloc(n*sizeof(int));//为26个字符权值分配空间

　　info=(char*)malloc(n*sizeof(char));//为26个字符分配空间

　　ifstream infile("ABC.txt",ios::in);

　　if(!infile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for(i=0;i>info[i];

　　infile>>w[i];

　　}

　　infile.close();

　　cout<<"读入字符成功！"<<endl;

　　HuffmanCoding(HT,HC,w,n);

　　//————打印编码———–

　　cout<<"依次显示各个字符的值,权值或频度,编码如下"<<endl;

　　cout<<"字符"<<setw(6)<<"权值"<<setw(11)<<"编码"<<endl;

　　for(i=0;i<n;i++)

　　{

　　cout<<setw(3)<<info[i];

　　cout<<setw(6)<<w[i]<<setw(12)<<HC[i+1]<<endl;

　　}

　　//———将建好的哈夫曼树写入文件————

　　cout<<"下面将哈夫曼树写入文件"<<endl;

　　ofstream outfile("hfmTree.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for(i=0;i<n;i++,w++)

　　{

　　outfile<<info[i]<<" ";

　　outfile<<w[i]<<" ";

　　outfile<<HC[i+1]<<" ";

　　}

　　outfile.close();

　　cout<<"已经将字符与对应的权值，编码写入根目录下文件hfmTree.txt"<<endl;

　　}

　　//*****************输入待编码字符函数*************************

　　void Input()

　　{

　　char string[100];

　　ofstream outfile("ToBeTran.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　cout<<"请输入你想要编码的字符串(字符个数应小于100),以#结束"<>string;

　　for(int i=0;string[i]!='0';i++)

　　{

　　if(string[i]=='0') break;

　　outfile<<string[i];

　　}

　　cout<<"报文成功"<<endl;

　　outfile.close();

　　cout<<"——"<<"已经将报文存入根目录下的ToBeTran.txt文件"<<endl;

　　}

　　//******************编码函数****************

　　void Encoding()

　　{

　　int i,j;

　　char*string;

　　string=(char*)malloc(MaxN*sizeof(char));

　　cout<<"下面对根目录下的ToBeTran.txt文件中的字符进行编码"<<endl;

　　ifstream infile("ToBeTran.txt",ios::in);

　　if(!infile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for(i=0;i>string[i];

　　}

　　for(i=0;i<100;i++)

　　if(string[i]!='#')

　　cout<<string[i];

　　else break;

　　infile.close();

　　ofstream outfile("CodeFile.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for(i=0;string[i]!='#';i++)

　　{

　　for(j=0;j<n;j++)

　　{

　　if(string[i]==info[j])

　　outfile<<HC[j+1];

　　}

　　}

　　outfile<<'#';

　　outfile.close();

　　free(string);

　　cout<<"编码完成——";

　　cout<<"编码已写入根目录下的文件CodeFile.txt中"<<endl;

　　}

　　//******************译码函数****************

　　void Decoding()

　　{

　　int j=0,i;

　　char *code;

　　code=(char*)malloc(MaxC*sizeof(char));

　　char*string;

　　string=(char*)malloc(MaxN*sizeof(char));

　　cout<<"下面对根目录下的CodeFile.txt文件中的代码进行译码"<<endl;

　　ifstream infile("CodeFile.txt",ios::in);

　　if(!infile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for( i=0;i>code[i];

　　if(code[i]!='#')

　　{

　　cout<<code[i];

　　}

　　else break;

　　}

　　infile.close();

　　int m=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]='#';

　　ofstream outfile("TextFile.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　cout<<"的译码为——"<<endl;

　　for( i=0;string[i]!='#';i++)

　　{

　　outfile<<string[i];

　　cout<<string[i];

　　}

　　outfile<<'#';

　　outfile.close();

　　cout<<"——译码完成——"<<endl;

　　cout<<"译码结果已写入根目录下的文件TextFile.txt中"<<endl;

　　free(code);

　　free(string);

　　}

　　//*************打印编码函数****************

　　void Code_printing()

　　{

　　int i;

　　char *code;

　　code=(char*)malloc(MaxC*sizeof(char));

　　cout<<"下面打印根目录下文件CodeFile.txt中的编码"<<endl;

　　ifstream infile("CodeFile.txt",ios::in);

　　if(!infile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for( i=0;i>code[i];

　　if(code[i]!='#')

　　cout<<code[i];

　　else break;

　　}

　　infile.close();

　　cout<<endl;

　　ofstream outfile("CodePrin.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<<endl;

　　exit(1);

　　}

　　for(i=0;code[i]!='#';i++)

　　{

　　outfile<<code[i];

　　}

　　outfile.close();

　　free(code);

　　cout<<"——打印结束——"<<endl;

　　cout<<"该字符形式的编码文件已写入文件CodePrin.txt中"<<endl;

　　}

　　//*************打印哈夫曼树函数****************

　　int numb=0;

　　void coprint(HuffmanTree start,HuffmanTree HT) //start=ht+26这是一个递归算法

　　{

　　if(start!=HT)

　　{

　　ofstream outfile("TreePrint.txt",ios::out);

　　if(!outfile)

　　{

　　cerr<<"打开失败"<rchild,HT); //递归先序遍历

　　cout<<setw(5*numb)<weight<rchild==0) cout<<info[start-HT-1]<<endl;

　　outfile<weight;

　　coprint(HT+start->lchild,HT);

　　numb–;

　　outfile.close();

　　}

　　}

　　void Tree_printing(HuffmanTree HT,int num)

　　{

　　HuffmanTree p;

　　p=HT+2*num-1; //p=HT+26

　　cout<<"下面打印赫夫曼树"<<endl;

　　coprint(p,HT); //p=HT+26

　　cout<<"打印工作结束"<<endl;

　　}

　　//*************主函数**************************

　　int main()

　　{

　　char choice;

　　do{

　　cout<<"************哈弗曼编/译码器系统***************"<<endl;

　　cout<<"请选择您所需功能："<<endl;

　　cout<<":初始化哈弗曼树"<<endl;

　　cout<<":输入待编码字符串"<<endl;

　　cout<<":利用已建好的哈夫曼树进行编码"<<endl;

　　cout<<":利用已建好的哈夫曼树进行译码"<<endl;

　　cout<<":打印代码文件"<<endl;

　　cout<<":打印哈夫曼树"<<endl;

　　cout<<":退出"<<endl;

　　if(flag==0)

　　{

　　cout<<"请先初始化哈夫曼树,输入I"<<endl;

　　cout<<""<>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<<"输入的命令出错，请重新输入！"<<endl;

　　}

　　}while(choice!='Q');

　　free(w);

　　free(info);

　　free(HT);

　　free(HC);

　　system("pause");

　　return 0;

　　}