哈夫曼編碼譯碼器實驗報告

1、中北大學數(shù) 據(jù) 結 構課 程 設 計 說 明 書   學生姓名:郝晨棟 學 號：1021010933 學 院:軟件學院專 業(yè):軟件開發(fā)與測試 題 目:哈夫曼編碼/譯碼器指導教師康珺    2011年12月20日目 錄1 問題描述12 需求分析13 概要設計131抽象數(shù)據(jù)類型定義132總體框圖以及功能描述24 詳細設計241數(shù)據(jù)類型的定義242主要模塊的算法描述35 測試分析46 課程設計總結6附錄（源程序清單）7- 24 - 1 問題描述1. 設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并

2、處理以下項目，直到選擇退出為止。(1) 將權值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于當前目錄中)；(2) 分別采用動態(tài)和靜態(tài)存儲結構; 初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹;(3) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；輸出編碼；設計要求：(1) 符合課題要求，實現(xiàn)相應功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實用性、安全性。2 需求分析 編寫此軟件是為了實現(xiàn)一個利用哈夫曼算法的編碼和譯碼系統(tǒng)。比如，再利用電報進行通訊時，需要將文字轉換成由二進制的字符組成的字符串。比如需傳送的電文為“A B A C C

3、 D A”假設將A,B,C,D分別編碼為00、01、10、11.則上述電文遍為00010010101100，總長度為14位。但是在傳送過程中，總希望長度能夠盡可能的短，于是我們想采用長度不等的編碼。但是這種編碼必須遵循：任何一個字符的編碼都不是另一個字符編碼的前綴。對此軟件的要求：能夠正確的使得對于輸入的字符進行編碼以及譯碼，并且是的在譯碼過程中不會出錯，同時能夠?qū)⒕幋a以及譯碼的結果正確的存入文件當中。3 概要設計31抽象數(shù)據(jù)類型定義ADT BinaryTree數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,.,n, n0數(shù)據(jù)關系：若D為空集，則稱為空樹。若D僅為一個數(shù)據(jù)元素，則R為空集，

4、否則R=H，H是如下的二元關系： （1）再D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關系H下無前驅(qū)。 （2）若D-root<>空集，則存在一個劃分D1，D2，···，Dm（m>0）。 （3）對應于D-root的劃分，H-<root，X1，···，<root，Xm> 有唯一的一個劃分H1，H2，···，Hm（m>0）?；静僮鳎篒nitTree(&T)操作結果：構造空樹T。DestroyTree(&T)初始條件：樹T已存在。操作結果：樹T被銷毀。C

5、learTree(&T)初始條件：樹T已存在。操作結果：將樹T清為空棧。TreeEmpty(T)初始條件：樹T已存在。操作結果：若樹T為空，則返回TRUE，否則FALSE。TreeDepth(T)初始條件:樹T已存在。操作結果：返回T的深度。Root（T）初始條件：樹T已存在。操作結果：返回樹T的根。32總體框圖以及功能描述4 詳細設計41數(shù)據(jù)類型的定義（1）哈夫曼樹節(jié)點類型 struct hufmtreenode /哈弗曼樹結點數(shù)據(jù)類型 char data; float weight; /結點權值 int parent,lchild,rchild; /父結點，左、右孩子結點 ;（2）

6、哈夫曼樹類型 struct hufmtree /哈弗曼樹數(shù)據(jù)類型 hufmtreenode *node; /結點數(shù)組（根據(jù)n的值動態(tài)分配） int n; /葉子結點數(shù);（3)哈夫曼編碼數(shù)據(jù)類型 struct Codetype /哈弗曼編碼數(shù)據(jù)類型 char *bits; /編碼流數(shù)組， int start;/編碼實際在編碼流數(shù)組里的開始位置42主要模塊的算法描述（1) 主函數(shù)： void main() printf("哈夫曼編碼譯碼系統(tǒng)n"); tree=CreateHuffmanTreeFromSourceFile();/讀取文件建立哈樹tree=CreateHuffma

7、nTreeByInput(); /手動輸入建立哈夫曼樹HuffmanCode(tree); /打印字符集的哈夫曼編碼tree=Encoding(tree); /對文本文件編碼Decoding(tree); /對代碼文件譯碼 （2）構造哈夫曼樹 hufmtree* BuildHuffmanTree(hufmtree *tree)/構建葉子結點已初始化的哈夫曼樹For(p=HT,i=1;i<=n;+i,+p,+w) *p=0,0,0,0; For(;i<=m;+i,+p) *p=0,0,0,0); For(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2);

