哈夫曼树源代码

1、#include<iostream>#include<string>#include<fstream>using namespace std;#define Max 200 /最大结点数目#define INT 10000char chMax; /叶子结点信息（字符）int i,wMax; /w为输入的权值数组typedef struct unsigned int weight; /权值 unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef

2、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) /赫夫曼树叶子结点的初始化&

3、#160;  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;  fo

4、r(i=n+1;i<=m;+i) /建赫夫曼树  /在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为S1和S2  min1=min2=INT;  for(j=1;j<i;j+)   if(HTj.parent=0&&(HTj.weight<min1)      min1=HTj.weight;  s1=j;        for(j=

5、1;j<i;j+)      if(HTj.parent=0&&(HTj.weight<min2)&&j!=s1)      min2=HTj.weight;  s2=j;   推荐精选          HTs1.parent=i; HTs2.parent=i;    HTi.lchild=s1;HTi.rchi

6、ld=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'  /编码结束符

7、 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'   else    cd-start='1&

8、#39;   HCi=new charn-start;/为第i个字符编码分配空间   strcpy(HCi,&cdstart); /从cd复制编码（串）到HC      delete cd;void Initialization(HuffmanTree &HT,HuffmanCode &HC,int &n)/初始化,注意加引用符号  char c;     ifstream fin("hfmTr

9、ee.txt",ios:in);/读出      if(fin.fail() /若不存在此文件，则从终端读入           cout<<"请输入字符个数n："   cin>>n;   cout<<"请输入字符及相应权值："<<endl;   for(i=1;i<=n;i+)/注意点

10、0;       /getchar()是在输入缓冲区顺序读入一个字符(包括空格、回车和tab)。             getchar(); /取消换行符    /getchar每次只能读取一个字符.如果需要取消'n'的影响,可以用getchar();来清除,    /这里getchar();只是取得了'n'但是并没有赋给任何字符变量

11、,所以不会有影响,相当于清除了这个字推荐精选符.    chi=getchar(); /保证空格读进    cin>>wi;      HuffmanCoding(HT,HC,w,n);         ofstream fout("hfmTree.txt",ios:out);/写入      fout<<n<<

12、endl;         for(i=1;i<=2*n-1;i+)/写入字符，权值，父结点，左右孩子      fout<<chi<<" "<<HTi.weight<<" "<<HTi.parent<<     " "<<HTi.lchild<<" "&l

13、t;<HTi.rchild<<endl;    for(i=1;i<=n;i+)/写入字符及相应的编码    fout<<chi<<"  "<<HCi<<endl;   fout.close();   else   /如果文件存在，即读到内存中        fin>>n;  

14、;      for(i=1;i<=2*n-1;i+)             fin.get(chi);     fin>>HTi.weight>>HTi.parent>>HTi.lchild>>HTi.rchild;     fin.get(c);     &#

15、160;      for(i=1;i<=n;i+)         fin.get(chi);       fin>>HCi;       fin.get(c);      fin.close();void Encoding(HuffmanCode & HC,int n)

16、 /编码 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);/读入一行，可以读入空格 whil

17、e(!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)  fout<<HCj; 

18、    fout<<endl; 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<

19、;<"文件CodeFile.txt打开失败！"<<endl;   return ;     fin>>str;    fin.close();   len=str.size();   i=0;j=m;  while(i<len)  /从根出发，按字符0或1确定找左孩子或右孩子，直至叶子结点   if(stri='0')    

20、     j=HTj.lchild;   else j=HTj.rchild;推荐精选   if(HTj.lchild=0)      fout<<chj;  j=m;    i+;    fout<<endl;void Print(HuffmanTree HT,int n)/打印代码文件 int i; char strMax; ifstream fin("Cod

21、eFile.txt",ios:in); ofstream fout("CodePrin.txt",ios:out); if(fin.fail()  cout<<"文件CodeFile.txt打开失败！"<<endl; fin>>str; cout<<"毎行50个代码形式的编码如下："<<endl; for(i=0;i<strlen(str);i+)   if(i

22、%50=0&&i!=0) /毎50以换行     cout<<endl; fout<<endl;        cout<<stri;fout<<stri;         cout<<endl;fout<<endl;  fin.close(); fout.close();/非叶子结点用权值

23、表示，叶子结点用字符表示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;i<=2*n-1;i+)    if(HTi.parent=0)/找根结点的权值     m=HTi.weight; for(l=m;l>0;

24、l-)     for(i=1;i<=2*n-1;i+)   if(HTi.weight=l)推荐精选          for(j=0;j<k;j+)     cout<<"   " fout<<"   " /控制每层前面的空格   

25、; if(chi!='?') /如果是叶子结点就直接输出，否则输出权重          if(chi=' ')  chi='#'/标记为空的字符       cout<<chi<<endl; fout<<chi<<endl;         

26、else        cout<<HTi.weight<<endl; fout<<HTi.weight<<endl;  p+; /p 表示每层的非叶子结点数       q+;/q 记录每层的结点数目       if(q=r) k+; r=2*p; p=0; q=0; /如果该层的结点满了，就到下一层，即k+1   

27、   int 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<<"   

28、60;     菜单如下："<<endl; cout<<"                 I、初始化"<<endl; cout<<"             &

29、#160;   E、编码"<<endl; cout<<"                 D、译码"<<endl; cout<<"               &

30、#160; P、打印代码文件"<<endl; cout<<"                 T、打印哈夫曼树"<<endl; cout<<"                 Q、退出"<<endl;  while(c!='Q')      cout<<"请选择操作："  cin>>c;  switch(c)    case 'I': Initialization(推荐精选HT,HC,n);           &#