數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告——哈夫曼編譯器

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)說(shuō)明書(shū)</b></p><p><b>　　計(jì)算機(jī)與通信學(xué)院</b></p><p>　　2011年 6月 23 日</p><p><b>　　一、課題任務(wù)與說(shuō)明</b&g

2、t;</p><p>　　1．編輯一個(gè)哈夫曼編譯器系統(tǒng)程序</p><p><b>　　2．問(wèn)題描述</b></p><p>　　設(shè)某編碼系統(tǒng)共有n個(gè)字符，使用頻率分別為{w1,w2,…,wn}，設(shè)計(jì)一個(gè)不等長(zhǎng)編碼方案，使得該編碼系統(tǒng)的空間效率最好。</p><p><b>　　3.所具有的功能：</b&

3、gt;</p><p>　　(1) 為一字符文本編碼功能：將一字符文本復(fù)制到指定的文本中，并保存到指定路徑，讓程序自動(dòng)為它編碼。</p><p>　　(2) 為部分字符編碼功能：輸入部分字符與對(duì)應(yīng)的字符頻率，讓程序?yàn)橹幋a（需注意輸入格式）。</p><p>　　(3) 保存輸出到文本功能：將編碼結(jié)果輸出到文本。</p><p>　　(4)

4、輸出保存文本信息功能：將功能3保存的文本信息輸出到屏幕上，用于查看結(jié)果是否正確。</p><p><b>　　4.設(shè)計(jì)要求</b></p><p>　?。?）設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)；</p><p>　?。?）設(shè)計(jì)編碼算法；</p><p>　?。?）分析時(shí)間復(fù)雜度和空間復(fù)雜度。</p><p>　?。?）

5、字符和頻度如下：</p><p>　　字符 空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z</p><p>　　頻度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 48 51 80 23 8 18 1 16</p><p><b>　　

6、5.設(shè)計(jì)內(nèi)容與步驟</b></p><p>　　（1）選擇合適的數(shù)據(jù)結(jié)構(gòu)</p><p>　?。?）結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計(jì)</p><p>　?。?）算法設(shè)計(jì)與分析</p><p>　?。?）程序設(shè)計(jì)、實(shí)現(xiàn)、調(diào)試</p><p>　?。?）課程設(shè)計(jì)說(shuō)明書(shū)</p><p>　　6.設(shè)計(jì)工作計(jì)劃

7、與進(jìn)度安排</p><p>　　（1）設(shè)計(jì)工作4學(xué)時(shí)</p><p>　?。?）實(shí)現(xiàn)與調(diào)試16學(xué)時(shí)</p><p>　?。?）課程設(shè)計(jì)說(shuō)明書(shū)4學(xué)時(shí)</p><p><b>　　二、算法設(shè)計(jì)</b></p><p>　　Huffman編碼是一種可變長(zhǎng)編碼方式，是由美國(guó)數(shù)學(xué)家David Huffman

8、創(chuàng)立的，是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長(zhǎng)度較短的代碼，而使用次數(shù)少的可以使用較長(zhǎng)的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計(jì)的(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)為最小，也就是權(quán)值(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)的和最小。</p><p>　　三、程序的功能設(shè)計(jì)</p><p>　　為實(shí)現(xiàn)系統(tǒng)功能，本程序主要分為五個(gè)模塊。

9、它們分別為：</p><p><b>　　1.初始化功能模塊</b></p><p>　　此功能模塊的功能為從鍵盤(pán)接收字符集大小n,以及n各字符和n個(gè)權(quán)值。</p><p>　　2.建立哈弗曼樹(shù)的功能模塊</p><p>　　此模塊功能為使用1中或從一文本中得到的數(shù)據(jù)按照教材的構(gòu)造哈夫曼樹(shù)的算法構(gòu)造哈夫曼樹(shù)。</p