8、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) start=n-1; for(c=i;f=HTi.parent;f!=0;c=f,f =HTf.par

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

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

11、相結合起來，從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。在設計的過程中遇到問題，這畢竟獨立做的，難免會遇到過各種各樣的問題，同時在設計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學過的知識理解得不夠深刻，掌握得不夠牢固，比如說結構體通過這次課程設計之后，一定把以前所學過的知識重新溫故。這次課程設計終于順利完成了，在設計中遇到了很多編程問題，最后在謝老師的辛勤指導下，終于游逆而解。同時，在李玉蓉老師的軟件工程導論課上我學得到很多實用的知識，在次我表示感謝！同時，對給過我?guī)椭乃型瑢W和各位指導老師再次表示忠心的感謝！附錄（源程序清單）#include <st

12、dio.h>#include <conio.h>#include <stdlib.h>#define MAXVAL 10000.0struct hufmtreenode/哈弗曼樹結點數(shù)據(jù)類型char data;double weight;/結點權值int parent,lchild,rchild;/父結點，左、右孩子結點;struct hufmtree/哈弗曼樹數(shù)據(jù)類型hufmtreenode *node;/結點數(shù)組（根據(jù)n的值動態(tài)分配）int n;/葉子結點數(shù);struct Codetype/哈弗曼編碼數(shù)據(jù)類型char *bits;/編碼流數(shù)組，n為為哈夫曼樹中

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

14、;nodei=tree->nodek;tree->nodek=temp;Codetype* HuffmanCode(hufmtree *tree)/哈弗曼編碼的生成int i,j,p,k;Codetype *code;if (tree=NULL)return NULL;code=(Codetype*)malloc(tree->n*sizeof(Codetype);for (i=0;i<tree->n;i+)printf("%c ",tree->nodei.data);/打印字符信息codei.bits=(char*)malloc(tree

15、->n*sizeof(char);codei.start=tree->n-1;j=i;p=tree->nodei.parent;while(p!=-1)if (tree->nodep.lchild=j)codei.bitscodei.start='0'elsecodei.bitscodei.start='1'codei.start-;j=p;p=tree->nodep.parent;for (k=codei.start+1;k<tree->n;k+)/打印字符編碼printf("%c",codei.b

16、itsk);printf("n");return code;hufmtree* BuildHuffmanTree(hufmtree *tree)/構建葉子結點已初始化的哈夫曼樹/tree中所有葉子結點已初始化int i,j,p1,p2,m;float small1,small2;m=2*(tree->n)-1;for (i=tree->n;i<m;i+)/初始化所有非葉子結點tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;tree->nodei.we

17、ight=0.0;for (i=tree->n;i<m;i+)/構建哈夫曼樹small1=small2=MAXVAL;for (j=0;j<=i-1;j+)if (tree->nodej.parent=-1 && tree->nodej.weight<=small1)small1=tree->nodej.weight;p1=j;for (j=0;j<=i-1;j+)if (tree->nodej.parent=-1 && tree->nodej.weight<=small2 &&

18、(j!=p1)small2=tree->nodej.weight;p2=j;tree->nodep1.parent=tree->nodep2.parent=i;tree->nodei.weight=tree->nodep1.weight+tree->nodep2.weight;tree->nodei.lchild=p1;tree->nodei.rchild=p2;return tree;hufmtree* CreateHuffmanTreeFromSourceFile()/通過解析源文件建立哈夫曼樹FILE *textfile,*datafile

19、;char ch,sourcefilename100;int i,j=0,n=0;float count128; /用于統(tǒng)計字符在源文件中出現(xiàn)的次數(shù)，27表示26個英文字母和1個空格字符hufmtree *tree;/打開一個源文件printf("n請輸入源文件所在路徑:n");scanf("%s",sourcefilename);if (textfile=fopen(sourcefilename,"r")=NULL)printf("n找不到文件%sn",sourcefilename);return NULL;fo

20、r(i=0;i<128;i+)counti=0;/對源文件中各字符的個數(shù)統(tǒng)計ch=fgetc(textfile);while(!feof(textfile)for(i=0;i<128;i+)if (ch=char(i)counti+;break;ch=fgetc(textfile);/將統(tǒng)計結果寫入權值信息文件data.txt中，并構建哈夫曼樹datafile=fopen("f:data.txt","w");for (i=0;i<128;i+)if (counti!=0)n+;fprintf(datafile,"%dn&quo

21、t;,n);tree=(hufmtree*)malloc(sizeof(hufmtree); tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;printf("n源文件的字符集及其權值信息如下：n");for(i=0;i<128;i+)if (counti!=0)/fprintf(datafile,"%c%fn",char(i),counti); fprintf(datafile,"%c %.0fn",char(i),coun

22、ti); printf("%c %.0fn",char(i),counti);tree->nodej.data=char(i);tree->nodej.weight=counti;tree->nodej.parent=-1;tree->nodej.lchild=-1;tree->nodej.rchild=-1;j+;SortHufmtree(tree);BuildHuffmanTree(tree);fclose(textfile);fclose(datafile);printf("n哈夫曼樹建立完畢，已將權值信息保存至data.txt

23、n");return tree;hufmtree* CreateHuffmanTreeByInput()/通過用戶輸入建立哈夫曼樹int n;hufmtree *tree;int i,m;FILE *datafile;tree=(hufmtree*)malloc(sizeof(hufmtree);datafile=fopen("f:data.txt","w");/由用戶輸入字符與權值信息并將其寫入data.txt，同時進行哈夫曼樹初始化printf("請輸入字符數(shù)：");scanf("%d",&n

24、);if (n<=0)printf("n您的輸入有誤。n");return NULL;tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;m=2*n-1;for (i=0;i<n;i+)tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;tree->nodei.weight=0.0;fprintf(datafile,"%dn",n);for

25、 (i=0;i<n;i+)printf("n輸入第%d個字符及其權值：",i+1);tree->nodei.data=getche();tree->nodei.weight=getche();fprintf(datafile,"%c,%.0fn",tree->nodei.data,tree->nodei.weight-48);fclose(datafile);/哈夫曼樹構建SortHufmtree(tree);BuildHuffmanTree(tree);printf("n哈夫曼樹建立完畢，已將權值信息保存至dat

26、a.txtn");return tree;hufmtree* CreateHuffmanTreeFromDataFile()/通過讀取權值信息文件建立哈夫曼樹FILE *datafile;int i,n;hufmtree *tree;if (datafile=fopen("f:data.txt","r")=NULL)printf("n哈夫曼樹尚未建立n");return NULL;/哈夫曼樹初始化fscanf(datafile,"%d",&n);fgetc(datafile);tree=(hufm

27、tree*)malloc(sizeof(hufmtree);tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;for (i=0;i<n;i+)tree->nodei.data=fgetc(datafile);fscanf(datafile,"%fn",&tree->nodei.weight);tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;fcl

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

29、ULL)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&

30、quot;,ch);ch=fgetc(textfile);/編碼printf("n字符集的哈夫曼編碼如下：n");code=HuffmanCode(tree);/將源文件中各字符編碼并寫入codefilecodefile=fopen("f:CodeFile.txt","w");fseek(textfile,0,SEEK_SET);ch=fgetc(textfile);while (!feof(textfile)for(i=0;i<tree->n;i+)if (ch=tree->nodei.data)for(j=cod

31、ei.start+1;j<tree->n;j+)fputc(codei.bitsj,codefile);break;if (i=tree->n)/在哈夫曼樹樹中找不到與文本內(nèi)容里對應的字符printf("n字符%c不在哈夫曼樹中，不能正確編碼。n",ch);fclose(codefile);return NULL;ch=fgetc(textfile);fclose(codefile);/提示成功信息并打印代碼printf("n編碼成功,已將代碼寫入CodeFile.txt,代碼如下：n");codefile=fopen("f:

32、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(hufmtree *tree)/對編碼文件進行譯碼并將其輸出至新文件FILE *codefile,*decodefile;char ch,codefilename100;int i;if (tree

33、=NULL)/如果尚未建立哈夫曼樹/試從data.txt中讀取權值信息并建立哈夫曼樹tree=CreateHuffmanTreeFromDataFile();if (tree=NULL)return ;/打開編碼文件printf("n請輸入代碼文件所在路徑:n");scanf("%s",codefilename);if (codefile=fopen(codefilename,"r")=NULL)printf("n找不到文件%sn",codefilename);return;/打印編碼文件的正文printf(&qu

34、ot;n代碼文件原文如下：n");ch=fgetc(codefile);while(!feof(codefile)printf("%c",ch);ch=fgetc(codefile);/進行譯碼并將譯文寫入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&

35、gt;=0 && tree->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)/在哈夫曼樹中找不到對應葉子結點printf("n編碼與當前哈夫曼樹結構不相符，不能正確譯碼。n",ch);fclose(decodef

36、ile);return;ch=fgetc(codefile);if (tree->nodei.lchild>=0 && tree->nodei.rchild>=0)/尋找葉子結點的過程中突然讀到了文件尾printf("n代碼文件編碼內(nèi)容不完整，不能完整譯碼。n",ch);fclose(decodefile);return;fputc(tree->nodei.data,decodefile);fclose(decodefile);/提示成功信息并打印譯文printf("nn譯碼成功，譯文已保存至DecodeFile.txtn&qu