哈夫曼树源代码

#include#include#includeusing namespace std;#define Max 200 /最大结点数目#define INT 10000char chMax; /叶子结点信息（字符）int i,wMax; /w为输入的权值数组typedef structunsigned int weight; /权值unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char * *HuffmanCode; /动态分配数组存储赫夫曼编码表void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/w存放n个字符的权值(均0),构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。int s1,s2,j,min1,min2;if(n=1) return;int m=2*n-1;HT=new HTNodem+1;/0号单元未用for(i=1;i=n;+i) /赫夫曼树叶子结点的初始化HTi.weight=wi; HTi.parent=0;HTi.lchild=0; HTi.rchild=0;for(i=n+1;i=m;+i) /非叶子结点的初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0;for(i=n+1;i=m;+i) /建赫夫曼树 /在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为S1和S2min1=min2=INT;for(j=1;ji;j+)if(HTj.parent=0&(HTj.weightmin1) min1=HTj.weight; s1=j; for(j=1;ji;j+) if(HTj.parent=0&(HTj.weightmin2)&j!=s1) min2=HTj.weight; s2=j; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; chi=?;/非叶子结点的结点字符/从叶子到根逆向求每个字符的赫夫曼编码HC=new char*n+1; /分配n个字符编码的头指针向量char *cd=new charn; /分配求编码的工作空间HTi.lchild=s1; HTi.rchild=s2;cdn-1=0; /编码结束符for(i=1;i=n;i+) /逐个字符求赫夫曼编码int c,f,start=n-1;/编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=new charn-start;/为第i个字符编码分配空间strcpy(HCi,&cdstart); /从cd复制编码（串）到HC delete cd;void Initialization(HuffmanTree &HT,HuffmanCode &HC,int &n)/初始化,注意加引用符号 char c; ifstream fin(hfmTree.txt,ios:in);/读出 if(fin.fail() /若不存在此文件，则从终端读入 coutn; cout请输入字符及相应权值：endl; for(i=1;iwi; HuffmanCoding(HT,HC,w,n); ofstream fout(hfmTree.txt,ios:out);/写入 foutnendl; for(i=1;i=2*n-1;i+)/写入字符，权值，父结点，左右孩子 foutchi HTi.weight HTi.parent HTi.lchild HTi.rchildendl; for(i=1;i=n;i+)/写入字符及相应的编码 foutchi HCin; for(i=1;iHTi.weightHTi.parentHTi.lchildHTi.rchild; fin.get(c); for(i=1;iHCi; fin.get(c); fin.close();void Encoding(HuffmanCode & HC,int n) /编码int i,j;string str,str1;ifstream fin(ToBeTran.txt,ios:in);/打开文件ofstream fout(CodeFile.txt,ios:out);if(fin.fail()cout文件ToBeTran.txt打开失败！endl; getline(fin,str);/读入一行，可以读入空格while(!fin.eof()/文件不结束getline(fin,str1);str=str+str1; fin.close();for(i=0;stri!=0;i+)/编码过程，一个字符一个字符来j=1;while(chj!=stri&j=n) j+;if(j=n) foutHCj; foutendl;fout.close();void Decoding(HuffmanTree HT,int n)/译码 int j,len,m; string str; m=2*n-1; ifstream fin(CodeFile.txt,ios:in); ofstream fout(TextFile.txt,ios:out); if(fin.fail() cout文件CodeFile.txt打开失败！str; fin.close(); len=str.size(); i=0;j=m; while(ilen) /从根出发，按字符0或1确定找左孩子或右孩子，直至叶子结点 if(stri=0) j=HTj.lchild; else j=HTj.rchild; if(HTj.lchild=0) foutchj; j=m; i+; foutendl;void Print(HuffmanTree HT,int n)/打印代码文件int i;char strMax;ifstream fin(CodeFile.txt,ios:in);ofstream fout(CodePrin.txt,ios:out);if(fin.fail()cout文件CodeFile.txt打开失败！str;cout毎行50个代码形式的编码如下：endl;for(i=0;istrlen(str);i+)if(i%50=0&i!=0) /毎50以换行coutendl; foutendl; coutstri;foutstri; coutendl;foutendl;fin.close(); fout.close();/非叶子结点用权值表示，叶子结点用字符表示void PrintTree(HuffmanTree &HT,int &n)ofstream fout(TreePrint.txt,ios:out);/写入文件int l,j,m=0,k=1,q=0,p=0,r=1;/k 表示层数,r表示每层的结点数for(i=1;i0;l-) for(i=1;i=2*n-1;i+)if(HTi.weight=l)for(j=0;jk;j+)cout ; fout ; /控制每层前面的空格if(chi!=?) /如果是叶子结点就直接输出，否则输出权重if(chi= ) chi=#;/标记为空的字符 coutchiendl; foutchiendl; else coutHTi.weightendl; foutHTi.weightendl; p+; /p 表示每层的非叶子结点数 q+;/q 记录每层的结点数目 if(q=r) k+; r=2*p; p=0; q=0; /如果该层的结点满了，就到下一层，即k+1int main()HuffmanTree HT;HuffmanCode HC;char c;int n;HT=new HTNodeMax;HC=new char*Max;for(int i=1;i=Max;i+)/初始化HCi=new char20;cout-欢迎进入哈夫曼的编/译码系统-endl;cout 菜单如下：endl;cout I、初始化endl;cout E、编码endl;cout D、译码endl;cout P、打印代码文件endl;cout T、打印哈夫曼树endl;cout Q、退出endl; while(c!=Q) coutc; switch(c) case I: Initialization(HT,HC,n); cout哈夫曼树成功存入文件hfmTree中！endl; break; case E: Encoding(HC,n); cout对文件ToBeTran的编码结果成功存入文件CodeFile中！endl; break; case D: Decoding(HT,n); cout对文件CodeFile的译码结果成功存入文件TextFile中！endl; break; case P: Print(HT,n); cout毎行50个代码形式的编码结果