赫夫曼編譯碼器的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　題 目：赫夫曼編/譯碼器的實(shí)現(xiàn)</p><p><b>　　學(xué)生姓名： </b></p><p>　　學(xué) 號(hào)： </p><p><b>　　所在學(xué)院： </b></p><p>

2、　　班 級(jí)： </p><p>　　指導(dǎo)教師： </p><p>　　職 稱(chēng)： </p><p>　　2010年 6 月 25日</p><p>　　XXX學(xué)院本科學(xué)生課程設(shè)計(jì)任務(wù)書(shū)</p><p><b>　　摘要</b></p><p&

3、gt;　　利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)，試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼編譯碼系統(tǒng)。</p><p>　　關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)、哈夫曼編碼</p><p><b>

4、　　目錄</b></p><p><b>　　第一章. 序言1</b></p><p>　　第二章．問(wèn)題分析與說(shuō)明1</p><p><b>　　一．功能分析1</b></p><p>　　二．問(wèn)題描述與說(shuō)明1</p><p>　　第三章．程序總體設(shè)計(jì)2

5、</p><p>　　一．設(shè)計(jì)思路及方案2</p><p>　　二.設(shè)計(jì)的總體框架3</p><p>　　第四章.詳細(xì)算法與設(shè)計(jì)5</p><p>　　一．實(shí)現(xiàn)算法流程圖5</p><p>　　二．哈夫曼編碼的算法6</p><p>　　三．文件的編碼和解碼8</p>

6、<p>　　第五章.程序調(diào)試與運(yùn)行結(jié)果8</p><p>　　第六章.課程設(shè)計(jì)總結(jié)9</p><p>　　第七章.參考文獻(xiàn)10</p><p><b>　　第八章.附錄11</b></p><p><b>　　第一章. 序言</b></p><p><

7、b>　　目的：</b></p><p>　　1、為了使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類(lèi)型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?lt;/p><p>　　為了使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)化</p><p><b>　　軟件設(shè)計(jì)的能力。</b></p>

8、<p>　　3、為了使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。</p><p><b>　　意義：</b></p><p>　　通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我掌握了赫夫曼編/譯碼器的實(shí)現(xiàn)所需要的各種知識(shí)，了解到了哈夫曼程序設(shè)計(jì)的基本原理和知識(shí)，我相信在以后的學(xué)習(xí)當(dāng)中我會(huì)更加的喜歡計(jì)算機(jī)這門(mén)高新技術(shù)學(xué)科。</p>&

9、lt;p>　　第二章．問(wèn)題分析與說(shuō)明</p><p><b>　　一．功能分析</b></p><p>　　利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編／譯碼系統(tǒng)。因此

10、為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編／譯碼系統(tǒng)存在著相當(dāng)大的必要。</p><p>　　相關(guān)知識(shí)：數(shù)據(jù)結(jié)構(gòu)、哈夫曼編碼譯碼器、程序設(shè)計(jì)格式等。</p><p>　　二．問(wèn)題描述與說(shuō)明：</p><p>　　1.《數(shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)

11、單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門(mén)計(jì)算機(jī)專(zhuān)業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　2. 哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹(shù)求得的用于通信的二進(jìn)制編碼稱(chēng)為哈夫曼編碼。樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”

12、碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。</p><p>　　通常我們把數(shù)據(jù)壓縮的過(guò)程稱(chēng)為編碼，解壓縮的過(guò)程稱(chēng)為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度盡可能最短，即采用最短碼。</p><p>　　作為信息管理專(zhuān)業(yè)的學(xué)生，我們應(yīng)該很好的掌握這門(mén)技術(shù)。在課堂上，我們能過(guò)學(xué)到許多的理論知識(shí)，但我們很少有過(guò)自己動(dòng)手

13、實(shí)踐的機(jī)會(huì)！課程設(shè)計(jì)就是為解決這個(gè)問(wèn)題提供了一個(gè)平臺(tái)。</p><p>　　3. 課程設(shè)計(jì)題目：哈夫曼編\譯碼器</p><p><b>　　任務(wù)和功能：</b></p><p>　?。?）從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)；</p><p>　?。?）利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)