10、><p>　　3.建立哈夫曼編碼與譯碼的功能模塊</p><p>　　此模塊功能為讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，并將譯碼結(jié)果輸出，在必要時(shí)也可保存到文件中。</p><p>　　其中各個(gè)函數(shù)的功能分別如下：</p><p>　　notesave函數(shù)用于保存輸出的結(jié)果；</p><p>　　hfmtree函數(shù)用于建立結(jié)點(diǎn)

11、哈夫曼樹(shù)并輸出最終結(jié)果；</p><p>　　readnote函數(shù)用于讀取目標(biāo)文本字符信息；</p><p><b>　　4.流程圖：</b></p><p><b>　　四、函數(shù)編碼及調(diào)試</b></p><p>　　由于本人能力有限難免不會(huì)在編碼與調(diào)試過(guò)程中遇到這樣或那樣的問(wèn)題，但通過(guò)長(zhǎng)時(shí)間的改

12、正，查詢資料與詢問(wèn)，終于能將出現(xiàn)一些致命錯(cuò)誤得以修正。例如：在輸入編碼結(jié)果信息時(shí)由于少了一個(gè)很不明顯的Getchar（）的接收Enter的函數(shù)，后面的就全亂了使程序出現(xiàn)了不能達(dá)到意料之中的效果。還有先是運(yùn)行完一個(gè)函數(shù)后就跳出了整個(gè)運(yùn)行程序不能再繼續(xù)，后來(lái)通過(guò)查閱書(shū)籍，明白再主函數(shù)中加一個(gè)For語(yǔ)句就可以避免這一問(wèn)題。第三個(gè)問(wèn)題就是由于調(diào)用完一個(gè)函數(shù)后顯示的信息還是留在運(yùn)行界面，但它們的確有沒(méi)什么用且占用界面，不美觀，后來(lái)通過(guò)詢問(wèn)同學(xué)得知

13、，在每個(gè)要調(diào)用的函數(shù)后加一個(gè)system("cls")語(yǔ)句就可達(dá)到清除上屏信息的功能。</p><p><b>　　五、總結(jié)</b></p><p>　　該程序主要用于哈夫曼編碼，并在必要時(shí)保存數(shù)據(jù)。做法主要是用一個(gè)主函數(shù)MAIN，用它達(dá)到顯示歡迎界面，提示選擇操作與調(diào)用其它函數(shù)功能（用到Switch函數(shù)），這樣使得程序簡(jiǎn)單，易讀，運(yùn)行效果也好。但

14、由于能力有限，該程序在時(shí)間與空間復(fù)雜度上有待作改正。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　?。?） 劉振鵬、張小莉等編著；數(shù)據(jù)結(jié)構(gòu)（第二版）.中國(guó)鐵道出版社。</p><p>　?。?） 石強(qiáng)、羅文浩等編著；數(shù)據(jù)結(jié)果習(xí)題解答與實(shí)驗(yàn)指導(dǎo)（第二版）.中國(guó)鐵道出版社。</p><p>　　（3）

15、劉克成 主編；C語(yǔ)言程序設(shè)計(jì).中國(guó)鐵道出版社。</p><p>　　附全部代碼(正常運(yùn)行VC++6.0)：</p><p>　　#include<stdio.h></p><p>　　#include<conio.h></p><p>　　#include<string.h></p><

16、p>　　#include<stdlib.h></p><p>　　#define MAXLEAF 27</p><p>　　#define MAXNODE MAXLEAF*2-1</p><p>　　#define MAXBIT 25</p><p>　　#define MAXVALUE 2000</p>&l

17、t;p>　　#define H "\t\t =======================================\n"</p><p>　　typedef struct{</p><p>　　int parent;</p><p>　　int weight;</p><p>　　int lchild

18、;</p><p>　　int rchild;</p><p><b>　　}hfm_n;</b></p><p>　　typedef struct{</p><p>　　int bit[MAXBIT];</p><p>　　int start;</p><p><b

19、>　　}hfm_c;</b></p><p>　　void notesave(int n,char a[],hfm_c hfm_code[])</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　int i=0,j;&

