1 #include "stdio.h" 2 #include "malloc.h" 3 4 #define maxlen 100 5 #define infinity 65535 6 7 struct bnode 8 { 9 int data;//数据 10 bnode *lchild,*rchild; 11 bool flags;//使用标志 12 }; 13 14 bnode *tree[maxlen]; 15 16 void initialization(int A[],int N,bnode *tree[maxlen])//初始化 17 { 18 int i; 19 for(i=0;i<N;i++) 20 { 21 tree[i] = (bnode *)malloc(sizeof bnode);//分配存储区域 22 tree[i]->data = A[i];//结点的值 23 tree[i]->flags = true;//标识未使用 24 tree[i]->lchild = NULL;//左子树为空 25 tree[i]->rchild = NULL;//右子树为空 26 } 27 } 28 29 int merge(int n,bnode *tree[maxlen])//寻找当前根结点值最小的两个子树将其合并 30 { 31 int i,num1,num2,min1,min2; 32 min1 = infinity; 33 min2 = infinity; 34 for(i=0;i<n;i++)//寻找当前值最小的根节点 35 { 36 if((tree[i]->data<min1)&&tree[i]->flags) 37 { 38 min1 = tree[i]->data; 39 num1 = i; 40 } 41 } 42 tree[num1]->flags = false;//设置标识已使用过 43 44 for(i=0;i<n;i++)//寻找当前值最小的根节点 45 { 46 if((tree[i]->data<min2)&&tree[i]->flags) 47 { 48 min2 = tree[i]->data; 49 num2 = i; 50 } 51 } 52 tree[num2]->flags = false;//设置标识已使用过 53 //将两个子树合并 54 tree[n] =(bnode *)malloc(sizeof bnode);//分配存储区域 55 tree[n]->data = tree[num1]->data + tree[num2]->data; 56 tree[n]->flags = true; 57 tree[n]->lchild = tree[num1]; 58 tree[n]->rchild = tree[num2]; 59 n++; 60 return n; 61 } 62 63 int Huffmantree(int n,bnode *tree[maxlen])//构造哈夫曼树 64 { 65 int i,num; 66 bool flags = true;//标识 67 while(flags) 68 { 69 num = 0;//计数 70 for(i=0;i<n;i++)//统计未使用结点数 71 { 72 if(tree[i]->flags) 73 { 74 num++; 75 } 76 } 77 if(num>=2) 78 { 79 n = merge(n,tree);//合并当前根结点值最小的两棵子树 80 }else{ 81 flags = false;//哈夫曼树构造完成标识 82 } 83 } 84 return n; 85 } 86 87 88 void PrintTree(bnode *Tree,int nlayer) //按树状打印二叉树 89 { 90 if(Tree==NULL) 91 { 92 return ; 93 } 94 PrintTree( Tree->rchild,nlayer+1); //打印右子树 95 for(int i=0;i<nlayer;i++) 96 { 97 printf(" "); 98 } 99 printf("%d ",Tree->data); 100 PrintTree(Tree->lchild,nlayer+1); //打印左子树 101 } 102 103 int main() 104 { 105 int x,nlayer=1; 106 int Array[maxlen];//存放节点的值 107 int count=0;//结点的个数 108 printf("[输入叶子结点,-1输入结束]: "); 109 printf("Data:"); 110 scanf("%d",&x); 111 while(x!=-1) 112 { 113 Array[count++] = x; 114 scanf("%d",&x); 115 } 116 117 initialization(Array,count,tree);//左右子树初始化 118 count = Huffmantree(count,tree);//构造哈夫曼树 119 120 printf("哈夫曼树树状输出: "); 121 122 PrintTree(tree[count-1],nlayer); 123 124 printf(" "); 125 return 0; 126 }
#include "iostream" #include "fstream" #include "string" using namespace std; const int maxlen = 100; #define infinity 65535 struct total { char ch;//字符 int weight;//权值 }; struct HfmTree { char ch;//字符 string encode;//编码组成的字符串 }; total Data[maxlen]; struct bnode { int data;//权值 char ch;//字符 bnode *lchild,*rchild;//左孩子，右孩子 char encode[maxlen];//结点存放编码 int count;//节点编码的位数 bool flags;//使用标志 }; bnode *tree[maxlen];//存放哈夫曼树所有的结点 //--------------------------初始化-------------------------------------- void initialization(total Data[maxlen],int N,bnode *tree[maxlen])//初始化 { int i; for(i=0;i<N;i++) { tree[i] = new bnode; tree[i]->data = Data[i].weight;//结点的值 tree[i]->ch= Data[i].ch;//结点的值 tree[i]->flags = true; //标识未使用 tree[i]->count= 0; //编码位数为0 tree[i]->lchild = NULL;//左子树为空 tree[i]->rchild = NULL;//右子树为空 } } //--------------------------初始化-------------------------------------- //------------------------------------------------------------------------- //寻找当前根结点值最小的两个子树将其合并 void merge(int &n,bnode *tree[maxlen])//寻找当前根结点值最小的两个子树将其合并 { int i,num1,num2,min1,min2; min1 = infinity; min2 = infinity; for(i=0;i<n;i++)//寻找当前值最小的根节点 { if((tree[i]->data<min1)&&tree[i]->flags) { min1 = tree[i]->data; num1 = i; } } tree[num1]->flags = false;//设置标识已使用过 for(i=0;i<n;i++)//寻找当前值最小的根节点 { if((tree[i]->data<min2)&&tree[i]->flags) { min2 = tree[i]->data; num2 = i; } } tree[num2]->flags = false;//设置标识已使用过 //将两个子树合并,形成新的结点 tree[n] = new bnode; tree[n]->data = tree[num1]->data + tree[num2]->data; tree[n]->ch ='~'; tree[n]->flags = true; tree[n]->count = 0; tree[n]->lchild = tree[num1]; tree[n]->rchild = tree[num2]; n++; } //------------------------------------------------------------------------- //-------------------------------构造哈夫曼树------------------------- void Huffmantree(int &n,bnode *tree[maxlen])//构造哈夫曼树 { int i,num; bool flags = true;//标识 while(flags) { num = 0;//计数 for(i=0;i<n;i++)//统计未使用结点数 { if(tree[i]->flags) { num++; } } if(num>=2) { merge(n,tree);//合并当前根结点值最小的两棵子树 }else{ flags = false;//哈夫曼树构造完成标识 } } } //-------------------------------构造哈夫曼树------------------------- //-------------------------------每个结点进行编码---------------------- void Encode(bnode *Tree)//每个结点进行编码 { int i; if(Tree) { if(Tree->lchild)//左子树根结点添加'0' { for(i=0;i<Tree->count;i++)//获得父节点的编码 { Tree->lchild->encode[i] = Tree->encode[i] ; Tree->lchild->count++; } Tree->lchild->encode[Tree->lchild->count++] = '0';//左子树加'0' } if(Tree->rchild)//右子树根结点添加'1' { for(i=0;i<Tree->count;i++) { Tree->rchild->encode[i] = Tree->encode[i]; Tree->rchild->count++; } Tree->rchild->encode[Tree->rchild->count++] = '1'; } Encode(Tree->lchild);//左子树继续 Encode(Tree->rchild);//右子树继续 } } //-------------------------------每个结点进行编码---------------------- //---------------------------------输出字符编码------------------------ void Print_Encode(int num)///输出字符编码 { int i; cout<<"哈夫曼编码为:"<<endl; for(i=1;i<num;i++) { if(tree[i]->ch!='~') { cout<<"字符["<<tree[i]->ch<<"],编码["; for(int j=0;j<tree[i]->count;j++) { cout<<tree[i]->encode[j];//写入字符 } cout<<"]"<<endl;//写入换行符 } } } //---------------------------------输出字符编码------------------------ //-------------------------------保存hfmTree---------------------------- void Save(int num)//保存hfmTree { int i; ofstream out; out.open("hfmTree.txt");//将护哈夫曼树存到文件中 if(out.is_open())//打开文件 { for(i=1;i<num;i++) { if(tree[i]->ch!='~') { out<<tree[i]->ch;//写入字符 out<<" ";//写入换行符 //cout<<tree[i]->encode[tree[i]->count-1]<<endl; for(int j=0;j<tree[i]->count;j++) { out<<tree[i]->encode[j];//写入字符 } out<<" ";//写入换行符 } } }else cout<<"文件操作出错!"<<endl; //文件带卡失败 } //-------------------------------保存hfmTree---------------------------- //-------------------------------编码Encoding---------------------------- void Encoding(int num)//编码Encoding { ifstream in,hfmtreefile,file; ofstream out; int select;//选择 string s; string start_file="";//存放原始报文 string encode_file="";//存放编码文件 char ch; HfmTree hfm[maxlen];//保存哈夫曼结果 int i,j,count =0;//结点个数 cout<<" ---------------------------------------"<<endl; cout<<"|-------------哈夫曼读取----------------|"<<endl; cout<<" ---------------------------------------"<<endl; cout<<"|--------------1:从内存中读取-----------|"<<endl; cout<<"|--------------0:从文件中读取-----------|"<<endl; cout<<" ---------------------------------------"<<endl; cout<<" 请选择[0|1]:"; cin>>select; while(select!=0&&select!=1) { cout<<" 您的输入有误,请重新输入:"<<endl; cin>>select; } switch(select) { case 1://从内存中读取 for(i=0;i<num;i++) { if(tree[i]->ch!='~') { hfm[count].ch = tree[i]->ch; s =""; for(j=0;j<tree[i]->count;j++) { s+=tree[i]->encode[j]; } hfm[count].encode = s; count++; } } break; case 0://从文件中读取 hfmtreefile.open("hfmTree.txt");//打开原文件 int line = 0;//行数 if(hfmtreefile.is_open())//打开文件 { while(hfmtreefile.get(ch))//当文件没有读完 { s = ""; while(ch!=' ') { s +=ch; hfmtreefile.get(ch); } if(line%2==0) { hfm[count].ch = s[0]; }else { hfm[count].encode = s; count ++; } line++; } }else cout<<"文件操作出错!"<<endl; //文件打开失败 break; } //文件打开失败 file.open("Textfile.txt");//将哈夫曼树存到文件中 out.open("CodeFile.txt");//将哈夫曼树存到文件中 if(file.is_open())//打开文件 { if(out.is_open()) { while(file.get(ch)) { start_file +=ch;//存放到字符串start_file for(i=0;i<count;i++)//从哈夫曼编码中找到对应的编码 { if(ch==hfm[i].ch)//找到哈夫曼树中相应的编码 { for(j=0;j<hfm[i].encode.length();j++) { encode_file +=hfm[i].encode[j];//保存到字符串encode_file中去 out<<hfm[i].encode[j]; } out<<' ';//编码以空格区分开 encode_file +=' ';//每个编码文件以空格分开 } } } }else cout<<"文件操作出错!"<<endl; //文件带卡失败 }else cout<<"文件操作出错!"<<endl; //文件带卡失败 cout<<"原始报文如下:"<<endl; for(i=0;i<start_file.length();i++) { cout<<start_file[i]; } cout<<endl; cout<<"以上为原始报文!"<<endl<<endl; cout<<"编码文件如下:"<<endl;; for(i=0;i<encode_file.length();i++) { cout<<encode_file[i]; } cout<<endl; cout<<"以上为编码文件!"<<endl<<endl; } //-------------------------------编码Encoding---------------------------- //-------------------------------译码Encoding---------------------------- void Decoding(int num)//译码Encoding { ifstream in; ofstream out; in.open("Codefile.txt");//读取哈夫曼树文件 out.open("TextFile.txt");//将护哈夫曼树存到文件中 string s,result_file="";//保存译码文件 char ch; int i,j; cout<<"文件译码如下:"<<endl; if(in.is_open())//打开文件 { if(out.is_open()) { while(in.get(ch)) { //cout<<"ch:"<<ch<<endl; s=""; while(ch!=' ') { s +=ch; in.get(ch); } for(i=0;i<num;i++)//从哈夫曼编码中找到对应的编码 { string temp=""; for(j=0;j<tree[i]->count;j++) { temp +=tree[i]->encode[j]; } if(s==temp) { //cout<<"s:"<<s<<endl; //cout<<"temp:"<<temp<<endl; cout<<tree[i]->ch;//输出原始字符 out<<tree[i]->ch; } } } }else cout<<"文件操作出错!"<<endl; //文件带卡失败 }else cout<<"文件操作出错!"<<endl; //文件带卡失败 cout<<endl; cout<<"文件译码如上!"<<endl; } //-------------------------------译码Encoding---------------------------- //------------------------------长度-------------------------------------- void Length_File()//长度 { ifstream textfle,codefile; codefile.open("Codefile.txt");//读取哈夫曼树文件 textfle.open("TextFile.txt");//将护哈夫曼树存到文件中 char ch; int TextFile_num=0,Codefile_num=0; if(textfle.is_open())//打开文件 { while(textfle.get(ch)) { TextFile_num++; } }else cout<<"文件操作出错!"<<endl; //文件打开失败 if(codefile.is_open())//打开文件 { while(codefile.get(ch)) { if(ch!=' ')Codefile_num++; } }else cout<<"文件操作出错!"<<endl; //文件打开失败 cout<<endl; cout<<"原始报文长度:"<<TextFile_num*8<<"Bits"<<endl; cout<<"编码后的报文长度:"<<Codefile_num<<"Bits"<<endl; } //-----------------------------长度-------------------------------------- //---------------------------------初始化结点---------------------------- void Data_Initialzation() { Data[0].ch = ' '; Data[0].weight = 186; Data[1].ch = 'A'; Data[1].weight = 64; Data[2].ch = 'B'; Data[2].weight = 13; Data[3].ch = 'C'; Data[3].weight = 22; Data[4].ch = 'D'; Data[4].weight = 32; Data[5].ch = 'E'; Data[5].weight = 103; Data[6].ch = 'F'; Data[6].weight = 21; Data[7].ch = 'G'; Data[7].weight = 15; Data[8].ch = 'H'; Data[8].weight = 47; Data[9].ch = 'I'; Data[9].weight = 57; Data[10].ch = 'J'; Data[10].weight = 1; Data[11].ch = 'K'; Data[11].weight = 5; Data[12].ch = 'L'; Data[13].weight = 32; Data[13].ch = 'M'; Data[14].weight = 20; Data[14].ch = 'N'; Data[15].weight = 57; Data[16].ch = 'O'; Data[16].weight = 63; Data[17].ch = 'P'; Data[17].weight = 15; Data[18].ch = 'Q'; Data[18].weight = 1; Data[19].ch = 'R'; Data[19].weight = 48; Data[20].ch = 'S'; Data[20].weight = 51; Data[21].ch = 'T'; Data[21].weight = 80; Data[22].ch = 'U'; Data[22].weight = 23; Data[23].ch = 'V'; Data[23].weight = 8; Data[24].ch = 'W'; Data[24].weight = 18; Data[25].ch = 'X'; Data[25].weight = 1; Data[26].ch = 'Y'; Data[26].weight = 16; Data[27].ch = 'Z'; Data[27].weight = 1; } //---------------------------------初始化结点---------------------------- int main() { int n; Data_Initialzation(); n =27; initialization(Data,n,tree);//左右子树初始化 Huffmantree(n,tree);//构造哈夫曼树 Encode(tree[n-1]); Print_Encode(n-1); Save(n-1); Encoding(n-1); Decoding(n-1); Length_File(); return 0; }