14、存，則從文件htmTree中讀入），對(duì)給定的n個(gè)字符正文進(jìn)行編碼，并輸出結(jié)果。</p><p>　?。?）利用已建好的哈夫曼樹(shù)，對(duì)給定的一個(gè)哈夫曼編碼進(jìn)行譯碼，判斷此編碼對(duì)應(yīng)的字符，并輸出結(jié)果。</p><p><b>　　4.問(wèn)題分析</b></p><p>　　該問(wèn)題要求將輸入的字符以及相應(yīng)的權(quán)值建立哈夫曼樹(shù)，并利用建好的哈夫曼樹(shù)生成哈夫曼

15、編碼。把輸入的字符按權(quán)值從小到大排序，挑出2個(gè)最小權(quán)值供哈夫曼編碼調(diào)用，再將輸入的字符以及他的權(quán)值，按照哈夫曼規(guī)則建立二叉樹(shù)，從葉子到根逆向求編碼，再使用循環(huán),從根結(jié)點(diǎn)開(kāi)始遍歷輸出。</p><p>　　第三章．程序總體設(shè)計(jì)</p><p><b>　　一．設(shè)計(jì)思路及方案</b></p><p><b>　　1.哈弗曼樹(shù)的構(gòu)造<

16、/b></p><p>　　根據(jù)哈夫曼樹(shù)的定義，一棵二叉樹(shù)要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。</p><p>　　這種方法的基本思想是：</p><p>　?。?）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合F＝{T1，T2，…，Tn}；</p>

17、;<p>　　（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；</p><p>　　（3）在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中；</p><p>　?。?）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。</

18、p><p><b>　　2.哈弗曼編碼 </b></p><p>　　設(shè)S={d0,d1,……,d(n-1)}為待編碼的字符集，W={w0,w1,……,w(n-1)}是S中各字符在電文中出現(xiàn)的頻率。現(xiàn)以W為權(quán)值，構(gòu)造哈弗曼樹(shù)。哈弗曼的每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符。在哈弗曼樹(shù)的每個(gè)結(jié)點(diǎn)到其左孩子的邊上標(biāo)上0，到其右孩子的邊上標(biāo)上1。將從根的每個(gè)葉子的路徑上的數(shù)碼連接起來(lái)，就是該

19、葉子所代表的字符編碼。</p><p>　　因此，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹(shù)，此構(gòu)造過(guò)程稱(chēng)為哈夫曼編碼。</p><p><b>　　3.哈弗曼譯碼</b></p><p>　　譯碼過(guò)程為：自左向右逐一掃描碼文，并從哈弗曼樹(shù)的根開(kāi)始，將掃描得到的二進(jìn)制位串中的相鄰位于哈弗曼樹(shù)上標(biāo)的0，1相匹

20、配，以確定一條從跟到葉子結(jié)點(diǎn)的路徑，一但到達(dá)葉子，則譯出了一個(gè)字符；再回到樹(shù)根，從二進(jìn)制的下一位開(kāi)始繼續(xù)譯碼</p><p>　　4.該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：</p><p>　　從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)；利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件htmTree中讀入），對(duì)給定的n個(gè)字符正文進(jìn)行編碼，并輸出結(jié)果。</p>&l

21、t;p>　　利用已建好的哈夫曼樹(shù)，對(duì)給定的一個(gè)哈夫曼編碼進(jìn)行譯碼，判斷此編碼對(duì)應(yīng)的字符，并輸出結(jié)果。</p><p><b>　　二.設(shè)計(jì)的總體框架</b></p><p>　　第四章.詳細(xì)算法與設(shè)計(jì)</p><p><b>　　一．實(shí)現(xiàn)算法流程圖</b></p><p>　　1.建立Huff

