《哈夫曼樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計赫夫曼編碼/譯碼器設(shè)計指導(dǎo)教師：孫樹森、周維達(dá)班級：09數(shù)媒（2）班學(xué)號：E09700203姓名：林真超數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告一、題目：赫夫曼編碼/譯碼器設(shè)計二、目的：1、提高分析問題、解決問題的能力，進(jìn)一步鞏固數(shù)據(jù)結(jié)構(gòu)各種原理與方法。2、熟悉掌握一門計算機(jī)語言，可以進(jìn)行數(shù)據(jù)算法的設(shè)計。三、要求3.1總體要求 1、要充分認(rèn)識課程設(shè)計對培養(yǎng)自己的重要性，認(rèn)真做好設(shè)計前的各項準(zhǔn)備工作。尤其是對編程軟件的使用有基本的認(rèn)識。2、既要虛心接受老師的指導(dǎo)，又要充分發(fā)揮主觀能動性。結(jié)合課題，獨(dú)立思考，努力鉆研，勤于實踐，勇于創(chuàng)新。3、獨(dú)立按時完成規(guī)定的工作任務(wù)，不得弄虛作假，不準(zhǔn)抄襲他

2、人內(nèi)容，否則成績以不及格計。4、在設(shè)計過程中，要嚴(yán)格要求自己，樹立嚴(yán)肅、嚴(yán)密、嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度，必須按時、按質(zhì)、按量完成課程設(shè)計。3.2實施要求1、理解赫夫曼編碼/譯碼的確切意義。2、獨(dú)立進(jìn)行方案的制定，系統(tǒng)結(jié)構(gòu)設(shè)計要合理。3、在程序開發(fā)時，則必須清楚主要實現(xiàn)函數(shù)的目的和作用，需要在程序書寫時說明做適當(dāng)?shù)淖⑨?。在寫課設(shè)報告時，必須要將主要函數(shù)的功能和參數(shù)做詳細(xì)的說明。4、通過多組數(shù)據(jù)來檢測該系統(tǒng)的穩(wěn)定性和正確性。3.3 課程設(shè)計報告的內(nèi)容及要求 在完成課題驗收后，學(xué)生應(yīng)在規(guī)定的時間內(nèi)完成課程設(shè)計報告一份（不少于2000字）。1一、實驗?zāi)康? 進(jìn)一步掌握最優(yōu)二叉樹的含義。2 掌握最優(yōu)二叉樹的結(jié)構(gòu)特

3、征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。3 熟練掌握哈夫曼樹的建立和哈夫曼編碼方法。4 掌握用指針類型描述、訪問和處理運(yùn)算。二、實驗原理哈夫曼（Huffman）編碼屬于碼詞長度可變的編碼類，是哈夫曼在1952年提出的一種編碼方法，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，可區(qū)別的不同碼詞的生成是基于不同符號出現(xiàn)的不同概率。生成哈夫曼編碼算法基于一種稱為“編碼樹”（coding tree）的技術(shù)。算法步驟如下：（1）初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M(jìn)行排序。（2）把概率最小的兩個符號組成一個新符號（節(jié)點(diǎn)），即新符號的概率等于這兩個符號概率之和。（3）重復(fù)第2步，直到形成一個

4、符號為止（樹），其概率最后等于1。（4）從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為1，上分枝賦值為0。 譯碼的過程是分解電文中字符串，從根出發(fā)，按字符“0”或“1”確定找做孩子或右孩子，直至葉子節(jié)點(diǎn)，便求得該子串相應(yīng)的字符。三、實驗內(nèi)容（一）需求分析一個完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。(2) E：編碼。利用已建好的哈夫曼樹，對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。(3) D：譯碼。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼

5、，結(jié)果存入文件Textfile中。(4) P：印代碼文件（Print）.將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。(5) T：印哈夫曼樹（Treeprinting）.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint 中。（二）實驗步驟1.定義結(jié)點(diǎn)結(jié)構(gòu)，定義哈夫曼樹結(jié)構(gòu)；2.初始化哈夫曼樹，存儲哈夫曼樹信息；3.定義求哈夫曼編碼的函數(shù)；4.定義譯哈夫曼編碼的函數(shù)；5.寫出主函數(shù)。6.測試系統(tǒng)。（三）概要設(shè)計1 設(shè)計思想赫夫曼樹用鄰接矩陣作為存儲結(jié)構(gòu)，借助靜態(tài)鏈表

