數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----huffman編碼

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>　　題目： Huffman編碼 </p><p>　　姓名： </p><p>　　班級： </p><p>　　學(xué)號： </p><p>　　指導(dǎo)老師：

2、 </p><p>　　日期： 2013年6月24日 </p><p><b>　　前言3</b></p><p><b>　　課程設(shè)計報告5</b></p><p><b>　　一．實(shí)驗(yàn)?zāi)康?</b></p><p>　　二．實(shí)驗(yàn)題目：赫夫

3、曼編碼7</p><p><b>　　1.問題描述7</b></p><p><b>　　2.需求分析7</b></p><p><b>　　三. 概要設(shè)計9</b></p><p>　　四. 詳細(xì)設(shè)計11</p><p><b>　

4、　1.設(shè)計思想11</b></p><p>　　五. 測試分析16</p><p>　　六. 使用說明18</p><p>　　七. 測試結(jié)果19</p><p><b>　　八. 附錄20</b></p><p><b>　　1.源代碼20</b>&

5、lt;/p><p><b>　　2.運(yùn)行結(jié)果25</b></p><p><b>　　前言</b></p><p>　　隨著計算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及設(shè)計最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計算機(jī)資源高效地開發(fā)非數(shù)值

6、處理的計算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。</p><p>　　算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計算機(jī)加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達(dá)到最優(yōu)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)

7、和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計算機(jī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機(jī)中的存儲表示，以及在其上進(jìn)行各種運(yùn)算時的實(shí)現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間的一門計算機(jī)專業(yè)的核心課程

8、，它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。</p><p><b>　　課程設(shè)計報告</b></p><

9、p><b>　　一．實(shí)驗(yàn)?zāi)康?lt;/b></p><p>　　數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，

10、通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間的一門計算機(jī)專業(yè)的核心課程，它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學(xué)習(xí)數(shù)據(jù)結(jié)

11、構(gòu)是為了將實(shí)際問題中所涉及的對象在計算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達(dá)到以下目的：</p><p>　　1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；</p><p>　　2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；</p>

12、<p>　　3、提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；</p><p>　　4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　二．實(shí)驗(yàn)題目：赫夫曼編碼</p><p><b>　　1.問題描述</b></p><p>　

13、　已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符（a,b,c,d,e,f,g,h），其概率分別是:0.06，0.28，0.07，0.09，0.14，0.21，0.03，0.12</p><p>　?、佥斎?種字符的概率；</p><p><b>　?、跇?gòu)造赫夫曼樹；</b></p><p>　?、圯敵雒總€字符的赫夫曼編碼;</p>&l

14、t;p><b>　　2.需求分析</b></p><p>　　赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進(jìn)制編碼成為赫夫曼編碼。樹中從根到 每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示 “1”碼，取每條路徑上的“0”或“1”的序列作為和每個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。 </p><p>　

15、　通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進(jìn)制碼形式 的字符串，但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。</p><p>　　假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為W i ,編碼長度為L i ，電文中有n 種字符，則電文編碼總長為∑W i L i 。 若將此對應(yīng)到二叉樹上，W i 為葉節(jié)點(diǎn)的權(quán) ，L i 為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑長度。那么，∑W i L i 恰好為二叉

16、樹上帶權(quán)路徑長度。 </p><p>　　因此，設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以n 種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹， 此構(gòu)造過程成為赫夫曼編碼。 </p><p>　　本演示程序用C++6.0編寫，完成赫夫曼樹的構(gòu)造以及赫夫曼編碼的設(shè)計。</p><p>　　（1）輸入的形式和輸入值的范圍：n中字符，其出現(xiàn)的頻率</p><p&g

17、t;　?。?） 輸出的形式： 二進(jìn)制前綴編碼</p><p>　?。?） 程序所能達(dá)到的功能：設(shè)計一顆赫夫曼樹，由此得到二進(jìn)制前綴編碼，即赫夫曼編碼。</p><p><b>　　（4）測試數(shù)據(jù)：</b></p><p>　　已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符（a,b,c,d,e,f,g,h），其概率分別是:0.06，0.28，0.07，