22、manTree</p><p>　　void HaffmanTree::Haffman(int weight[],HaffmanTree HT[])</p><p>　　查找哈夫曼鏈表中兩個(gè)權(quán)值最小的節(jié)點(diǎn)： </p><p><b>　　創(chuàng)建哈弗曼樹(shù)</b></p><p>　　2.哈夫曼編碼和譯碼（略）</p&

23、gt;<p>　　二．哈夫曼編碼的算法 </p><p>　　給定字符集的哈夫曼樹(shù)生成后，求哈夫曼編碼的具體實(shí)現(xiàn)過(guò)程是：依次以葉子T[i](0≤i≤n-1)為出發(fā)點(diǎn)，向上回溯至根為止。</p><p>　　上溯時(shí)走左分支則生成代碼0，走右分支則生成代碼1。 </p><p><b>　　注意： </b></p>&l

24、t;p>　　① 由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個(gè)臨時(shí)向量中，并設(shè)一個(gè)指針start指示編碼在</p><p>　　該向量中的起始位置（start初始時(shí)指示向量的結(jié)束位置）。 </p><p>　?、?當(dāng)某字符編碼完成時(shí)，從臨時(shí)向量的start處將編碼復(fù)制到該字符相應(yīng)的位串bits中即可。 </p><p>　?、?因?yàn)樽址?/p>

25、大小為n，故變長(zhǎng)編碼的長(zhǎng)度不會(huì)超過(guò)n，加上一個(gè)結(jié)束符'\0'，bits的大小應(yīng)為n+1。 </p><p>　?。?）字符集編碼的存儲(chǔ)結(jié)構(gòu)及其算法描述 </p><p>　　typedef struct { </p><p>　　char ch； //存儲(chǔ)字符 </p><p>　　char bits[n+1]； //存放編碼

26、位串 </p><p>　　}CodeNode； </p><p>　　typedef CodeNode HuffmanCode[n]； </p><p>　　void CharSetHuffmanEncoding(HuffmanTree T，HuffmanCode H) </p><p>　　{//根據(jù)哈夫曼樹(shù)T求哈夫曼編碼表H </

27、p><p>　　int c，p，i;//c和p分別指示T中孩子和雙親的位置 </p><p>　　char cd[n+1]； //臨時(shí)存放編碼 </p><p>　　int start； //指示編碼在cd中的起始位置 </p><p>　　cd[n]='\0'； //編碼結(jié)束符 </p><p>　　fo

28、r(i=0，i<n，i++){ //依次求葉子T[i]的編碼 </p><p>　　H[i].ch=getchar()；//讀入葉子T[i]對(duì)應(yīng)的字符 </p><p>　　start=n； //編碼起始位置的初值 </p><p>　　c=i； //從葉子T[i]開(kāi)始上溯 </p><p>　　while((p=T[c].parent

29、)>=0){//直至上溯到T[c]是樹(shù)根為止 </p><p>　　//若T[c]是T[p]的左孩子，則生成代碼0；否則生成代碼1 </p><p>　　cd[--start]=(T[p).1child==C)?'0'：'1'； </p><p>　　c=p； //繼續(xù)上溯 </p><p><b&

30、gt;　　} </b></p><p>　　strcpy(H[i].bits，&cd[start])； //復(fù)制編碼位串 </p><p>　　}//endfor </p><p>　　}//CharSetHuffmanEncoding</p><p>　　三．文件的編碼和解碼 （略）</p><p&g

31、t;　　第五章．程序調(diào)試與運(yùn)行結(jié)果</p><p><b>　　運(yùn)行結(jié)果圖：</b></p><p><b>　　運(yùn)行結(jié)果分析：</b></p><p>　　通過(guò)調(diào)試發(fā)現(xiàn)該程序滿(mǎn)足哈弗曼樹(shù)，哈弗曼編碼的基本要求，滿(mǎn)足課程設(shè)計(jì)任務(wù)的基本功能與要求。但是，該程序還是有所欠缺和不足，不能通過(guò)編碼譯出電文。在以后的學(xué)習(xí)中希望能將其

