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

1、 計(jì)算機(jī)與信息工程系實(shí)踐環(huán)節(jié)名稱報(bào)告專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí)：* 學(xué)號(hào)：* 姓名：楊明英 報(bào)告完成日期 ：2011/6/10 指導(dǎo)教師：* 評(píng)語(yǔ)：成績(jī)：批閱教師簽名： 批閱時(shí)間：目錄1問(wèn)題描述1 2基本要求13數(shù)據(jù)結(jié)構(gòu)14總體設(shè)計(jì)15詳細(xì)設(shè)計(jì)25.1主函數(shù) void main() 2 5.2建立文件 void jianliwenjian()3 5.3輸入原文 void luruyuanwen()4 5.4創(chuàng)建哈夫曼樹 void chuangjian()5 5.5編碼 void bianma()6 5.6對(duì)哈夫曼碼譯碼 void yiwen()7 5.7保存譯文 void baocunyiw

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

3、ar ywn; /記錄譯文字符數(shù)組typedef char * hcodem+1; /存放哈夫曼字符編碼串的頭指針的數(shù)組typedef struct char a; int num;dangenode; /記錄單個(gè)字符的類別和出現(xiàn)的次數(shù)typedef structdangenode bm; int tag;jilunode; /統(tǒng)計(jì)原文出現(xiàn)的字符種類和數(shù)量typedef struct node /靜態(tài)三叉的哈夫曼樹的定義 int weight; /結(jié)點(diǎn)的權(quán)值 int parent; /雙親的下標(biāo) int lchild; /左孩子結(jié)點(diǎn)的下標(biāo) int rchild; /右孩子結(jié)點(diǎn)的下標(biāo)htnode

4、,hnm+1; / hn是結(jié)構(gòu)數(shù)組類型，0號(hào)單元不用4. 總體設(shè)計(jì)功能函數(shù)模塊劃分void main() /主函數(shù)void jianliwenjian() /建立存儲(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) /建立哈夫曼樹void bianma(jilunode * jilu,hn ht,hcode hc,int n) /對(duì)原文進(jìn)行編碼void b

5、ianmabaocun(hcode hc,jilunode * jilu) /保存編碼在文件yiwen中void yiwen(hcode hc,jilunode * jilu) /讀取yiwen中的編碼，并將其翻譯為原文void baocunyiwen() /將翻譯的譯文保存到文件textfile中void duqubianma() /在編碼文件yiwen中讀取編碼void duquyiwen() /從文件textfile中讀取譯文5. 詳細(xì)設(shè)計(jì)5.1 主函數(shù) void main()開始int tep=1;ntep=1ya=1nyna=2yjianliwenjian();nya=3luruyu

6、anwen();nyc=1chuangjian(jilu,humtree);na=4nc=1yytep=0;nbianma(jilu,humtree,hc,jilu-tag);hc,jilu);yyiwen(hc,jilu);tep=0;a=5system(cls);yna=6duquyuanwen();bianmabaocun(hc,jiolu);system(cls);break;ybaocunyiwen();na=7break;nnc=1c=1nc=1duqubianma();ynyyduquyiwen();c=1tep=0;tep=0;nya=8tep=0;system(cls);ny

7、c=1tep=0;system(cls);yybreak;system(cls);tep=0;system(cls);break;if yesbreak;system(cls);break;結(jié)束5.2建立文件 void jianliwenjian()首先，要建立一個(gè)文件來(lái)存儲(chǔ)原文，在這里文件的名稱按要求默認(rèn)為yuanwen，文件建立時(shí)有可能成功，有可能失敗，建立失敗時(shí)輸出“cannot open file”，成功后會(huì)提示：“文件已建立，名稱為yuanwen”。ny 5.3輸入原文 void luruyuanwen() 輸入原文時(shí)首先要打開原文件，成功打開文件后逐個(gè)讀取輸入的字符存放到文件中，直

8、到遇到結(jié)束標(biāo)志，然后關(guān)閉文件。ynny 5.4創(chuàng)建哈夫曼樹 void chuangjian() 打開存儲(chǔ)原文的文件yuanwen，將字符逐個(gè)讀出，然后統(tǒng)計(jì)字符的種類，類別和數(shù)量，最后建立靜態(tài)的三叉鏈表來(lái)建立哈夫曼樹，樹中的葉子結(jié)點(diǎn)對(duì)應(yīng)出現(xiàn)的個(gè)字符。ynyn 5.5編碼 void bianma() 該函數(shù)實(shí)現(xiàn)對(duì)哈夫曼樹的編碼，先申請(qǐng)一個(gè)能存儲(chǔ)字符編碼的臨時(shí)空間cd，編碼從哈夫曼樹的葉子結(jié)點(diǎn)開始，尋找其父母結(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)的