6、來實現(xiàn)遍歷。2 函數(shù)間的關(guān)系函數(shù)間的關(guān)系如圖所示：主函數(shù)顯示表頭初始化樹輸入字符編碼譯碼打印編碼打印赫夫曼樹選最小兩個權(quán)值Select()圖3.1 函數(shù)間的關(guān)系3 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計赫夫曼編譯碼器的主要功能是先建立赫夫曼樹，然后利用建好的赫夫曼樹生成赫夫曼編碼后進(jìn)行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵赫夫曼樹，規(guī)定赫夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對應(yīng)字符的編碼，稱之為赫夫曼編碼。最簡單的二進(jìn)制編碼方式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較

7、短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。赫夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。其主要流程圖如圖3.2所示。開始結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時編碼為0I2*N?I+編碼為1結(jié)束否否否右子是否為空是是否否是是是圖3.2 赫夫曼樹編譯碼器流程圖4.功能函數(shù)模塊劃分void main()void printhead()void printree(HuffmanTree HT,int w) /打印赫夫曼樹void copr

8、int(HuffmanTree start,HuffmanTree HT)/打印代碼文件void printcode() /打印代碼void decode() /完成譯碼功能void encode() /完成編碼功能void inputcode() void init()void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)void select(HuffmanTree t,int i,int &s1,int &s2)int min(HuffmanTree t,int i)/找兩個最小的權(quán)值（四）詳細(xì)設(shè)計（1）哈夫曼編碼

9、：首先定義函數(shù)，找出全部權(quán)值中最小的兩個，然后定義一個變量，使他始終成為最小的那個。再將兩個函數(shù)最為葉子結(jié)點(diǎn)，并得到一個父親節(jié)點(diǎn)，此父親節(jié)點(diǎn)的權(quán)值為其葉子節(jié)點(diǎn)的權(quán)值之和。并將此父親節(jié)點(diǎn)的權(quán)值與其余權(quán)值進(jìn)行比較，重新選出兩個最小的權(quán)值，再進(jìn)行上述步驟，直到所有權(quán)值形成了一顆二叉樹，而此二叉樹就是我們所說的最優(yōu)二叉樹，即哈夫曼樹。以上為哈夫曼樹的建立過程，下面為哈夫曼編碼的過程，從葉子節(jié)點(diǎn)出發(fā)，若此葉子節(jié)點(diǎn)為其父親節(jié)點(diǎn)的左孩子，則將其編碼為0，若為右孩子，則將其編碼為1，然后為其父親節(jié)點(diǎn)編碼，若為祖先的左孩子，則變?yōu)?，為右孩子則為1，依次向上一層進(jìn)行遍歷，直到遍歷到根節(jié)點(diǎn)，停止編碼。（2）譯碼：

10、對于已經(jīng)建好的哈夫曼樹，要對其進(jìn)行譯碼，首先從根出發(fā)如果編碼為0，則往左孩子遍歷，如果編碼為1，則往右孩子遍歷，直到遍歷到葉子節(jié)點(diǎn)，便求得該子串相應(yīng)的字符。（3）初始化哈夫曼鏈表:首先輸入結(jié)點(diǎn)個數(shù)，再將字符及權(quán)值輸入，調(diào)用編碼函數(shù)，得到每個字符編碼并將其輸出。最后將哈夫曼編碼寫入文件。（4）完成編碼功能：打開目錄下文件tobetran.txt，讀取里面的字符，對其進(jìn)行編碼后，將編碼寫入目錄下的codefile.txt中。（5）完成譯碼功能：打開根目錄下codefile.txt文件，讀取里面的編碼，對其中的編碼進(jìn)行譯碼，并將得到的內(nèi)容寫入根目錄下的文件txtfile.txt中。（6）打印編碼（7

11、）打印哈夫曼樹四、實驗結(jié)果1程序運(yùn)行環(huán)境為DOS，執(zhí)行文件為：Huffman2.exe2 . 初始化哈夫曼鏈表(實驗一)在這里，有一個要注意的問題，在程序剛開始運(yùn)行的時候，需要先用“i”命令對哈夫曼樹進(jìn)行初始化。若不進(jìn)行初始化，則表明哈夫曼樹并未建立，這樣就無法進(jìn)行后續(xù)的調(diào)試。3.編碼字符4.編碼5.譯碼6.打印編碼7.打印哈夫曼樹（實驗二）1.初始化的內(nèi)容如表所示：字符ABCDEFGHIJKLM頻度1886413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811612.初始化3.輸入的字符以及其對應(yīng)的編碼4、譯碼5. 文件te

12、xtfile.txt中內(nèi)容： THIS1PROGRAM1IS1MY1FAVORIT（這里的空格字符定義為1，故出現(xiàn)此譯碼）6.打印編碼7.打印哈夫曼樹五、實驗結(jié)果分析此算法的時間復(fù)雜度為：O（n），n為哈夫曼樹的結(jié)點(diǎn)個數(shù)。在對哈夫曼編碼/譯碼器算法設(shè)計過程中，主要參考了教材中對哈夫曼編碼/譯碼的算法。在實現(xiàn)的過程中遇到了一些問題，后來參考網(wǎng)上的一些代碼，進(jìn)行與自己帶嗎的整合，將編碼/譯碼算法完成。而在對編碼以及字符進(jìn)行文件保存、打開時，也遇到了不小的問題，很大一部分來源于對于以前C語言對文件操作的不熟練，所以在解決過程中，參考了一些類似的成功算法實例。六、實驗心得對于本次課程設(shè)計，主要是需要掌