18、0.09，0.14，0.21，0.03，0.12</p><p>　?、佥斎?種字符的概率；</p><p><b>　?、跇?gòu)造赫夫曼樹；</b></p><p>　?、圯敵雒總€字符的赫夫曼編碼;</p><p><b>　　三. 概要設(shè)計</b></p><p>　?。?）

19、為了實(shí)現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：</p><p>　　ADT BinaryTree {</p><p>　　數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。</p><p>　　數(shù)據(jù)關(guān)系R： 若D=，則R=，稱BinaryTree為空二叉樹；</p><p><b>　　若D，則R={H}</b><

20、;/p><p><b>　　基本操作：</b></p><p>　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)</p><p>　　操作結(jié)果：求赫夫曼編碼</p><p>　　void Select(HuffmanTree,int,int*,int*)&

21、lt;/p><p>　　操作結(jié)果：查找權(quán)值較小的兩個結(jié)點(diǎn)</p><p>　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)</p><p>　　操作結(jié)果：輸出赫夫曼編碼</p><p>　?。?）本程序包含4個函數(shù)：　?、?主函數(shù)main()　?、?求赫夫曼編碼函數(shù)HuffmanC

22、oding();</p><p>　?、鄄檎覚?quán)值較小的兩個結(jié)點(diǎn)函數(shù)Select ();　　④ 輸出赫夫曼編碼函數(shù)OutputHuffmanCode ()　　</p><p>　　各函數(shù)間關(guān)系如下： </p><p>　　HuffmanCoding()</p><p>　　Main Select ()&l

23、t;/p><p>　　OutputHuffmanCode ()</p><p><b>　　四. 詳細(xì)設(shè)計</b></p><p>　　實(shí)現(xiàn)概要設(shè)計中定義的所有的數(shù)據(jù)類型，對每個操作給出偽碼算法。對主程序和其他模塊也都需要寫出偽碼算法。</p><p><b>　　1.設(shè)計思想</b></p>

24、;<p>　　哈夫曼編譯碼系統(tǒng)的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。 </p><p>　　在通信中可以采用0和1的不同排列來表示不同的字符，稱為二進(jìn)制編碼。而赫夫曼樹在數(shù)據(jù)編碼中的應(yīng)用是數(shù)據(jù)的最小冗余編碼問題他是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。若每個字符出現(xiàn)的頻率相同，則可以采用等長的二進(jìn)制編碼，頻率不同，采用不等長的二進(jìn)制編碼，頻率達(dá)的字符采用位數(shù)較

25、少的編碼，頻率小的采用位數(shù)較多的編碼。赫夫曼編碼就是一種不等長的二進(jìn)制編碼，而赫夫曼樹是一種最優(yōu)二叉樹，它 的編碼也是一種最優(yōu)編碼。在赫夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子節(jié)點(diǎn)的編碼為從根結(jié)點(diǎn)帶葉子結(jié)點(diǎn)中所有路徑中0和1的順序排列。 </p><p>　　設(shè)計包含的幾個方面： </p><p>　?、?#160;赫夫曼樹的構(gòu)造 <

26、;/p><p>　　假設(shè)有n個權(quán)值，則構(gòu)造出的赫夫曼樹有n個葉子結(jié)點(diǎn)。n個權(quán)值分別為w1,w2,………wn,則赫夫曼樹構(gòu)造規(guī)則為： </p><p>　　1、將w1,w2,…….wn,看成有n棵樹的森林。 </p><p>　　2、在森林中選出兩個根結(jié)點(diǎn)最小的樹合并，作為一棵新樹的左右子書，且新樹根結(jié)點(diǎn)權(quán)值為左右子樹根結(jié)點(diǎn)權(quán)值之和。 <

27、;/p><p>　　3、從森林中刪除選取的兩棵樹，并將新樹加入森林。 </p><p>　　4、重復(fù)2和3步驟，直到森林中只剩一棵樹為止</p><p><b>　　② 赫夫曼編碼</b></p><p><b>　?。?）結(jié)點(diǎn)類型</b></p><p>　

28、　typedef struct {</p><p>　　ElemType elem;</p><p>　　unsigned int weight;</p><p>　　unsigned int parent,lchild,rchild;</p><p>　　} HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹</

29、p><p>　?。?）其他模塊偽碼算法</p><p>　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int)</p><p><b>　　（偽碼算法）</b></p><p>　　void Select(HuffmanTree,int,int*,int*)&l