9、編碼后就釋放臨時(shí)空間cd。 ny 5.6對(duì)哈夫曼碼譯碼 void yiwen() 打開文件yiwen，打開成功后，逐個(gè)讀取存放在里邊的編碼字符，并與先前的編碼相匹配，直到找到編碼對(duì)應(yīng)的原字符，當(dāng)找完編碼后就關(guān)閉文件。nyynyn 5.7保存譯文 void baocunyiwen() 打開文件textfile，打開成功后，將譯文保存到文件中，然后關(guān)閉文件。 yn 5.8輸出原文 void duquyuanwen() 打開文件yuanwen，將里邊的原文輸出，以便查看。yn 5.9輸出原文編碼 void duqubianma() 打開文件yiwen，打開成功后，將文件中存放的編碼輸出，然后關(guān)閉文件

10、。 yn 5.10輸出譯文 void duquyiwen() 打開文件textfile，打開成功后，輸出里邊的譯文，然后關(guān)閉文件。 ny 6. 測(cè)試與調(diào)試程序調(diào)試采用microsoft visual studio2008，程序在調(diào)試過(guò)程中遇到了各種問(wèn)題，首先在建立哈夫曼樹時(shí)我是用靜態(tài)三叉鏈表實(shí)現(xiàn)的，但里邊的參數(shù)parent，lchild，rchild定義為指針類型，在原理上是可行，但調(diào)試時(shí)總得不到正確結(jié)果，后來(lái)改為書中用基本類型整型后就很好的得到了滿意結(jié)果，其它一些小錯(cuò)誤在不斷地調(diào)試，不斷地改善后，基本達(dá)到可滿意的效果。各模塊的調(diào)試結(jié)果截屏如下：6.1主函數(shù)菜單 6.2建立文件6.3通過(guò)程序輸

11、入原文6.4直接將原文存放到文件yuawen中6.5對(duì)原文編碼6.6對(duì)編碼譯碼6.7輸出原文6.8輸出編碼6.9輸出譯文7.源程序清單#include#include#include#define n 5000#define m 128 /葉子結(jié)點(diǎn)個(gè)數(shù)，即字符總類數(shù)#define m 2*m-1 /哈夫曼樹的節(jié)點(diǎn)數(shù) char chn; /記錄原文字符數(shù)組char ywn; /記錄譯文字符數(shù)組typedef char * hcodem+1; /存放哈夫曼字符編碼串的頭指針的數(shù)組typedef struct char a; int num;dangenode; /記錄單個(gè)字符的類別和出現(xiàn)的次數(shù)ty

12、pedef struct dangenode b129; int tag;jilunode; /統(tǒng)計(jì)原文出現(xiàn)的字符種類數(shù)typedef struct node int 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)三叉的哈夫曼樹的定義void jianliwenjian()printf(現(xiàn)在建立文件，以存儲(chǔ)原文（文件名稱默認(rèn)為“yuanwen”）n);printf( 文件建立中.n);file *fp;if(fp=fopen(yuanwen,wb)=null) /建立

13、文件printf(cannot open filen);exit(0);printf(文件已建立,名稱為：yuanwen); fclose(fp); /關(guān)閉文件void luruyuanwen() /原文輸入完后，將其保存到文件yuanwen中char ch;file *fp;if(fp=fopen(yuanwen,wb)=null) /打開文件printf(cannot open filen);exit(0); printf(請(qǐng)輸入原文（結(jié)束標(biāo)志為：“”）n); do ch=getchar(); fputc(ch,fp); /將字符保存到文件中 while(ch!=); /判斷結(jié)束 getc

14、har(); /接收回車命令符 fclose(fp); /關(guān)閉文件 void min_2(hn ht,int n,int *tag1,int *tag2)/在建哈夫曼樹的過(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*ta

15、g1.weight=ht*tag2.weight&ht*tag2.lchild!=0)s=(*tag1); /如果結(jié)點(diǎn)權(quán)值相同，先出現(xiàn)的放在哈夫曼樹的左邊(*tag1)=(*tag2);(*tag2)=s; void chuangjian(jilunode * jilu,hn ht) /建立哈夫曼樹、以及對(duì)原 文字符的類別和數(shù)量統(tǒng)計(jì) int i,j,s,tag1,tag2; s=0; i=-1; char ch; file *fp;if(fp=fopen(yuanwen,rb)=null) /以只讀的方式打開文件printf(cannot open filen);exit(0); while(

16、!feof(fp) /判斷文件指示標(biāo)志是否移動(dòng)到了文件尾處ch=fgetc(fp);if(ch!=) /判斷字符是否是結(jié)束標(biāo)志 +i; chi=ch; 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

17、+) s+; printf(%c的個(gè)數(shù)為:%d ,jilu-bi.a,jilu-bi.num); if(s%4=0) /每行放四個(gè)數(shù)據(jù) printf(n); printf(n); for(i=1;itag)-1;i+) if(itag) hti.weight=jilu-bi.num; /初始化葉子結(jié)點(diǎn)權(quán)值hti.lchild=0; /初始化葉子結(jié)點(diǎn)左孩子hti.parent=0; /初始化葉子結(jié)點(diǎn)父母hti.rchild=0; /初始化葉子結(jié)點(diǎn)右孩子 else hti.lchild=0; /初始化非葉子結(jié)點(diǎn)左孩子hti.parent=0; /初始化非葉子結(jié)點(diǎn)父母hti.rchild=0; /初

