哈弗曼编码算法源代码

/* 数电一班 张颖 2007430040 */ #define MAXVALUE 800 //一定要足够大才行!! //先看看字符集中各权值，都有100多的了，你想想啊，如果设置成100那是肯定不行的！！200,500的也不行！ //如果设置过小会使哈夫曼树的构建出现错误，因为MAXVALUE是启动寻找“最小、次小”子树的初值 #define MAXLEAF 40 #define MAXNODE MAXLEAF*2-1 #define MAXBIT 20 //一定也得足够大，如果不足够大的话会访问越界!! #define LENGTH 15 //************************************主函数********************************************************* #include <iostream> #include <fstream> using namespace std; typedef struct //存储结点 静态链表结点结构 { int weight; //结点权值 int lchild; int rchild; int parent; }HNodeType; typedef struct //存储译码 { int bit[MAXBIT]; int start; }HCodeType; //=======================================全局变量============================================= HNodeType HuffNode[MAXNODE];//哈夫曼数的静态链表 char *a; //******************************************************************************************** //初始化功能：从键盘接收字符集大小n，以及n个字符和n个权值 //******************************************************************************************** char * init(int &n) { ifstream in("init.dat"); //定义输入流对象in if(in) cout<<"文件“init.dat”已打开……"<<endl; else { cout<<"文件打开失败！"; return NULL; } in>>n; cout<<"字符集的大小为：n="<<n<<endl; char *a=new char[n]; //a用来存储字符集，数组中的每一位分别对应静态链表中前n个元素的权值 for(int i=0;i<MAXNODE;i++) //初始化静态链表 { HuffNode[i].weight=0; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; HuffNode[i].parent=-1; } for(i=0;i<n;i++) //初始化字符集及静态链表中的对应权值 { in>>a[i]; in>>HuffNode[i].weight; } //in.close(); cout<<"-------------------------"<<endl; //输出字符集及静态链表中的对应权值 cout<<"字符集及对应权值为："<<endl; for(i=0;i<n;i++) { cout<<a[i]<<'\t'; cout<<HuffNode[i].weight<<"\t"; if((i+1)%4==0)cout<<endl; //四组换行 } cout<<endl; return a; } //******************************************************************************************** //构造哈夫曼树，并将哈夫曼数组存储在文件中 //******************************************************************************************** int HuffmanTree(int n) { int i,j,m1,m2,x1,x2; for(i=0;i<n-1;i++) { m1=m2=MAXVALUE; x1=x2=0; for(j=0;j<n+i;j++) //找到权值最小的两棵子树的根结点，记录其数组下标和权值 { if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) { m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) { m2=HuffNode[j].weight; x2=j; } } HuffNode[x1].parent=n+i; //合并两棵子树为一棵 HuffNode[x2].parent=n+i; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2; HuffNode[n+i].weight=m1+m2; } //-----------------------------------哈夫曼树创建完成-------------------- ofstream out("hfmtree.dat"); if(out) cout<<"文件“hfmtree.dat”已打开……开始写入哈夫曼树数据……"<<endl; else { cout<<"文件打开失败！"; return NULL; } for(i=0;i<2*n-1;i++) out<<i<<"\t"<<HuffNode[i].weight<<"\t"<<HuffNode[i].lchild<<"\t"<<HuffNode[i].rchild<<"\t"<<HuffNode[i].parent<<endl; return 1; } //******************************************************************************************** //从文件读入哈夫曼树，编码存入数组并写入文件 //******************************************************************************************** int HuffmanCode(int n) { int i,j,c,p; HCodeType HuffCode[MAXLEAF],cd; /*因为哈夫曼树存在于全局的静态链表里，所以调用完函数init()之后，哈夫曼树仍然存在所以不必 再从文件中读取了；如果不是全局变量，调用函数init()之后哈夫曼树丢失，只存在于文件中就需要 重新从文件中读取哈夫曼树的数据到内存中来 ifstream in("hfmtree.dat"); if(in) cout<<"文件“hfmtreea.dat”已打开……开始读取哈夫曼树数据……"<<endl; else { cout<<"文件打开失败！"; return NULL; } for(i=0;i<2*n-1;i++) in>>c>>HuffNode[i].weight>>HuffNode[i].lchild>>HuffNode[i].rchild>>HuffNode[i].parent;*/ for(i=0;i<n;i++) //求每个叶子结点i(0<=i<n)的哈夫曼编码 { cd.start=MAXBIT-1; //cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) { if(HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent; //一直向上，直至根结点 } for(j=cd.start+1;j<MAXBIT;j++) HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start; } //-----------------------------------哈夫曼树编码完成-------------------- ofstream out("codefile.dat"); if(out) cout<<"文件“codefile.dat”已打开……开始写入哈夫曼编码……"<<endl; else { cout<<"文件打开失败！"; return NULL; } for(i=0;i<n;i++) { out<<a[i]<<"\t"; for(j=HuffCode[i].start+1;j<MAXBIT;j++) out<<HuffCode[i].bit[j]; //out<<"\t"<<HuffCode[i].start<<endl; //向文本中输入start out<<endl; } cout<<" 字符 编码"<<endl; for(i=0;i<n;i++) { cout<<"\t"<<a[i]<<"\t"; for(j=HuffCode[i].start+1;j<MAXBIT;j++) cout<<HuffCode[i].bit[j]; cout<<endl; } return 1; } //******************************************************************************************** //从文件读入“哈夫曼编码”、“待译码的文本”---译码---并将译码结果写入文件 //******************************************************************************************** int HuffmanDisCode(int n) { int i,j,k; char temp1; int code[MAXLEAF]; char str1[100]; int str2[100]; ifstream in("codefile.dat"); if(in) cout<<"文件“codefile.dat”已打开……开始读取编码……"<<endl; else { cout<<"文件打开失败！"; return NULL; } for(i=0;i<n;i++) //读取哈夫曼编码并放入整形数组code中 in>>temp1>>code[i]; //------------------------------------------------------------------------- ifstream in2("todiscodefile.dat"); if(in2) cout<<"文件“todiscodefile.dat”已打开……开始读取待译码的文档……"<<endl; else { cout<<"文件打开失败！"; return NULL; } i=0; while(in2) //读取待译码的文本内容到字符型数组str1中 { in2>>str1[i++]; } //-------------------------------------------------------------------------- cout<<"待译码的文本内容为："<<endl; //输出待译码的文本内容 for(j=0;j<i;j++) cout<<str1[j]; cout<<endl; //-------------------------------------------------------------------------- for(j=0;j<i;j++) //译码，将译码存入整形数组str2中 for(k=0;k<n;k++) { if(str1[j]==a[k]) str2[j]=code[k]; } //-------------------------------------------------------------------------- cout<<"译码结果："<<endl; //输出译码结果 for(k=0;k<i-1;k++) cout<<str2[k]; cout<<endl; //-------------------------------------------------------------------------- ofstream out("textfile.dat"); //将译码结果写入文件 if(out) cout<<"文件“textfile.dat”已打开……开始写入译码……"<<endl; else { cout<<"文件打开失败！"; return NULL; } for(k=0;k<i-1;k++) out<<str2[k]; return