30、t;/p><p><b>　?。▊未a算法）</b></p><p>　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int)　?。▊未a算法）</p><p><b>　　(3)算法分析設(shè)計</b></p><p>　　void HuffmanCodin

31、g(HuffmanTree&HT,HuffmanCode&HC,int n);</p><p><b>　　{</b></p><p>　　int i,m,s1,s2,start,c,f;</p><p><b>　　char*cd;</b></p><p>　　char chl//

32、元素</p><p><b>　　if(n<=1)</b></p><p><b>　　return;</b></p><p><b>　　m=2*n-1;</b></p><p>　　HT=new HTNode[m+1];</p><p>　　f

33、or(i=1;i<=n;i++)</p><p>　　{//初始化前n個節(jié)點(diǎn)</p><p>　　cout<<"輸入元素和所占比例：";</p><p>　　cin>>ch>>wei;</p><p>　　HT[i].elem=ch;</p><p>　　H

34、T[i].weight=wei;</p><p>　　HT[i].parent=HT[i].lchild=HT[i]rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+1;i<=m;++i)</p><p>　　{//初始化后n+1...m</p><

35、p>　　HT[i].elem='0';</p><p>　　HT[i].weight=HT[i].parent=HT[i]lchild=HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+1;i<=m;++i)</p><p>　　{//

36、生成n+1...m</p><p>　　Select(HT,i-1,&s1,&s2);//查找權(quán)值較小的兩個節(jié)點(diǎn)</p><p>　　HT[s1].parent=i;HT[s2]parent=i;</p><p>　　HT[i].lchild=s1;HT[i].rchild=s2;</p><p>　　HT[i].weight

37、=HT[s1].weight+HT[s2].weight;</p><p><b>　　}</b></p><p>　　HC=new char*[n+1];</p><p>　　cd=new char[n];</p><p>　　cd[n-1]='\0';</p><p>　　fo

38、r(i=1;i<=m;++i)</p><p>　　{//生成HuffmanCode</p><p>　　start=n-1;</p><p>　　for(c=i;f=HT[i].parent;f!=0;c=f;f=HT[f].parent)</p><p><b>　　{</b></p><p

39、>　　if(HT[f].child==c)cd[--start]='0';</p><p>　　else cd[--start]='1';</p><p><b>　　}</b></p><p>　　HC[i]=new char[n-start];</p><p>　　strcpy(

40、HC[i],&cd[start]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　五. 測試分析</b></p><p>　　在我自己課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及

41、困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：</p><p>　　在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；</p><p>　　在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，

42、很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個文件的功能，這是我們設(shè)計的失敗之處。</p><p>　　通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自

43、己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。</p><p>　　這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。</p><p><b>　　六. 使用說明</b></p><p>　　1.程序名為k

44、eshe.exe，運(yùn)行環(huán)境為DOS。程序執(zhí)行后顯示：</p><p>　　2.輸入要編碼的字符種類數(shù)為8然后程序顯示：</p><p>　　3.然后依次輸入8個字符及出現(xiàn)比例</p><p><b>　　七. 測試結(jié)果</b></p><p>　　1.輸入第一個字符與所占比例：a , 6</p><p

45、>　　2. 輸入第一個字符與所占比例：b, 28</p><p>　　3. 輸入第一個字符與所占比例：c, 7</p><p>　　4. 輸入第一個字符與所占比例：d, 9</p><p>　　5. 輸入第一個字符與所占比例：e, 14</p><p>　　6. 輸入第一個字符與所占比例：f, 21</p><p&g

46、t;　　7. 輸入第一個字符與所占比例：g, 3</p><p>　　8. 輸入第一個字符與所占比例：h, 12</p><p><b>　　八. 附錄</b></p><p><b>　　1.源代碼</b></p><p>　　#include<iostream.h></p>

47、;<p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<string.h></p><p>　　typedef int Status;</p><p>　　typedef char ElemType;&l

48、t;/p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　ElemType elem;</p><p>　　unsigned int weight;</p><p>　　unsigned int parent,lchild,rchild;<

49、/p><p>　　}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹</p><p>　　typedef char**HuffmanCode;// 動態(tài)分配數(shù)組存儲赫夫曼編碼表</p><p>　　void HuffmanCoding(HuffmanTree&,HuffmanCode&,int);</p><p&g

50、t;　　void Select(HuffmanTree,int,int*,int*);</p><p>　　void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);</p><p>　　Status main()</p><p><b>　　{</b></p><p>　　

51、HuffmanTree HT;</p><p>　　HuffmanCode HC;</p><p>　　int i,n;//the number of elements;</p><p>　　cout<<"請輸入要編碼的字符種類數(shù)：";</p><p><b>　　cin>>n;</

52、b></p><p>　　HuffmanCoding(HT,HC,n);</p><p>　　OutputHuffmanCode(HT,HC,n);</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　vo

53、id HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n)</p><p><b>　　{</b></p><p>　　int i,m,s1,s2,start,c,f;</p><p><b>　　char *cd;</b></p><p&

54、gt;　　char ch;//元素;</p><p>　　int wei;//權(quán)重;</p><p>　　if(n<=1)return;</p><p><b>　　m=2*n-1;</b></p><p>　　HT=new HTNode[m+1];</p><p>　　for(i=1;i&

55、lt;=n;++i)</p><p>　　{//初始化前n個結(jié)點(diǎn)</p><p>　　cout<<"輸入元素和所占比例：";</p><p>　　cin>>ch>>wei;</p><p>　　HT[i].elem=ch;</p><p>　　HT[i].weig

56、ht=wei;</p><p>　　HT[i].parent=HT[i].lchild=HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+1;i<=m;++i)</p><p>　　{//初始化后幾個結(jié)點(diǎn)n+1...m</p><p>

57、;　　HT[i].elem='0';</p><p>　　HT[i].parent=HT[i].lchild=HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+1;i<=m;++i)</p><p>　　{//生成n+1...m個結(jié)點(diǎn);<

58、;/p><p>　　Select(HT,i-1,&s1,&s2);//查找權(quán)值較小的兩個結(jié)點(diǎn)</p><p>　　HT[s1].parent=i;HT[s2].parent=i;</p><p>　　HT[i].lchild=s1;HT[i].rchild=s2;</p><p>　　HT[i].weight=HT[s1].wei

59、ght+HT[s2].weight;</p><p><b>　　}</b></p><p>　　HC=new char*[n+1];</p><p>　　cd=new char[n];</p><p>　　cd[n-1]='\0';</p><p>　　for(i=1;i<

60、=n;++i)</p><p>　　{//生成HuffmanCode</p><p>　　start=n-1;</p><p>　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)</p><p>　　{if(HT[f].lchild==c)cd[--start]='0';<

61、/p><p>　　else cd[--start]='1';</p><p><b>　　}</b></p><p>　　HC[i]=new char[n-start];</p><p>　　strcpy(HC[i],&cd[start]);</p><p><b>

