//裏面有遞歸遍歷，有叠代遍歷。可以寫文件，可以壓縮編碼。可以讀文件。
//妳不需要什麽功能的話就刪去相應的函數就行了。
//希望加分。
#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
using namespace std;
const int maxlen = 10000; //結點最大數目
const int maxlen2 = 260; //字符最大數目，葉節點最大數目
const int maxchar = 260; //字符最大數目
#define INTMAX 10000000; //大數，大於任意壹個權值
struct CharSet //程序初始化時保存字符和結點的結構體。
{
char ch;
int weight;
};
struct HaffNode //哈夫曼樹結點結構
{
int weight,parent,lchild,rchild;
char ch;
HaffNode() {weight=0; parent=lchild=rchild=-1; ch='\n';}
};
struct HaffCode //哈夫曼樹字符編碼信息結構
{
unsigned int bit; //通過位運算，用壹個無符號整形來表示壹串二進制編碼。
int startb; //記錄偏移量。
int weight;
char ch;
HaffCode() { bit=0; startb = -1; weight=0; ch='\n';}
HaffCode& operator=(HaffCode & obj) //重載賦值符號
{
bit=obj.bit; startb=obj.startb;
ch=obj.ch; weight=obj.weight;
return *this;
}
};
class HaffmanSystem
{
private:
CharSet cs[maxlen/2]; //保存初始化時的字符和權值信息。
HaffNode hn[maxlen]; //保存哈夫曼樹結點信息。
HaffCode hc[maxlen/2]; //保存哈夫曼樹字符編碼信息。
HaffCode hc2[maxchar]; //索引散列。考慮到字符數少，以字符的十進制數作為下標保存和索引字符編碼信息，時間為O(1);
int head; //根結點的數組下標。
int n;
int leafnum; //葉節點個數，字符個數。
public:
HaffmanSystem() {n=head=leafnum=0;}
void Haffman(); //哈夫曼樹生成函數。
void InitisLization(); //初始化，調用Haffman();
void Encoding(); //對文件"ToBeTran"進行編碼。
void Decoding(); //對文件"CodeFile"譯碼。
void Print(); //印代碼至屏幕。
static void TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop);
void TreePrinting(); //輸出哈夫曼樹圖形到屏幕和文件，其中要調用靜態實例函數完成遞歸功能。
void TreeFromFile(); //從文件中獲取哈夫曼樹。
};
void HaffmanSystem::InitisLization()
{
cout<<"字符集大小n,（去掉空格）："<<endl; //讀入字符和權值信息。
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"第"<<i+1<<"個字符和權值，用空格隔開：";
cin>>cs[i].ch>>cs[i].weight;
}
cout<<"最後輸入空格的權值(小於等於0表示空格不存在): "<<endl; //對空格特殊處理。
cin>>cs[n].weight;
cs[n].ch=' ';
if(cs[n].weight>0) n++;
this->Haffman(); //調用哈夫曼樹生成函數。
}
//哈夫曼樹生成函數。
void HaffmanSystem::Haffman()
{
leafnum=n;
int i,j,m1,m2,k1,k2;
for(i=0;i<n;i++)
{
hn[i].weight = cs[i].weight;
hn[i].ch = hc[i].ch = cs[i].ch;
}
for(i=0;i<n-1;i++) //n-1個分支節點；
{
m1=m2=INTMAX; k1=k2=0;
for(j=0;j<n+i;j++)
{
if(m1>hn[j].weight && hn[j].parent==-1)
{
m2 = m1; k2 = k1;
m1 = hn[j].weight ; k1 = j;
}
else
if(m2>hn[j].weight && hn[j].parent==-1)
{
m2 = hn[j].weight; k2 = j;
}
}
hn[k1].parent = n+i; hn[k2].parent = n+i;
hn[n+i].weight = hn[k1].weight+hn[k2].weight;
hn[n+i].lchild = k1; hn[n+i].rchild = k2;
head = n+i;
}
int child,parent;
for(i=0;i<n;i++)
{
hc[i].weight = hn[i].weight;
child = i;
parent = hn[child].parent;
while(parent != -1)
{
if(hn[parent].lchild == child)
{
++hc[i].startb;
}
else if(hn[parent].rchild == child)
{
hc[i].bit = hc[i].bit|(1<<++hc[i].startb);
}
child = parent;
parent = hn[child].parent;
}
hc2[hc[i].ch]=hc[i];
}
char choice='N';
cout<<"是否保存當前哈夫曼樹進hfmTree.dat中？"<<endl;
cin>>choice;
if(choice=='y'||choice=='Y') //把生成的哈弗曼樹保存在文件hfmTree.dat中。
{
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
if(!fop) {cout<<"打開文件錯誤，保存失敗"<<endl; return ;}
fop.write((char*)&leafnum,sizeof(leafnum));
for(i=0;i<2*leafnum-1;i++)
{
fop.write((char*)&hn[i],sizeof(hn[i]));
}
for(i=0;i<maxchar;i++)
{
fop.write((char*)&hc2[i],sizeof(hc2[i]));
}
fop.close();
cout<<"保存成功！"<<endl;
}
}
//編碼函數。
void HaffmanSystem::Encoding()
{
if(leafnum==0) { TreeFromFile(); }
char ch;
int i,num=0,bitTemp, startTemp=-1, temp2=0;
ifstream fip2("ToBeTran.txt",ios::in);
if(!fip2){ cout<<"無法打開指定文件ToBeTran.txt！"<<endl; return ;}
while(fip2.get(ch)) { num++;}
fip2.close();
ofstream fop1("CodeFile.dat",ios::out|ios::trunc|ios::binary);
if(!fop1){ cout<<"無法打開指定文件CodeFile.dat！"<<endl; return ;}
ofstream fop2("CodePrin.txt",ios::out|ios::trunc);
if(!fop2){ cout<<"無法打開指定文件CodePrin.txt！"<<endl; return ;}
ifstream fip1("ToBeTran.txt",ios::in);
if(!fip1){ cout<<"無法打開指定文件ToBeTran.txt！"<<endl; return ;}
fop1.write((char*)& num,sizeof(num)); //先寫入字符數量。
char bitBuf=0; //用壹個字符空間來緩沖二進制數據，每湊滿八位就寫入編碼文件。
cout<<"\n待編碼文件ToBeTran.txt: ";
for(i=7;;i--)
{
if(i==-1)
{
//用壹個字符空間bitBuf來緩沖二進制數據，每湊滿八位就寫入編碼文件。
fop1.write((char*)& bitBuf,sizeof(bitBuf));
i=7; bitBuf=0;//初始字符，使之為二進制“00000000”;
}
if(startTemp<0)
{
if(num--<=0) break;
fip1.get(ch);
cout<<ch;
bitTemp = hc2[ch-0].bit;
startTemp = hc2[ch-0].startb;
}
//位運算，確定某位上是0還是1。
temp2 = (1 & bitTemp>>startTemp--);
if(temp2) fop2<<"1";
else fop2<<"0";
bitBuf = bitBuf | temp2<<i;
//還是位運算，把0或1與原字符相與得到新的編碼信息。如00010000 | 1<<7 =10010000.
}
fop1.write((char*)& bitBuf,sizeof(bitBuf)); //把最後的壹段寫入文件。
fip1.close();
fop1.close(); //關閉文件流。
fop2.close();
cout<<"\n\n編碼成功！"<<endl;
}
//譯碼函數。
void HaffmanSystem::Decoding()
{
if(leafnum==0) { TreeFromFile();}
ofstream fop("TextFile.txt",ios::out|ios::trunc);
if(!fop) {cout<<"無法打開指定文件[TextFile.txt]"<<endl; return ;}
ifstream fip("CodeFile.dat",ios::in);
if(!fip) {cout<<"無法打開指定文件[CodeFile.dat]"<<endl; return ;}
char ch,bitBuf;
int num,bitTemp=-1, startTemp=-1;
int FLAG=0,parent=head;
fip.read((char*)& num,sizeof(num));
cout<<"譯碼結果： ";
for(int i=-1;num>0;i--)
{
if(i==-1)
{
fip.read((char*)& bitBuf,sizeof(bitBuf));
i=7;
}
//譯碼和編碼壹樣，同樣飄逸的位運算處理，可以節省時間和空間。
FLAG=(1<<i)&bitBuf;
if(FLAG==0) //0向左
{
parent = hn[parent].lchild;
}
else //1向右
{
parent = hn[parent].rchild;
}
//自頂向下搜索，碰到葉節點就是所求結點字符。
if(hn[parent].lchild==-1 && hn[parent].rchild==-1)
{
ch=hn[parent].ch;
cout<<ch;
fop <<ch;
parent = head;
num--;
}
}
cout<<endl;
fip.close();
fop.close();
cout<<"譯碼成功！"<<endl;
}
//打印編碼函數。
void HaffmanSystem::Print()
{
ifstream fip("CodePrin.txt",ios::in);
if(!fip) {cout<<"無法打開指定文件[CodePrin.txt]"<<endl; return ;}
int j =0;
char ch;
cout<<"字符形式編碼文件CodePrin.txt: ";
while(fip>>ch)
{
if(j%50==0) cout<<endl; //50個字符換行。
j++;
cout<<ch;
}
cout<<endl;
fip.close();
}
//輸出哈夫曼樹到屏幕和文件TreePrint.txt
void HaffmanSystem::TreePrinting()
{
if(leafnum==0) { TreeFromFile();}
ofstream fop("TreePtint.txt",ios::out|ios::trunc);
if(!fop) {cout<<"無法打開指定文件TreePtint.txt！"<<endl; return;}
cout<<"逆時針90度直觀輸出二叉樹(括號裏面是權值)：\n"<<endl;
fop <<"逆時針90度直觀輸出二叉樹(括號裏面是權值)：\n"<<endl;
TreePrinting(head,1,2,this,fop); //fop傳遞壹個文件流，用於在遞歸的各個層次對同壹文件輸出。
cout<<endl;
fop.close();
}
//輸出函數，靜態實現，方便遞歸調用。
void HaffmanSystem::TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop)
{ //模仿課本輸出二叉樹。
if(pos>=0 && pos<=p->head)
{
TreePrinting(p->hn[pos].rchild,i+1,1,p,fop);
for(int j=0; j<4*(i-1); j++) {cout<<" "; fop<<" ";}
if(child_flag==-1) {cout<<"\\"; fop<<"\\";}
else if(child_flag== 1) {cout<<"/"; fop<<"/";}
if(p->hn[pos].ch=='\n') {cout<<"--NULL"<<endl; fop<<"--NULL"<<endl;}
else
{
cout<<"--"<<p->hn[pos].ch<<"("<<p->hn[pos].weight<<")"<<endl;
fop<<"--"<<p->hn[pos].ch<<"("<<p->hn[pos].weight<<")"<<endl;
}
TreePrinting(p->hn[pos].lchild,i+1,-1,p,fop);
}
}
void HaffmanSystem::TreeFromFile()
{
int i;
cout<<"哈夫曼樹不在內存中，嘗試從文件中讀入哈夫曼樹..."<<endl;
ifstream file;
file.open("hfmTree.dat",ios::in|ios::binary);
if(!file) {cout<<"無法打開指定文件hfmTree.dat！"<<endl; return ;}
if(file.eof()) {cout<<"哈夫曼樹文件空，請初始化！"<<endl; return ;}
file.read((char*)&leafnum,sizeof(leafnum));
head=leafnum*2-2;
for(i=0;i<2*leafnum-1;i++)
{
file.read((char*)&hn[i],sizeof(hn[i]));
}
for(i=0;i<=maxchar;i++)
{
file.read((char*)&hc2[i],sizeof(hc2[i]));
}
file.close();
}
//主函數.
int main()
{
HaffmanSystem * T = new HaffmanSystem();
char choice = 'Y';
while(choice!='0')
{
cout<<"-------------------------------------------------------------------------------"<<endl;
cout<<std::left<<setw(12)<<" 1--初始化"<<setw(12)<<"2--編碼 "<<setw(12)<<"3--譯碼 "<<setw(17)<<"4--印代碼文件 "<<setw(15)<<"5--印哈夫曼樹 "<<"0--退出"<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
cout<<std::right<<setw(40)<<"操作： ";
cin>>choice;
switch(choice)
{
case '0': { cout<<"系統已經退出"<<endl; return 0;}
case '1': { T->InitisLization(); break;}
case '2': { T->Encoding(); break;}
case '3': { T->Decoding(); break;}
case '4': { T->Print(); break;}
case '5': { T->TreePrinting(); break;}
default :break;
}
}
return 0;
}