哈夫曼樹編碼實(shí)驗(yàn)報(bào)告材料

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目： 哈夫曼編碼/譯碼 學(xué) 院 數(shù)學(xué)與信息科學(xué)學(xué)院 學(xué)科門類 理科 專 業(yè) 數(shù)學(xué)類 學(xué) 號(hào) 姓 名 田娟 2014年 12 月30日 目 錄一、需求分析1 程序的功能·······························

2、3;··················32輸入輸出的要求······························&

3、#183;···············33測(cè)試數(shù)據(jù)·································&

4、#183;··················3二、概要設(shè)計(jì)1本程序所用的抽象數(shù)據(jù)類型的定義···························&#

5、183;···32 主程序模塊·············································

6、······33 主模塊的流程及各子模塊的主要功能·····························44 模塊之間的層次關(guān)系··········

7、;·································4三、詳細(xì)設(shè)計(jì)1采用c語言定義相關(guān)的數(shù)據(jù)類型·············&

8、#183;···················42. 偽碼算法·····························

9、;························5四、調(diào)試分析1調(diào)試中遇到的問題及對(duì)問題的解決方法·····················

10、3;·····15五、使用說明及測(cè)試結(jié)果1.建立哈夫曼樹，輸入葉子結(jié)點(diǎn)個(gè)數(shù)，權(quán)值，字符集··················152.編碼···················

11、83;······································153.譯碼··········

12、83;···············································164.顯示碼文·&

13、#183;·················································&

14、#183;··165.顯示哈夫曼樹·············································

15、83;····16六、源程序一、需求分析1程序的功能；哈夫曼編碼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為譯碼。進(jìn)行信息傳遞時(shí)，發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)（明文）預(yù)先編碼，而接收端將傳來的數(shù)據(jù)（密文）進(jìn)行譯碼。2輸入輸出的要求；：2.1構(gòu)造哈夫曼樹及哈夫曼編碼：從終端讀入字符集大小n、n個(gè)字符以及n個(gè)對(duì)應(yīng)的權(quán)值，建立哈夫曼樹；利用已經(jīng)建好的哈夫曼樹求每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼，并保存。2.2編碼：利用已構(gòu)造的哈夫曼編碼對(duì)“明文”文件中的正文進(jìn)

16、行編碼，然后將結(jié)果存入“密文”文件中。2.3譯碼：將“密文”文件中的0、1代碼序列進(jìn)行譯碼。2.4打印“密文”文件：將文件以緊湊格式顯示在終端上，每行30個(gè)代碼；同時(shí)，將此字符形式的編碼文件保存。2.5打印哈夫曼樹及哈夫曼編碼：將已在內(nèi)存中的哈夫曼樹以凹入表形式顯示在終端上，同時(shí)將每個(gè)字符的哈夫曼編碼顯示出來；并保存到文件。3測(cè)試數(shù)據(jù)。3.1.令葉子結(jié)點(diǎn)個(gè)數(shù)N為4，權(quán)值集合為1,3,5,7，字符集合為A,B,C,D，且字符集與權(quán)值集合一一對(duì)應(yīng)。3.2.請(qǐng)自行選定一段英文文本，統(tǒng)計(jì)給出的字符集，實(shí)際統(tǒng)計(jì)字符的頻度，建立哈夫曼樹，構(gòu)造哈夫曼編碼，并實(shí)現(xiàn)其編碼和譯碼。二、概要設(shè)計(jì)1本程序所用的抽象數(shù)

17、據(jù)類型的定義；class HuffmanTree /哈夫曼樹private: HuffmanNode *Node; /Node存放哈夫曼樹 int LeafNum; /哈夫曼樹的葉子個(gè)數(shù)，也是源碼個(gè)數(shù)2.主程序模塊main()2.2 建立哈夫曼樹函數(shù)/ 函數(shù)功能：建立哈夫曼樹void HuffmanTree:CreateHuffmanTree() 2.3 函數(shù)功能：為哈夫曼樹編碼void HuffmanTree:Encoder()2.4 函數(shù)功能：對(duì)哈夫曼樹進(jìn)行譯碼void HuffmanTree:Decoder()2.5輸出碼文函數(shù)/ 函數(shù)功能：從文件中輸出哈夫曼樹的碼文void Huffm

