Ⅰ 我們有個數據結構的哈夫曼編碼解碼的課程設計，你能幫幫我嗎
樹和哈夫曼樹實驗報告
一．實驗目的
練習樹和哈夫曼樹的有關操作，和各個演算法程序，理解哈夫曼樹的編碼和解碼
二．實驗環境
Microsoft visual c++
三．實驗問題描述
1. 問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，並對其進行遍歷（先序、中序和後序），列印輸出遍歷結果。
基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），並將此二叉樹按照「樹狀形式」列印輸出，然後對其進行遍歷（先序、中序和後序），最後將遍歷結果列印輸出。在遍歷演算法中要求至少有一種遍歷採用非遞歸方法。
測試數據：
ABCØØDEØGØØFØØØ（其中Ø表示空格字元）
輸出結果為：
先序：ABCDEGF
先序：CBEGDFA
先序：CGEFDBA
2. 問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮簡訊息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接受端將傳來的數據進行解碼（復原）。對於雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/解碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/解碼系統。
基本要求：(至少完成功能1-2）
一個完整的系統應具有以下功能：
I：初始化（Initialization）。從終端讀入字元集大小n，以及n個字元和n個權值，建立哈夫曼樹，並將它存於文件hfmTree中。
基本要求：
E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然後將結果存入文件CodeFile中。
D：解碼（Decoding )。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行解碼，結果存入文件TextFile中。
P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字元形式的編碼文件寫入文件CodePrint中。
T：印哈夫曼樹（TreePrinting）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字元形式的哈夫曼樹寫入文件TreePrint中。
測試數據：
設權值w=（5，29，7，8，14，23，3，11），n=8。
按照字元『0』或『1』確定找左孩子或右孩子，則權值對應的編碼為：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
用下表給出的字元集和頻度的實際統計數據建立哈夫曼樹，並實現以下報文的編碼和解碼：「THIS PROGRAM IS MY FAVORITE」。
四．實驗主要程序流
實驗題目一主要程序：
1．
void CreatBiTree(BitTree *bt)//用擴展先序遍歷序列創建二叉樹，如果是#當前樹根置為空，否則申請一個新節點//
{
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
}
2．void Visit(char ch)//訪問根節點
{
printf("%c ",ch);
}
3．
void PreOrder(BitTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
4． void InOrder(BitTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
5．int PostTreeDepth(BitTree bt) //後序遍歷求二叉樹的高度遞歸演算法//
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); //求左子樹的深度
hr=PostTreeDepth(bt->RChild); //求右子樹的深度
max=hl>hr?hl:hr; //得到左、右子樹深度較大者
return(max+1); //返回樹的深度
}
else return(0); //如果是空樹，則返回0
}
6．void PrintTree(BitTree Boot,int nLayer) //按豎向樹狀列印的二叉樹 //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",Boot->data);
PrintTree(Boot->LChild,nLayer+1);
}
7．void main()
{
BitTree T;
int h;
int layer;
int treeleaf;
layer=0;
printf("請輸入二叉樹中的元素(以擴展先序遍歷序列輸入,其中.代表空子樹):\n");
CreatBiTree(&T);
printf("先序遍歷序列為:");
PreOrder(T);
printf("\n中序遍歷序列為:");
InOrder(T);
printf("\n後序遍歷序列為:");
PostOrder(T);
h=PostTreeDepth(T);
printf("\此二叉樹的深度為:%d\n",h);
printf("此二叉樹的橫向顯示為：\n");
PrintTree(T,layer);
}
實驗二主要程序流：
1．int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n**********************歡迎使用哈夫曼編碼/解碼系統**********************\n";
cout<<"*您可以進行以下操作: *\n";
cout<<"*1.建立哈夫曼樹 *\n";
cout<<"*2.編碼(源文已在文件ToBeTra中，或鍵盤輸入) *\n";
cout<<"* 3.解碼(碼文已在文件CodeFile中) *\n";
cout<<"* 4.顯示碼文 *\n";
cout<<"* 5.顯示哈夫曼樹 *\n";
cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n";
cout<<"請選擇一個操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感謝使用本系統!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
2．// 建立哈夫曼樹函數
// 函數功能：建立哈夫曼樹（調用鍵盤建立哈夫曼樹或調用從文件建立哈夫曼樹的函數）
void HuffmanTree::CreateHuffmanTree()
{char Choose;
cout<<"你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？";
cin>>Choose;
if(Choose=='2') { //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
}
}
3. // 從鍵盤建立哈夫曼樹函數
// 函數功能：從鍵盤建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
cout<<"\n請輸入源碼字元集個數：";
cin>>Num;
if (Num<=1) {
cout<<"無法建立少於2個葉子結點的哈夫曼樹。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
for(int i=0;i<Num;i++) {//讀入哈夫曼樹的葉子結點信息
cout<<"請輸入第"<<i+1<<"個字元值";
getchar();
Node[i].sourcecode=getchar(); //源文的字元存入字元數組Info[]
getchar();
cout<<"請輸入該字元的權值或頻度";
cin>>Node[i].weight; //源文的字元權重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for(int j=Num;j<2*Num-1;j++) {//循環建立哈夫曼樹內部結點
int pos1,pos2;
int max1,max2;
pos2=pos1=j;
max2=max1=numeric_limits<int>::max( );
//在所有子樹的根結點中，選權重最小的兩個根結點，pos1最後應指向權重最小的根結點的下標
//pos2最後應指向權重第二小的根結點的下標
//max1存放當前找到的權重最小的根結點的權重
//max2存放當前找到的權重第二小的根結點的權重
for(int k=j-1;k>=0;k--) {
if (Node[k].parent==-1){//如果是某棵子樹的根結點
if (Node[k].weight<max1){ //發現比當前最大值還大的權重
max2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if(Node[k].weight<max2){ //發現比當前次大值還大的次大權重
max2=Node[k].weight;
pos2=k;
}
}//if (Node[j].parent==-1)
} //for
//在下標i處新構造一個哈夫曼樹的內部結點，其左、右孩子就是以上pos1、pos2所指向的結點
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
} //for
//產生所有葉子結點中字元的編碼
for (int m=0;m<Num;m++) {
//產生Node[i].sourcecode的編碼，存入Node[i].code中
int j=m;
int j1;
while(Node[j].parent!=-1) { //從葉結點開始往根結點走，每往上走一層，就產生一位編碼存入code[]
j1=Node[j].parent;
if(Node[j1].lchild==j)
Node[m].code.insert(0,"0");
else
Node[m].code.insert(0,"1");
j=j1; }}
cout<<"哈夫曼樹已成功構造完成。\n";
//把建立好的哈夫曼樹寫入文件hfmTree.dat
char ch;
cout<<"是否要替換原來的哈夫曼樹文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件
if(fop.fail()) {
cout<<"\n哈夫曼樹文件打開失敗，無法將哈夫曼樹寫入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數
for(int n=0;n<2*Num-1;n++) { //最後寫入哈夫曼樹的各個結點（存儲在Node[]中）
fop.write((char*)&Node[n],sizeof(Node[n]));
flush(cout); }
fop.close(); //關閉文件
cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n";}
4. // 從文件建立哈夫曼樹函數
// 函數功能：從文件建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromFile(){
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼樹文件hfmTree.dat打開失敗，無法建立哈夫曼樹。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼樹文件中的數據有誤，葉子結點個數少於2個，無法建立哈夫曼樹。\n";
fip.close();
return;
}
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼樹已從文件成功構造完成。\n";
}
5. // 編碼函數
// 函數功能：為哈夫曼樹編碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Encoder()
{
if(Node==NULL) { //內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}//if
char *SourceText; //字元串數組，用於存放源文
//讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入
char Choose;
cout<<"你要從文件中讀入源文(按1)，還是從鍵盤輸入源文(按2)？";
cin>>Choose;
if(Choose=='1') {
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) {
cout<<"源文文件打開失敗!無法繼續執行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次讀文件只統計文件中有多少個字元，將字元數存入k
fip1.close();
SourceText=new char[k+1]; //申請存放源文的字元數組空間
ifstream fip2("ToBeTran.txt"); //第二次讀源文文件，把內容寫入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
}
else { //從鍵盤輸入源文
string SourceBuff;
cin.ignore();
cout<<"請輸入需要編碼的源文(可輸入任意長，按回車鍵結束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需編碼的源文為：";
cout<<SourceText<<endl;
//開始解碼
ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件
int k=0;
while(SourceText[k]!='\0') //源文串中從第一個字元開始逐個編碼
{
int i;
for(i=0;i<LeafNum;i++){ //找到當前要編碼的源文的字元在哈夫曼樹Node[]中的下標
if(Node[i].sourcecode==SourceText[k]) { //將對應編碼寫入碼文文件
fop<<Node[i].code;
break;
};
}
if (i>=LeafNum) {
cout<<"源文中存在不可編碼的字元。無法繼續執行。\n"<<endl;
fop.close();
return;
}
k++; //源文串中的字元後移一個
}
fop.close();
cout<<"已完成編碼，碼文已寫入文件CodeFile.dat中。\n\n";
}
6. // 解碼函數
// 函數功能：對哈夫曼樹進行解碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Decoder()
{//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
//將碼文從文件CodeFile.dat中讀入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail()) {
cout<<"沒有碼文，無法解碼。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"經解碼得到的源文為：";
ofstream fop("TextFile.dat");
int j=LeafNum*2-1-1; //j指向哈夫曼樹的根
int i=0; //碼文從第一個符號開始，順著哈夫曼樹由根下行，按碼文的當前符號決定下行到左孩子還是右孩子
while(CodeStr[i]!='\0') { //下行到哈夫曼樹的葉子結點處，則譯出葉子結點對應的源文字元
if(CodeStr[i]=='0')
j=Node[j].lchild;
else
j=Node[j].rchild;
if(Node[j].rchild==-1) { //因為哈夫曼樹沒有度為1的結點，所以此條件等同於Node[j]為葉結點
cout<<Node[j].sourcecode; //屏幕輸出譯出的一個源文字元
fop<<Node[j].sourcecode;
j=LeafNum*2-1-1; //j再指向哈夫曼樹的根
}
i++;
}
fop.close();
cout<<"\n解碼成功且已存到文件TextFile.dat中。\n\n";
}
7. // 輸出碼文函數
// 函數功能：從文件中輸出哈夫曼樹的碼文
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"沒有碼文文件，無法顯示碼文文件內容。\n";
return;
}
while(fip.get(ch))
{cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
8. // 輸出函數
// 函數功能：從內存或文件中直接輸出哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintHuffmanTree()
{
//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return; }}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
Ⅱ 利用 數據結構 實現 哈夫曼編碼/解碼實現
//D:\2010 代碼\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定義最大權值
#define MAXBIT 100//定義哈夫曼樹中葉子結點個數
typedef struct
{
char data;//字元值
int num;//某個值的字元出現的次數
}TotalNode;
//統計結點，包括字元種類和出現次數
typedef struct
{
TotalNode tot[300];//統計結點數組
int num;//統計數組中含有的字元個數
}Total;
//統計結構體，包括統計數組和字元種類數
typedef struct
{
char mes[300];//字元數組
int num;//總字元數
}Message;
//信息結構體，包括字元數組和總字元數
typedef struct{
int locked[500];//密碼數組
int num;//密碼總數
}Locking;
//哈夫曼編碼後的密文信息
typedef struct
{
char data;//字元
int weight;//權值
int parent;//雙親結點在數組HuffNode[]中的序號
int lchild;//左孩子結點在數組HuffNode[]中的序號
int rchild;//右孩子結點在數組HuffNode[]中的序號
}HNodetype;
//哈夫曼樹結點類型，包括左右孩子，權值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼編碼結構體，包括編碼數組和起始位
void reading_file(Message *message);//從文件中讀取信息
int writing_file(Message *message);//將信息寫進文件
void total_message(Message *message,Total *total);//統計信息中各字元的次數
void HaffmanTree(Total *total,HNodetype HuffNode[]);//構建哈夫曼樹
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//將編碼規則寫進文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼
void writing_lock(Locking *locking);//將已編碼信息寫進文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過來並寫進文
//D:\2010 代碼\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark標記文件信息是否讀入到內存中
HNodetype HuffNode[500];//保存哈夫曼樹中各結點信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化變數
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：從文件讀取信息**********************※\n");
printf(" *********** 2：顯示編碼規則 ********************* \n");
printf(" ********** 3：將原文件信息寫進文件 ************ \n");
printf(" ********* 4：將編碼規則寫進文件 ************ \n");
printf(" ********** 5：將編碼後的信息寫進文件 ********** \n");
printf(" *********** 6：將解碼後的信息寫進文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//從文件中讀取信息
mark=1;
break;
case 2://顯示編碼規則
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"編碼規則為"<<endl;
for(i=0;i<total->num;i++)//顯示編碼規則
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://將原文件信息寫進文件a_test1.txt
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
writing_file(message);//將信息寫進文件
break;
case 4://將編碼規則寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//將編碼規則寫進文件
}
break;
case 5://將編碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//將已編碼信息寫進文件
}
break;
case 6://將解碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過來並寫進文件
}
break;
}
}
/**
列印haffman樹
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}
void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}
}
void reading_file(Message *message)
/**
絕對路徑下讀取a_test.txt file
message 中的num記錄suoyou字元總數 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打開失敗則結束
{
cout<<"打開a_test.txt文件失敗"<<endl;
exit(1);
}
else
cout<<"讀取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//讀取字元直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//記錄總字元數
infile.close();//關閉文件
}
int writing_file(Message *message)
/**
把從數組message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打開文件
if( !outfile )//打開失敗則結束
{
cout<<"打開a_test1.txt文件失敗"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//寫文件
outfile.put(message->mes[i]);
cout<<"信息寫進文件成功"<<endl;
outfile.close();//關閉文件
return 0;*/
int i;
FILE *fp1=NULL;
if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件寫入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void total_message(Message *message,Total *total)
/**
統計message中不同字元 的個數，和相同字元重復的次數，重復字元用mark標記，
total.tot[] 放不同字元，TotalNode 類型（char，num）
total.num 統計不同字元個數
使total這塊內存空間有數據，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍歷message中的所有字元信息
{
if(message->mes[i]!=' ')//字元不為空格時
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索當前字元
if(total->tot[j].data==message->mes[i])//搜索到，則此字元次數加1，mark標志為1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字元種類，保存進total中，字元類加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}
void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字元個數為葉子節點個數對應書上的n，
相同字元的個數為其權值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹並存入葉子結點權值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改親人結點位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權值小
HuffNode[total->num+i].rchild=x2;
}
}
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每個不同字元（葉子）的編碼，
存貯在數組HuffCode【】中,bit[] store the char,start store the loction
**/
{
int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立葉子結點個數的編碼
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//從葉結點向上爬直到到達根結點
{
if(HuffNode[p].lchild==c)//左分支則為0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支則為1
cd.start--;//起始位向前移動
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每個葉結點編碼和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打開HCode文件，失敗則結束。將信息寫進文件*/
int i,j;
FILE *fp2=NULL;
if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("編碼規則寫進文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
對messag操作，對所有字元加密，
結果存貯在數組locked[]中，locking 記錄已經加密後的密文
**/
{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字元全部 遍歷
{
if(message->mes[i]==' ')//碰到空格則以-1形式保存進locked數組中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//從total中找到對應的字元
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中對應字元，找到下標j
// 在HuffCode
for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}
void writing_lock(Locking *locking)
/*
將密文寫到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;
if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已編碼信息寫進文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻譯成明文，然後存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;
if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
min=0;
for(max=0;max<locking->num;max++)//寫文件
{
if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格
{
printf(" ");//把空格寫到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找從min開始到max的編碼對應的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //對應編碼比所給編碼短則不在比較
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到對應信息，則寫進文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//寫到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
}
}
printf("文件寫入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//統計信息中各字元的出現次數
HaffmanTree(total,HuffNode);//構建哈夫曼樹
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼
}