1、中北大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計 說 明 書學(xué)生姓名:學(xué) 號：學(xué) 院:軟件學(xué)院專 業(yè):軟件開發(fā)與測試題 目:哈夫曼編碼/譯碼器指導(dǎo)教師康珺2011年12月20日目 錄1 問題描述12 需求分析13 概要設(shè)計131抽象數(shù)據(jù)類型定義132總體框圖以及功能描述24 詳細(xì)設(shè)計241數(shù)據(jù)類型的定義242主要模塊的算法描述35 測試分析46 課程設(shè)計總結(jié)6附錄（源程序清單）71 問題描述1. 設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止。(1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于當(dāng)前目錄中)；(2)分別采用動態(tài)和靜態(tài)存儲結(jié)構(gòu); 初始化：鍵盤輸入

2、字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹;(3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；輸出編碼；設(shè)計要求：(1) 符合課題要求，實現(xiàn)相應(yīng)功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實用性、安全性。2 需求分析 編寫此軟件是為了實現(xiàn)一個利用哈夫曼算法的編碼和譯碼系統(tǒng)。比如，再利用電報進(jìn)行通訊時，需要將文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。比如需傳送的電文為“A B A C C D A”假設(shè)將A,B,C,D分別編碼為00、01、10、11.則上述電文遍為100，總長度為14位。但是在傳送過程中，總希望長度能夠盡可能的短，于是我們想采用長度不等的編碼。但是這種編碼必須遵循

3、：任何一個字符的編碼都不是另一個字符編碼的前綴。對此軟件的要求：能夠正確的使得對于輸入的字符進(jìn)行編碼以及譯碼，并且是的在譯碼過程中不會出錯，同時能夠?qū)⒕幋a以及譯碼的結(jié)果正確的存入文件當(dāng)中。3 概要設(shè)計31抽象數(shù)據(jù)類型定義ADT BinaryTree數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,.,n, n0數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹。若D僅為一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān)系： （1）再D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)。 （2）若D-root空集，則存在一個劃分D1，D2，Dm（m0）。 （3）對應(yīng)于D-root的劃分，H-root，

4、X1， 有唯一的一個劃分H1，H2，Hm（m0）。基本操作：InitTree(&T)操作結(jié)果：構(gòu)造空樹T。DestroyTree(&T)初始條件：樹T已存在。操作結(jié)果：樹T被銷毀。ClearTree(&T)初始條件：樹T已存在。操作結(jié)果：將樹T清為空棧。TreeEmpty(T)初始條件：樹T已存在。操作結(jié)果：若樹T為空，則返回TRUE，否則FALSE。TreeDepth(T)初始條件:樹T已存在。操作結(jié)果：返回T的深度。Root（T）初始條件：樹T已存在。操作結(jié)果：返回樹T的根。32總體框圖以及功能描述4 詳細(xì)設(shè)計41數(shù)據(jù)類型的定義（1）哈夫曼樹節(jié)點(diǎn)類型 struct hufmtreenode

