哈夫曼樹(shù)源代碼

1、#include<iostream>#include<string>#include<fstream>using namespace std;#define Max 200 /最大結(jié)點(diǎn)數(shù)目#define INT 10000char chMax; /葉子結(jié)點(diǎn)信息（字符）int i,wMax; /w為輸入的權(quán)值數(shù)組typedef struct unsigned int weight; /權(quán)值 unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)typedef

2、char * *HuffmanCode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹(shù)HT，并求出n個(gè)字符的赫夫曼編碼HC。 int s1,s2,j,min1,min2; if(n<=1)  return; int m=2*n-1; HT=new HTNodem+1;/0號(hào)單元未用 for(i=1;i<=n;+i) /赫夫曼樹(shù)葉子結(jié)點(diǎn)的初始化&

3、#160;  HTi.weight=wi;  HTi.parent=0;  HTi.lchild=0;     HTi.rchild=0;   for(i=n+1;i<=m;+i) /非葉子結(jié)點(diǎn)的初始化     HTi.weight=0;   HTi.parent=0;    HTi.lchild=0;   HTi.rchild=0;  fo

4、r(i=n+1;i<=m;+i) /建赫夫曼樹(shù)  /在HT1.i-1選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為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='?'/非葉子結(jié)點(diǎn)的結(jié)點(diǎn)字符  /從葉子到根逆向求每個(gè)字符的赫夫曼編碼 HC=new char*n+1; /分配n個(gè)字符編碼的頭指針向量 char *cd=new charn; /分配求編碼的工作空間 HTi.lchild=s1; HTi.rchild=s2; cdn-1='0'  /編碼結(jié)束符

7、 for(i=1;i<=n;i+)  /逐個(gè)字符求赫夫曼編碼   int c,f,start=n-1;/編碼結(jié)束符位置  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個(gè)字符編碼分配空間   strcpy(HCi,&cdstart); /從cd復(fù)制編碼（串）到HC      delete cd;void Initialization(HuffmanTree &HT,HuffmanCode &HC,int &n)/初始化,注意加引用符號(hào)  char c;     ifstream fin("hfmTr

9、ee.txt",ios:in);/讀出      if(fin.fail() /若不存在此文件，則從終端讀入           cout<<"請(qǐng)輸入字符個(gè)數(shù)n："   cin>>n;   cout<<"請(qǐng)輸入字符及相應(yīng)權(quán)值："<<endl;   for(i=1;i<=n;i+)/注意點(diǎn)

10、0;       /getchar()是在輸入緩沖區(qū)順序讀入一個(gè)字符(包括空格、回車和tab)。             getchar(); /取消換行符    /getchar每次只能讀取一個(gè)字符.如果需要取消'n'的影響,可以用getchar();來(lái)清除,    /這里getchar();只是取得了'n'但是并沒(méi)有賦給任何字符變量

11、,所以不會(huì)有影響,相當(dāng)于清除了這個(gè)字推薦精選符.    chi=getchar(); /保證空格讀進(jìn)    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+)/寫入字符，權(quán)值，父結(jié)點(diǎn)，左右孩子      fout<<chi<<" "<<HTi.weight<<" "<<HTi.parent<<     " "<<HTi.lchild<<" "&l

13、t;<HTi.rchild<<endl;    for(i=1;i<=n;i+)/寫入字符及相應(yīng)的編碼    fout<<chi<<"  "<<HCi<<endl;   fout.close();   else   /如果文件存在，即讀到內(nèi)存中        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);/打開(kāi)文件 ofstream fout("CodeFile.txt",ios:out); if(fin.fail()推薦精選  cout<<"文件ToBeTran.txt打開(kāi)失?。?quot;<<endl;    getline(fin,str);/讀入一行，可以讀入空格 whil

17、e(!fin.eof()/文件不結(jié)束   getline(fin,str1);  str=str+str1;    fin.close(); for(i=0;stri!='0'i+)/編碼過(guò)程，一個(gè)字符一個(gè)字符來(lá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打開(kāi)失?。?quot;<<endl;   return ;     fin>>str;    fin.close();   len=str.size();   i=0;j=m;  while(i<len)  /從根出發(fā)，按字符0或1確定找左孩子或右孩子，直至葉子結(jié)點(diǎn)   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打開(kāi)失?。?quot;<<endl; fin>>str; cout<<"毎行50個(gè)代碼形式的編碼如下："<<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();/非葉子結(jié)點(diǎn)用權(quán)值

23、表示，葉子結(jié)點(diǎn)用字符表示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 表示層數(shù),r表示每層的結(jié)點(diǎn)數(shù) for(i=1;i<=2*n-1;i+)    if(HTi.parent=0)/找根結(jié)點(diǎn)的權(quán)值     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!='?') /如果是葉子結(jié)點(diǎn)就直接輸出，否則輸出權(quán)重          if(chi=' ')  chi='#'/標(biāo)記為空的字符       cout<<chi<<endl; fout<<chi<<endl;         

26、else        cout<<HTi.weight<<endl; fout<<HTi.weight<<endl;  p+; /p 表示每層的非葉子結(jié)點(diǎn)數(shù)       q+;/q 記錄每層的結(jié)點(diǎn)數(shù)目       if(q=r) k+; r=2*p; p=0; q=0; /如果該層的結(jié)點(diǎn)滿了，就到下一層，即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<<"-歡迎進(jìn)入哈夫曼的編/譯碼系統(tǒng)-"<<endl; cout<<"   

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

29、#160;   E、編碼"<<endl; cout<<"                 D、譯碼"<<endl; cout<<"               &

30、#160; P、打印代碼文件"<<endl; cout<<"                 T、打印哈夫曼樹(shù)"<<endl; cout<<"                 Q、退出"<<endl;  while(c!='Q')      cout<<"請(qǐng)選擇操作："  cin>>c;  switch(c)    case 'I': Initialization(推薦精選HT,HC,n);           &#