這是Huffman.cpp文件// Huffman.cpp: implementation of the Huffman class.////////////////////////////////////////////////////////////////////////#include "Huffman.h"#include <iostream>#include <fstream>#include <string>#include <cmath>#include <iomanip>//#include <climits>using namespace std;//////////////////////////////////////////////////////////////////////// Construction/Destruction////////////////////////////////////////////////////////////////////////(1)//從文件(text.txt)讀入原文void Huffman::ReadTextFromFile(const char *infilename){?flength = 0;?unsigned char temp;???????//定義unsigned char類型，暫存文件中字符的中間變量?for (int i=0; i<256; i++)?{?? treeNode[i].weight = 0;?? treeNode[i].ch=(unsigned char)i;?}?ifstream infile(infilename,ios::in|ios::binary);?while(infile.peek()!=EOF)?????//peek()方法預(yù)讀取下一個字符（不管是何符號）?{??infile.read((char *)&temp,sizeof(unsigned char));?//讀入一個字符??/*??由代碼來看，infile 是一個記錄式文件的輸入流，以二進制打開。??這條語句的作用就是以二進制形式從文件讀入一個 unsigned char 的信息。??(char*)&temp這是獲取 unsigned char 的首地址，sizeof(unsigned char) 是獲取 unsigned char 的大小，??read 函數(shù)將從文件中讀入相應(yīng)大小的數(shù)據(jù)放入該地址??*/??treeNode[temp].weight++;????????? //統(tǒng)計對應(yīng)結(jié)點字符權(quán)重??flength++;????????????? //統(tǒng)計文件長度?}??? infile.close();????????????? //關(guān)閉文件//?for (int a=0; a<256; a++)//??cout << treeNode[a].weight << endl;}/*int Huffman::compare(const void *a,const void *b){?struct node *p1 = (struct node *)a;?struct node *p2 = (struct node *)b;?return p1->weight < p1->weight;}*/void Huffman::sortNode(){?for(int i=0;i<256-1;i++)??????????? //對結(jié)點進行冒泡排序,權(quán)重大的放在上面，編碼時效率高?for(int j=0;j<256-1-i;j++)??if(treeNode[j].weight<treeNode[j+1].weight)??{???tempNode=treeNode[j];???treeNode[j]=treeNode[j+1];???treeNode[j+1]=tempNode;??}}void Huffman::display(){?leafnum = 0;?sortNode();?for(int i=0;i<256;i++)?{??if(treeNode[i].weight == 0) ???break;?}?leafnum = i;?????//取得哈夫曼樹中葉子結(jié)點數(shù)?pointnum = 2*leafnum - 1;??//取得哈夫曼樹中總結(jié)點數(shù)目//?cout << leafnum << endl;//?for (int a=0; a<256; a++)//??cout << treeNode[a].weight << endl;?????//?cout << pointnum << endl;???}void Huffman::MakeCharMap(){?cout << "構(gòu)造Huffman樹中...";/*********************************根據(jù)哈夫曼樹編碼**********************************/?display();??? long min;?????? ?int s1,s2;?for(int i=leafnum;i<pointnum;i++)?{??min = treeNode[0].weight;??for(int j=0; j<i ;j++)?????????? //挑權(quán)重最小的一個???if(treeNode[j].parent == -1 && treeNode[j].weight<=min)???{????min=treeNode[j].weight;????s1=j;???}????treeNode[s1].parent = i;???//填寫第一個葉子結(jié)點信息??min = treeNode[0].weight;??for(j=0; j<i; j++)????//挑權(quán)重最小的第二個???if(treeNode[j].parent == -1 && treeNode[j].weight<=min)???{????min=treeNode[j].weight;????s2=j;???}??treeNode[s2].parent=i;????treeNode[i].weight=treeNode[s1].weight + treeNode[s2].weight;??? //填寫父結(jié)點信息??treeNode[i].lchild=s1;??treeNode[i].rchild=s2;?}??//從葉子到根節(jié)點逆向求每個字符的哈弗曼編碼?char tmp[256];????????????? //定義臨時變量，暫存編碼?tmp[255]='\0';????????????? //添加結(jié)束標志?int start;??? int c;??????????????? //記錄當(dāng)前葉結(jié)點下標?int f;??????????????? //存儲父結(jié)點的下標?for(int k=0; k<leafnum; k++)????{??start=255;????????????? //另開始等于數(shù)組最后位??for(c=k,f=treeNode[k].parent;f!=0;c=f,f=treeNode[f].parent)???//對葉結(jié)點進行編碼??{???if(treeNode[f].lchild == c) ????tmp[--start]='0';???else ????tmp[--start]='1';??}??strcpy(treeNode[k].bits,&tmp[start]);?}}/************************************對文件進行編碼，寫入新文件(核心)*********************************/void Huffman::compressText(const char *infilename,const char *outfilename){?long clength=8;??????????//編碼從偏移量8記錄，統(tǒng)計壓縮后編碼長度加8?unsigned char temp;?????????//定義unsigned char類型，暫存文件中字符的中間變量?ifstream infile;?ofstream outstream;?infile.open(infilename,ios::in|ios::binary);?????? //打開待壓縮的文件?infile.clear();???//把文件清零?infile.seekg(0);??//把文件指針置為開頭處?ofstream outfile(outfilename,ios::out|ios::binary);????? //打開壓縮后將生成的文件?outfile.write((char *)&flength,sizeof(long));?????? //寫入原文件長度?char buf[513]="\0"; //初始化編碼緩沖區(qū)?outfile.seekp(8);????????????? //指針定向偏移量8?while(infile.peek()!=EOF)?{??infile.read((char *)&temp,sizeof(unsigned char));???? //讀入字符//??strcat(buf,code(temp,leafnum));????????? //檢索出字符對應(yīng)編碼，連到buf[]中??while(strlen(buf) >= 8)??????????? //當(dāng)buf中字符長度大于8時，一直處理寫入，直至小于8??{???temp=ctoa(buf);???????????? //上面臨時變量已經(jīng)完成使命，可以賦新值了???outfile.write((char *)&temp,sizeof(unsigned char));??? //轉(zhuǎn)成二進制寫入???clength++;????????????? //統(tǒng)計代碼結(jié)尾偏移加1,用于找到葉子結(jié)點位置???strcpy(buf,buf+8);????????????????????????????????????????? //字符串前移八位??}? //當(dāng)此循環(huán)結(jié)束時，表示buf[]中已經(jīng)小于8了，沒到文件末尾，讀下一個，繼續(xù)，否則退出?}?? //while 此層循環(huán)退出時，表示已到末尾,再判斷buf中是否寫完，沒寫完，連滿至少8個字符，再寫一個字節(jié)，就夠了???if(strlen(buf)>0)?{??strcat(buf,"0000000");??temp=ctoa(buf);????????????? //前八位轉(zhuǎn)成二進制形式??outfile.write((char *)&temp,sizeof(unsigned char));??clength++;?????????????????? //統(tǒng)計代碼結(jié)尾偏移加1,用于找到葉子結(jié)點位置?}?outfile.seekp(4);?outfile.write((char *)&clength,sizeof(long));?????? //寫入文件中將記錄葉子結(jié)點位置?infile.close();?long bytelen;?????????????????????? //記錄編碼以二進制存儲時需要占多少個字節(jié)?outfile.clear();?outfile.seekp(clength);???????????? //將文件指針移到編碼后面的第一位置，在此處記錄葉子結(jié)點數(shù)?outfile.write((char *)&leafnum,sizeof(long));?????? //寫入葉子結(jié)點數(shù)?for(int i=0; i<leafnum; i++)?{??outfile.write((char *)&treeNode[i].ch,sizeof(unsigned char));?? //寫入字符??treeNode[i].weight = strlen(treeNode[i].bits);??????? //不再設(shè)置其他變量,權(quán)值這時已無使用價值,可以用相應(yīng)結(jié)點的權(quán)值變量記錄長度??outfile.write((char *)&treeNode[i].weight,sizeof(unsigned char)); //寫入長度的ASCII碼??if(treeNode[i].weight%8==0) ???bytelen = treeNode[i].weight/8;??else ??{???bytelen = treeNode[i].weight/8+1;???strcat(treeNode[i].bits,"0000000");??????? //在編碼后面補0，使其最后湊滿8的倍數(shù)，???//超過無妨，可以用bytelen控制好寫入字節(jié)的長度??}??for(int j=0;j<bytelen;j++)??{???temp=ctoa(treeNode[i].bits);???outfile.write((char *)&temp,sizeof(unsigned char));???strcpy(treeNode[i].bits,treeNode[i].bits+8);?????????? ??}?}?? //此循環(huán)結(jié)束后就完成了編碼對照表的寫入}char * Huffman::code(unsigned char temp,int leafnum/*葉子節(jié)點*/)????? //尋找對應(yīng)字符的編碼串，并返回{??? for(int i=0;i<leafnum;i++)?{??if(temp == treeNode[i].ch)???return treeNode[i].bits;?}?return NULL;}unsigned char Huffman::ctoa(char a[])?????????? /*將數(shù)組的前八位轉(zhuǎn)成二進制形式比特位*/{??? unsigned char c=0;??? for(int i=0;i<8;i++)?{??if(a[i]!=0) ???c = c+(int)(a[i]-'0')*pow(2,8-1-i);??//這里的pow(x,y)是求x的y次方?}?return c;}void Huffman::ctoa(unsigned char a,char code[])??????? /*字符轉(zhuǎn)為二進制形式存入8位數(shù)組*/{? ??? int n=9;??? for(int i=0;i<n;i++) code[i]='0';???? //整個字符串初始化??? code[n-1]='\0';????????? //添加結(jié)束標志??? n=n-2;??? int c=(int)a;??? while(c>0)?{??code[n--]=c%2+'0';??c=c/2;?}}int Huffman::strcmp1(char buf[],huffmanNode head[],int n,unsigned char &c)??? //將buf字符串與treeNode[i].bits[]中匹配，成功后對應(yīng)的字符由c帶回{??? for(int i=0;i<n;i++)??????? if(strcmp(buf,head[i].bits)==0)??{??????????? c=head[i].ch;??????????? return 1;??}??return 0;}void Huffman::strcpy1(char buf[],char a[],int j)?? //將字符串a(chǎn)中長度為j的部分復(fù)制到buf數(shù)組中{??? for(int i=0;i<j;i++)??buf[i]=a[i];??? buf[i]='\0';}void Huffman::decompressText(char *infilename,char *outfilename){??? long flength;????????? //定義原文件長度，從壓縮后文件前四字節(jié)獲取值??? long clength;????????? //獲取編碼長度后的第一偏移量,從壓縮文件第五字節(jié)開始獲取值??? int n;??????????? //葉子結(jié)點數(shù)，從編碼尾端開始獲取??? string str;?????????? //讀取編碼到字符串,好進行統(tǒng)一解碼??? char code[9];????????? //將字符轉(zhuǎn)為二進制數(shù)組形式暫存??? unsigned char temp;???????? //讀取字符存放此臨時變量??? long readlen=0;????????? //記錄已經(jīng)讀取的長度(讀文件解碼時用)??? long writelen=0;???????? //記錄已經(jīng)寫入的字節(jié)??? long clen;?????????? //臨時變量，讀取字符編碼對照表時使用?因為不能上傳這么多代碼，我把部分（Huffman.cpp）的文件和頭文件（Huffman.h）和main（demo.cpp）放在下一個問題中