18、anTree:PrintCodeFile()2.6 函數(shù)功能：用凹入法輸出哈夫曼樹void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)3主模塊的流程及各子模塊的主要功能；哈夫曼編碼/譯碼系統(tǒng) 顯示哈夫曼樹建立哈夫曼樹顯示哈夫曼樹編碼 顯示碼文譯碼 基本功能分析4模塊之間的層次關(guān)系。 初始化：從鍵盤接收字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。 建立哈夫曼樹：構(gòu)造哈夫曼樹，即將HNode數(shù)組中的各個(gè)位置的各個(gè)域都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件HTree.txt中。 構(gòu)造哈夫曼編碼：為從文件HTree.txt中讀入相關(guān)的字符信息進(jìn)行哈

19、夫曼編碼，然后將結(jié)果存入HNode.txt中，同時(shí)將字符與0、1代碼串的一一對(duì)應(yīng)關(guān)系打印到屏幕上。 編碼：利用已構(gòu)造的哈夫曼編碼（HNode.txt）對(duì)文件SourceFile.txt（明文）中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile.txt（密文）中。 譯碼：將文件CodeFile.txt（密文）中的代碼按照中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，進(jìn)行譯碼，結(jié)果存入文件TextFile.txt（明文）中。（如果正確，TextFile.txt的內(nèi)容與SourceFile.txt的內(nèi)容一致） 顯示哈夫曼樹：從HNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以凹入表方式將各個(gè)結(jié)點(diǎn)以

20、及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的三、詳細(xì)設(shè)計(jì)1采用c語言定義相關(guān)的數(shù)據(jù)類型；結(jié)點(diǎn)的類型定義描述如下：struct HuffmanNode /哈夫曼樹的一個(gè)結(jié)點(diǎn) int weight; int parent; int lchild,rchild; char sourcecode; std:string code; ;class HuffmanTree /哈夫曼樹private: HuffmanNode *Node; /Node存放哈夫曼樹 int LeafNum; 2. 偽碼算法public: HuffmanTree(); HuffmanTree(); void CreateHuffm

21、anTree(); void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); void Decoder(); void PrintCodeFile(); void PrintHuffmanTree(); void PrintHuffmanTree_aoru(int T,int layer=1); ;/ 構(gòu)造函數(shù)/ 函數(shù)功能：初始化哈夫曼樹HuffmanTree:HuffmanTree() Node=NULL; LeafNum=0; / 函數(shù)功能：將哈夫曼的數(shù)組的空間釋放/參數(shù)返

22、回值：無HuffmanTree:HuffmanTree() delete Node; / 建立哈夫曼樹函數(shù)/ 函數(shù)功能：建立哈夫曼樹void HuffmanTree:CreateHuffmanTree() char Choose; cout<<"從鍵盤輸入哈夫曼樹(按2)？" cin>>Choose; if(Choose='2') CreateHuffmanTreeFromKeyboard(); /choose='2' else /從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 CreateHuffman

23、TreeFromFile(); / 函數(shù)功能：從鍵盤建立哈夫曼樹void HuffmanTree:CreateHuffmanTreeFromKeyboard() int Num; cout<<"n請(qǐng)輸入源碼字符集個(gè)數(shù)：" cin>>Num; if (Num<=1) cout<<"無法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。nn" return; LeafNum=Num; Node=new HuffmanNode2*Num-1; for(int i=0;i<Num;i+) /讀入哈夫曼樹的葉子結(jié)點(diǎn)信息 cout<

