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

1、計算機與信息工程系實踐環(huán)節(jié)名稱報告專業(yè)：計算機科學(xué)與技術(shù)班級： *學(xué)號： *姓名：楊明英報告完成日期：2011/6/10指導(dǎo)教師： *評語：成績：批閱教師簽名：批閱時間：目錄1問題描述12 基本要求13數(shù)據(jù)結(jié)構(gòu)14總體設(shè)計15詳細設(shè)計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測試與調(diào)試117源程序清單88 實驗心得281. 問題描述打開一篇英文文章，統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，設(shè)計一個哈夫曼編 / 譯碼系統(tǒng) 。2.基本要求以每個字符出現(xiàn)的次數(shù)為權(quán)值，建立哈夫曼樹，求出哈夫曼編碼，對文件yuanwen中的正文進行編碼，將結(jié)果存到文件yiwen 中，再對文件 yiwen 中的代碼進行譯碼，結(jié)果存到 textfile中。3.數(shù)據(jù)結(jié)構(gòu)charCHN;/記錄原文字符數(shù)組charYWN;/ 記錄譯文字符數(shù)組typedef char * Hcodem+1; / 存放哈夫曼字符編碼串的頭指針的數(shù)組 typedef

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

4、儲原文的文件 yuanwenvoid luruyuanwen()/通過程序錄入原文到文件yuanwen 中void min_2(hn ht,int n,int *tag1,int *tag2)/選擇權(quán)值較小的兩個結(jié)點void chuangjian(jilunode * jilu,hn ht)/建立哈夫曼樹void bianma(jilunode * jilu,hn ht,Hcode hc,int 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. 詳細設(shè)計5.1 主函數(shù)void main()開始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()首先，要建立一個文件來存儲原文，在這里文件的名稱按要求默認為 yuanwen，文件建立時有可能成功，有可能失敗，建立失敗時輸出“ Cannot open file ”，成功后會提示：“文件已建立，名稱為 yuanwen”。開始printf( 現(xiàn)在建立文件，以存儲原文（文件名稱默認為“ yuanwen”）n);N(fp=fopen(yuanwen,wb)=NULLYprintf(Cannot open filen);printf( 文件已建立 ,名稱為： yuanwen);結(jié)束35.3 輸入原文void luruyuan

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

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

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

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

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

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

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

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

16、t,int n,int *tag1,int *tag2)/在建哈夫曼樹的過程中，選擇權(quán)值小的兩個結(jié)點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é)點下標(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é)點權(quán)值相

17、同，先出現(xiàn)的放在哈夫曼樹的左邊(*tag1)=(*tag2);(*tag2)=s;void chuangjian(jilunode * jilu,hn ht)/建立哈夫曼樹、以及對原文字符的類別和數(shù)量統(tǒng)計int i,j,s,tag1,tag2;s=0;i=-1;char ch;FILE *fp;if(fp=fopen(yuanwen,rb)=NULL)/以只讀的方式打開文件19printf(Cannot open filen);exit(0);while(!feof(fp)/判斷文件指示標(biāo)志是否移動到了文件尾處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)計狀況如下： n); printf(*n); for(i=1;itag;i+)s+;printf(%c的個數(shù)為 :%d,jilu-bi.a,jilu-bi.num);if(s%4=0)/每行放四個數(shù)據(jù)printf(n);printf(n);

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

20、為0的結(jié)點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)/哈夫曼樹建完后，對葉子結(jié)點逐個編碼char * cd;int start,i,p,c;cd=(char *)malloc(n+1)*sizeof(char);/申請存儲字符的臨時空間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);/將臨時空間中的編碼復(fù)制到字符數(shù)組中21free(cd);/釋放臨時空間void bianmabaocun(Hcode hc,jilunode * jilu)/將原文以編碼的形式保存到文件 yiwen 中int i,j;FILE *fp;if(fp=fopen(yiwen,wb)=NULL)/以寫的方式打開文件printf(Cannot open filen);exit(0);/文件打開失敗退出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)/以只讀的方式打開文件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);/釋放臨時字符存儲空間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)/以只讀的方式打開文件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)/以只讀的方式打開文件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;/定義用三叉鏈表方式實現(xiàn)的哈夫曼樹Hcode hc;/定義存放哈夫曼字符編碼串的頭指針的數(shù)組jilunode ji;/定義存放字符種類數(shù)量的棧jilunode *jilu;jilu=&ji;/取指針jilu-tag=0;/字符種類數(shù)標(biāo)志初始化while

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

28、nliwenjian();/建立存儲字符的文件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 注意：原文件將保存在名稱為“ 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)建哈夫曼樹printf(n各字符編碼結(jié)果為： n);bianma(jilu,humtree,hc,jilu-tag);/對哈夫曼樹的葉子結(jié)點編碼printf(原文的編碼為： n);printf(* *n);bianmabaocun(hc,jilu);/保存編碼printf(n*n);printf(n注意：原文的編碼將保存在以名稱為“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(編碼對應(yīng)的譯文為： n);yiwen(hc,jilu);/對編碼譯碼baocunyiwen();/保存譯文printf(n注意：譯文將保存在以名稱為“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();/