赫夫曼編碼器數(shù)據(jù)結構課程設計

1、數(shù)據(jù)結構課程設計報告課程設計:赫夫曼編碼器任務描述1 )建立一個文本文件，統(tǒng)計該文件中各字符頻率，對各字符進行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成原文件。2 )“壓縮文件”即：讀文件、統(tǒng)計文件中的字符個數(shù)、對文件進行哈夫曼編碼和譯碼、并將編碼譯碼后的字符存儲在文件中。要求：根據(jù)以上任務說明，設計程序完成功能。二、問題分析1、功能分析分析設計課題的要求，要求編程實現(xiàn)以下功能：(1) I:初始化(Initialization)。從終端讀入字符集大小n,以及n個字符和n個權值，建立赫夫曼樹，并將它存于文件hfmTree中。(2) E：編碼(Enc

2、oding)。利用已建好的赫夫曼樹(如不在內存，則從文件hfmTree中讀入)，對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。(3) D：譯碼(Decoding)。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件Textfile中。三、數(shù)據(jù)結構設計.哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedefstruct/赫夫曼樹的結構體charch;intweight;/權值intparent,lchild,rchild;htnode,*hfmtree;四、功能設計(一)主控菜單設計為實現(xiàn)通信錄管理的操作功能，首先設計一個含有多個菜單項的主控菜單程序，

3、然后再為這些菜單項配上相應的功能。程序運行后，給出6個菜單項的內容和輸入提示，如下：1 .一個功能函數(shù)對ASCII碼的初始化并需要一個數(shù)組來保存它們；2 .定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的過程當中保存被選中的字符，即給定報文中出現(xiàn)的字符,模擬哈夫曼樹選取和刪除左右子樹的過程；3 .自底而上地創(chuàng)建哈夫曼樹，保存根的地址和每個葉節(jié)點的地址，即字符的地址，然后自底而上檢索，首尾對換調整為哈夫曼樹實現(xiàn)哈弗曼編碼；4 .從哈弗曼編碼文件當中讀入字符，根據(jù)當前字符為0或者1的狀況訪問左子樹或者右孩子，實現(xiàn)解碼；5 .使用文件讀寫操作哈夫曼編碼和解碼結果的寫入；（二）程序模塊結構由課題要求可將程序劃分為

4、以下幾個模塊（即實現(xiàn)程序功能所需的函數(shù)）：intmain（）主函數(shù)：利用已建好的哈夫曼樹（如不在內存，則從文件hfmtree.txt中讀入）對文件中的正文進行編碼，然后將結果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內容，將編碼好的哈夫曼編碼存儲到CodeFile中。（2）Encoding編碼功能：對輸入字符進行編碼、Decoding譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼，結果存入文件textfile.dat中。（三）函數(shù)調用關系程序的主要結構（函數(shù)調用關系）如

5、下圖所示。其中main()是主函數(shù)，它進行菜單驅動，根據(jù)選擇項05調用相應的函數(shù)。main()函數(shù)使用for循環(huán)實現(xiàn)重復選擇。其循環(huán)結構如下：intmain()charcode100,h100,hl100;intn,i,j,k,l;ifstreaminput_file;文件輸入輸出流ofstreamoutput_file;charchoice,str100;hfmtreeHT;hfmcodeHC;cout<<"n"cout<<""<<"計算機(3)班"<<""<

6、<"Q07620307"<<""<<"XXX'n"while(choice!='Q'&&choice!='q')/當 choice 的值不為q 且不為 Q 時循cout<<"<<"*赫夫曼編碼/譯碼器*、c”.cout<<""<<"I.Init"<<""<<"E.Encoding"

7、<<"<<"D.Decoding"<<""<<"Q.Exitn"cout<<"請輸入您要操作的步驟："cin>>choice;if(choice='I'|choice='i')/初始化赫夫曼樹cout<<"請輸入字符個數(shù)："cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<&l

