哈夫曼樹編碼實驗報告材料

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、據(jù)類型的定義；class HuffmanTree /哈夫曼樹private: HuffmanNode *Node; /Node存放哈夫曼樹 int LeafNum; /哈夫曼樹的葉子個數(shù)，也是源碼個數(shù)2.主程序模塊main()2.2 建立哈夫曼樹函數(shù)/ 函數(shù)功能：建立哈夫曼樹void HuffmanTree:CreateHuffmanTree() 2.3 函數(shù)功能：為哈夫曼樹編碼void HuffmanTree:Encoder()2.4 函數(shù)功能：對哈夫曼樹進行譯碼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個字符和n個權(quán)值。 建立哈夫曼樹：構(gòu)造哈夫曼樹，即將HNode數(shù)組中的各個位置的各個域都添上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件HTree.txt中。 構(gòu)造哈夫曼編碼：為從文件HTree.txt中讀入相關(guān)的字符信息進行哈

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

20、及葉子結(jié)點的權(quán)值和左分支上的0和右分支上的三、詳細設(shè)計1采用c語言定義相關(guān)的數(shù)據(jù)類型；結(jié)點的類型定義描述如下：struct HuffmanNode /哈夫曼樹的一個結(jié)點 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請輸入源碼字符集個數(shù)：" cin>>Num; if (Num<=1) cout<<"無法建立少于2個葉子結(jié)點的哈夫曼樹。nn" return; LeafNum=Num; Node=new HuffmanNode2*Num-1; for(int i=0;i<Num;i+) /讀入哈夫曼樹的葉子結(jié)點信息 cout<

24、;<"請輸入第"<<i+1<<"個字符值" getchar(); Nodei.sourcecode=getchar(); /源文的字符存入字符數(shù)組Info getchar(); cout<<"請輸入該字符的權(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é)點 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits<int>:max( ); /在所有子樹的根結(jié)點中，選權(quán)重最小的兩個根結(jié)點，pos1最后應(yīng)指向權(quán)重最小的根結(jié)點的下標for(int k=j-1;k>=0;k-) if (Nodek.parent=-1)/如果是某棵子樹的根結(jié)點 if (Nodek.weight<max1) /發(fā)現(xiàn)比當前最大值還大的權(quán)重 max2=max1; max1=Nodek.weight; pos2=pos1; po

26、s1=k; else if(Nodek.weight<max2) /發(fā)現(xiàn)比當前次大值還大的次大權(quán)重 max2=Nodek.weight; pos2=k; /if (Nodej.parent=-1) /for/在下標i處新構(gòu)造一個哈夫曼樹的內(nèi)部結(jié)點，其左、右孩子就是以上pos1、pos2所指向的結(jié)點 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é)點中字符的編碼 for (int m=0;m<Num;m+) /產(chǎn)生Nodei.sourcecode的編碼，存入Nodei.code中 int j=m; int j1; while(Nodej.parent!=-1) /從葉結(jié)點開始往根結(jié)點走，每往上走一層，就產(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é)點個數(shù) for(int n=0;n<2*Num-1;n+) /最后寫入哈夫曼樹的各個結(jié)點（存儲在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é)點個數(shù)少于2個，無法建立哈夫曼樹。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<<"請輸入需要編碼的源文(按回車鍵結(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') /源文串中從第一個字符開始逐個編碼 int i; for(i=0;i<LeafNum;i+) /找到當前要編碼的源文的字符在哈夫曼樹Node中的下標 if(Nodei.sourcecode=SourceTextk) /將對應(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ù)功能：對哈夫曼樹進行譯碼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é)點處，則譯出葉子結(jié)點對應(yīng)的源文字符 if(CodeStri='0') j=Nodej.lchild; else j=Nodej.rchild; if(Nodej.rchild=-1) /因為哈夫曼樹沒有度為1的結(jié)點，所以此條件等同于Nodej為葉結(jié)點 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