24、;<"請(qǐng)輸入第"<<i+1<<"個(gè)字符值" getchar(); Nodei.sourcecode=getchar(); /源文的字符存入字符數(shù)組Info getchar(); cout<<"請(qǐng)輸入該字符的權(quán)值" cin>>Nodei.weight; /源文的字符權(quán)重存入Node.weight Nodei.parent=-1; Nodei.lchild=-1; Nodei.rchild=-1; Nodei.code="0" for(int j=Num;j<

25、2*Num-1;j+) /循環(huán)建立哈夫曼樹內(nèi)部結(jié)點(diǎn) int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits<int>:max( ); /在所有子樹的根結(jié)點(diǎn)中，選權(quán)重最小的兩個(gè)根結(jié)點(diǎn)，pos1最后應(yīng)指向權(quán)重最小的根結(jié)點(diǎn)的下標(biāo)for(int k=j-1;k>=0;k-) if (Nodek.parent=-1)/如果是某棵子樹的根結(jié)點(diǎn) if (Nodek.weight<max1) /發(fā)現(xiàn)比當(dāng)前最大值還大的權(quán)重 max2=max1; max1=Nodek.weight; pos2=pos1; po

26、s1=k; else if(Nodek.weight<max2) /發(fā)現(xiàn)比當(dāng)前次大值還大的次大權(quán)重 max2=Nodek.weight; pos2=k; /if (Nodej.parent=-1) /for/在下標(biāo)i處新構(gòu)造一個(gè)哈夫曼樹的內(nèi)部結(jié)點(diǎn)，其左、右孩子就是以上pos1、pos2所指向的結(jié)點(diǎn) Nodepos1.parent=j; Nodepos2.parent=j; Nodej.lchild=pos1; Nodej.rchild=pos2; Nodej.parent=-1; Nodej.weight=Nodepos1.weight+Nodepos2.weight; /for /產(chǎn)生

27、所有葉子結(jié)點(diǎn)中字符的編碼 for (int m=0;m<Num;m+) /產(chǎn)生Nodei.sourcecode的編碼，存入Nodei.code中 int j=m; int j1; while(Nodej.parent!=-1) /從葉結(jié)點(diǎn)開始往根結(jié)點(diǎn)走，每往上走一層，就產(chǎn)生一位編碼存入code j1=Nodej.parent; if(Nodej1.lchild=j) Nodem.code.insert(0,"0"); else Nodem.code.insert(0,"1"); j=j1; cout<<"哈夫曼樹已成功構(gòu)造完成

28、。n" 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; f

29、op.write(char*)&Num,sizeof(Num); /先寫入哈夫曼樹的葉子結(jié)點(diǎn)個(gè)數(shù) for(int n=0;n<2*Num-1;n+) /最后寫入哈夫曼樹的各個(gè)結(jié)點(diǎn)（存儲(chǔ)在Node中） fop.write(char*)&Noden,sizeof(Noden); flush(cout); fop.close(); /關(guān)閉文件 cout<<"n哈夫曼樹已成功寫入hfmTree.dat文件。n"/ 從文件建立哈夫曼樹函數(shù)/ 函數(shù)功能：從文件建立哈夫曼樹void HuffmanTree:CreateHuffmanTreeFromFil

30、e() 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<<"哈夫曼樹文件中的數(shù)據(jù)有誤，葉子結(jié)點(diǎn)個(gè)數(shù)少于2個(gè)，無法建立哈夫曼樹。n" fip.close(); return; Node=n

