數(shù)據(jù)結(jié)構(gòu)--huffman編碼和譯碼

1、<p>　　《數(shù) 據(jù) 結(jié) 構(gòu)》</p><p><b>　　課程設(shè)計(jì)說(shuō)明書</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p><b>　　目 錄</b></p><p>　　目 錄III</p><p&

2、gt;　　第一章 需求分析4</p><p><b>　　1.1引言4</b></p><p>　　1.2任務(wù)概述4</p><p>　　1.3數(shù)據(jù)描述4</p><p>　　1.4功能需求5</p><p>　　1.5性能需求5</p><p>　

3、　1.6運(yùn)行需求5</p><p>　　第二章概要設(shè)計(jì)6</p><p>　　2.1總體設(shè)計(jì)6</p><p>　?。ㄒ唬?設(shè)計(jì)目的：6</p><p>　?。ǘ?函數(shù)劃分7</p><p>　　2.2數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)）7</p><p>　　2.3接口設(shè)計(jì)

4、7</p><p>　　2.4運(yùn)行界面設(shè)計(jì)8</p><p>　　第三章詳細(xì)設(shè)計(jì)9</p><p>　　3.1輸入、創(chuàng)建模塊設(shè)計(jì)9</p><p>　　3.2編碼模塊設(shè)計(jì)10</p><p>　　3.3譯碼模塊設(shè)計(jì)11</p><p>　　3.4主函數(shù)模塊設(shè)計(jì)13<

5、/p><p>　　第四章測(cè)試分析15</p><p>　　4.1測(cè)試程序執(zhí)行情況15</p><p>　　4.2出現(xiàn)的問(wèn)題和解決的方法17</p><p>　　第五章課程設(shè)計(jì)總結(jié)18</p><p>　　附錄：程序代碼19</p><p><b>　　參考文獻(xiàn)26<

6、;/b></p><p><b>　　第一章 需求分析</b></p><p><b>　　引言</b></p><p>　　目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)化成由二級(jí)制的字符組成的字符串。</p><p>　　利用哈夫曼樹(shù)求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼

7、。樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過(guò)程稱為編碼，解壓縮的過(guò)程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度盡可能最短，即采用最短碼。因此，哈夫曼樹(shù)在通信、編碼和數(shù)據(jù)壓縮等技術(shù)領(lǐng)域有著廣泛的應(yīng)用。</p><

8、;p>　　此設(shè)計(jì)說(shuō)明書是對(duì)編碼/譯碼系統(tǒng)開(kāi)發(fā)的一個(gè)初步的分析說(shuō)明性文檔，旨在通過(guò)該文檔清晰的闡述系統(tǒng)的實(shí)際功能，方便系統(tǒng)開(kāi)發(fā)人員對(duì)系統(tǒng)的理解以及與用戶的溝通。文檔相關(guān)說(shuō)明部分在目錄部分已全部涵蓋，閱讀此文檔的相關(guān)人員可以通過(guò)目錄索引找到相應(yīng)部分予以閱讀。</p><p><b>　　任務(wù)概述</b></p><p>　　Huffman編碼和譯碼</p>

9、;<p>　　根據(jù)給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對(duì)一段文本（定義在該字符集上）進(jìn)行編碼和譯碼，實(shí)現(xiàn)一個(gè)Huffman編碼/譯碼系統(tǒng)。</p><p><b>　　數(shù)據(jù)描述</b></p><p>　　該哈夫曼編碼/譯碼系統(tǒng)程序中的數(shù)據(jù)主要有：哈夫曼樹(shù)、哈夫曼編碼，哈夫曼譯碼等。</p><p&g

10、t;<b>　　功能需求</b></p><p>　　輸入模塊：輸入各個(gè)元素，建立哈夫曼樹(shù)；</p><p>　　編碼模塊：將輸入的各個(gè)元素建立哈夫曼樹(shù)，進(jìn)行編碼；</p><p>　　譯碼模塊：將電文以0或1輸入后，根據(jù)之前的哈夫曼樹(shù)進(jìn)行譯碼；</p><p>　　輸出模塊：建立好的哈夫曼樹(shù)、編碼、譯碼進(jìn)行輸出。<