32、實(shí)現(xiàn)，使程序變得更完善。</p><p>　　第六章．課程設(shè)計(jì)總結(jié)</p><p>　　通過(guò)一周的課程設(shè)計(jì)使我對(duì)哈夫曼樹(shù)以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。</p><p>　　通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)和課程設(shè)計(jì)的學(xué)習(xí)，使我們能夠以問(wèn)題求解方法、程序設(shè)計(jì)方法以及一些典型的數(shù)據(jù)結(jié)構(gòu)算法為研究對(duì)象，分析數(shù)據(jù)對(duì)象的特征，掌握數(shù)

33、據(jù)組織的方法和在計(jì)算機(jī)中的表示方法，為數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及相應(yīng)的處理算法，使我們初步掌握了算法的時(shí)間、空間復(fù)雜度的分析技巧，并逐步培養(yǎng)了良好的程序設(shè)計(jì)風(fēng)格以及進(jìn)行復(fù)雜程序設(shè)計(jì)的技能。數(shù)據(jù)結(jié)構(gòu)一科的重要內(nèi)容和主要難點(diǎn)是讓我們理解、習(xí)慣和熟悉算法構(gòu)造性思維方法。</p><p>　　在課設(shè)過(guò)程中，我深刻認(rèn)識(shí)到算法的邏輯性對(duì)程序的重要影響，算法的準(zhǔn)確度對(duì)程序運(yùn)行結(jié)果的重要影響，構(gòu)建最小代價(jià)生成樹(shù)時(shí)，一個(gè)

34、細(xì)微的循環(huán)控量的錯(cuò)誤都能影響到程序的正確性，而所有的代碼機(jī)制都是為一個(gè)目標(biāo)的實(shí)現(xiàn)而運(yùn)作的，所以，細(xì)致是實(shí)現(xiàn)算法和程序準(zhǔn)確性必不可少的。</p><p>　　許多的錯(cuò)誤讓我明白了一個(gè)道理---細(xì)心是非常重要的。同時(shí)，對(duì)于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。請(qǐng)教老師也很重要，因?yàn)楫吘刮覀兪切率郑瑢?duì)于某些問(wèn)題很難弄清楚。而且，某些錯(cuò)誤對(duì)于我們來(lái)說(shuō)有時(shí)候想半天都弄不來(lái)，

35、但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。</p><p>　　做課程設(shè)計(jì)不僅讓我修補(bǔ)了以前學(xué)習(xí)的漏洞，也讓我知道一個(gè)道理：編程需要興趣和實(shí)際動(dòng)手。這應(yīng)該可以借鑒在老師的教學(xué)工作上。創(chuàng)新思維至關(guān)重要，這不僅能讓我們寫(xiě)出精簡(jiǎn)的代碼，也有助于開(kāi)發(fā)出高效的程序。</p><p><b>　　第七章.參考文獻(xiàn)</b></p><p>　?。?］

36、《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），劉大有等，高等教育出版社</p><p>　　［2］《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），嚴(yán)蔚敏等，清華大學(xué)出版社</p><p>　　［3］《C語(yǔ)言程序設(shè)計(jì)》（第二版），譚浩強(qiáng)、張溫基等編著，高等教育出版社</p><p>　?。?］《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》，蘇仕華等，機(jī)械工業(yè)出版社</p><p>　　［5］《C++面向?qū)ο蟪绦?/p>

37、設(shè)計(jì)》，譚浩強(qiáng)編著，清華出版社，中國(guó)鐵道出版社</p><p>　　［6］《C程序設(shè)計(jì)語(yǔ)言》，徐寶文 李志等著，機(jī)械工業(yè)出版社</p><p>　?。?］《C和指針》，徐波譯，人民郵電出版社</p><p>　?。?］《C陷阱與缺陷》，高巍譯，人民郵電出版社</p><p>　?。?］《C專(zhuān)家編程》，徐波譯，人民郵電出版社</p>