5、 /哈弗曼樹結(jié)點(diǎn)數(shù)據(jù)類型 char data; float weight; /結(jié)點(diǎn)權(quán)值 int parent,lchild,rchild; /父結(jié)點(diǎn)，左、右孩子結(jié)點(diǎn) ;（2）哈夫曼樹類型 struct hufmtree /哈弗曼樹數(shù)據(jù)類型 hufmtreenode *node; /結(jié)點(diǎn)數(shù)組（根據(jù)n的值動態(tài)分配） int n; /葉子結(jié)點(diǎn)數(shù);（3)哈夫曼編碼數(shù)據(jù)類型 struct Codetype /哈弗曼編碼數(shù)據(jù)類型 char *bits; /編碼流數(shù)組， int start;/編碼實際在編碼流數(shù)組里的開始位置42主要模塊的算法描述（1) 主函數(shù)： void main() printf(哈夫曼

6、編碼譯碼系統(tǒng)n); tree=CreateHuffmanTreeFromSourceFile();/讀取文件建立哈樹tree=CreateHuffmanTreeByInput(); /手動輸入建立哈夫曼樹HuffmanCode(tree); /打印字符集的哈夫曼編碼tree=Encoding(tree); /對文本文件編碼Decoding(tree); /對代碼文件譯碼 （2）構(gòu)造哈夫曼樹 hufmtree* BuildHuffmanTree(hufmtree *tree)/構(gòu)建葉子結(jié)點(diǎn)已初始化的哈夫曼樹For(p=HT,i=1;i=n;+i,+p,+w) *p=0,0,0,0; For(;i

7、=m;+i,+p) *p=0,0,0,0); For(i=n+1;i=m;i+) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTs1.parent=s1; HTs1.parent=s2; HTi.weight=HTs1.weight+HTs2.weight; （3）利用哈夫曼編碼算法哈夫曼編碼HuffmanCode(tree) hc=(HuffmanCode)malloc(n+1*sizeof(char *) cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(c=i;i=n;+i) sta

8、rt=n-1; for(c=i;f=HTi.parent;f!=0;c=f,f =HTf.parent) If(HTf.lchild=c) cd-start=0; HCi=(car *)malloc(n-start)*sizeof(char); Strcpy(HCi,&cdstart); 5 測試分析 (1)打開源文件統(tǒng)計各字符及權(quán)值信息并存入data.txt文件中 (2)將統(tǒng)計出的權(quán)值信息進(jìn)行哈夫曼編碼（3） 將編碼內(nèi)容存入CodeFile.txt文件中（4） 將CodeFile.txt文件中的內(nèi)容譯碼（5) 成功譯碼把原字符信息存入DeCodeFile.txt文件中（6）輸入各字符及其權(quán)值

9、（7） 將各字符的權(quán)值信息進(jìn)行哈夫曼編碼（7） 根據(jù)編碼再進(jìn)行譯碼工作6 課程設(shè)計總結(jié)課程設(shè)計是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程.隨著科學(xué)技術(shù)發(fā)展的日新日異，當(dāng)今計算機(jī)應(yīng)用在生活中可以說得是無處不在。因此作為二十一世紀(jì)的大學(xué)來說掌握計算機(jī)開發(fā)技術(shù)是十分重要的?；仡櫰鸫舜握n程設(shè)計，至今我仍感慨頗多，的確，自從拿到題目到完成整個編程，從理論到實踐，在整整一個星期的日子里，可以學(xué)到很多很多的的東西，同時不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實際

10、相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨(dú)立思考的能力。在設(shè)計的過程中遇到問題，這畢竟獨(dú)立做的，難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固，比如說結(jié)構(gòu)體通過這次課程設(shè)計之后，一定把以前所學(xué)過的知識重新溫故。這次課程設(shè)計終于順利完成了，在設(shè)計中遇到了很多編程問題，最后在謝老師的辛勤指導(dǎo)下，終于游逆而解。同時，在李玉蓉老師的軟件工程導(dǎo)論課上我學(xué)得到很多實用的知識，在次我表示感謝！同時，對給過我?guī)椭乃型瑢W(xué)和各位指導(dǎo)老

11、師再次表示忠心的感謝！附錄（源程序清單）#include #include #include #define MAXVAL 10000.0struct hufmtreenode/哈弗曼樹結(jié)點(diǎn)數(shù)據(jù)類型char data;double weight;/結(jié)點(diǎn)權(quán)值int parent,lchild,rchild;/父結(jié)點(diǎn)，左、右孩子結(jié)點(diǎn);struct hufmtree/哈弗曼樹數(shù)據(jù)類型hufmtreenode *node;/結(jié)點(diǎn)數(shù)組（根據(jù)n的值動態(tài)分配）int n;/葉子結(jié)點(diǎn)數(shù);struct Codetype/哈弗曼編碼數(shù)據(jù)類型char *bits;/編碼流數(shù)組，n為為哈夫曼樹中葉子結(jié)點(diǎn)的數(shù)目，編碼的