11、;/p><p><b>　　性能需求</b></p><p>　　要求該編碼/譯碼系統(tǒng)具有一定的可擴(kuò)展性以便適應(yīng)發(fā)展，且便于維護(hù)；</p><p>　　要求該編碼/譯碼系統(tǒng)便于使用，使用步驟簡(jiǎn)易明了。</p><p><b>　　運(yùn)行需求</b></p><p>　　基于wind

12、ows平臺(tái)下的窗口圖形界面軟件，運(yùn)行主界面為windows的經(jīng)典運(yùn)行界面，采用多文檔界面，從而使程序更加美觀，整齊有序，簡(jiǎn)易操作。</p><p>　　軟件運(yùn)行基于windows平臺(tái)上的xp,Vista,win7等</p><p><b>　　概要設(shè)計(jì)</b></p><p><b>　　總體設(shè)計(jì)</b></p>

13、;<p><b>　　設(shè)計(jì)目的：</b></p><p>　　掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；</p><p

14、>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　圖2.1：程序主體設(shè)計(jì)圖</p><p><b>　　函數(shù)劃分</b></p><p>　　該程序有一個(gè)主函數(shù)和多個(gè)子函數(shù)，主函數(shù)完成對(duì)子函數(shù)的調(diào)用，各子函數(shù)實(shí)現(xiàn)相應(yīng)的功能。</p><p>&

15、lt;b>　　結(jié)點(diǎn)的開(kāi)辟。</b></p><p>　　實(shí)現(xiàn)對(duì)輸入字符串中出現(xiàn)的不同字符及其出現(xiàn)字?jǐn)?shù)的信息記錄。</p><p>　　用葉子結(jié)點(diǎn)構(gòu)造赫夫曼樹(shù)。</p><p>　　獲得構(gòu)造的赫夫曼樹(shù)中所有葉子結(jié)點(diǎn)的元素及其赫夫曼編碼。</p><p>　　輸出各葉子結(jié)點(diǎn)元素及其對(duì)應(yīng)的赫夫曼編碼。</p><

16、;p>　　輸出輸入的字符串的赫夫曼編碼。</p><p><b>　　調(diào)用各子函數(shù)</b></p><p>　　數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)）</p><p>　　表2.1：數(shù)據(jù)類型設(shè)計(jì)</p><p><b>　　接口設(shè)計(jì)</b></p><p><b>　

17、　表2.1：函數(shù)列表</b></p><p><b>　　運(yùn)行界面設(shè)計(jì)</b></p><p>　　圖2.1：運(yùn)行界面設(shè)計(jì)</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　輸入、創(chuàng)建模塊設(shè)計(jì)</b></p><p>

18、　　輸入、創(chuàng)建哈夫曼樹(shù)：</p><p>　　int HuffmanCreate(HuffNode*ht)</p><p><b>　　{</b></p><p>　　int i,k,n,m1,m2,p1,p2;</p><p>　　printf("請(qǐng)輸入元素個(gè)數(shù)\n");</p>&l

19、t;p>　　scanf("%d",&n);</p><p>　　for(i=1;i<=n;i++) //輸入結(jié)點(diǎn)值和信息</p><p><b>　　{</b></p><p>　　getchar();//接收回車</p><p>　　

20、printf("第%d個(gè)元素的:\n結(jié)點(diǎn)值:",i);</p><p>　　scanf("%c",&ht[i].data);</p><p>　　printf("權(quán)值:");</p><p>　　scanf("%d",&ht[i].weight);</p>

21、<p><b>　　}</b></p><p>　　for(i=1;i<=2*n-1;i++) //對(duì)數(shù)組初始化</p><p>　　ht[i].parent=ht[i].left=ht[i].right=0;</p><p>　　for(i=n+1;i<=2*n-1