38、<p>　?。?0］《實(shí)用C語(yǔ)言編程》，郭大海譯，中國(guó)電力出版社</p><p>　　［11］《C語(yǔ)言核心技術(shù)》，蔡學(xué)鏞譯，機(jī)械工業(yè)出版社</p><p><b>　　第八章．附錄</b></p><p><b>　　源程序：</b></p><p>　　#include<ios

39、tream></p><p>　　#include<iomanip></p><p>　　#include<string></p><p>　　using namespace std;</p><p>　　const int MaxValue = 10000;</p><p>　　cla

40、ss HaffmanTree</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　HaffmanTree(int n);</p><p>　　HaffmanTree();</p><p>　　~HaffmanTree

41、();</p><p>　　void Haffman(int weight[],HaffmanTree HT[]);</p><p>　　void HaffmanCode(HaffmanTree haffTree[],HaffmanTree HaffCode[],char ch[],string s);</p><p><b>　　private:<

42、/b></p><p>　　int weight;//權(quán)值</p><p>　　int flag;//標(biāo)記</p><p>　　int parent;//雙親結(jié)點(diǎn)下標(biāo)</p><p>　　int leftChild;//左孩子下標(biāo)</p><p>　　

43、int rightChild;//右孩子下標(biāo)</p><p>　　int bit[6]; //數(shù)組</p><p>　　int start;//編碼的起始下標(biāo)</p><p><b>　　int N;</b></p><p><b>　　};</b>

44、</p><p>　　HaffmanTree::HaffmanTree(int n)</p><p><b>　　{</b></p><p><b>　　N=n;</b></p><p><b>　　}</b></p><p>　　HaffmanTree

45、::HaffmanTree()</p><p><b>　　{</b></p><p><b>　　}</b></p><p>　　HaffmanTree::~HaffmanTree()</p><p><b>　　{</b></p><p><

46、;b>　　}</b></p><p>　　void HaffmanTree::Haffman(int weight[],HaffmanTree HT[])</p><p><b>　　{</b></p><p>　　int j, m1, m2, x1, x2;</p><p>　　//哈夫曼樹(shù)haffT

47、ree初始化。n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)</p><p>　　for(int i = 0; i < 2 * N - 1 ; i++)</p><p><b>　　{</b></p><p>　　if(i < N) HT[i].weight = weight[i];</p><p>　　else

48、 HT[i].weight = 0;</p><p>　　HT[i].parent = 0;</p><p>　　HT[i].flag = 0;</p><p>　　HT[i].leftChild = -1;</p><p>　　HT[i].rightChild = -1;</p><p><b>

49、　　}</b></p><p>　　//構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉結(jié)點(diǎn)</p><p>　　for(i = 0;i < N-1;i++)</p><p><b>　　{</b></p><p>　　m1 = m2 = MaxValue;</p><p>　　x1