13、握哈夫曼樹建立、哈夫曼編碼以及哈夫曼譯碼的算法。并能將其熟練應(yīng)用于編譯碼器的完成。經(jīng)過這次的課程設(shè)計，使我們更加了解了數(shù)據(jù)結(jié)構(gòu)，也更深入地了解了哈夫曼編碼與譯碼算法，課程設(shè)計的題目比我們平常的實驗內(nèi)容要難，完成它不僅需要有厚實的語言基礎(chǔ)，而且還要熟練掌握哈夫曼編碼與譯碼的算法，另外對于文件的基本操作也需要熟悉。由于本次課程設(shè)計時間安排得比較遲，所以大部分同學(xué)都在上課之前就把實驗做好了，由于在課外做，碰到許多問題無法請教老師，但是通過上網(wǎng)找尋解決辦法，大部分的錯誤與問題也都能基本解決。七、主要代碼#include #include #include #include #include const

14、 int UINT_MAX=1000;typedef struct /哈夫曼樹的存儲表示 int weight; /權(quán)值int parent,lchild,rchild; /父節(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)HTNode,* HuffmanTree; /動態(tài)分配數(shù)組存儲哈夫曼樹typedef char *HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表/-全局變量-HuffmanTree HT; /代表赫夫曼樹HuffmanCode HC; /代表赫夫曼編碼int *w,i,j,n; char *z;int flag=0; int numb=0;/ -求赫夫曼編碼-void line()/畫

15、分割線的函數(shù)coutn-n;int min(HuffmanTree t,int i)/找兩個最小的權(quán)值 int j,flag;int k=UINT_MAX; / 取k為不小于可能的值for(j=1;j=i;j+)if(tj.weights2)/ s1為最小的兩個值中序號較小的那個j=s1;s1=s2;s2=j;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(n=1)return;m=2*n-1;/申請2n-1

16、個內(nèi)存單元HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號單元未用for(p=HT+1,i=1;iweight=*w;/賦權(quán)值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);/調(diào)用建子樹的函數(shù)HTs1.parent=HTs2.parent=i;/i是s1和s2的父節(jié)點(diǎn)HTi.lchild=s1;HTi.rchild=s2;/s1和s2是i的兒子節(jié)點(diǎn)HTi.weight=HTs1.weight+HTs2.w