20、lt;/p><p><b>　　char c;</b></p><p>　　if((fp=fopen("d:\\notesave.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　printf("\n Can

21、not open file!\n");</p><p>　　getchar();</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++)</p><p><b&g

22、t;　　{</b></p><p>　　fputc(a[i],fp);</p><p>　　fputs("-->",fp);</p><p>　　for(j=hfm_code[i].start+1;j<n;j++)</p><p><b>　　{</b></p>

23、<p>　　c=char(48+hfm_code[i].bit[j]);</p><p>　　fputc(c,fp);</p><p><b>　　}</b></p><p>　　fputs(" ",fp);</p><p>　　if((i+1)%3==0) fputs("\n&

24、quot;,fp);</p><p><b>　　}</b></p><p>　　fclose(fp);</p><p>　　printf("\n 保存成功!\n");</p><p><b>　　}</b></p><p>　　hfm_n *hfmtre

25、e(int n,char a[],int s[])</p><p><b>　　{</b></p><p>　　hfm_n hfm_node[MAXNODE];</p><p>　　hfm_c hfm_code[MAXLEAF],cd;</p><p>　　int i,j,m1,m2,x1,x2,c,p;</p&g

26、t;<p><b>　　char ch1;</b></p><p>　　for(i=0;i<2*n-1;i++)</p><p><b>　　{</b></p><p>　　hfm_node[i].weight=0;</p><p>　　hfm_node[i].parent=-1

27、;</p><p>　　hfm_node[i].lchild=-1;</p><p>　　hfm_node[i].rchild=-1;</p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++)</p><p>　　hfm_node[i].weight=s[

28、i];</p><p>　　for(i=0;i<n-1;i++)</p><p><b>　　{</b></p><p>　　m1=m2=MAXVALUE;</p><p><b>　　x1=x2=0;</b></p><p>　　for(j=0;j<n+i;j+

29、+)</p><p><b>　　{</b></p><p>　　if(hfm_node[j].parent==-1&&hfm_node[j].weight<m1)</p><p><b>　　{</b></p><p><b>　　m2=m1;</b>&

30、lt;/p><p><b>　　x2=x1;</b></p><p>　　m1=hfm_node[j].weight;</p><p><b>　　x1=j;</b></p><p><b>　　}</b></p><p><b>　　else&l

31、t;/b></p><p>　　if(hfm_node[j].parent==-1&&hfm_node[j].weight<m2)</p><p><b>　　{</b></p><p>　　m2=hfm_node[j].weight;</p><p><b>　　x2=j;<

32、/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　hfm_node[x1].parent=hfm_node[x2].parent=n+i;</p><p>　　hfm_node[n+i].weight=hfm_node[x1].weig

33、ht+hfm_node[x2].weight;</p><p>　　hfm_node[n+i].lchild=x1;</p><p>　　hfm_node[n+i].rchild=x2;</p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++)</p><p&

34、gt;<b>　　{</b></p><p>　　cd.start=n-1;</p><p><b>　　c=i;</b></p><p>　　p=hfm_node[c].parent;</p><p>　　while(p!=-1)</p><p><b>　　{&

35、lt;/b></p><p>　　if(hfm_node[p].lchild==c)</p><p>　　cd.bit[cd.start]=0;</p><p><b>　　else</b></p><p>　　cd.bit[cd.start]=1;</p><p>　　cd.start--

36、;</p><p><b>　　c=p;</b></p><p>　　p=hfm_node[c].parent;</p><p><b>　　}</b></p><p>　　for(j=cd.start+1;j<n;j++)</p><p>　　hfm_code[i].

37、bit[j]=cd.bit[j];</p><p>　　hfm_code[i].start=cd.start;</p><p><b>　　}</b></p><p>　　printf("\n\n 所有編碼:\n ");</p><p>　　for(i=0;i<n;i++)</p>

38、<p>　　printf("%c",a[i]);</p><p>　　printf("<===>");</p><p>　　for(i=0,c=0;i<n;i++)</p><p>　　for(j=hfm_code[i].start+1;j<n;j++)</p><p&g

39、t;<b>　　{</b></p><p>　　printf("%d",hfm_code[i].bit[j]);</p><p><b>　　c++;</b></p><p>　　if(c==48||(c-48)%78==0) printf("\n ");</p>&l

40、t;p><b>　　}</b></p><p>　　printf("\n\n 各字符對(duì)應(yīng)的編碼:\n");</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　printf(" ");&

41、lt;/p><p>　　printf("%c-->",a[i]);</p><p>　　for(j=hfm_code[i].start+1;j<n;j++)</p><p>　　printf("%d",hfm_code[i].bit[j]);</p><p>　　printf(" &

42、quot;);</p><p>　　if((i+1)%5==0) printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n\n 是否將結(jié)果保存到--->路徑D:\\ notesave (y/n)?");</p><p>　　

43、ch1=getchar();getchar();</p><p>　　if(ch1=='y'||ch1=='Y')</p><p>　　notesave(n,a,hfm_code);</p><p>　　return NULL;</p><p><b>　　}</b></p>

44、<p>　　int readnote()</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　int i,j,b[26],s[26],k;</p><p>　　char a[26],ch,ch1='n';&l

45、t;/p><p>　　memset(b,0,sizeof(b));</p><p>　　if((fp=fopen("d:\\note.txt","r"))==NULL)</p><p><b>　　{</b></p><p>　　printf("\n Cannot open

46、the file of note!");</p><p>　　printf("\n Please creat a new text!\n");</p><p><b>　　ch1='y';</b></p><p><b>　　}</b></p><p>

47、　　if(ch1=='y')</p><p><b>　　{</b></p><p>　　printf("\n 此功能你要做的只是將要編碼的字符文本復(fù)制到下面文本并將它命名為note并\</p><p>　　\n 保存到--->D:\\...\</p><p>　　\n 需注意的是一定要是

48、字符文本且文本保存路徑是D盤(pán)下.\n ");</p><p>　　system("notepad");printf("\n 保存好文本后，請(qǐng)按任意鍵繼續(xù)....");</p><p>　　getchar();</p><p>　　if((fp=fopen("d:\\note.txt","

49、r"))==NULL)</p><p><b>　　{</b></p><p>　　printf("\n Open files fail!");</p><p>　　getchar();</p><p><b>　　exit(1);</b></p><

50、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{</b></p><p>　　if(sizeof(ch)!=1) break;</p>

51、<p>　　k=int(ch);</p><p>　　if(k>=65&&k<=90)</p><p>　　b[k-65]++;</p><p>　　if(k>=97&&k<=122) </p><p>　　b[k-97]++;</p><p>&l

52、t;b>　　}</b></p><p>　　fclose(fp);</p><p>　　printf("\n 文本中各字符的頻率為:\n");</p><p>　　for(i=0,j=0;i<26;i++)</p><p>　　if(b[i]!=0) </p><p>&l

53、t;b>　　{</b></p><p>　　ch=char(i+65); a[j]=ch;s[j]=b[i];</p><p>　　printf(" %c--->%d ",a[j],s[j]); j++;</p><p>　　if(j%6==0) printf("\n");</p><

54、;p><b>　　}</b></p><p>　　hfmtree(j,a,s);</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b

55、>　　{</b></p><p>　　int i,h,n=0,b[26];</p><p>　　char a[26],c[30],ch,ch1;</p><p><b>　　for(;;)</b></p><p><b>　　{</b></p><p>　　

56、printf("\n\n\n\t\t <<-\1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1->>\n");</p><p>　　printf("\t\t =======* * * * * * * * * * * * * *=======\n");</p>&

57、lt;p>　　printf("\t\t =====>>*歡迎使用本哈夫曼編碼系統(tǒng)!*<<=====\n");</p><p>　　printf("\t\t = *__*__*__*__*__*__*__*__* =\n");</p><p>　　printf("\t\t

58、 = |_ _ _ _ 功能選項(xiàng)!_ _ _ _| =\n");</p><p>　　printf("\t\t = ------------/ \\----------- =\n");</p><p>　　printf("\t\t = |

59、 | =\n");</p><p>　　printf("\t\t = | 1.為一字符文本編碼. | =\n");</p><p>　　printf("\t\t = | | =\n");</p><p&g

60、t;　　printf("\t\t = | 2.輸入部分字符與相應(yīng)頻率為之編碼.| =\n");</p><p>　　printf("\t\t = | | =\n");</p><p>　　printf("\t\t = | 3.退出程序.

61、 | =\n");</p><p>　　printf("\t\t = | | =\n");</p><p>　　printf("\t\t = | 4.打開(kāi)保存的文本. | =\n");</p>

62、<p>　　printf("\t\t = | | =\n");</p><p>　　printf("\t\t = ------------------------------------- =\n");</p><p>　　printf(H);</p&

63、gt;<p>　　printf("\n\t\t 請(qǐng)選擇某功能選項(xiàng)(1~4):");</p><p>　　scanf("%d",&h);getchar();</p><p><b>　　switch(h)</b></p><p><b>　　{</b></

64、p><p>　　case 1: system("cls");printf("\n 功能1:為一字符文本編碼!\n");readnote();break;</p><p>　　case 2: system("cls");printf("\n 功能2:輸入部分字符與相應(yīng)頻率為之編碼!\n");</p>&

65、lt;p>　　printf("\n ===>輸入格式應(yīng)為:字符+空格\n ===>例如:a b c.....\</p><p>　　\n ===>對(duì)應(yīng)的字符頻率格式也應(yīng)如此.\n");</p><p><b>　　do</b></p><p><b>　　{</b></p&

66、gt;<p>　　printf("\n 請(qǐng)輸入葉子結(jié)點(diǎn)個(gè)數(shù):");</p><p>　　if(scanf("%d",&n)!=1||sizeof(n)!=4)</p><p><b>　　{</b></p><p><b>　　ch='s';</b&g

67、t;</p><p>　　printf("\n Input worry!\n Please input again.\n");</p><p><b>　　}</b></p><p>　　else ch='n';</p><p>　　getchar();</p><

68、p>　　}while(ch=='s');</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　printf("\n =======>請(qǐng)輸入相應(yīng)個(gè)字符:");</p><p>　　for(i=0;i<

69、;n;i++)</p><p><b>　　{</b></p><p>　　a[i]=getchar();</p><p>　　ch1=getchar();</p><p><b>　　}</b></p><p>　　if(ch1!='\n') gets(c)

70、;</p><p>　　printf("\n 請(qǐng)輸入相應(yīng)字符對(duì)應(yīng)的頻率:");</p><p>　　for(i=0;i<n;i++)</p><p>　　scanf("%d",&b[i]);</p><p>　　ch1=getchar();</p><p>　　if

71、(ch1!='\n') gets(c);</p><p>　　printf("\n 確認(rèn)所有數(shù)據(jù)無(wú)誤后請(qǐng)按'Enter'(否則按'y')");</p><p>　　ch=getchar();</p><p>　　}while(ch=='y'||ch=='Y');<

72、;/p><p>　　hfmtree(n,a,b);break;</p><p>　　case 3: printf("\n\n\n");printf(H);printf("\t\t\t\t \1歡迎下次使用\1\n");printf(H);</p><p>　　printf("\t\t");return;<

73、/p><p>　　case 4: printf("\nNotesave 中的信息:\n");system("type d:\\notesave.txt");break;</p><p>　　default: printf("\t\t \a輸入有誤!\t");getchar();break;</p><p>&

74、lt;b>　　}</b></p><p>　　printf("\n ");</p><p>　　system("pause");</p><p>　　system("cls");</p><p><b>　　}</b></p>&