50、= x2 = 0;</p><p>　　for(j = 0; j < N+i;j++)</p><p><b>　　{</b></p><p>　　if(HT[j].weight < m1 && HT[j].flag == 0)</p><p><b>　　{</b>&l

51、t;/p><p><b>　　m2 = m1;</b></p><p><b>　　x2 = x1;</b></p><p>　　m1 = HT[j].weight;</p><p><b>　　x1 = j;</b></p><p><b>　　

52、}</b></p><p>　　else if(HT[j].weight < m2 && HT[j].flag == 0)</p><p><b>　　{</b></p><p>　　m2 = HT[j].weight;</p><p><b>　　x2 = j;</b&

53、gt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//將找出的兩棵權(quán)值最小的子樹(shù)合并為一棵子樹(shù)</p><p>　　HT[x1].parent = N+i; </p><p>　　HT[x2].parent =

54、 N+i;</p><p>　　HT[x1].flag = 1;</p><p>　　HT[x2].flag = 1;</p><p>　　HT[N+i].weight = HT[x1].weight+HT[x2].weight;</p><p>　　HT[N+i].leftChild = x1;</p><p

55、>　　HT[N+i].rightChild = x2;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void HaffmanTree::HaffmanCode(HaffmanTree haffTree[], HaffmanTree HaffCode[],char

56、 ch[],string s)</p><p><b>　　{</b></p><p>　　int child, parent;</p><p>　　string cs;</p><p>　　for(int i = 0; i < N; i++)</p><p><b>　　{&

57、lt;/b></p><p>　　start = N-1;//不等長(zhǎng)編碼的最后一位為n-1</p><p>　　weight = haffTree[i].weight;//取得編碼對(duì)應(yīng)權(quán)值的字符</p><p>　　child = i;</p><p>　　parent = haffTree[child].parent;&l

58、t;/p><p>　　//由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)</p><p>　　while(parent != 0)</p><p><b>　　{</b></p><p>　　if(haffTree[parent].leftChild == child)</p><p>　　bit[start] = 0;

59、//左孩子結(jié)點(diǎn)編碼0</p><p>　　else</p><p>　　bit[start] = 1;//右孩子結(jié)點(diǎn)編碼1</p><p><b>　　start--;</b></p><p>　　child = parent;</p><p>　　parent = ha

60、ffTree[child].parent;</p><p><b>　　}</b></p><p>　　//保存葉結(jié)點(diǎn)的編碼和不等長(zhǎng)編碼的起始位</p><p>　　for(int j = start+1; j < N; j++) </p><p>　　HaffCode[i].bit[j] = bit[j];<

61、;/p><p>　　HaffCode[i].start = start;</p><p>　　HaffCode[i].weight = weight;//記住編碼對(duì)應(yīng)權(quán)值的字符</p><p><b>　　}</b></p><p>　　cout<<setw(16)<<"權(quán)值"

62、;<<setw(11)<<"編碼"<<endl;</p><p>　　for(i = 0; i < N; i++)</p><p><b>　　{</b></p><p>　　cout<<setw(5)<<ch[i]<<setw(10)<&l

63、t;HaffCode[i].weight<<setw(10);</p><p>　　for(int j = HaffCode[i].start+1; j < N; j++)</p><p>　　cout << HaffCode[i].bit[j];</p><p>　　cout << endl;</p><

64、;p><b>　　}</b></p><p>　　system("pause");</p><p>　　cout<<"進(jìn)行譯碼：";</p><p>　　for(i=0;i<s.size();i++)</p><p><b>　　{</b&g

65、t;</p><p>　　for(int j=0;j<N;j++)</p><p><b>　　{</b></p><p>　　if(s[i]==ch[j])</p><p>　　for(int m = HaffCode[j].start+1; m < N; m++)</p><p>

66、　　cout << HaffCode[j].bit[m];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><

67、p>　　void main(void)</p><p><b>　　{</b></p><p><b>　　int m,q;</b></p><p><b>　　char p;</b></p><p>　　string str,ch;</p><p&g

68、t;　　cout<<"請(qǐng)輸入權(quán)值個(gè)數(shù)：";</p><p><b>　　cin>>m;</b></p><p>　　int weight[26];</p><p>　　char node[26];</p><p>　　for(int i=0;i<m;++i)</p&

69、gt;<p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)字符：";</p><p><b>　　cin>>p;</b></p><p>　　node[i]=p;</p>

70、;<p>　　cout<<" 請(qǐng)輸入權(quán)值：";</p><p><b>　　cin>>q;</b></p><p>　　weight[i]=q;</p><p>　　}system("pause");</p><p>　　cout&l

71、t;<"請(qǐng)輸入電文（注意電文必須只包含以上字符）：";</p><p><b>　　cin>>str;</b></p><p>　　HaffmanTree h(m);</p><p>　　HaffmanTree *myHaffTree = new HaffmanTree[2*m+1];</p>

72、<p>　　HaffmanTree *myHaffCode = new HaffmanTree[m];</p><p>　　h.Haffman(weight , myHaffTree);</p><p>　　h.HaffmanCode(myHaffTree, myHaffCode,node,str);</p><p><b>　　}</b