62、　　}</b></p><p><b>　　}</b></p><p>　　void Select(HuffmanTree HT,int n,int *s1,int *s2)</p><p>　　{//查找權(quán)值較小的兩個結(jié)點(diǎn)</p><p><b>　　int i;</b></p&

63、gt;<p>　　(*s1)=(*s2)=0;</p><p>　　for(i=1;i<=n;i++)</p><p>　　if(HT[i].weight<HT[(*s2)].weight&&HT[i].parent==0)</p><p>　　if(HT[i].weight<HT[(*s1)].weight)<

64、/p><p>　　{(*s2)=(*s1);</p><p><b>　　(*s1)=i;</b></p><p><b>　　}</b></p><p>　　else(*s2)=i;</p><p>　　if((*s1)>(*s2))</p><p&g

65、t;<b>　　{i=(*s1);</b></p><p>　　(*s1)=(*s2);</p><p><b>　　(*s2)=i;</b></p><p><b>　　}</b></p><p><b>　　return;</b></p>

66、<p><b>　　}</b></p><p>　　void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)</p><p>　　{//輸出 HuffmanCode</p><p><b>　　int i;</b></p><p&

67、gt;　　cout<<"\nnumber---element---weight---huffman code\n";</p><p>　　for(i=1;i<=n;i++)</p><p>　　cout<<" "<<i<<" "<<HT[i].e