12、長度不可能超過nint start;/編碼實際在編碼流數(shù)組里的開始位置;void SortHufmtree(hufmtree *tree)/將哈夫曼樹n個葉子結(jié)點(diǎn)由大到小排序int i,j,k;hufmtreenode temp;if (tree=NULL)return;for (i=0;in;i+)k=i;for(j=i+1;jn;j+)if (tree-nodej.weighttree-nodek.weight)k=j;if (k!=i)temp=tree-nodei;tree-nodei=tree-nodek;tree-nodek=temp;Codetype* HuffmanCode(h

13、ufmtree *tree)/哈弗曼編碼的生成int i,j,p,k;Codetype *code;if (tree=NULL)return NULL;code=(Codetype*)malloc(tree-n*sizeof(Codetype);for (i=0;in;i+)printf(%c ,tree-nodei.data);/打印字符信息codei.bits=(char*)malloc(tree-n*sizeof(char);codei.start=tree-n-1;j=i;p=tree-nodei.parent;while(p!=-1)if (tree-nodep.lchild=j)c

14、odei.bitscodei.start=0;elsecodei.bitscodei.start=1;codei.start-;j=p;p=tree-nodep.parent;for (k=codei.start+1;kn;k+)/打印字符編碼printf(%c,codei.bitsk);printf(n);return code;hufmtree* BuildHuffmanTree(hufmtree *tree)/構(gòu)建葉子結(jié)點(diǎn)已初始化的哈夫曼樹/tree中所有葉子結(jié)點(diǎn)已初始化int i,j,p1,p2,m;float small1,small2;m=2*(tree-n)-1;for (i=t

15、ree-n;inodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0.0;for (i=tree-n;im;i+)/構(gòu)建哈夫曼樹small1=small2=MAXVAL;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.weight;p1=j;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.weight;p2=j;tree-nodep1.parent=tree-nodep2.parent=i

16、;tree-nodei.weight=tree-nodep1.weight+tree-nodep2.weight;tree-nodei.lchild=p1;tree-nodei.rchild=p2;return tree;hufmtree* CreateHuffmanTreeFromSourceFile()/通過解析源文件建立哈夫曼樹FILE *textfile,*datafile;char ch,sourcefilename100;int i,j=0,n=0;float count128; /用于統(tǒng)計字符在源文件中出現(xiàn)的次數(shù)，27表示26個英文字母和1個空格字符hufmtree *tree;

17、/打開一個源文件printf(n請輸入源文件所在路徑:n);scanf(%s,sourcefilename);if (textfile=fopen(sourcefilename,r)=NULL)printf(n找不到文件%sn,sourcefilename);return NULL;for(i=0;i128;i+)counti=0;/對源文件中各字符的個數(shù)統(tǒng)計ch=fgetc(textfile);while(!feof(textfile)for(i=0;i128;i+)if (ch=char(i)counti+;break;ch=fgetc(textfile);/將統(tǒng)計結(jié)果寫入權(quán)值信息文件da

18、ta.txt中，并構(gòu)建哈夫曼樹datafile=fopen(f:data.txt,w);for (i=0;inode=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;printf(n源文件的字符集及其權(quán)值信息如下：n);for(i=0;inodej.data=char(i);tree-nodej.weight=counti;tree-nodej.parent=-1;tree-nodej.lchild=-1;tree-nodej.rchild=-1;j+;SortHufmtree(tree);BuildHuffmanTree(

19、tree);fclose(textfile);fclose(datafile);printf(n哈夫曼樹建立完畢，已將權(quán)值信息保存至data.txtn);return tree;hufmtree* CreateHuffmanTreeByInput()/通過用戶輸入建立哈夫曼樹int n;hufmtree *tree;int i,m;FILE *datafile;tree=(hufmtree*)malloc(sizeof(hufmtree);datafile=fopen(f:data.txt,w);/由用戶輸入字符與權(quán)值信息并將其寫入data.txt，同時進(jìn)行哈夫曼樹初始化printf(請輸入字

20、符數(shù)：);scanf(%d,&n);if (nnode=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;m=2*n-1;for (i=0;inodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0.0;fprintf(datafile,%dn,n);for (i=0;inodei.data=getche();tree-nodei.weight=getche();fprintf(datafile,%c,%.0fn,tree-nod

21、ei.data,tree-nodei.weight-48);fclose(datafile);/哈夫曼樹構(gòu)建SortHufmtree(tree);BuildHuffmanTree(tree);printf(n哈夫曼樹建立完畢，已將權(quán)值信息保存至data.txtn);return tree;hufmtree* CreateHuffmanTreeFromDataFile()/通過讀取權(quán)值信息文件建立哈夫曼樹FILE *datafile;int i,n;hufmtree *tree;if (datafile=fopen(f:data.txt,r)=NULL)printf(n哈夫曼樹尚未建立n);re

22、turn NULL;/哈夫曼樹初始化fscanf(datafile,%d,&n);fgetc(datafile);tree=(hufmtree*)malloc(sizeof(hufmtree);tree-node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;for (i=0;inodei.data=fgetc(datafile);fscanf(datafile,%fn,&tree-nodei.weight);tree-nodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchi

23、ld=-1;fclose(datafile);/哈夫曼樹構(gòu)建SortHufmtree(tree);BuildHuffmanTree(tree);return tree;hufmtree* Encoding(hufmtree *tree)/對源文件進(jìn)行編碼并將其輸出至新文件FILE *textfile,*codefile;char ch,sourcefilename50;int i,j;Codetype *code;if (tree=NULL)/如果內(nèi)存中尚未建立哈夫曼樹/試從data.txt中讀取權(quán)值信息并建立哈夫曼樹tree=CreateHuffmanTreeFromDataFile();i

24、f (tree=NULL)return NULL;/讀取源文件printf(n請輸入源文件所在路徑:n);scanf(%s,sourcefilename);if (textfile=fopen(sourcefilename,r)=NULL)printf(n找不到文件%sn,sourcefilename);return NULL;/打印源文件內(nèi)容printf(n源文件的原文如下：n);ch=fgetc(textfile);while(!feof(textfile)printf(%c,ch);ch=fgetc(textfile);/編碼printf(n字符集的哈夫曼編碼如下：n);code=Huf

25、fmanCode(tree);/將源文件中各字符編碼并寫入codefilecodefile=fopen(f:CodeFile.txt,w);fseek(textfile,0,SEEK_SET);ch=fgetc(textfile);while (!feof(textfile)for(i=0;in;i+)if (ch=tree-nodei.data)for(j=codei.start+1;jn;j+)fputc(codei.bitsj,codefile);break;if (i=tree-n)/在哈夫曼樹樹中找不到與文本內(nèi)容里對應(yīng)的字符printf(n字符%c不在哈夫曼樹中，不能正確編碼。n,c

26、h);fclose(codefile);return NULL;ch=fgetc(textfile);fclose(codefile);/提示成功信息并打印代碼printf(n編碼成功,已將代碼寫入CodeFile.txt,代碼如下：n);codefile=fopen(f:CodeFile.txt,r);ch=fgetc(codefile);while(!feof(codefile)printf(%c,ch);ch=fgetc(codefile);printf(n);fclose(textfile);fclose(codefile);return tree;void Decoding(hufm

27、tree *tree)/對編碼文件進(jìn)行譯碼并將其輸出至新文件FILE *codefile,*decodefile;char ch,codefilename100;int i;if (tree=NULL)/如果尚未建立哈夫曼樹/試從data.txt中讀取權(quán)值信息并建立哈夫曼樹tree=CreateHuffmanTreeFromDataFile();if (tree=NULL)return ;/打開編碼文件printf(n請輸入代碼文件所在路徑:n);scanf(%s,codefilename);if (codefile=fopen(codefilename,r)=NULL)printf(n找不到

28、文件%sn,codefilename);return;/打印編碼文件的正文printf(n代碼文件原文如下：n);ch=fgetc(codefile);while(!feof(codefile)printf(%c,ch);ch=fgetc(codefile);/進(jìn)行譯碼并將譯文寫入DecodeFiledecodefile=fopen(f:DecodeFile.txt,w);fseek(codefile,0,SEEK_SET);ch=fgetc(codefile); while(!feof(codefile)for(i=2*tree-n-2;tree-nodei.lchild=0 & tree-

29、nodei.rchild=0 & ch!=EOF;)if(ch=0)i = tree-nodei.lchild;else if(ch=1)i = tree-nodei.rchild;else/printf(n存在異常字符%c，不能正確譯碼。n,ch);return ;if (i=-1)/在哈夫曼樹中找不到對應(yīng)葉子結(jié)點(diǎn)printf(n編碼與當(dāng)前哈夫曼樹結(jié)構(gòu)不相符，不能正確譯碼。n,ch);fclose(decodefile);return;ch=fgetc(codefile);if (tree-nodei.lchild=0 & tree-nodei.rchild=0)/尋找葉子結(jié)點(diǎn)的過程中突然讀到了文件尾printf(n代碼文件編碼內(nèi)容不完整，不能完整譯碼。n,ch);fclose(deco