北京理工大學數(shù)據(jù)結構課程設計哈弗曼樹文件壓縮

文件壓縮第十組問題描述在信息通信過程中，我們需要傳輸大量文件。在大的文件中有許多冗余，為了提高信道利用率、縮短信息傳輸時間、降低傳輸成本，我們設計一個編譯系統(tǒng)，發(fā)送方利用哈夫曼編碼對文件進行壓縮后傳輸，接收方將接收到的數(shù)據(jù)進行譯碼。第2

頁設計要求分析（1）保存：傳輸文件存于文本文件中，如：源文件textfile（2）預處理：從文件中讀取數(shù)據(jù)，處理并建立字符集頻率表（3）初始化：利用字符集頻率表建立哈夫曼樹（4）編碼：利用建立好的哈夫曼樹對源文件進行編碼，實現(xiàn)文件壓縮，然后將結果以文件形式保存，如編碼文件codefile（5）譯碼：利用建立好的哈夫曼樹對codefile中的代碼進行譯碼。結果存入譯碼文件decofile中。（6）輸出：可以顯示testfile、codefile、decofile和哈夫曼樹第3

頁數(shù)據(jù)結構與算法分析（一）利用字符和權值建立哈夫曼樹求得哈夫曼編碼（二）利用二叉樹先序遍歷輸出哈夫曼樹第4

頁系統(tǒng)各部分詳細設計及實現(xiàn)一、

哈夫曼樹類定義

classHaffmanCode{private: intnum;//字符集個數(shù) Node*ht;//哈夫曼樹 HaffCode*hc;//哈夫曼碼

public: HaffmanCode():num(0),ht(NULL),hc(NULL){};~HaffmanCode();第5

頁系統(tǒng)各部分詳細設計及實現(xiàn) voidbuildHfmtree(charstr[],intw[],intn);//構

造哈夫曼樹

voidHfmcode(charstr[]);//由哈夫曼樹生成哈

夫曼編碼

voidencoding(); voiddecoding(); voidprintcode(); voidprinttree();//打印樹的實例函數(shù) voidprinttree(fstream&outfile,intn,intlen);//

打印樹的遞歸函數(shù) intloct(charc);//查找字符c所在的下標第6

頁系統(tǒng)各部分詳細設計及實現(xiàn)二、建立哈夫曼樹（一）構造哈夫曼樹

voidHaffmanCode::buildHfmtree(charstr[],intw[],intn){ num=n; ht=newNode[2*n-1]; hc=newHaffCode[n]; inti,j,m1,m2;//m1、m2分別表示最小、次小的權值 intx1,x2;//x1、x2分別表示當前分支結點的左右兒子第7

頁系統(tǒng)各部分詳細設計及實現(xiàn)for(i=0;i<2*n-1;i++)//哈夫曼樹初始化 { if(i<n) ht[i].weight=w[i]; else ht[i].weight=0; ht[i].parent=-1; ht[i].lchild=-1; ht[i].rchild=-1; }第8

頁系統(tǒng)各部分詳細設計及實現(xiàn)for(i=0;i<n-1;i++)//構造哈夫曼樹的 n-1個分支結點 { m1=m2=1000; x1=x2=0; for(j=0;j<n+i;j++) { //在沒掛進哈夫曼樹的節(jié)點中尋找權值最小的節(jié)點 if(ht[j].parent==-1&&ht[j].weight<m1)第9

頁系統(tǒng)各部分詳細設計及實現(xiàn){ m2=m1;//最小保存到次小 x2=x1; m1=ht[j].weight; x1=j; } elseif(ht[j].parent==-1&&ht[j].weight<m2) {第10

頁系統(tǒng)各部分詳細設計及實現(xiàn)m2=ht[j].weight; x2=j; } } ht[x1].parent=n+i; ht[x2].parent=n+i; ht[n+i].weight=ht[x1].weight+ht[x2].weight; ht[n+i].lchild=x1; ht[n+i].rchild=x2;第11

頁系統(tǒng)各部分詳細設計及實現(xiàn)（二）由哈夫曼樹生成哈夫曼編碼voidHaffmanCode::Hfmcode(charstr[]){ HaffCodecd; intchild,parent,i,j; for(i=0;i<num;i++) { cd.start=num-1;第12

頁系統(tǒng)各部分詳細設計及實現(xiàn) cd.weight=ht[i].weight; child=i; parent=ht[child].parent; while(parent!=-1) { if(ht[parent].lchild==child) cd.bit[cd.start]=0; else cd.bit[cd.start]=1;第13

頁系統(tǒng)各部分詳細設計及實現(xiàn) cd.start--; child=parent; parent=ht[child].parent; } for(j=cd.start+1;j<num;j++) hc[i].bit[j]=cd.bit[j]; hc[i].start=cd.start; hc[i].weight=cd.weight; hc[i].ch=str[i]; }第14

頁系統(tǒng)各部分詳細設計及實現(xiàn)（三）將生成的哈夫曼編碼寫入文件

hfmTree.txt中

fstreamoutput; output.open("hfmTree.txt",ios::out); if(!output) { cout<<"hfmTree.txtcan'topen!"<<endl; abort(); }第15

頁系統(tǒng)各部分詳細設計及實現(xiàn) for(i=0;i<num;i++) { output<<hc[i].ch<<""<<hc[i].weight<<""; for(j=hc[i].start+1;j<num;j++) output<<hc[i].bit[j]; output<<endl; } output.close();第16

頁系統(tǒng)各部分詳細設計及實現(xiàn)三、對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile

voidHaffmanCode::encoding() { fstreaminfile,outfile; infile.open("ToBeTran.txt",ios::in); outfile.open("CodeFile.txt",ios::out); if(!infile)

第17

頁系統(tǒng)各部分詳細設計及實現(xiàn) { cout<<"ToBeTran.txtcan'topen!"<<endl; abort(); } if(!outfile) { cout<<"CodeFile.txtcan'topen!"<<endl; abort(); }第18

頁系統(tǒng)各部分詳細設計及實現(xiàn)inti,j,loc; charch[255]; while(!infile.eof()) { infile.getline(ch,255); i=0; while(ch[i]!='\0') { loc=loct(ch[i]);第19

頁系統(tǒng)各部分詳細設計及實現(xiàn) if(loc!=-1) for(j=hc[loc].start+1;j<num;j++) outfile<<hc[loc].bit[j]; i++; } } infile.close(); outfile.close(); }第20

頁系統(tǒng)各部分詳細設計及實現(xiàn)四、利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，將結果存入TextFile中

voidHaffmanCode::decoding() { fstreaminfile,outfile; infile.open("CodeFile.txt",ios::in); outfile.open("TextFile.txt",ios::out); if(!infile) {

cout<<"CodeFile.txtcan'topen!"<<endl;

abort();第21

頁系統(tǒng)各部分詳細設計及實現(xiàn) } if(!outfile) cout<<"TextFile.txtcan'topen!"<<endl; abort(); } inti,j; charch[255]; memset(ch,'5',255); while(!infile.eof()) {第22

頁系統(tǒng)各部分詳細設計及實現(xiàn) infile.getline(ch,255); i=0; while(ch[i]!='\0') {

j=2*num-2; while(ht[j].lchild!=-1) { if(ch[i]=='1') j=ht[j].rchild; else j=ht[j].lchild;第23

頁系統(tǒng)各部分詳細設計及實現(xiàn)