22、;i++)</p><p><b>　　{</b></p><p>　　m1=m2=32767; //初始化，令m1,m2為整數(shù)最大值</p><p><b>　　p1=p2=1;</b></p><p>　　for(k=1;k<=i-1;k++)

23、 //從數(shù)組中找</p><p>　　if(ht[k].parent==0) //parent為零切權(quán)值最小的兩個(gè)結(jié)點(diǎn)</p><p>　　if(ht[k].weight<m1)</p><p><b>　　{</b></p><p>　　m2=m1

24、; //令m1為最小權(quán)值</p><p>　　p2=p1; //p1 為最小權(quán)值的位置</p><p>　　m1=ht[k].weight; //m1存放最小權(quán)值</p><p><b>　　p1=k;</b></p><p><b>　　}<

25、;/b></p><p>　　else if(ht[k].weight<m2)</p><p><b>　　{</b></p><p>　　m2=ht[k].weight; //m2 為次小權(quán)值</p><p>　　p2=k; //p2為次小權(quán)值所在位置

26、</p><p><b>　　}</b></p><p>　　ht[p1].parent=i; //i分別付給下標(biāo)為p1，p2的數(shù)組中</p><p>　　ht[p2].parent=i;</p><p>　　ht[i].weight=m1+m2; //新節(jié)點(diǎn)權(quán)值為最小權(quán)值和次小權(quán)值之和</p>

27、<p>　　ht[i].left=p1; //p1為新節(jié)點(diǎn)的左孩子</p><p>　　ht[i].right=p2; //p2為新節(jié)點(diǎn)的右孩子</p><p><b>　　}</b></p><p>　　printf("哈夫曼樹(shù)已成功建立!\n");</p><

28、;p>　　return n; //返回結(jié)點(diǎn)數(shù)</p><p><b>　　}</b></p><p><b>　　編碼模塊設(shè)計(jì)</b></p><p>　　根據(jù)創(chuàng)建好的哈夫曼樹(shù)，進(jìn)行編碼：</p><p>　　void Encoding(HuffNode

29、 ht[],HuffCode hcd[],int n)</p><p><b>　　{</b></p><p>　　HuffCode d;</p><p>　　int i,k,f,c;</p><p>　　for(i=1;i<=n;i++)//對(duì)所有節(jié)點(diǎn)循環(huán)</p><p><b>

30、;　　{</b></p><p>　　d.start=n+1; //起始地點(diǎn)</p><p>　　c=i; //從葉結(jié)點(diǎn)開(kāi)始向上</p><p>　　f=ht[i].parent;</p><p>　　while(f!=0) //到樹(shù)根結(jié)束

31、</p><p><b>　　{</b></p><p>　　if(ht[f].left==c)</p><p>　　d.cd[--d.start]='0'; //規(guī)定左數(shù)代碼為零</p><p><b>　　else</b></p><p

32、>　　d.cd[--d.start]='1'; //規(guī)定右樹(shù)代碼為一</p><p>　　c=f;//c為孩子位置</p><p>　　f=ht[f].parent; //f指雙親位置</p><p><b>　　}</b></p><p&g

33、t;<b>　　hcd[i]=d;</b></p><p><b>　　}</b></p><p>　　printf("輸出哈夫曼編碼:\n");</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></

34、p><p>　　printf("%c:",ht[i].data); </p><p><b>　　//先輸出結(jié)點(diǎn)</b></p><p>　　for(k=hcd[i].start;k<=n;k++) //在輸出對(duì)應(yīng)編碼</p><p>　　printf("

35、%c",hcd[i].cd[k]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　譯碼模塊設(shè)計(jì)</b></p><p

36、>　　根據(jù)已有的哈夫曼樹(shù)和提供的電文，進(jìn)行譯碼：</p><p>　　void Decoding(HuffNode ht[],HuffCode hcd[],int n)</p><p><b>　　{</b></p><p>　　int f,m,k;</p><p>　　DataType c,ch[200];

37、 //c接收文件,ch存儲(chǔ)</p><p>　　printf("請(qǐng)輸入電文(0 or 1),以#結(jié)束\n");</p><p>　　c=getchar();</p><p><b>　　k=1;</b></p><p>　　while(c!='#')

38、 //單字符循環(huán)輸入，以#結(jié)束</p><p><b>　　{</b></p><p>　　ch[k]=c; //單字符一次存入ch字串中</p><p>　　c=getchar();</p><p>　　k=k+1;

39、 //ch 下地址后移</p><p><b>　　}</b></p><p>　　m=k; //標(biāo)記數(shù)組存儲(chǔ)末位位置</p><p><b>　　f=2*n-1;</b></p><p>　　k=1;//k

40、 記錄電文字符個(gè)數(shù)</p><p>　　printf("輸出哈夫曼譯碼:\n");</p><p>　　while(k<m) //k循環(huán)到數(shù)組末尾結(jié)束</p><p><b>　　{</b></p><p>　　whi

41、le(ht[f].left!=0) //直到左孩子結(jié)點(diǎn)為零結(jié)束</p><p><b>　　{</b></p><p>　　if(ch[k]=='0') //若接收字符為0，則存為左孩子</p><p>　　f=ht[f].left;</p&g

42、t;<p>　　if(ch[k]=='1') //若接收字符為1，則存為右孩子</p><p>　　f=ht[f].right;</p><p>　　k++; //ch數(shù)組下標(biāo)后移</p><p><b>　　}</b></p>&l

43、t;p>　　printf("%c",ht[f].data);</p><p>　　f=2*n-1; //每次都從根節(jié)點(diǎn)開(kāi)始查找</p><p><b>　　}</b></p><p>　　printf("\n");</p><p&g

44、t;<b>　　}</b></p><p><b>　　主函數(shù)模塊設(shè)計(jì)</b></p><p><b>　　主函數(shù)的設(shè)計(jì)：</b></p><p>　　int main(int argc,char*argv[])</p><p><b>　　{</b>&l

45、t;/p><p>　　int n,select,flag=FALSE; //flag為零標(biāo)記第一次選擇功能</p><p>　　HuffNode ht[2*MAXNUM]; //定義存放哈夫曼的數(shù)組</p><p>　　HuffCode hcd[MAXNUM]; //定義存放編碼的數(shù)

46、組</p><p>　　while(TRUE)</p><p><b>　　{</b></p><p>　　printf("\n——————?dú)g迎進(jìn)入赫夫曼編碼譯碼——————\n\n");</p><p>　　printf("1.建立哈夫曼樹(shù) \n");</p>

47、<p>　　printf("2.編碼 \n");</p><p>　　printf("3.譯碼 \n");</p><p>　　printf("4.退出程序 \n\n");</p><p>　　printf("請(qǐng)選擇您要實(shí)現(xiàn)的功能:(請(qǐng)輸入1-4)

48、\n");</p><p>　　scanf("%d",&select);</p><p>　　if(select>=1&&select<=4){</p><p>　　if(select!=1&&select!=4&&flag==0)</p><p&g

49、t;<b>　　{</b></p><p>　　printf("請(qǐng)先建立哈夫曼樹(shù)在選擇其他功能!\n");</p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　flag=TRUE;</p&

50、gt;<p>　　switch(select) </p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　n=HuffmanCreate(ht);</p><p><b>　　break;</b>&

51、lt;/p><p><b>　　case 2:</b></p><p>　　Encoding(ht,hcd,n);</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　Decoding(h

52、t,hcd,n);</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>

53、<b>　　}else{</b></p><p>　　printf("請(qǐng)重新輸入!\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b><

54、/p><p><b>　　}</b></p><p><b>　　測(cè)試分析</b></p><p><b>　　測(cè)試程序執(zhí)行情況</b></p><p>　　圖4.1：選擇建立哈夫曼樹(shù)</p><p>　　圖4.2：輸入需建立哈夫曼樹(shù)的元素個(gè)數(shù)</p&

55、gt;<p>　　圖4.3：成功建立哈夫曼樹(shù)</p><p>　　圖4.4：根據(jù)建立好的哈夫曼樹(shù)，進(jìn)行編碼</p><p>　　圖4.5：根據(jù)建立好的哈夫曼樹(shù)以及輸入的電文，進(jìn)行譯碼</p><p>　　出現(xiàn)的問(wèn)題和解決的方法</p><p>　　程序的語(yǔ)句結(jié)束后，忘記打分號(hào)：程序運(yùn)行出現(xiàn)錯(cuò)誤后，加上分號(hào)；</p>

56、<p>　　輸入電文時(shí)，誤將0和1輸成其他數(shù)據(jù)，結(jié)果程序出現(xiàn)將其他數(shù)據(jù)隨機(jī)當(dāng)做0或1。</p><p><b>　　課程設(shè)計(jì)總結(jié)</b></p><p>　　在課程設(shè)計(jì)過(guò)程中，我們每個(gè)人選擇一個(gè)課題，認(rèn)真研究，根據(jù)課堂教授內(nèi)容，借助書本，自己動(dòng)手實(shí)踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強(qiáng)我們的獨(dú)立思考能力和動(dòng)手能力；通過(guò)編寫實(shí)驗(yàn)代碼和調(diào)試運(yùn)行

57、，我們可以逐步積累調(diào)試C程序的經(jīng)驗(yàn)并逐漸培養(yǎng)我們的編程能力、用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力。</p><p>　　在課程設(shè)計(jì)過(guò)程中，我們不但有自己的獨(dú)立思考，還借助各種參考文獻(xiàn)來(lái)幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強(qiáng)了交流，在對(duì)問(wèn)題的認(rèn)識(shí)方面可以交換不同的意見(jiàn)。</p><p>　　在寫代碼前，首先，對(duì)問(wèn)題進(jìn)行了分析，明確了目標(biāo)，列出了大的框架，然后逐漸細(xì)化，劃分出不同的功能模塊，由

58、具體的子函數(shù)去實(shí)現(xiàn)，先在紙上編寫代碼，寫好后進(jìn)行了反復(fù)的邏輯推理，發(fā)現(xiàn)并解決邏輯問(wèn)題，然后，上機(jī)調(diào)試，方法是：一個(gè)一個(gè)功能模塊分開(kāi)進(jìn)行調(diào)試，主要看調(diào)試的模塊能否達(dá)到預(yù)期的結(jié)果，這樣可以縮小排錯(cuò)的范圍，便以糾錯(cuò)和提高編程的效率，當(dāng)每個(gè)功能模塊都調(diào)試好后，就把各個(gè)部分組合起來(lái)，再進(jìn)行調(diào)試，主要檢查各函數(shù)接口是否正確，當(dāng)達(dá)到預(yù)期的結(jié)果，調(diào)試結(jié)束，編程部分完成，然后按實(shí)驗(yàn)要求完成實(shí)驗(yàn)報(bào)告。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課

59、程具有比較強(qiáng)的理論性，同時(shí)也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。課程設(shè)計(jì)是一個(gè)重要的教學(xué)環(huán)節(jié)。我們?cè)谝话闱闆r下都能夠重視實(shí)驗(yàn)環(huán)節(jié)，但是容易忽略實(shí)驗(yàn)的總結(jié)，忽略實(shí)驗(yàn)報(bào)告的撰寫。通過(guò)這次實(shí)驗(yàn)讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達(dá)能力。需要逐步培養(yǎng)書寫科學(xué)實(shí)驗(yàn)報(bào)告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會(huì)有好的提高。</p><p><b>　　附錄：程序代碼</b></

60、p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p><p>　　#include<limits.h></p><p>　　#include<string.h></p><p>　　#include<std

61、lib.h></p><p>　　#include<io.h></p><p>　　#include<math.h></p><p>　　#include<process.h></p><p>　　#define TRUE 1</p><p>　　#define FALSE 0

62、</p><p>　　#define OK 1</p><p>　　#define ERROR -1</p><p>　　#define INFEASIBLE -1</p><p>　　typedef char DataType;</p><p>　　#define MAXNUM 50</p><p

63、>　　typedef struct //huffman 樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)定義</p><p><b>　　{</b></p><p>　　DataType data; //數(shù)據(jù)用字符表示</p><p>　　int weight; //權(quán)值</p&g

64、t;<p>　　int parent; //雙親</p><p>　　int left; //左孩子</p><p>　　int right; //右孩子</p><p>　　}HuffNode;</p><p>　　typedef stru

65、ct//huffman 樹(shù)結(jié)點(diǎn)的存儲(chǔ)定義</p><p><b>　　{</b></p><p>　　DataType cd[MAXNUM]; //存放編碼位串</p><p>　　int start; //編碼起始位置</p&

66、gt;<p>　　}HuffCode;</p><p>　　int HuffmanCreate(HuffNode*ht)</p><p><b>　　{</b></p><p>　　int i,k,n,m1,m2,p1,p2;</p><p>　　printf("請(qǐng)輸入元素個(gè)數(shù)\n");

67、</p><p>　　scanf("%d",&n);</p><p>　　for(i=1;i<=n;i++) //輸入結(jié)點(diǎn)值和信息</p><p><b>　　{</b></p><p>　　getchar();

68、 //接收回車</p><p>　　printf("第%d個(gè)元素的:\n結(jié)點(diǎn)值:",i);</p><p>　　scanf("%c",&ht[i].data);</p><p>　　printf("權(quán)值:");</p><p>　　scanf("%d"

69、,&ht[i].weight);</p><p><b>　　}</b></p><p>　　for(i=1;i<=2*n-1;i++) //對(duì)數(shù)組初始化</p><p>　　ht[i].parent=ht[i].left=ht[i].right=0;</p><p&g

70、t;　　for(i=n+1;i<=2*n-1;i++)</p><p><b>　　{</b></p><p>　　m1=m2=32767; //初始化，令m1,m2為整數(shù)最大值</p><p><b>　　p1=p2=1;</b></p><p>　　

71、for(k=1;k<=i-1;k++) //從數(shù)組中找</p><p>　　if(ht[k].parent==0) //parent為零切權(quán)值最小的兩個(gè)結(jié)點(diǎn)</p><p>　　if(ht[k].weight<m1)</p><p><b>　　{</b></p>&l

72、t;p>　　m2=m1; //令m1為最小權(quán)值</p><p>　　p2=p1; //p1 為最小權(quán)值的位置</p><p>　　m1=ht[k].weight; //m1存放最小權(quán)值</p><p><b>　　p1=k;</b></p><p

73、><b>　　}</b></p><p>　　else if(ht[k].weight<m2)</p><p><b>　　{</b></p><p>　　m2=ht[k].weight; //m2 為次小權(quán)值</p><p>　　p2=k;

74、 //p2為次小權(quán)值所在位置</p><p><b>　　}</b></p><p>　　ht[p1].parent=i; //i分別付給下標(biāo)為p1，p2的數(shù)組中</p><p>　　ht[p2].parent=i;</p><p>　　ht[i].weight=m1+m2;

75、 //新節(jié)點(diǎn)權(quán)值為最小權(quán)值和次小權(quán)值之和</p><p>　　ht[i].left=p1;//p1為新節(jié)點(diǎn)的左孩子</p><p>　　ht[i].right=p2;//p2為新節(jié)點(diǎn)的右孩子</p><p><b>　　}</b></p><p>　　printf("哈夫曼樹(shù)已成功建立!\n&quo

76、t;);</p><p>　　return n; //返回結(jié)點(diǎn)數(shù)</p><p><b>　　}</b></p><p><b>　　//編碼</b></p><p>　　void Encoding(HuffNode ht[],HuffCode hcd[],int n)

77、</p><p><b>　　{</b></p><p>　　HuffCode d;</p><p>　　int i,k,f,c;</p><p>　　for(i=1;i<=n;i++) //對(duì)所有節(jié)點(diǎn)循環(huán)</p><p><b>　　{</b>

78、</p><p>　　d.start=n+1; //起始地點(diǎn)</p><p>　　c=i; //從葉結(jié)點(diǎn)開(kāi)始向上</p><p>　　f=ht[i].parent;</p><p>　　while(f!=0) //到樹(shù)根結(jié)束&

79、lt;/p><p><b>　　{</b></p><p>　　if(ht[f].left==c)</p><p>　　d.cd[--d.start]='0'; //規(guī)定左數(shù)代碼為零</p><p><b>　　else</b></p><

80、;p>　　d.cd[--d.start]='1'; //規(guī)定右樹(shù)代碼為一</p><p>　　c=f; //c為孩子位置</p><p>　　f=ht[f].parent; //f指雙親位置<

81、;/p><p><b>　　}</b></p><p><b>　　hcd[i]=d;</b></p><p><b>　　}</b></p><p>　　printf("輸出哈夫曼編碼:\n");</p><p>　　for(i=1;i

82、<=n;i++)</p><p><b>　　{</b></p><p>　　printf("%c:",ht[i].data); //先輸出結(jié)點(diǎn)</p><p>　　for(k=hcd[i].start;k<=n;k++) //在輸出對(duì)應(yīng)編碼</p><p

83、>　　printf("%c",hcd[i].cd[k]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//譯碼</b>

84、</p><p>　　void Decoding(HuffNode ht[],HuffCode hcd[],int n)</p><p><b>　　{</b></p><p>　　int f,m,k;</p><p>　　DataType c,ch[200]; //c接收文件,ch

85、存儲(chǔ)</p><p>　　printf("請(qǐng)輸入電文(0 or 1),以#結(jié)束\n");</p><p>　　c=getchar();</p><p><b>　　k=1;</b></p><p>　　while(c!='#') //單字符循

86、環(huán)輸入，以#結(jié)束</p><p><b>　　{</b></p><p>　　ch[k]=c; //單字符一次存入ch字串中</p><p>　　c=getchar();</p><p>　　k=k+1; //ch下地址后移</p>

87、<p><b>　　}</b></p><p>　　m=k; //標(biāo)記數(shù)組存儲(chǔ)末位位置</p><p><b>　　f=2*n-1;</b></p><p>　　k=1; //k記錄電文字符個(gè)數(shù)</p><p>　　

88、printf("輸出哈夫曼譯碼:\n");</p><p>　　while(k<m) //k循環(huán)到數(shù)組末尾結(jié)束</p><p><b>　　{</b></p><p>　　while(ht[f].left!=0) //直到左孩子結(jié)點(diǎn)為零結(jié)束</p&

89、gt;<p><b>　　{</b></p><p>　　if(ch[k]=='0') //若接收字符為0，則存為左孩子</p><p>　　f=ht[f].left;</p><p>　　if(ch[k]=='1') //若接收字符為1，

90、則存為右孩子</p><p>　　f=ht[f].right;</p><p>　　k++; //ch數(shù)組下標(biāo)后移</p><p><b>　　}</b></p><p>　　printf("%c",ht[f].data);</p>

91、<p>　　f=2*n-1; //每次都從根節(jié)點(diǎn)開(kāi)始查找</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　int

92、 main(int argc,char*argv[])</p><p><b>　　{</b></p><p>　　int n,select,flag=FALSE; //flag為零標(biāo)記第一次選擇功能</p><p>　　HuffNode ht[2*MAXNUM]; //定義存放哈夫曼的數(shù)組&

93、lt;/p><p>　　HuffCode hcd[MAXNUM]; //定義存放編碼的數(shù)組</p><p>　　while(TRUE)</p><p><b>　　{</b></p><p>　　printf("\n——————?dú)g迎進(jìn)入赫夫曼編碼譯碼——————\n\n");

94、</p><p>　　printf("1.建立哈夫曼樹(shù) \n");</p><p>　　printf("2.編碼 \n");</p><p>　　printf("3.譯碼 \n");</p><p>　　printf("4.退出程序

95、 \n\n");</p><p>　　printf("請(qǐng)選擇您要實(shí)現(xiàn)的功能:(請(qǐng)輸入1-4)\n");</p><p>　　scanf("%d",&select);</p><p>　　if(select>=1&&select<=4){</p><p>　

96、　if(select!=1&&select!=4&&flag==0)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)先建立哈夫曼樹(shù)在選擇其他功能!\n");</p><p><b>　　continue;</b></p>&l

97、t;p><b>　　}</b></p><p>　　flag=TRUE;</p><p>　　switch(select)</p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　n=Huff

98、manCreate(ht);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　Encoding(ht,hcd,n);</p><p><b>　　break;</b></p><p&g

99、t;<b>　　case 3:</b></p><p>　　Decoding(ht,hcd,n);</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p><b>　　exit(0);</b>&

100、lt;/p><p><b>　　}</b></p><p><b>　　}else{</b></p><p>　　printf("請(qǐng)重新輸入!\n");</p><p><b>　　}</b></p><p><b>　　}&l

101、t;/b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu) （C語(yǔ)言版）》嚴(yán)蔚敏、吳偉民 主編 清華大學(xué)出版社 </p><