8、t;":"<<HCi<<endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"can'toenfile!"<<endl;return1;for(i=1;i<=n;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();cout<<"赫夫曼樹已經(jīng)

9、創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl;elseif(choice='E'|choice='e')/進行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf("請輸入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_file)cout<<"can'toenfile!"<<endl;return1;output_fil

10、e<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file)cout<<"can'toenfile!"<<endl;return1;for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n&quo

11、t;cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n"input_file.open("CodeFile.txt");/從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)cout<<"can'toenfile!"<<endl;return1;input_file>>code;cout<<"編碼碼值為："<<code<<endl;input_file.close();elseif

12、(choice='D'|choice='d')/讀入CodeFile.txt中的編碼進行譯碼，將譯出來的字符放入Textfile.txt中input_file.open("CodeFile.txt");if(!input_file)cout<<"can'toenfile!"<<endl;return1;input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_fil

13、e)cout<<"can'toenfile!"<<endl;return1;k=0;/先用編碼中的前幾個和字符的編碼相比較，然后while(hk!='0')往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l+)hlj=hl;hlj='0'if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("

14、;Textfile.txt");if(!input_file)cout<<"can'toenfile!"<<endl;return1;input_file>>h;cout<<h<<endl;input_file.close();cout<<"譯碼結束，字符已經(jīng)存入Textfile.txt文件中！"<<endl;elseif(choice='Q'|choice='q')/退出程序exit(0);else/如果選了選項之外的就

15、讓用戶重新選擇cout<<"您沒有輸入正確的步驟，請重新輸入！"<<endl;cout<<endl;return0;(四)文件結構1、linklist.h：赫夫曼樹相關的定義與聲明2、linklist.cpp:單鏈表運算的實現(xiàn)3、menu.h：主菜單函數(shù)的聲明4、menu.cpp：主菜單函數(shù)的實現(xiàn)5、mn.cpp：主函數(shù)（五）各函數(shù)的算法設計Iselete算法原理：選出HT樹到a為止，權值最小且parent為。的2個節(jié)點流程圖：代碼描述：voidSelect(hfmtree&HT,inta,int*p1,int*p2)/Selec

16、t函數(shù)，選出HT樹到a為止，權值最小且parent為0的2個節(jié)點inti,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i;/選出最小的節(jié)點for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&HTi.parent=0

17、&&x!=i)y=i;/選出次小的節(jié)點if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;算法的時間復雜度分析：O(a)流程圖:2、hfmcoding算法原理：構建赫夫曼樹HT,并求出n個字符的赫夫曼編碼 HC代碼描述:構建赫夫曼樹HT,并求出 個字符的赫夫曼編碼 HCintp1,p2;char*cd,z;if(n<=1)return;算法的時間復雜度分O(n)五、測試數(shù)據(jù)和結果1、測試數(shù)據(jù)自定義一組如下的測試數(shù)據(jù)，包含三個人員：字符權值A1B12C3D7E8F14G31H23U41J9K182、測試結果本程序在VC+環(huán)境下實現(xiàn)，下面是對以上測試數(shù)

18、據(jù)的運行結果。(1)主菜單顯示如下：子9閂s-FI. 口口U口口口口 .tH-鼻4乖不 白隹U意用士怠 1?佰賽自甘 SS ±HlkR上拿 7 R y » 1 2 n ± X 1 2 a 2 K 與Ekchrll-'Nl-.krnfc-n £入入殳K-Li=00X0M二C土電1屯£3NS11I4Uq=00J-XXMX10l<二E>=1HX/T=&&&=QX0±XLizPiw-iai>=tnK=00X1113.11.1標吳甚樹己經(jīng)aJ建元畢,拜且己統(tǒng)放.入hr-(2)編碼:*哧乖去號端冏/i舉g器此XMM一!<MX*MiJf*xMMiXX*Mi1»InitE.EncodingD.DecodingQ.Exit遣逾分作褰操作的步驟：E詢瑜入于符】R編翻完畢，押且己經(jīng)存入外如支相"武文件|編弼陰值為】0*掘*WW*:W*X*AMXWXitKNIt*導，扁干馬/干畢/月售星1. InitE«EncodinigD<Decodinf請施入您塞操作的步驟，E請輸入字