數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書哈夫曼編譯碼器

1、課 程 設(shè) 計(jì) 說 明 書 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目： 哈夫曼編/譯碼器 學(xué) 院： 計(jì)算機(jī)科學(xué)與信息工程學(xué)院 學(xué)生姓名： 學(xué)生學(xué)號： 專業(yè)班級： 網(wǎng)絡(luò)工程13-01 指導(dǎo)教師： 2015年 6月 25日課 程 設(shè) 計(jì) 任 務(wù) 書設(shè)計(jì)題目哈夫曼編/譯碼器學(xué)生姓名申恒恒所在院部計(jì)算機(jī)科學(xué)與信息工程學(xué)院專業(yè)、班級網(wǎng)絡(luò)工程13-1設(shè)計(jì)要求：1、根據(jù)哈夫曼樹編碼原理，構(gòu)造哈夫曼樹，創(chuàng)建一套哈夫曼編碼；2、讀取文本文件，并對文件內(nèi)容編碼，生成編碼文件；3、對編碼文件進(jìn)行譯碼，獲得恢復(fù)文件；4、比較恢復(fù)文件和原文件是否相同。學(xué)生應(yīng)完成的工作：1. 學(xué)生應(yīng)認(rèn)真學(xué)習(xí)參考程序，理解每個文件、每個函數(shù)以及各個

2、變量的作用和意義。在此基礎(chǔ)上進(jìn)一步改進(jìn)程序，最后正確地運(yùn)行程序。2. 對程序進(jìn)行測試，設(shè)計(jì)詳細(xì)的測試計(jì)劃，然后根據(jù)測試計(jì)劃設(shè)計(jì)測試用例，對程序進(jìn)行測試。測試時應(yīng)注意對各種邊緣情況進(jìn)行測試。3. 完成課程設(shè)計(jì)報告。參考文獻(xiàn)：1. 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（c語言版） 清華大學(xué)出版社 20112. 譚浩強(qiáng) c程序設(shè)計(jì)（第四版） 清華大學(xué)出版社2010工作計(jì)劃：1. 小組審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料準(zhǔn)備（3天）。 2. 把程序完整運(yùn)行出來（4天）。 3. 增加改進(jìn)程序（3天）。 4. 寫課程設(shè)計(jì)報告（3天）。 5. 提交課程設(shè)計(jì)報告及答辯（1天）任務(wù)下達(dá)日期：2015 年 6 月 9 日 任務(wù)完成日

3、期：2015 年 6 月 22 日指導(dǎo)教師（簽名）： 學(xué)生（簽名）：申恒恒哈夫曼編/譯碼器摘 要：采用哈夫曼編碼思想實(shí)現(xiàn)對字符串的編碼，以及對編碼的解碼。字符串的長度不小于5000字節(jié)。讀取要編碼的文本文件，將文件的內(nèi)容進(jìn)行編碼，生成新的文件。對編碼文件進(jìn)行解碼，獲得文本文件。將譯碼的文本文件和原文件進(jìn)行比較，恢復(fù)文件和原文件必須完全一致。關(guān)鍵詞：哈夫曼編碼 哈夫曼譯碼 解碼19目 錄哈夫曼編/譯碼器21. 設(shè)計(jì)背景41.1程序的功能41.2輸入輸出的要求42.設(shè)計(jì)方案52.1程序結(jié)構(gòu)52.2數(shù)據(jù)結(jié)構(gòu)53. 方案實(shí)施63.1詳細(xì)設(shè)計(jì)63.2 調(diào)試分析63.2.1 發(fā)現(xiàn)問題63.2.2 逐步解決

4、問題63.2.3 代碼實(shí)現(xiàn)過程73.3 核心源程序清單124. 結(jié)果與結(jié)論144.1程序運(yùn)行結(jié)果圖144.2結(jié)論與心得體會155. 參考文獻(xiàn)161. 設(shè)計(jì)背景1.1程序的功能(1) 從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmtree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；(2) 利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmtree中讀入），對文件tobetran中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中，并輸出結(jié)果，將文件codefile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件cod

5、eprint中；(3) 利用已建好的哈夫曼樹將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中，并輸出結(jié)果。1.2輸入輸出的要求先在執(zhí)行文件的同根目錄下創(chuàng)建abc.txt文件，在abc文件中輸入各字母及相應(yīng)的權(quán)值。測試數(shù)據(jù)：字符空格abcdefghijklm頻度1866413223210321154757153220字符nopqrstuvwxyz頻度57631514851802381811612.設(shè)計(jì)方案2.1程序結(jié)構(gòu) 2.2數(shù)據(jù)結(jié)構(gòu)typedef struct int weight; /權(quán)重 int parent,lchild,rchild; /父親節(jié)點(diǎn)，左孩子，右孩子h

6、tnode,* huffmantree; /定義節(jié)點(diǎn)和哈夫曼樹結(jié)構(gòu)體3. 方案實(shí)施3.1詳細(xì)設(shè)計(jì)初始化哈夫曼鏈表: void initialization();輸入帶編碼的字符并寫入文件：void inputcode();編碼: encoding();譯碼: decoding(); 打印編碼:code_printing();3.2 調(diào)試分析3.2.1 發(fā)現(xiàn)問題如何根據(jù)輸入的字符和使用頻率構(gòu)建哈夫曼樹并得到它的哈夫曼編碼？3.2.2 逐步解決問題哈夫曼樹是什么？給定n個權(quán)值作為n個葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(huffman tre

7、e)。如何構(gòu)建哈夫曼樹？假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點(diǎn)。 n個權(quán)值分別設(shè)為 w1、w2、wn，則哈夫曼樹的構(gòu)造規(guī)則為：(1) 將w1、w2、，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點(diǎn))；(2) 在森林中選出兩個根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼編碼是什么？哈夫曼編碼(huffman coding)是一種編碼方式，哈夫曼編碼是可變字長編碼(vlc)的一種。huffman于1

8、952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作huffman編碼。如何得到哈夫曼編碼？通過從哈夫曼樹根結(jié)點(diǎn)開始，對左子樹分配代碼“0”，右子樹分配代碼“1”，一直到達(dá)葉子結(jié)點(diǎn)為止，然后將從樹根沿每條路徑到達(dá)葉子結(jié)點(diǎn)的代碼排列起來，便得到了哈夫曼編碼。3.2.3 代碼實(shí)現(xiàn)過程/ -哈夫曼編碼- / w存放n個字符的權(quán)值(均0),構(gòu)造哈夫曼樹ht,并求出n個字符的哈夫曼編碼hcvoid huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) int m,i,s1,

9、s2,start; int c,f; huffmantree p; char *cd; if(n=1)return; /檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹 m=2*n-1; /需要構(gòu)造多少個頂點(diǎn) ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0號單元未用 for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼樹 select(ht,i-1,s1,s2); / 在ht1i-1中選擇parent為0且weight最

10、小的兩個結(jié)點(diǎn),其序號分別為s1和s2 hts1.parent=hts2.parent=i; /建立父親節(jié)點(diǎn) hti.lchild=s1; /初始化左右孩子節(jié)點(diǎn) hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; /把孩子節(jié)點(diǎn)的權(quán)值累加到父親節(jié)點(diǎn) hc=(huffmancode)malloc(n+1)*sizeof(char*); / 從葉子到根逆向求每個字符的哈夫曼編碼 cd=(char*)malloc(n*sizeof(char); / 分配n個字符編碼的頭指針向量(0不用) cdn-1=0; / 編碼結(jié)束符 for(i=1;i=n;i+)

11、/ 逐個字符求哈夫曼編碼 start=n-1; / 編碼結(jié)束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) / 從葉子到根逆向求編碼 if(htf.lchild=c) cd-start=0; /左子樹為0 else cd-start=1; /右子樹為1 hci=(char*)malloc(n-start)*sizeof(char); /為第i個字符編碼分配空間 strcpy(hci,&cdstart); /從cd復(fù)制編碼(串)到hc free(cd); / 釋放工作空間編碼：上面已經(jīng)得到了相應(yīng)的字符的編碼。直接輸出即可。如何進(jìn)行哈夫曼編碼的譯碼？

12、知道了編碼用的哈夫曼樹后。從根結(jié)點(diǎn)出發(fā)，逐個讀入編碼的二進(jìn)制碼；若代碼為“0”，則走左子樹的根結(jié)點(diǎn)，否則走向右子樹的根結(jié)點(diǎn)；一旦到達(dá)葉子結(jié)點(diǎn)，便譯出代碼所對應(yīng)的字符。然后又重新從根結(jié)點(diǎn)開始繼續(xù)譯碼，直到二進(jìn)制編碼結(jié)束。編碼和譯碼的代碼如下：/-編碼函數(shù)-void encoding() printf(下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼n); file *tobetran,*codefile; if(tobetran=fopen(tobetran.txt,rb)=null) /打開將要編碼的文件 printf(不能打開文件n); if(codefile=fopen(codef

13、ile.txt,wb)=null) /保存編碼結(jié)果的文件 printf(不能打開文件n); char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=null) printf(不能打開文件n); break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) printf(字符錯誤，無法編碼!n); break; printf(n編碼完成n編碼寫入目錄下的codefile.txt中nn); fclose(tobetran); fclose(

14、codefile); free(tran);/-譯碼函數(shù)-void decoding() printf(下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼n); file *codef,*txtfile; if(txtfile=fopen(textfile.txt,w)=null) /打開譯碼結(jié)果保存的文件 printf(不能打開文件n); if (codef=fopen(codefile.txt,r)=null) /打開將要譯碼的文件 printf(不能打開文件n); char *work,*work2,i2;int i4=0,i,i3; unsigned long length=1

15、0000; work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1; /n=26 i3=huffman樹的全部節(jié)點(diǎn)數(shù)i=0;doi2=*(work+i); /求編碼后的二進(jìn)制if(hti3.lchild=0&hti3.rchild=0) /如果到達(dá)葉子節(jié)點(diǎn) *(work2+i4)=*(z+i3-1);i4+;i3=2*n-1; /重新從根節(jié)點(diǎn)開始查找i-;else if(i2=0) i3=hti3.lchild; /左子樹為0

16、else if(i2=1) i3=hti3.rchild; /右子樹為1i+;while(*(work+i-1)!=0);*(work2+i4)=0;fputs(work2,txtfile);printf(譯碼完成n內(nèi)容寫入根目錄下的文件textfile.txt中nn);free(work);free(work2); fclose(txtfile); fclose(codef);3.3 核心源程序清單void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) int m,i,s1,s2,start; int c,f; huf

17、fmantree p; char *cd; if(n=1)return; /檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹 m=2*n-1; /需要構(gòu)造多少個頂點(diǎn) ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0號單元未用 for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼樹 select(ht,i-1,s1,s2); / 在ht1i-1中選擇parent為0且weight最小的兩個結(jié)點(diǎn),其序號分別為s1和s2 hts

18、1.parent=hts2.parent=i; /建立父親節(jié)點(diǎn) hti.lchild=s1; /初始化左右孩子節(jié)點(diǎn) hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; /把孩子節(jié)點(diǎn)的權(quán)值累加到父親節(jié)點(diǎn) hc=(huffmancode)malloc(n+1)*sizeof(char*); / 從葉子到根逆向求每個字符的哈夫曼編碼 cd=(char*)malloc(n*sizeof(char); / 分配n個字符編碼的頭指針向量(0不用) cdn-1=0; / 編碼結(jié)束符 for(i=1;i=n;i+) / 逐個字符求哈夫曼編碼 start=n-1; / 編碼結(jié)束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) / 從葉子到根逆向求編碼 if(htf.lchild=c) cd-start=0; /左子樹為0 else cd-start=1; /右子樹為1 hci=(char*)malloc(n-start)*sizeof(char); /為第i個字符編碼分配空間 strcpy(hci,&cdstart); /從cd復(fù)制編碼(串