17、eight;/i的權(quán)值為s1和s2的和HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n個字符編碼的頭指針向量cd=(char*)malloc(n*sizeof(char); /分配求編碼的工作空間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;elsecd-start=1;HCi=(char*)malloc(n-st

18、art)*sizeof(char);/為第i個字符編碼分配空間strcpy(HCi,&cdstart); /從cd復(fù)制編碼（串）到HCfree(cd);/釋放工作空間/-初始化哈夫曼鏈表-void init() flag=1;int num;int num2;cout下面初始化赫夫曼鏈表endlnum;/輸入結(jié)點(diǎn)個數(shù)n=num;w=(int*)malloc(n*sizeof(int);/權(quán)值z=(char*)malloc(n*sizeof(char);/字符coutn請依次輸入n個字符(字符型)n注意:必須以回車結(jié)束：endl;char temp2;for(i=0;in;i+)/輸入字符 co

19、ut第i+1個字符:endl; gets(temp); *(z+i)=*temp;line();for(i=0;i=n-1;i+)/輸出字符coutsetw(6)*(z+i);line();coutn請依次輸入n個權(quán)值(n注意:必須以回車結(jié)束)：endl;for(i=0;i=n-1;i+)/輸入權(quán)值coutendl第i+1num2;*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/調(diào)用哈夫曼編碼/-打印編碼-cout字符對應(yīng)的編碼為:endl;for(i=1;i=n;i+)/輸出所有編碼puts(HCi);/-將赫夫曼編碼寫入文件-cout下面將赫夫曼編碼寫入文件en

20、dl;FILE *htmTree;char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL)cout文件打開失敗endl;return;fputs(z,htmTree);for(i=0;in+1;i+)fprintf(htmTree,%6d,*(w+i);fputs(r,htmTree);for(i=1;i=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmTree);cout已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中endlendl;/init/-獲取字符并寫入文件-void inpu

21、tcode() FILE *virttran,*tobetran;char str100;if(tobetran=fopen(tobetran.txt,w)=NULL)cout不能打開文件endl;return;cout請輸入你想要編碼的字符endl;gets(str);fputs(str,tobetran);cout獲取字符成功endl;fclose(tobetran);/-void encode() /完成編碼功能cout下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼endl;FILE *tobetran,*codefile;if(tobetran=fopen(tobetran.

22、txt,rb)=NULL)cout不能打開文件endl;if(codefile=fopen(codefile.txt,wb)=NULL)cout不能打開文件endl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char); /為tran分配100個字節(jié)while(i=99)if(fgets(tran,100,tobetran)=NULL)cout不能打開文件endl;break;for(i=0;*(tran+i)!=0;i+)for(j=0;jn)cout字符錯誤，無法編碼!endl;break;cout編碼工作完成endl編碼寫入目錄下的cod

23、efile.txt中endlendl;fclose(tobetran);fclose(codefile);free(tran);/-void decode() /完成譯碼功能cout下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼endl;FILE *codef,*txtfile;if(txtfile=fopen(Textfile.txt,w)=NULL)cout不能打開文件endl;if (codef=fopen(codefile.txt,r)=NULL)cout不能打開文件endl;char *tbdc,*outext,i2;int io=0,i,m;unsigned long

24、length=10000;tbdc=(char*)malloc(length*sizeof(char); /分配空間fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char); /分配空間m=2*n-1;for(i=0;*(tbdc+i)!=0;i+) /進(jìn)入循環(huán)i2=*(tbdc+i);if(HTm.lchild=0) *(outext+io)=*(z+m-1);io+;m=2*n-1;i-;else if(i2=0) m=HTm.lchild;else if(i2=1) m=HTm.rchild;*(outext+io

25、)=0;fputs(outext,txtfile);cout譯碼完成endl內(nèi)容寫入根目錄下的文件txtfile.txt中endlendl;free(tbdc);free(outext);fclose(txtfile);fclose(codef);/-void printcode() /打印代碼cout下面打印根目錄下文件CodePrin.txt中編碼字符endl-n;FILE * CodePrin,* codefile;if(CodePrin=fopen(CodePrin.txt,w)=NULL)cout不能打開文件endl;return;if(codefile=fopen(codefile

26、.txt,r)=NULL)cout不能打開文件endl;return;char *work3;work3=(char*)malloc(51*sizeof(char);doif(fgets(work3,51,codefile)=NULL)cout不能讀取文件endl;break;fputs(work3,CodePrin);puts(work3);while(strlen(work3)=50);free(work3);cout打印工作結(jié)束endlendl;fclose(CodePrin); fclose(codefile);void coprint(HuffmanTree start,Huffma

27、nTree HT)/打印代碼文件char t= ;if(start!=HT)FILE * TreePrint;if(TreePrint=fopen(TreePrint.txt,a)=NULL)cout創(chuàng)建文件失敗rchild,HT);if(start-lchild!=NULL&start-rchild!=NULL) t=;coutsetw(5*numb)weighttweight);coprint(HT+start-lchild,HT);numb-;fclose(TreePrint);void printree(HuffmanTree HT,int w) /打印赫夫曼樹HuffmanTree

28、p;p=HT+w;cout下面打印赫夫曼樹endl; / 輸出打印赫夫曼樹語句coprint(p,HT);cout打印工作結(jié)束endl; /輸出打印工作結(jié)束void printhead() coutt數(shù)據(jù)結(jié)構(gòu)t課程設(shè)計t09數(shù)媒2班 林真超 E09700203n;coutntt; cout i.初始化赫夫曼鏈表 w.編碼字符 ntt;cout e.編 碼 d.譯 碼 ntt;cout p.打印編碼 t.打印赫夫曼樹 ntt;cout q.退 出 ntt; if(flag=0)coutn請先初始化赫夫曼鏈表,輸入in;coutchoice; switch(choice) case i: /按下i

29、則進(jìn)行初始化赫夫曼鏈表,調(diào)用init函數(shù) init(); break; case w: /按下w編碼字符，調(diào)用inputcode函數(shù)inputcode();break; case e: /按下e編碼，調(diào)用encode函數(shù)encode();break; case d: /按下d譯碼，調(diào)用decode函數(shù)decode();break; case p: /按下p打印編碼，調(diào)用printcode函數(shù)printcode();break; case t: /按下t打印赫夫曼樹，調(diào)用printree函數(shù)printree(HT,2*n-1);break; case q: /按下q退出break; default:cout輸入錯誤，請重新選擇endl; free(z); /釋放z結(jié)點(diǎn)free(w); /釋放w結(jié)點(diǎn)free(HT); /釋放HT結(jié)點(diǎn)成績評定表平時成績答辯成績最終成績24