31、ew HuffmanNode2*LeafNum-1; for(int i=0;i<2*LeafNum-1;i+) fip.read(char*)&Nodei,sizeof(Nodei); fip.close(); cout<<"哈夫曼樹已從文件成功構(gòu)造完成。n"/ 編碼函數(shù)/ 函數(shù)功能：為哈夫曼樹編碼void HuffmanTree:Encoder() if(Node=NULL) /內(nèi)存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 CreateHuffmanTreeFromFile(); if (LeafNum<

32、;=1) cout<<"內(nèi)存無哈夫曼樹。操作撤銷。nn" return; /if char *SourceText; /讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入 char Choose; cout<<"從鍵盤輸入源文(按2)？" cin>>Choose; if(Choose='1') ifstream fip1("ToBeTran.txt"); if(fip1.fail() cout<<"源文文件打開失敗!無法繼續(xù)執(zhí)行。n&quo

33、t; return; char ch; int k=0; while(fip1.get(ch) k+; fip1.close(); SourceText=new chark+1; ifstream fip2("ToBeTran.txt"); k=0; while(fip2.get(ch) SourceTextk+=ch; fip2.close(); SourceTextk='0' else string SourceBuff; cin.ignore(); cout<<"請(qǐng)輸入需要編碼的源文(按回車鍵結(jié)束):n" getline

34、(cin,SourceBuff,'n'); int k=0; while(SourceBuffk!='0') k+; SourceText=new chark+1; k=0; while(SourceBuffk!='0') SourceTextk=SourceBuffk; k+; SourceTextk='0' cout<<"需編碼的源文為：" cout<<SourceText<<endl; ofstream fop("CodeFile.dat",ios:

35、trunc); /打開碼文存放文件 int k=0; while(SourceTextk!='0') /源文串中從第一個(gè)字符開始逐個(gè)編碼 int i; for(i=0;i<LeafNum;i+) /找到當(dāng)前要編碼的源文的字符在哈夫曼樹Node中的下標(biāo) if(Nodei.sourcecode=SourceTextk) /將對(duì)應(yīng)編碼寫入碼文文件 fop<<Nodei.code; break; ; if (i>=LeafNum) cout<<"源文中存在不可編碼的字符。無法繼續(xù)執(zhí)行。n"<<endl; fop.clo

36、se(); return; k+; fop.close(); cout<<"已完成編碼，碼文已寫入文件CodeFile.dat中。nn"/ 函數(shù)功能：對(duì)哈夫曼樹進(jìn)行譯碼void HuffmanTree:Decoder()/如果內(nèi)存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 if(Node=NULL) CreateHuffmanTreeFromFile(); if (LeafNum<=1) cout<<"內(nèi)存無哈夫曼樹。操作撤銷。nn" return; ifstream fip1("

37、CodeFile.dat"); if(fip1.fail() cout<<"沒有碼文，無法譯碼。n" return; char* CodeStr; int k=0; char ch; while(fip1.get(ch) k+; fip1.close(); CodeStr=new chark+1; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch) CodeStrk+=ch; fip2.close(); CodeStrk='0'cout<<&quo

38、t;經(jīng)譯碼得到的源文為：" ofstream fop("TextFile.dat"); int j=LeafNum*2-1-1; int i=0; while(CodeStri!='0') /下行到哈夫曼樹的葉子結(jié)點(diǎn)處，則譯出葉子結(jié)點(diǎn)對(duì)應(yīng)的源文字符 if(CodeStri='0') j=Nodej.lchild; else j=Nodej.rchild; if(Nodej.rchild=-1) /因?yàn)楣蚵鼧錄]有度為1的結(jié)點(diǎn)，所以此條件等同于Nodej為葉結(jié)點(diǎn) cout<<Nodej.sourcecode; fop<

39、;<Nodej.sourcecode; j=LeafNum*2-1-1; i+; fop.close(); cout<<"n譯碼成功且已存到文件TextFile.dat中。nn"/ 輸出碼文函數(shù)/ 函數(shù)功能：從文件中輸出哈夫曼樹的碼文void HuffmanTree:PrintCodeFile() char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail() cout<<"沒

40、有碼文文件，無法顯示碼文文件內(nèi)容。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(); / 輸出函數(shù)/ 函數(shù)功能：從內(nèi)存或文件中直接輸出哈夫曼樹void HuffmanTree:PrintHuffmanTree() if(Node=NULL) CreateHuffmanTreeFromFile(

41、); if (LeafNum<=1) cout<<"內(nèi)存無哈夫曼樹。操作撤銷。nn" return; ofstream fop("TreePrint.dat",ios_base:trunc); fop.close(); PrintHuffmanTree_aoru(2*LeafNum-1-1); return;/ 凹入法輸出函數(shù)/ 函數(shù)功能：用凹入法輸出哈夫曼樹void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)if (T!=-1) PrintHuffmanTree_aoru(NodeT.lchild,layer+1); ofstream fop("TreePrint.dat",ios_base:app);cout<<e