?? haffmantree.cpp
字號:
//程序名：HaffmanTree.cpp
//程序功能：實現哈弗曼樹的編碼和譯碼功能
//作者：黃秋旋
//日期：2008.12.4
//版本：1.0
//對應類頭文件：hafuman.h
//對應主程序：main.cpp
#include"hafuman.h"
#include<stack>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：初始化函數
//函數功能：初始化數據，并生成哈弗曼樹
//函數參數：無
//參數返回值：
// 如果重新初始化哈弗曼樹，則返回葉子節點的個數
// 如果從文件中讀取哈弗曼樹，則返回0表示讀取成功
int HaffmanTree::Haffman()
{
int num;
int choice;
cout<<"\n1:重新構造哈弗曼樹！";
cout<<"\n2:從文件中讀取哈弗曼樹！";
cout<<"請選擇： 1 或 2 ！"; //選擇重新構造哈弗曼樹，還是從文件中讀取哈弗曼樹
cin>>choice;
if(choice==1) //選擇重新構造哈弗曼樹
{
int fl;
int n;
cout<<"請輸入葉子的個數：";
cin>>n;
num=n;
ofstream fop;
fop.open("hfmTreey.txt", ios::out|ios::binary); //打開文件，存儲哈弗曼樹的初始化字符
HaffNode * ht= new HaffNode[2*num-1]; //申請存儲哈弗曼樹的節點的空間
char *yezi=new char[num]; //申請存儲初始化字符的空間
for(int i=0; i<num; i++)
{
cout<<"請出入第"<<i+1<<"個字符： ";
cin>>yezi[i]; //從終端輸入初始化字符
fop<<yezi[i]; //并將字符存儲到文件 hfmTreey.txt 中
cout<<"請輸入該字符的權值: ";
cin>>ht[i].weight; //從終端輸入初始化字符的權值
ht[i].parent=0;
ht[i].lchild=-1;
ht[i].rchild=-1;
ht[i].floor=1;
cout<<endl;
}
cout<<endl;
fop.close(); //關閉文件
for(int i=num; i<2*num-1; i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=-1;
ht[i].rchild=-1;
ht[i].floor=1;
}
for(int i=0; i<num-1; i++) //構造哈弗曼樹
{
int m1,m2,x1,x2;
m1=m2=1000; //存儲兩個最小的權值
x1=x2=0; //存儲兩個最小權值在結構體數組中的位置
for(int j=0; j<num+i; j++)
{
if(ht[j].weight<m1 && ht[j].parent==0)
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if(ht[j].weight<m2 && ht[j].parent==0)
{
m2=ht[j].weight;
x2=j;
}
}
ht[x1].parent=num+i;
ht[x2].parent=num+i;
ht[num+i].lchild=x1;
ht[num+i].rchild=x2;
ht[num+i].weight=ht[x1].weight+ht[x2].weight; //給新節點付權值
if(ht[x1].floor>=ht[x2].floor)
{
fl=ht[x1].floor;
ht[x2].floor=fl;
}
else
{
fl=ht[x2].floor;
ht[x1].floor=fl;
}
ht[num+i].floor=fl+1; //新節點的層次值
}
ofstream fop1;
fop1.open("hfmTree.txt",ios::out|ios::binary); //打開文件，寫入初始化字符的信息
for(int i=0;i<2*num-1;i++) //向文件hfmTree.txt寫入哈弗曼樹的信息
{
fop1<<ht[i].weight<<" ";
fop1<<ht[i].parent<<" ";
fop1<<ht[i].lchild<<" ";
fop1<<ht[i].rchild<<" ";
fop1<<ht[i].floor<<" ";
fop1<<endl;
}
fop1.close(); //關閉文件
cout<<"\n初始化完成，且已將哈弗曼樹存儲到hfmTree.dat文件中！\n";
}
else if(choice==2) //選擇從文件中已有的哈弗曼樹
{
int i=0;
int in;
ifstream fip0;
fip0.open("hfmTree.txt",ios::in|ios::binary); //打開文件，讀取哈弗曼樹的信息
if(fip0.fail()) //判斷打開是否失敗
{
cout<<"\n打開失敗! 該文件不存在!\n";
return 0;
}
while(fip0>>in) //計算文件hfmTree中的節點個數
i++;
fip0.close();
leafnum=i/10+1; //////////////
cout<<"\n該二叉樹有"<<leafnum<<"個葉子節點!"<<endl; //測試段
HaffNode *ht= new HaffNode[2*leafnum-1]; //申請存儲節點的空間
ifstream fip;
fip.open("hfmTree.txt",ios::in|ios::binary); //打開文件hfmTree,讀取文件中的內容
i=0;
while(fip>>in) //讀取哈弗曼樹的節點信息
{
int j=i/5;
int k=i%5;
switch(k)
{
case 0:
ht[j].weight=in;
break;
case 1:
ht[j].parent=in;
break;
case 2:
ht[j].lchild=in;//cout<<ht[j].lchild<<" ";//
break;
case 3:
ht[j].rchild=in;//cout<<ht[j].rchild<<" ";cout<<endl;//
break;
case 4:
ht[j].floor=in;
break;
}
i++;
}
fip.close(); //關閉文件hfmTree
cout<<"\n讀取完成！請進行下一步操作！";
return 0;
}
return leafnum=num;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//編碼函數
//函數功能：利用哈弗曼樹為文件中的內容編碼
//函數參數：無
//參數返回值：無
void HaffmanTree::Encode()
{
char ch;
ifstream fip2;
fip2.open("hfmTreey.txt",ios::in|ios::binary); //打開存儲初始化字符的文件
if(fip2.fail())
{
cout<<"\n打開失敗！\n";
return;
}
HaffNode *ht= new HaffNode[2*leafnum-1];
char *yezi=new char[leafnum];
int i=0;
while(fip2.get(ch))
{
yezi[i]=ch; //將文件中的字符讀取到yezi數組中
i++;
}
yezi[i]='\0'; //結束標志
fip2.close(); //關閉文件hfmTreey
ifstream fip3;
fip3.open("hfmTree.txt",ios::in|ios::binary); //打開文件hfmTree,讀取文件中的內容
if(fip3.fail())
{
cout<<"\n打開失敗! 該文件不存在!\n";
return;
}
i=0;
int in;
while(fip3>>in) //讀取文件中內容
{
int j=i/5;
int k=i%5;
switch(k)
{
case 0:
ht[j].weight=in;
break;
case 1:
ht[j].parent=in;
break;
case 2:
ht[j].lchild=in;
break;
case 3:
ht[j].rchild=in;
break;
case 4:
ht[j].floor=in;
break;
}
i++;
}
fip3.close(); //關閉文件hfmTree
ifstream fip;
fip.open("ToBeTran.txt",ios::in|ios::binary); //打開文件ToBeTran
int count=0;
while(fip.get(ch))
count++; //計算ToBeTran.txt中字符的個數
fip.close(); //關閉文件ToBeTran.txt
char *Tran=new char[count++]; //存儲ToBeTran.txt中字符
count=0;
ifstream fipp;
fipp.open("ToBeTran.txt",ios::in|ios::binary);
if(fipp.fail())
{
cout<<"\n 打開文件失敗！\n";
return;
}
cout<<"\n需要編碼的內容是: ";
while(fipp.get(ch))
{
cout<<ch;
Tran[count]=ch; //讀取ToBeTran.txt中字符
count++;
}
cout<<endl;
Tran[count]='\0';
fipp.close(); //關閉文件ToBeTran.txt
ofstream fop;
fop.open("CodeFile.txt", ios::out|ios::binary); //打開存儲代碼的文件
char *code=new char[leafnum]; //存儲字符編碼
int k=0;
while(Tran[k]!='\0') //為文件ToBeTran.txt中的內容編碼
{
int start=0;int l;
for(l=0;l<leafnum;l++)
if(yezi[l]==Tran[k]) //查找與需要編碼字符的對應字符
{
int child=l;
int parent=ht[child].parent;
while(parent!=0) //編碼
{
start++;
if(ht[parent].lchild==child)
code[start]='0';
else
code[start]='1';
child=parent;
parent=ht[child].parent;
}//while
while(start!=0)
{
fop<<code[start];
start--;
}//whilec
}//if
k++;
}//while
fop.close();
cout<<"\n編碼完成！且已存儲到文件CodeFile.txt中！\n";
};//Encode
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//譯碼函數
//函數功能：將代碼還原稱字符
//函數參數：無
//參數返回值：無
void HaffmanTree::Decode()
{
char ch;
ifstream fip2;
fip2.open("hfmTreey.txt",ios::in|ios::binary); //打開存儲初始化字符的文件
if(fip2.fail())
{
cout<<"\n 打開失敗！\n";
return;
}
HaffNode *ht= new HaffNode[2*leafnum-1]; //申請存儲二叉樹的空間
char *yezi=new char[leafnum]; //申請存儲初始化字符的空間
int i=0;
while(fip2.get(ch))
{
yezi[i]=ch; //將文件中的字符讀取到yezi數組中
i++;
}
yezi[i]='\0'; //結束標志
fip2.close(); //關閉文件hfmTreey
ifstream fip1;
fip1.open("hfmTree.txt",ios::in|ios::binary); //打開文件hfmTree,讀取文件中的內容
i=0;
int in;
while(fip1>>in) //讀取文件中的內容
{
int j=i/5;
int k=i%5;
switch(k)
{
case 0:
ht[j].weight=in;
break;
case 1:
ht[j].parent=in;
break;
case 2:
ht[j].lchild=in;
break;
case 3:
ht[j].rchild=in;
break;
case 4:
ht[j].floor=in;
break;
}
i++;
}
fip1.close(); //關閉文件hfmTree
ifstream fip3;
fip3.open("CodeFile.txt",ios::in|ios::binary);
i=0;
while(fip3.get(ch))
i++; //計算文件CodeFile中字符的個數
fip3.close();
char *code=new char[i++]; //申請存放文件CodeFile中字符的數組
ifstream fip4;
fip4.open("CodeFile.txt",ios::in|ios::binary);
i=0;
while(fip4.get(ch))
{
code[i]=ch; //讀取文件CodeFile中的代碼
i++;
}
code[i]='\0';
fip4.close();//關閉文件
i=0;
int j=2*leafnum-1-1; //初始化變量j,使j指向ht數組的跟節點
cout<<"\n譯碼后，得到字符為： ";
while(code[i]!='\0')
{
if(code[i]=='0')
j=ht[j].lchild;
else j=ht[j].rchild;
if(ht[j].rchild ==-1)
{
cout<<yezi[j]; //找到代碼對應字符，輸出該字符
j=2*leafnum-1-1; //j指向ht數組的跟節點，進行大二個字符的翻譯
}
i++;
}
cout<<endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//印代碼函數
//函數功能：印代碼文件中的代碼
//函數參數：無
//參數返回值：無
void HaffmanTree::Print()
{
ifstream fip;
fip.open("CodeFile.txt",ios::in|ios::binary); //以只讀方式打開代碼文件
ofstream fop;
fop.open("CodePrin.txt",ios::out|ios::binary); //打開文件,將代碼寫入該文件
char ch;
cout<<"\n編碼文件中的代碼為:\n\n";
int i=0;
while(fip.get(ch))
{
if(i%50==0) //每行輸入50個代碼
{
cout<<endl;
fop<<endl; //將代碼存儲到文件CodePrin.txt中
}
i++;
cout<<ch;
fop<<ch;
}//while
fip.close(); //關閉文件
fop.close();
cout<<"\n代碼已寫入文件CodePrint.txt中!\n";
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
//印哈弗曼樹
//函數功能：利用棧以凹表示法輸出哈弗曼樹
//函數參數：無
//參數返回值：無
void HaffmanTree::PrintTree()
{
char ch;
ifstream fip2;
fip2.open("hfmTreey.txt",ios::in|ios::binary); //打開存儲初始化字符的文件
if(fip2.fail())
{
cout<<"\n 打開失敗！\n";
return;
}
HaffNode *ht= new HaffNode[2*leafnum-1]; //申請存儲二叉樹的空間
char *yezi=new char[leafnum]; //申請存儲初始化字符的空間
int i=0;
while(fip2.get(ch))
{
yezi[i]=ch; //將文件中的字符讀取到yezi數組中
i++;
}
yezi[i]='\0'; //結束標志
fip2.close(); //關閉文件hfmTreey
ifstream fip1;
fip1.open("hfmTree.txt",ios::in|ios::binary); //打開文件hfmTree,讀取文件中的內容
i=0;
int in;
while(fip1>>in)
{
int j=i/5;
int k=i%5;
switch(k)
{
case 0:
ht[j].weight=in;
break;
case 1:
ht[j].parent=in;
break;
case 2:
ht[j].lchild=in;
break;
case 3:
ht[j].rchild=in;
break;
case 4:
ht[j].floor=in;
break;
}
i++;
}
fip1.close(); //關閉文件hfmTree
ofstream op;
op.open("TreePrint.txt",ios::out|ios::binary|ios::trunc);
op.close();
cout<<"\n該哈夫曼樹的凹入表示圖為:\n";
ofstream fop;
fop.open("TreePrint.txt",ios::out|ios::binary); //打開文件，用于存入哈弗曼樹
fop<<endl;
cout<<endl;
stack <HaffNode> s; //聲明存儲節點信息的棧
stack <int> f; //聲明存儲節點位置值的棧
int fl=2*leafnum-1-1; //初始化整形變量j，使j指向哈弗曼樹的跟節點
HaffNode p;
p=ht[fl];
s.push(p); //將根節點信息壓入棧
f.push(fl); //將根節點位置值壓入棧
while(!s.empty()) //當棧不空時，已凹表示法輸出哈弗曼樹
{
p=s.top();
s.pop();
cout<<endl;
for(int i=0; i<p.floor; i++) //根據節點所在層次，輸出其對應長度的橫桿
{
fop<<"---"; //將橫桿寫入文件
cout<<"---"; //將橫桿向終端輸出
}
fop<<" ";
fop<<p.weight<<" "; //輸出權值
cout<<" ";
cout<<p.weight<<" ";
fl=f.top();
f.pop();
if(fl<leafnum) //當節點是葉子節點是，輸出初始化字符
{
fop<<yezi[fl]; //將字符寫入文件
cout<<yezi[fl]; //將字符向終端輸出
}
fop<<endl;
cout<<endl;
if(p.rchild!=-1) //當有左孩子時，左孩子入棧
{
f.push(p.rchild); //左孩子的位置值進棧
s.push(ht[p.rchild]);
}
if(p.lchild!=-1) //當有左孩子時，右孩子入棧
{
f.push(p.lchild); //右孩子的位置值進棧
s.push(ht[p.lchild]);
}
}
fop.close(); //關閉文件
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -