完整word版,《哈夫曼編碼譯碼課程設(shè)計(jì)》報(bào)告

1、計(jì)算機(jī)與信息工程系實(shí)踐環(huán)節(jié)名稱(chēng)報(bào)告專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)： *學(xué)號(hào)： *姓名：楊明英報(bào)告完成日期：2011/6/10指導(dǎo)教師： *評(píng)語(yǔ)：成績(jī)：批閱教師簽名：批閱時(shí)間：目錄1問(wèn)題描述12 基本要求13數(shù)據(jù)結(jié)構(gòu)14總體設(shè)計(jì)15詳細(xì)設(shè)計(jì)25.1void main()25.2void jianliwenjian()35.3void luruyuanwen()45.4void chuangjian()55.5void bianma()65.6void yiwen()75.7void baocunyiwen()85.8void duquyuanwen()95.9void duqubianma()105

2、.10void duquyiwen()116測(cè)試與調(diào)試117源程序清單88 實(shí)驗(yàn)心得281. 問(wèn)題描述打開(kāi)一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，設(shè)計(jì)一個(gè)哈夫曼編 / 譯碼系統(tǒng) 。2.基本要求以每個(gè)字符出現(xiàn)的次數(shù)為權(quán)值，建立哈夫曼樹(shù)，求出哈夫曼編碼，對(duì)文件yuanwen中的正文進(jìn)行編碼，將結(jié)果存到文件yiwen 中，再對(duì)文件 yiwen 中的代碼進(jìn)行譯碼，結(jié)果存到 textfile中。3.數(shù)據(jù)結(jié)構(gòu)charCHN;/記錄原文字符數(shù)組charYWN;/ 記錄譯文字符數(shù)組typedef char * Hcodem+1; / 存放哈夫曼字符編碼串的頭指針的數(shù)組 typedef

3、 structchar a;int num;dangenode;/ 記錄單個(gè)字符的類(lèi)別和出現(xiàn)的次數(shù)typedef structdangenode bm;int tag;jilunode;/ 統(tǒng)計(jì)原文出現(xiàn)的字符種類(lèi)和數(shù)量typedef struct node/ 靜態(tài)三叉的哈夫曼樹(shù)的定義intweight;/結(jié)點(diǎn)的權(quán)值intparent;/雙親的下標(biāo)intLchild;/左孩子結(jié)點(diǎn)的下標(biāo)intRchild;/ 右孩子結(jié)點(diǎn)的下標(biāo)htnode,hnM+1;/ hn 是結(jié)構(gòu)數(shù)組類(lèi)型，0 號(hào)單元不用4. 總體設(shè)計(jì)功能函數(shù)模塊劃分void main()/主函數(shù)void jianliwenjian()/建立存

4、儲(chǔ)原文的文件 yuanwenvoid luruyuanwen()/通過(guò)程序錄入原文到文件yuanwen 中void min_2(hn ht,int n,int *tag1,int *tag2)/選擇權(quán)值較小的兩個(gè)結(jié)點(diǎn)void chuangjian(jilunode * jilu,hn ht)/建立哈夫曼樹(shù)void bianma(jilunode * jilu,hn ht,Hcode hc,int n)/ 對(duì)原文進(jìn)行編碼void bianmabaocun(Hcode hc,jilunode * jilu)/保存編碼在文件 yiwen 中void yiwen(Hcode hc,jilunode *

5、 jilu)/ 讀取 yiwen 中的編碼，并將其翻譯為原文void baocunyiwen()/將翻譯的譯文保存到文件textfile 中void duqubianma()/在編碼文件 yiwen 中讀取編碼void duquyiwen()/從文件 textfile 中讀取譯文15. 詳細(xì)設(shè)計(jì)5.1 主函數(shù)void main()開(kāi)始Int tep=1;Ntep=1YNa=1YYNjianliwenjian();a=2NYa=3N luruyuanwen();Yc=1chuangjian(jilNNYu,humtree);a=4c=1tep=0;Ybianma(jilu,hYNtep=0; u

6、mtree,hc,jilua=5system(cls);yiwen(hc-tag);,jilu);YNsystem(cls);Bianmabaocduquyuanwen();a=6break;un(hc,jiolu); baocunyiwen();YNbreak;NNNduqubianma();a=7c=1c=1Yc=1Ytep=0; Ytep=0;YNduquyiwen();c=1Nsystem(cls);tep=0;a=8system(cls);YNtep=0; c=1break;system(cls);Ybreak;Ytep=0;break;system(cls);break;syste

7、m(cls);結(jié)束25.2 建立文件void jianliwenjian()首先，要建立一個(gè)文件來(lái)存儲(chǔ)原文，在這里文件的名稱(chēng)按要求默認(rèn)為 yuanwen，文件建立時(shí)有可能成功，有可能失敗，建立失敗時(shí)輸出“ Cannot open file ”，成功后會(huì)提示：“文件已建立，名稱(chēng)為 yuanwen”。開(kāi)始printf( 現(xiàn)在建立文件，以存儲(chǔ)原文（文件名稱(chēng)默認(rèn)為“ yuanwen”）n);N(fp=fopen(yuanwen,wb)=NULLYprintf(Cannot open filen);printf( 文件已建立 ,名稱(chēng)為： yuanwen);結(jié)束35.3 輸入原文void luruyuan

8、wen()輸入原文時(shí)首先要打開(kāi)原文件，成功打開(kāi)文件后逐個(gè)讀取輸入的字符存放到文件中，直到遇到結(jié)束標(biāo)志 ，然后關(guān)閉文件。開(kāi)始charch;(fp=fopen(yuanwen,wb)=NULLNYprintf(Cannot open filen);printf( 請(qǐng)輸入原文（結(jié)束標(biāo)志為： “ ”）n);ch=getchar();fputc(ch,fp)Ych!=Ngetchar();結(jié)束45.4 創(chuàng)建哈夫曼樹(shù)void chuangjian()打開(kāi)存儲(chǔ)原文的文件 yuanwen，將字符逐個(gè)讀出，然后統(tǒng)計(jì)字符的種類(lèi)，類(lèi)別和數(shù)量，最后建立靜態(tài)的三叉鏈表來(lái)建立哈夫曼樹(shù)，樹(shù)中的葉子結(jié)點(diǎn)對(duì)應(yīng)出現(xiàn)的個(gè)字符。開(kāi)始

9、N打開(kāi)文件 yuanwenYN文件未結(jié)束Y將文件中的字符逐個(gè)賦給數(shù)組CHi用棧 jilunode記錄字符的種類(lèi)、類(lèi)別及數(shù)量關(guān)閉文件輸出統(tǒng)計(jì)結(jié)果建立哈夫曼樹(shù)結(jié)束55.5 編碼void bianma()該函數(shù)實(shí)現(xiàn)對(duì)哈夫曼樹(shù)的編碼，先申請(qǐng)一個(gè)能存儲(chǔ)字符編碼的臨時(shí)空間 cd，編碼從哈夫曼樹(shù)的葉子結(jié)點(diǎn)開(kāi)始，尋找其父母結(jié)點(diǎn)，然后根據(jù)父母結(jié)點(diǎn)判斷孩子結(jié)點(diǎn)的左右位置，左邊置 1，右邊置 0，并將 1,0 這樣的字符從后往前逆序存放在 cd 中，每求得一個(gè)葉子結(jié)點(diǎn)的編碼，就將其復(fù)制到存儲(chǔ)哈夫曼編碼的頭指正數(shù)組中，找完葉子結(jié)點(diǎn)的編碼后就釋放臨時(shí)空間cd。開(kāi)始申請(qǐng)存放編碼的字符空間cdN葉子結(jié)點(diǎn)的父母不為0Y對(duì)哈夫

10、曼樹(shù)的葉子結(jié)點(diǎn)編碼將葉子結(jié)點(diǎn)的編碼存放在cd中將 cd中存放的編碼復(fù)制到存儲(chǔ)哈夫曼編碼的頭指針數(shù)組中釋放 cd的空間結(jié)束65.6 對(duì)哈夫曼碼譯碼void yiwen()打開(kāi)文件 yiwen，打開(kāi)成功后，逐個(gè)讀取存放在里邊的編碼字符，并與先前的編碼相匹配，直到找到編碼對(duì)應(yīng)的原字符，當(dāng)找完編碼后就關(guān)閉文件。開(kāi)始N打開(kāi)文件 yiwenYN文件未結(jié)束Y讀取文件 yiwen 中的字符逐個(gè)讀取字符后，將其與先前的編碼相匹配N(xiāo)匹配成功Y將匹配的結(jié)果（即譯文）保存到數(shù)組Yw中關(guān)閉文件結(jié)束75.7 保存譯文void baocunyiwen()打開(kāi)文件 textfile ，打開(kāi)成功后，將譯文保存到文件中，然后關(guān)閉

11、文件。開(kāi)始N打開(kāi)文件 textfileY將譯文保存到textfile文件中關(guān)閉文件結(jié)束85.8 輸出原文void duquyuanwen()打開(kāi)文件 yuanwen，將里邊的原文輸出，以便查看。開(kāi)始N打開(kāi)文件 yuanwenY輸出文件中的原文關(guān)閉文件結(jié)束95.9 輸出原文編碼void duqubianma()打開(kāi)文件 yiwen ，打開(kāi)成功后，將文件中存放的編碼輸出，然后關(guān)閉文件。開(kāi)始N打開(kāi)文件 yiwenY輸出文件中的編碼關(guān)閉文件結(jié)束105.10 輸出譯文void duquyiwen()打開(kāi)文件 textfile ，打開(kāi)成功后，輸出里邊的譯文，然后關(guān)閉文件。開(kāi)始N打開(kāi)文件 textfileY

12、輸出文件中的譯文關(guān)閉文件結(jié)束116. 測(cè)試與調(diào)試程序調(diào)試采用 Microsoft Visual Studio2008，程序在調(diào)試過(guò)程中遇到了各種問(wèn)題，首先在建立哈夫曼樹(shù)時(shí)我是用靜態(tài)三叉鏈表實(shí)現(xiàn)的，但里邊的參數(shù) parent， Lchild ，Rchild 定義為指針類(lèi)型，在原理上是可行，但調(diào)試時(shí)總得不到正確結(jié)果，后來(lái)改為書(shū)中用基本類(lèi)型整型后就很好的得到了滿意結(jié)果，其它一些小錯(cuò)誤在不斷地調(diào)試，不斷地改善后，基本達(dá)到可滿意的效果。各模塊的調(diào)試結(jié)果截屏如下：6.1 主函數(shù)菜單6.2 建立文件6.3 通過(guò)程序輸入原文126.4 直接將原文存放到文件yuawen 中6.5 對(duì)原文編碼1314156.6

13、對(duì)編碼譯碼6.7 輸出原文166.8 輸出編碼6.9 輸出譯文177. 源程序清單#include#include#include#define N 5000#define m 128/葉子結(jié)點(diǎn)個(gè)數(shù)，即字符總類(lèi)數(shù)#define M 2*m-1 /哈夫曼樹(shù)的節(jié)點(diǎn)數(shù)char CHN;/記錄原文字符數(shù)組char YWN;/記錄譯文字符數(shù)組typedef char * Hcodem+1; / 存放哈夫曼字符編碼串的頭指針的數(shù)組 typedef structchar a;int num;dangenode; / 記錄單個(gè)字符的類(lèi)別和出現(xiàn)的次數(shù) typedef structdangenode b129;i

14、nt tag;jilunode;/統(tǒng)計(jì)原文出現(xiàn)的字符種類(lèi)數(shù)typedef struct nodeint weight;/結(jié)點(diǎn)權(quán)值int parent;/雙親下標(biāo)int Lchild;/左孩子結(jié)點(diǎn)的下標(biāo)int Rchild;/右孩子的下標(biāo)htnode,hnM;/靜態(tài)三叉的哈夫曼樹(shù)的定義void jianliwenjian()printf(現(xiàn)在建立文件，以存儲(chǔ)原文（文件名稱(chēng)默認(rèn)為“yuanwen”） n);printf(文件建立中 .n);FILE *fp;if(fp=fopen(yuanwen,wb)=NULL)/建立文件printf(Cannot open filen);exit(0);pri

15、ntf(文件已建立 , 名稱(chēng)為： yuanwen);fclose(fp);/關(guān)閉文件void luruyuanwen()/原文輸入完后，將其保存到文件yuanwen中char ch;FILE *fp;if(fp=fopen(yuanwen,wb)=NULL)/打開(kāi)文件18printf(Cannot open filen);exit(0);printf(請(qǐng)輸入原文（結(jié)束標(biāo)志為：“”） n);doch=getchar();fputc(ch,fp);/將字符保存到文件中while(ch!=);/判斷結(jié)束getchar();/接收回車(chē)命令符fclose(fp);/關(guān)閉文件void min_2(hn h

16、t,int n,int *tag1,int *tag2)/在建哈夫曼樹(shù)的過(guò)程中，選擇權(quán)值小的兩個(gè)結(jié)點(diǎn)int i,min,s;min=N;for(i=1;i=n;i+)if(hti.weightmin&hti.parent=0)min=hti.weight;*tag1=i;/記錄權(quán)值最小的結(jié)點(diǎn)下標(biāo)min=N;for(i=1;i=n;i+)if(hti.weightmin&hti.parent=0&i!=*tag1)min=hti.weight;*tag2=i;if(ht*tag1.weight=ht*tag2.weight&ht*tag2.Lchild!=0)s=(*tag1);/如果結(jié)點(diǎn)權(quán)值相

17、同，先出現(xiàn)的放在哈夫曼樹(shù)的左邊(*tag1)=(*tag2);(*tag2)=s;void chuangjian(jilunode * jilu,hn ht)/建立哈夫曼樹(shù)、以及對(duì)原文字符的類(lèi)別和數(shù)量統(tǒng)計(jì)int i,j,s,tag1,tag2;s=0;i=-1;char ch;FILE *fp;if(fp=fopen(yuanwen,rb)=NULL)/以只讀的方式打開(kāi)文件19printf(Cannot open filen);exit(0);while(!feof(fp)/判斷文件指示標(biāo)志是否移動(dòng)到了文件尾處ch=fgetc(fp);if(ch!=)/判斷字符是否是結(jié)束標(biāo)志+i;CHi=ch

18、;for(j=1;jtag;j+)if(CHi=jilu-bj.a)jilu-bj.num+;break;if(j-1=jilu-tag&CHi!=jilu-bj-1.a)jilu-tag+;jilu-bjilu-tag.a=CHi;jilu-bjilu-tag.num=1;jilu-tag-;fclose(fp);/關(guān)閉文件printf( 原文中的各字符統(tǒng)計(jì)狀況如下： n); printf(*n); for(i=1;itag;i+)s+;printf(%c的個(gè)數(shù)為 :%d,jilu-bi.a,jilu-bi.num);if(s%4=0)/每行放四個(gè)數(shù)據(jù)printf(n);printf(n);

19、for(i=1;itag)-1;i+)if(itag)hti.weight=jilu-bi.num; /初始化葉子結(jié)點(diǎn)權(quán)值hti.Lchild=0;/初始化葉子結(jié)點(diǎn)左孩子20hti.parent=0;/初始化葉子結(jié)點(diǎn)父母hti.Rchild=0;/初始化葉子結(jié)點(diǎn)右孩子elsehti.Lchild=0;/初始化非葉子結(jié)點(diǎn)左孩子hti.parent=0;/初始化非葉子結(jié)點(diǎn)父母hti.Rchild=0;/初始化非葉子結(jié)點(diǎn)右孩子hti.weight=0;/初始化非葉子結(jié)點(diǎn)權(quán)值for(i=jilu-tag+1;itag)-1;i+)min_2(ht,i-1,&tag1,&tag2);需找權(quán)值小的兩個(gè)父母

20、為0的結(jié)點(diǎn)httag1.parent=i;httag2.parent=i;hti.Lchild=tag1;hti.Rchild=tag2;hti.weight=httag1.weight+httag2.weight;void bianma(jilunode * jilu,hn ht,Hcode hc,int n)/哈夫曼樹(shù)建完后，對(duì)葉子結(jié)點(diǎn)逐個(gè)編碼char * cd;int start,i,p,c;cd=(char *)malloc(n+1)*sizeof(char);/申請(qǐng)存儲(chǔ)字符的臨時(shí)空間cdn-1=0;/加結(jié)束標(biāo)志for(i=1;ibi.a,&cdstart);hci=(char *)m

21、alloc(n-start)*sizeof(char); /為字符數(shù)組分配空間strcpy(hci,&cdstart);/將臨時(shí)空間中的編碼復(fù)制到字符數(shù)組中21free(cd);/釋放臨時(shí)空間void bianmabaocun(Hcode hc,jilunode * jilu)/將原文以編碼的形式保存到文件 yiwen 中int i,j;FILE *fp;if(fp=fopen(yiwen,wb)=NULL)/以寫(xiě)的方式打開(kāi)文件printf(Cannot open filen);exit(0);/文件打開(kāi)失敗退出for(i=0;i=N&CHi!=;i+)for(j=1;jtag;j+)if(C

22、Hi=jilu-bj.a)fputs(hcj,fp);/將文件中的字符輸出到字符數(shù)組中printf(%s,hcj);fclose(fp);/關(guān)閉文件void yiwen(Hcode hc,jilunode * jilu)/讀取 yiwen 中的編碼，并將其翻譯為原文存放到字符數(shù)組 YWN中int tag1,tag2,i,j,s=0;FILE *fp;/文件指針char *c;if(fp=fopen(yiwen,rb)=NULL)/以只讀的方式打開(kāi)文件printf(cannot open filen);exit(0);while(!feof(fp)tag1=1;/結(jié)束 for 循環(huán)的輔助標(biāo)志ta

23、g2=1;/結(jié)束 for 循環(huán)的輔助標(biāo)志c=(char *)malloc(200*sizeof(char);for(i=0;i200&tag1;i+)ci=fgetc(fp);/將文件中的字符輸出到數(shù)組中ci+1=0;/加結(jié)束標(biāo)志for(j=1;(jtag)&tag2;j+)if(strcmp(hcj,c)=0)/將編碼與原文字符匹配YWs=jilu-bj.a;/匹配成功后將字符保存到數(shù)組YW中22tag1=0;s+;free(c);/釋放臨時(shí)字符存儲(chǔ)空間tag2=0;YWs=0;void baocunyiwen()/將翻譯的譯文保存到文件textfile中int i;FILE *fp;if(

24、fp=fopen(textfile,wb)=NULL)printf(Cannot open filen);exit(0);for(i=0;YWi!=0;i+)fputc(YWi,fp);/將數(shù)組中的字符保存到文件中putchar(YWi);fclose(fp);/關(guān)閉文件void duquyiwen()/從文件 textfile中讀取譯文char ch;FILE *fp;if(fp=fopen(textfile,rb)=NULL)/以只讀的方式打開(kāi)文件printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp);/將文件中的字符賦給

25、字符變量chprintf(%c,ch);/輸出字符fclose(fp);/關(guān)閉文件void duquyuanwen()/從文件 yuanwen中讀取原文char ch;23FILE *fp;if(fp=fopen(yuanwen,rb)=NULL)/以只讀的方式打開(kāi)文件printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp);/將文件中的字符賦給字符變量chprintf(%c,ch);/輸出字符fclose(fp);/關(guān)閉文件void duqubianma()/從文件 yiwen 中讀取原文char ch;FILE *fp;if

26、(fp=fopen(yiwen,rb)=NULL)printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp);/將文件中的字符賦給字符變量chprintf(%c,ch);/輸出字符fclose(fp);/關(guān)閉文件void main()int a,c,tep=1;hn humtree;/定義用三叉鏈表方式實(shí)現(xiàn)的哈夫曼樹(shù)Hcode hc;/定義存放哈夫曼字符編碼串的頭指針的數(shù)組jilunode ji;/定義存放字符種類(lèi)數(shù)量的棧jilunode *jilu;jilu=&ji;/取指針jilu-tag=0;/字符種類(lèi)數(shù)標(biāo)志初始化while

27、(tep)printf( (*_*) 哈夫曼編碼系統(tǒng)歡迎您 (*_*) n); printf(*n);printf(1創(chuàng)建存貯原文件的文件n);printf(2輸入原文 n);printf(3對(duì)原文編碼 n);printf(4對(duì)編碼譯碼 n);24printf(5輸出原文 n);printf(6輸出譯碼 n);printf(7輸出譯文 n);printf(8退出 n);printf(注意：如果您未創(chuàng)建原文件原文操作，請(qǐng)不要進(jìn)行后續(xù)項(xiàng)操作！n);printf(*n);printf(請(qǐng)輸入服務(wù)選項(xiàng)（ -8 ）:);scanf(%d,&a);getchar();switch(a)case 1:jia

28、nliwenjian();/建立存儲(chǔ)字符的文件printf(是否繼續(xù)？（ .YES 2 ，NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;case 2:system(cls);luruyuanwen();/將原文錄入到文件中printf(n 注意：原文件將保存在名稱(chēng)為“ yuanwen”的文件中！ n); printf( 是否繼續(xù)？（ .YES 2 ， NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;ca

29、se 3:chuangjian(jilu,humtree);/創(chuàng)建哈夫曼樹(shù)printf(n各字符編碼結(jié)果為： n);bianma(jilu,humtree,hc,jilu-tag);/對(duì)哈夫曼樹(shù)的葉子結(jié)點(diǎn)編碼printf(原文的編碼為： n);printf(* *n);bianmabaocun(hc,jilu);/保存編碼printf(n*n);printf(n注意：原文的編碼將保存在以名稱(chēng)為“yiwen ”的文件中！ n);25printf(是否繼續(xù)？（ .YES 2 ，NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;case 4:system(cls);printf(編碼對(duì)應(yīng)的譯文為： n);yiwen(hc,jilu);/對(duì)編碼譯碼baocunyiwen();/保存譯文printf(n注意：譯文將保存在以名稱(chēng)為“textfile”的文件中！ n);printf(是否繼續(xù)？（ .YES 2 ， NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;case 5:system(cls);printf(原文為： n);duquyuanwen();/