18、始化非葉子結(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è)父母為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) /哈夫曼樹建完后，對(duì)葉 子結(jié)點(diǎn)逐個(gè)編碼char * cd;int start

19、,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 *)malloc(n-start)*sizeof(char); /為字符數(shù)組分配空間strcpy(hci,&cdstart);/將臨時(shí)空間中的編碼復(fù)制到字符數(shù)組中free(cd); /釋放臨時(shí)空間void bianmabaocun(hcode hc,jilunode * jilu) /將原文以編碼的形式保存到 文件yiwen中int i,j;file *fp;if(fp=fopen(yi

20、wen,wb)=null) /以寫的方式打開文件printf(cannot open filen);exit(0); /文件打開失敗退出for(i=0;i=n&chi!=;i+) for(j=1;jtag;j+)if(chi=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 *

21、c;if(fp=fopen(yiwen,rb)=null) /以只讀的方式打開文件printf(cannot open filen);exit(0);while(!feof(fp)tag1=1; /結(jié)束for循環(huán)的輔助標(biāo)志tag2=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; /

22、匹配成功后將字符保存到數(shù)組yw中tag1=0;s+;free(c); /釋放臨時(shí)字符存儲(chǔ)空間 tag2=0;yws=0;void baocunyiwen() /將翻譯的譯文保存到文件textfile中int i;file *fp;if(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; f

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

24、(!feof(fp)ch=fgetc(fp); /將文件中的字符賦給字符變量chprintf(%c,ch); /輸出字符 fclose(fp); /關(guān)閉文件void duqubianma() /從文件yiwen中讀取原文char ch; file *fp;if(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; h

25、n humtree; /定義用三叉鏈表方式實(shí)現(xiàn)的哈夫曼樹hcode hc; /定義存放哈夫曼字符編碼串的頭指針的數(shù)組 jilunode ji; /定義存放字符種類數(shù)量的棧 jilunode *jilu; jilu=&ji; /取指針 jilu-tag=0; /字符種類數(shù)標(biāo)志初始化while(tep)printf( (*_*) 哈夫曼編碼系統(tǒng)歡迎您(*_*) n); printf(*n); printf( 1創(chuàng)建存貯原文件的文件n);printf( 2輸入原文n); printf( 3對(duì)原文編碼n);printf( 4對(duì)編碼譯碼n); printf( 5輸出原文n);printf( 6輸出譯碼n

26、); 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: jianliwenjian(); /建立存儲(chǔ)字符的文件 printf(是否繼續(xù)？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls); break;case 2: system(cls); luruyuanwen();

27、 /將原文錄入到文件中printf(n注意：原文件將保存在名稱為“yuanwen”的文件中！n);printf(是否繼續(xù)？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 3: chuangjian(jilu,humtree); /創(chuàng)建哈夫曼樹printf(n各字符編碼結(jié)果為：n); bianma(jilu,humtree,hc,jilu-tag); /對(duì)哈夫曼樹的葉子結(jié)點(diǎn)編碼printf(原文的編碼為：n); printf(*n); bianmabaocun(hc,jil

28、u); /保存編碼printf(n*n);printf(n注意：原文的編碼將保存在以名稱為“yiwen”的文件中！n); printf(是否繼續(xù)？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 4: system(cls);printf(編碼對(duì)應(yīng)的譯文為：n); yiwen(hc,jilu); /對(duì)編碼譯碼 baocunyiwen(); /保存譯文printf(n注意：譯文將保存在以名稱為“textfile”的文件中！n);printf(是否繼續(xù)？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 5: system(cls); printf(原文為：n); duquyuanwen(); /從文件中讀取原文 printf(n是否繼續(xù)？（.yes 2，no ）：); scanf(%d,&c);g