赫夫曼編譯碼器數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、<p><b>　　赫夫曼編\譯碼器</b></p><p>　　摘要 本次課程設(shè)計(jì)過程中我主要根據(jù)課本中的實(shí)現(xiàn)思想及算法編寫程序，體現(xiàn)以課本知識(shí)的應(yīng)用為主，在學(xué)習(xí)了線性表、棧、隊(duì)列、二叉樹、樹和圖等結(jié)構(gòu)的基礎(chǔ)上，以能夠更加熟練的應(yīng)用所學(xué)知識(shí)，并能結(jié)合一些著名算法來實(shí)現(xiàn)對(duì)一些實(shí)際問題的應(yīng)用，例如，赫夫曼樹等，從而更為深刻理解數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵，熟悉它們各自的應(yīng)用場(chǎng)合及方法。有些在平時(shí)課

2、程中并沒有掌握的內(nèi)容在這次課程設(shè)計(jì)中都是先通過看課本學(xué)懂了，然后再在課程設(shè)計(jì)中加深印象，實(shí)現(xiàn)算法的應(yīng)用和擴(kuò)展。這次課程設(shè)計(jì)的設(shè)計(jì)內(nèi)容主要是通過實(shí)際的例子和程序來實(shí)現(xiàn)課本中所學(xué)習(xí)的算法的應(yīng)用。程序設(shè)計(jì)設(shè)計(jì)語言采用C++,程序運(yùn)行平臺(tái)為Windows XP。</p><p>　　赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹，然后利用建好的赫夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。</p><p>　　

3、赫夫曼編譯系統(tǒng)分為五個(gè)功能模塊：原始數(shù)據(jù)載入，打印編碼規(guī)則、編碼、譯碼。以二叉樹的應(yīng)用為基礎(chǔ)，包括統(tǒng)計(jì)信息，并通過構(gòu)建赫夫曼樹、對(duì)信息進(jìn)行赫夫曼編碼，將編碼信息等存入文檔。</p><p>　　關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 棧和隊(duì)列 赫夫曼樹 赫夫曼編碼 </p><p><b>　　目錄</b></p><p>　　1引言…………………………………………

4、……………………………………….1</p><p>　　1.1課程設(shè)計(jì)目的……………………………………………………………….1 </p><p>　　1.2課程設(shè)計(jì)背景……………………………………………………………….1</p><p>　　1.3課程設(shè)計(jì)主要內(nèi)容………………………………………………………….1</p><p>　　

5、2需求分析…………………………………………………………………………….3</p><p>　　3 概要設(shè)計(jì)…………………………………………………………………………....4</p><p>　　3.1 設(shè)計(jì)思想……………………………………………………………………4</p><p>　　3.2 函數(shù)間的關(guān)系………………………………………………………………4</p

6、><p>　　3.3數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)………………………………………………………4</p><p>　　4詳細(xì)設(shè)計(jì)…………………………………………………………………………….6</p><p>　　4.1 赫夫曼的主要結(jié)構(gòu)…………………………………………………………..6</p><p>　　5 調(diào)試分析……………………………………………………

7、……………………..8</p><p>　　6 測(cè)試并列出測(cè)試結(jié)果……………………………………………………………..9</p><p>　　6.1 測(cè)試方式 ……………………………………………………………………9</p><p>　　6.2 測(cè)試結(jié)果……………………………………………………………………..9</p><p>　　7 總結(jié)…

8、……………………………………………………………………………13</p><p>　　致謝…………………………………………………………………………………..14</p><p>　　參考文獻(xiàn)……………………………………………………………………………..14</p><p>　　附錄…………………………………………………………………………………..15</p>

9、;<p><b>　　1 引言</b></p><p>　　當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，處理和傳輸?shù)臄?shù)據(jù)量越來越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。從而產(chǎn)生了哈夫曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過程稱為解碼。</p><p>　　樹狀

10、結(jié)構(gòu)簡(jiǎn)稱為樹，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。</p><p>　　1.1 課程設(shè)計(jì)目的</p><p>　　本課程設(shè)計(jì)是為了讓同學(xué)們了解數(shù)據(jù)結(jié)構(gòu)的作用和意義。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、計(jì)算機(jī)信息管理與應(yīng)用專業(yè)和電子商務(wù)的專業(yè)的基礎(chǔ)課，是十分重要的課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此

11、，想要更好地運(yùn)用計(jì)算機(jī)來解決實(shí)際問題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語言是難以應(yīng)付當(dāng)前眾多復(fù)雜的課題，想要有效地使用計(jì)算機(jī)，充分發(fā)揮它的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，打好數(shù)據(jù)結(jié)構(gòu)這門課的扎實(shí)基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、軟件工程、編譯原理、人工智能等十分有益。</p><p>　　1.2 課程設(shè)計(jì)背景</p><p>　　當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，

12、處理和傳輸?shù)臄?shù)據(jù)量越來越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。從而產(chǎn)生了哈夫曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過程稱為解碼。</p><p>　　樹狀結(jié)構(gòu)簡(jiǎn)稱為樹，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。</p><p>　　

13、在這信息量發(fā)達(dá)的時(shí)代，隨著社會(huì)的進(jìn)步，信息不斷地增多和更新，為了使信息更加快速、準(zhǔn)確有的傳遞。需要一個(gè)程序來完成。 </p><p>　　1.3課程設(shè)計(jì)主要內(nèi)容</p><p>　　本課程設(shè)計(jì)要求完成發(fā)送端對(duì)待傳送數(shù)據(jù)的編碼和接收端對(duì)傳送來的數(shù)據(jù)的譯碼。要實(shí)現(xiàn)五個(gè)功能:接受原始數(shù)據(jù)、編碼、譯碼、打印編碼規(guī)則、將編碼、譯碼存檔。通過系統(tǒng)的提示要建立哈夫曼樹并對(duì)載入的原文件進(jìn)行編碼，并保存到t

14、xtfile.txt文件中，同時(shí)輸出到屏幕。最后將建立的赫夫曼樹用某種樹的儲(chǔ)存方式儲(chǔ)存后輸出。</p><p><b>　　2 需求分析</b></p><p>　　一套完整的編碼譯碼系統(tǒng)應(yīng)該具有以下功能：</p><p>　?。?）I：初始化（initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹。并將

15、他存于文件hfmtree.txt中。</p><p>　　(2)E：編碼（encoding）。利用已經(jīng)建立好的赫夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入），對(duì)文件tobetree.txt中的正文進(jìn)行編碼。然后將結(jié)果存入文件codefile.txt文件中。</p><p>　　(3)D：譯碼（decoding）。利用已經(jīng)建立好的赫夫曼樹將文件codefile.txt中的代碼進(jìn)

16、行譯碼，將結(jié)果存入文件textfile.txt中。</p><p>　　（4）P：印代碼文件（print）。將文件codefile.txt以緊湊格式顯示在終端上。每行50個(gè)代碼。同時(shí)將字符形式的編碼文件寫入到文件codeprin.txt中。</p><p>　?。?）T：印赫夫曼樹（treeprint）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的赫

17、夫曼樹寫入文件treeprin.txt中。</p><p><b>　　3 概要設(shè)計(jì)</b></p><p><b>　　3.1 設(shè)計(jì)思想</b></p><p>　　赫夫曼樹用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，借助靜態(tài)鏈表來實(shí)現(xiàn)遍歷。</p><p>　　3.2 函數(shù)間的關(guān)系</p><p

18、>　　函數(shù)間的關(guān)系如圖3.1所示：</p><p>　　圖3.1 函數(shù)間的關(guān)系</p><p>　　3.3 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)</p><p>　　赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹，然后利用建好的赫夫曼樹生成赫夫曼編碼后進(jìn)行譯碼 。</p><p>　　在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，

19、稱之為編碼。構(gòu)造一棵赫夫曼樹，規(guī)定赫夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱之為赫夫曼編碼。</p><p>　　最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。赫夫曼樹課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。</p>

20、;<p>　　其主要流程圖如圖3.2所示。</p><p>　　圖3.2 赫夫曼樹編\譯碼器流程圖</p><p><b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　赫夫曼樹編、譯碼設(shè)計(jì)功能如下：</p><p>　　1．赫夫曼樹抽象數(shù)據(jù)類型定義</p><p>　　ADT H

21、uffmanCoding{</p><p>　　數(shù)據(jù)對(duì)象T：具有相同特性的數(shù)據(jù)元素的集合</p><p>　　數(shù)據(jù)關(guān)系R：滿足最優(yōu)二叉樹的關(guān)系</p><p><b>　　基本操作P：</b></p><p><b>　　Init（&t）</b></p><p>　　

22、操作結(jié)果：構(gòu)造一個(gè)空赫夫曼樹t。</p><p><b>　　encode()</b></p><p>　　操作結(jié)果：利用赫夫曼樹進(jìn)行編碼</p><p><b>　　Decode（）</b></p><p>　　操作結(jié)果：利用赫夫曼樹進(jìn)行譯碼</p><p><b&g

23、t;　　}</b></p><p><b>　　2. 主函數(shù)</b></p><p>　　Void mian（）</p><p><b>　　{打印表頭；</b></p><p>　　While(選擇項(xiàng)不為q){</p><p><b>　　輸入選擇項(xiàng)；

24、</b></p><p>　　Switch(選擇項(xiàng))</p><p>　　{Case i： 初始化；break;</p><p>　　Case w： 輸入要編碼的字符； break；</p><p>　　Case e： 編碼字符； break；</p><p>　　Case d； 譯碼操作；break；&

25、lt;/p><p>　　Case p； 打印代碼；break；</p><p>　　Case t； 打印赫夫曼樹； break；</p><p>　　Default：輸入錯(cuò)誤，重新選擇；</p><p><b>　　}</b></p><p>　　3. 求赫夫曼編碼[5]</p><

26、;p>　　if(t[j].weight<k&&t[j].parent==0)</p><p>　　k=t[j].weight,flag=j; //flag為標(biāo)志符，為不小于可能的值</p><p>　　t[flag].parent=1;</p><p><b>　　4. 建赫夫曼樹</b></p>&

27、lt;p>　　HT[s1].parent=HT[s2].parent=i;//將選好的兩個(gè)結(jié)點(diǎn)設(shè)置成有同一個(gè)雙親結(jié)點(diǎn)</p><p>　　HT[i].lchild=s1;//左孩子的權(quán)值</p><p>　　HT[i].rchild=s2;//右孩子的權(quán)值</p><p>　　HT[i].weight=HT[s1].weight+HT[s2].weight;/

28、/將兩個(gè)權(quán)值相加作為新的權(quán)值</p><p><b>　　}</b></p><p>　　HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//為赫夫曼代碼分配空間</p><p>　　5. 將赫夫曼編碼寫入文件</p><p>　　用fputs(HC[i],htmTree); fp

29、uts(r,htmTree);fclose(htmTree) 這些函數(shù)來實(shí)現(xiàn)編碼寫入文件;</p><p>　　6. 完成譯碼功能并將譯碼寫入文件</p><p>　　因?yàn)楹辗蚵鼧浣ê煤笫亲蠛⒆咏Y(jié)點(diǎn)旁標(biāo)上0，右孩子結(jié)點(diǎn)上標(biāo)上1</p><p>　　所以碰到1是用左孩子結(jié)點(diǎn)，2是用右孩子結(jié)點(diǎn)，可以用條件語句來實(shí)現(xiàn)。</p><p>　　if(i

30、2=='0') m=HT[m].lchild;</p><p>　　if(i2=='1') m=HT[m].rchild;</p><p>　　fputs(outext,txtfile);//將譯碼寫入文件</p><p><b>　　5 調(diào)試分析</b></p><p>　　1．本程序

31、要執(zhí)行首先要初始化一個(gè)赫夫曼樹，按照用戶設(shè)定的字符集大小，輸入每個(gè)字符及其對(duì)應(yīng)的出現(xiàn)概率即權(quán)值。分別存放在w和z這兩個(gè)變量中。再利用這兩個(gè)變量構(gòu)造赫夫曼樹。</p><p>　　2．執(zhí)行輸入字符命令時(shí)，程序?qū)⒂脩糨斎氲淖址嫒胛募obetran.txt中。以便執(zhí)行下一步編碼操作時(shí)自己從文件調(diào)用。</p><p>　　3．編碼時(shí)，程序直接從tobetran.txt中讀取字符，依次和字符數(shù)組

32、變量z中元素項(xiàng)比較，找到之后，將編碼表HC中對(duì)應(yīng)編號(hào)的代碼添加到分配的工作區(qū)間中，全部字符編碼完成后將代碼寫入文件codefile.txt中。</p><p>　　4．譯碼時(shí)，程序從codefile中讀取代碼，按照代碼從樹根開始向葉子節(jié)點(diǎn)查找對(duì)應(yīng)的字符，直到全部代碼譯碼完成，再將譯好的字符寫入文件txtfile.txt中</p><p>　　5．打印編碼操作，即從codefile.txt中

33、讀取代碼，按要求輸出到屏幕上。</p><p>　　6 測(cè)試并列出測(cè)試結(jié)果</p><p><b>　　6.1 測(cè)試方式 </b></p><p>　　1．程序運(yùn)行環(huán)境為DOS，執(zhí)行文件為：胡江英的程序設(shè)計(jì).exe</p><p>　　2．程序運(yùn)行后，出現(xiàn)的界面如圖6.1所示：</p><p>

34、<b>　　圖6.1 界面圖</b></p><p>　　3．首先須進(jìn)行初始化，按“i”執(zhí)行，輸入字符集數(shù)，對(duì)應(yīng)的字符和權(quán)值，初始化赫夫曼樹。然后才能進(jìn)行后續(xù)的操作。</p><p>　　4．選擇“w”，輸入要編碼的字符。</p><p>　　5．選擇“e”，對(duì)剛輸入的字符進(jìn)行編碼。</p><p>　　6．選擇“d”，

35、對(duì)剛編碼出的代碼再譯碼回去。</p><p>　　7．選擇“p”，打印編碼出的代碼。</p><p>　　8．選擇“t”，代印赫夫曼樹</p><p>　　9．選擇“q”，退出程序。</p><p><b>　　6.2 測(cè)試結(jié)果</b></p><p>　　1.初始化的內(nèi)容如表6.1所示：<

36、/p><p>　　表6.1 初始化的內(nèi)容</p><p>　　2.初始化的結(jié)果如圖6.2所示:</p><p>　　圖6.2 初始化的結(jié)果</p><p>　　3.將字符對(duì)應(yīng)編碼寫入htmtree.txt,如圖6.3所示：</p><p>　　圖6.3 將字符寫入文件</p><p>　　4.字符對(duì)

37、應(yīng)的編碼如圖6.4所示：</p><p>　　圖6.4 字符對(duì)應(yīng)的編碼</p><p>　　5.輸入要編碼的字符如圖6.5所示：</p><p>　　圖6.5 要編碼的字符</p><p>　　6.譯碼：文件textfile.txt中內(nèi)容：</p><p>　　THIS PROGRAM IS MY FAVORIT<

38、;/p><p>　　其操作如圖6.6所示：</p><p><b>　　圖6.6 譯碼操作</b></p><p>　　7.打印赫夫曼樹如圖6.7所示：</p><p><b>　　圖6.7 赫夫曼樹</b></p><p><b>　　7 總 結(jié)</b>

39、;</p><p>　　通過將近兩周的課設(shè)練習(xí)，認(rèn)識(shí)到知識(shí)的遷移運(yùn)用，理論應(yīng)用實(shí)際和相互間的密切聯(lián)系，感受到理論知識(shí)的重要，在今后的學(xué)習(xí)中一定會(huì)更加努力，認(rèn)真。</p><p>　　體會(huì)到自己知識(shí)有所缺乏，和個(gè)人能力的有限，只有通過同學(xué)、老師間的密切配合才能完成一項(xiàng)不錯(cuò)的工作。</p><p>　　從中也體會(huì)到了學(xué)習(xí)中的樂趣，可以自由的創(chuàng)作自己喜歡的東西并自己調(diào)試。

40、</p><p><b>　　致 謝</b></p><p>　　在課程設(shè)計(jì)過程中遇到了很多問題，不過在xx老師和和同學(xué)們的幫助下大部分都得以解決，首先要對(duì)他們表示感謝。同時(shí)，我們也要感謝學(xué)校為我們提供了大量的圖書，通過看書我們也學(xué)到了很多課堂上學(xué)不到的東西。通過此次課程設(shè)計(jì)我最大的收獲是學(xué)會(huì)了自主學(xué)習(xí)，也增加了與老師和同學(xué)們的交往、增進(jìn)了相互之間的感情。</

41、p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語言版. 北京：清華大學(xué)出版社,1997</p><p>　　[2]王昆侖,李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國(guó)鐵道出版社 </p><p>　　[3]周靄如，林偉健.C++程序設(shè)計(jì)基礎(chǔ). 北京：電子工業(yè)出版社, 2005</

42、p><p>　　[4]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu). 北京：高等教育出版社, 2005</p><p>　　[5] 王衛(wèi)東. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)課. 西安: 電子科技大學(xué)出版社, 2001年</p><p>　　[6] 趙文靜. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo). 西安：交通大學(xué)出版社, 1999年</p><p><b>　　附錄：</b></p>

43、<p>　　#include <iostream.h></p><p>　　#include <iomanip.h></p><p>　　#include <string.h></p><p>　　#include <malloc.h></p><p>　　#include <

44、;stdio.h></p><p>　　//typedef int TElemType;</p><p>　　const int UINT_MAX=1000;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int weight

45、; //權(quán)值</p><p>　　int parent,lchild,rchild; //父節(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)</p><p>　　}HTNode,* HuffmanTree;</p><p>　　typedef char **HuffmanCode;</p><p>　　//--------

46、---全局變量-----------------------</p><p>　　HuffmanTree HT; //代表赫夫曼樹</p><p>　　HuffmanCode HC; //代表赫夫曼編碼</p><p>　　int *w,i,j,n;</p><p><b&

47、gt;　　char *z;</b></p><p>　　int flag=0;</p><p>　　int numb=0;</p><p>　　// -----------------求赫夫曼編碼-----------------------</p><p>　　void line()</p><p>　　

48、{cout<<"\n--------------------------------------------------\n";}</p><p>　　int min(HuffmanTree t,int i)</p><p><b>　　{ </b></p><p>　　int j,flag;</p>

49、<p>　　int k=UINT_MAX; // 取k為不小于可能的值</p><p>　　for(j=1;j<=i;j++)</p><p>　　if(t[j].weight<k&&t[j].parent==0)</p><p>　　k=t[j].weight,flag=j;</p><p>　　t

50、[flag].parent=1;</p><p>　　return flag; //返回標(biāo)識(shí)符</p><p><b>　　}</b></p><p>　　//------------------------------------------</p><p>　　void select(HuffmanTree

51、t,int i,int &s1,int &s2)</p><p><b>　　{ </b></p><p><b>　　int j;</b></p><p>　　s1=min(t,i);</p><p>　　s2=min(t,i);</p><p>　　if(

52、s1>s2)// s1為最小的兩個(gè)值中序號(hào)小的那個(gè)</p><p><b>　　{</b></p><p><b>　　j=s1;</b></p><p><b>　　s1=s2;</b></p><p><b>　　s2=j;</b></p&

53、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)</p><p><b>　　{</b><

54、;/p><p>　　int m,i,s1,s2,start;</p><p><b>　　int c,f;</b></p><p>　　HuffmanTree p;</p><p><b>　　char *cd;</b></p><p><b>　　if(n<=1

55、)</b></p><p><b>　　return;</b></p><p><b>　　m=2*n-1;</b></p><p>　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號(hào)單元未用</p><p>　　for(p=HT+

56、1,i=1;i<=n;++i,++p,++w)</p><p><b>　　{</b></p><p>　　p->weight=*w;</p><p>　　p->parent=0;</p><p>　　p->lchild=0;</p><p>　　p->rchild=

57、0;</p><p><b>　　}</b></p><p>　　for(;i<=m;++i,++p)</p><p>　　p->parent=0;</p><p>　　for(i=n+1;i<=m;++i) // 建赫夫曼樹</p><p><b>　　{ </

58、b></p><p>　　select(HT,i-1,s1,s2);</p><p>　　HT[s1].parent=HT[s2].parent=i;</p><p>　　HT[i].lchild=s1;</p><p>　　HT[i].rchild=s2;</p><p>　　HT[i].weight=HT[s

59、1].weight+HT[s2].weight;</p><p><b>　　}</b></p><p>　　HC=(HuffmanCode)malloc((n+1)*sizeof(char*));</p><p>　　cd=(char*)malloc(n*sizeof(char)); </p><p>　　cd[n-1

60、]='\0'; </p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　start=n-1; </p><p>　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)</p>&l

61、t;p>　　// 從葉子到根逆向求編碼</p><p>　　if(HT[f].lchild==c)</p><p>　　cd[--start]='0';</p><p><b>　　else</b></p><p>　　cd[--start]='1';</p><

62、p>　　HC[i]=(char*)malloc((n-start)*sizeof(char));</p><p>　　strcpy(HC[i],&cd[start]); </p><p><b>　　}</b></p><p><b>　　free(cd);</b></p><p>&

63、lt;b>　　}</b></p><p>　　//--------------初始化赫夫曼鏈表---------------------------------</p><p>　　void init()</p><p>　　{ //--------------------------------------------</p>

64、<p><b>　　flag=1;</b></p><p><b>　　int num;</b></p><p><b>　　int num2;</b></p><p>　　cout<<"下面初始化赫夫曼鏈表"<<endl<<&qu

65、ot;請(qǐng)輸入結(jié)點(diǎn)的個(gè)數(shù)n：";</p><p><b>　　cin>>num;</b></p><p><b>　　n=num;</b></p><p><b>　　line();</b></p><p>　　w=(int*)malloc(n*sizeof

66、(int));//weight</p><p>　　z=(char*)malloc(n*sizeof(char));//word</p><p>　　cout<<"\n請(qǐng)依次輸入"<<n<<"個(gè)字符(字符型)\n注意:必須以回車結(jié)束："<<endl;</p><p>　　char

67、 temp[2];</p><p><b>　　line();</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　cout<<"第"<<i+1<<"個(gè)字符:

68、"<<endl;</p><p>　　gets(temp);</p><p>　　*(z+i)=*temp;</p><p><b>　　}</b></p><p><b>　　line();</b></p><p>　　for(i=0;i<=n-

69、1;i++)</p><p><b>　　{</b></p><p>　　cout<<setw(6)<<*(z+i);</p><p><b>　　}</b></p><p><b>　　line();</b></p><p>　

70、　cout<<"\n請(qǐng)依次輸入"<<n<<"個(gè)權(quán)值(\n注意:必須以回車結(jié)束)："<<endl;</p><p><b>　　line();</b></p><p>　　for(i=0;i<=n-1;i++)</p><p><b>　　{&

71、lt;/b></p><p>　　cout<<endl<<"第"<<i+1<<"個(gè)字符的權(quán)值:";</p><p>　　cin>>num2;</p><p>　　*(w+i)=num2;</p><p><b>　　}</

72、b></p><p>　　//輸入部分結(jié)束------------------------------------------</p><p>　　HuffmanCoding(HT,HC,w,n);</p><p>　　//------------------------打印編碼----------------------</p><p&g

73、t;<b>　　line();</b></p><p>　　cout<<"字符對(duì)應(yīng)的編碼為:"<<endl;</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　//cout<&l

74、t;"字符"<<*(z+i-1)<<"的編碼";</p><p>　　puts(HC[i]);</p><p><b>　　}</b></p><p>　　//--------------------------將赫夫曼編碼寫入文件---------</p><

75、p><b>　　line();</b></p><p>　　cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"...................."<<endl;</p><p>　　FILE *htmTree;</p><p>　　cha

76、r r[]={' ','\0'}; </p><p>　　if((htmTree=fopen("htmTree.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<"文件打開失敗&qu

77、ot;<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　fputs(z,htmTree);</p><p>　　for(i=0;i<n+1;i++)</p><p><b&g

78、t;　　{</b></p><p>　　fprintf(htmTree,"%6d",*(w+i));</p><p>　　fputs(r,htmTree);</p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><

79、p><b>　　{</b></p><p>　　fputs(HC[i],htmTree);</p><p>　　fputs(r,htmTree);</p><p><b>　　}</b></p><p>　　fclose(htmTree);</p><p>　　cout

80、<<"已將字符與對(duì)應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;</p><p><b>　　}//init</b></p><p>　　//---------------------獲取字符并寫入文件---------------------------------</p>

81、;<p>　　void inputcode() </p><p><b>　　{</b></p><p>　　//cout<<"請(qǐng)輸入你想要編碼的字符"<<endl;</p><p>　　FILE *virttran,*tobetran;</p><p>　

82、　char str[100];</p><p>　　if((tobetran=fopen("tobetran.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<"不能打開文件"<<endl;</p&

83、gt;<p><b>　　return;</b></p><p><b>　　}</b></p><p>　　cout<<"請(qǐng)輸入你想要編碼的字符"<<endl;</p><p>　　gets(str);</p><p>　　fputs(st

84、r,tobetran);</p><p>　　cout<<"獲取字符成功"<<endl;</p><p>　　fclose(tobetran);</p><p><b>　　}</b></p><p>　　//----------------------------------

85、--------------------</p><p>　　void encode() //完成譯碼功能</p><p><b>　　{</b></p><p>　　cout<<"下面對(duì)目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl;</p><

86、;p>　　FILE *tobetran,*codefile;</p><p>　　if((tobetran=fopen("tobetran.txt","rb"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<"不能打開文件"&

87、lt;<endl;</p><p><b>　　}</b></p><p>　　if((codefile=fopen("codefile.txt","wb"))==NULL)</p><p><b>　　{</b></p><p>　　cout<&

88、lt;"不能打開文件"<<endl;</p><p><b>　　}</b></p><p>　　char *tran;</p><p><b>　　i=99;</b></p><p>　　tran=(char*)malloc(100*sizeof(char)); /

89、/為tuan分配100個(gè)字節(jié)</p><p>　　while(i==99)</p><p><b>　　{</b></p><p>　　if(fgets(tran,100,tobetran)==NULL)</p><p><b>　　{</b></p><p>　　cout&

90、lt;<"不能打開文件"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　for(i=0;*(tran+i)!='\0';i++)</p><p><b>　　

91、{</b></p><p>　　for(j=0;j<=n;j++)</p><p><b>　　{</b></p><p>　　if(*(z+j-1)==*(tran+i))</p><p><b>　　{</b></p><p>　　fputs(HC[j]

92、,codefile);</p><p>　　puts(HC[j]);</p><p><b>　　if(j>n)</b></p><p><b>　　{</b></p><p>　　cout<<"字符錯(cuò)誤，無法編碼!"<<endl;</p>

93、;<p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

94、;<p><b>　　}</b></p><p>　　cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;</p><p>　　fclose(tobetran);</p><

95、;p>　　fclose(codefile);</p><p>　　free(tran);</p><p><b>　　}</b></p><p>　　//--------------------------------------------------</p><p>　　void decode()

96、//完成譯碼功能</p><p><b>　　{</b></p><p>　　cout<<"下面對(duì)根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl;</p><p>　　FILE *codef,*txtfile;</p><p>　　if((txtfile=f

97、open("Textfile.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<"不能打開文件"<<endl;</p><p><b>　　}</b></p><

98、p>　　if ((codef=fopen("codefile.txt","r"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<"不能打開文件"<<endl;</p><p><b>　　}</b&

99、gt;</p><p>　　char *tbdc,*outext,i2;</p><p>　　int io=0,i,m;</p><p>　　unsigned long length=10000;</p><p>　　tbdc=(char*)malloc(length*sizeof(char)); //分配空間</p><

100、p>　　fgets(tbdc,length,codef);</p><p>　　outext=(char*)malloc(length*sizeof(char)); //分配空間</p><p><b>　　m=2*n-1;</b></p><p>　　for(i=0;*(tbdc+i)!='\0';i++) //進(jìn)入循

101、環(huán)</p><p><b>　　{</b></p><p>　　i2=*(tbdc+i);</p><p>　　if(HT[m].lchild==0) </p><p><b>　　{</b></p><p>　　*(outext+io)=*(z+m-1);</p>

102、;<p><b>　　io++;</b></p><p><b>　　m=2*n-1;</b></p><p><b>　　i--;</b></p><p><b>　　}</b></p><p>　　else if(i2=='0&#

103、39;) m=HT[m].lchild;</p><p>　　else if(i2=='1') m=HT[m].rchild;</p><p><b>　　}</b></p><p>　　*(outext+io)='\0';</p><p>　　fputs(outext,txtfile);

104、</p><p>　　cout<<"譯碼完成"<<endl<<"內(nèi)容寫入根目錄下的文件txtfile.txt中"<<endl<<endl;</p><p>　　free(tbdc);</p><p>　　free(outext);</p><p&g

105、t;　　fclose(txtfile);</p><p>　　fclose(codef);</p><p><b>　　}</b></p><p>　　//---------------------------------------------</p><p>　　void printcode() //

106、打印代碼</p><p><b>　　{</b></p><p>　　cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl<<"-----------------------------------------------------------------\n"

107、;</p><p>　　FILE * CodePrin,* codefile;</p><p>　　if((CodePrin=fopen("CodePrin.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　cout<<&q

108、uot;不能打開文件"<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　if((codefile=fopen("codefile.txt","r"))==NULL)</p>

109、<p><b>　　{</b></p><p>　　cout<<"不能打開文件"<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　char *

110、work3;</p><p>　　work3=(char*)malloc(51*sizeof(char));</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　if(fgets(work3,51,codefile)==NULL)</p>

111、<p><b>　　{</b></p><p>　　cout<<"不能讀取文件"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　fputs(w

112、ork3,CodePrin);</p><p>　　puts(work3);</p><p>　　}while(strlen(work3)==50);</p><p>　　free(work3);</p><p><b>　　line();</b></p><p>　　cout<<&q

113、uot;打印工作結(jié)束"<<endl<<endl;</p><p>　　fclose(CodePrin);</p><p>　　fclose(codefile);</p><p><b>　　}</b></p><p>　　//------------------------打印赫夫曼樹的

114、函數(shù)----------------------</p><p>　　void coprint(HuffmanTree start,HuffmanTree HT)</p><p>　　{char t=' ';</p><p>　　if(start!=HT)</p><p><b>　　{</b></

115、p><p>　　FILE * TreePrint;</p><p>　　if((TreePrint=fopen("TreePrint.txt","a"))==NULL)</p><p>　　{cout<<"創(chuàng)建文件失敗"<<endl;</p><p><b&

116、gt;　　return;</b></p><p><b>　　} </b></p><p>　　numb++;//該變量為已被聲明為全局變量</p><p>　　coprint(HT+start->rchild,HT);</p><p>　　if(start->lchild!=NULL

117、&&start->rchild!=NULL) t='<';</p><p>　　cout<<setw(5*numb)<<start->weight<<t<<endl; </p><p>　　fprintf(TreePrint,"%d\n",start->weight

118、);</p><p>　　coprint(HT+start->lchild,HT);</p><p><b>　　numb--;</b></p><p>　　fclose(TreePrint);</p><p><b>　　}</b></p><p><b>

119、　　}</b></p><p>　　void printree(HuffmanTree HT,int w) //打印赫夫曼樹</p><p><b>　　{</b></p><p>　　HuffmanTree p;</p><p><b>　　p=HT+w;</b></p>

120、<p>　　cout<<"下面打印赫夫曼樹"<<endl; // 輸出“打印赫夫曼樹”語句</p><p><b>　　line();</b></p><p>　　coprint(p,HT);</p><p><b>　　line();</b></p>

121、<p>　　cout<<"打印工作結(jié)束"<<endl; //輸出“打印工作結(jié)束”</p><p><b>　　}</b></p><p>　　void printhead()</p><p><b>　　{ </b></p><p>　　cout

122、<<"===============================================================================\n";</p><p>　　cout<<"\t數(shù)據(jù)結(jié)構(gòu)\t課程設(shè)計(jì)\t計(jì)-0503 楊天心 29號(hào)\n";</p><p>　　cout&l

123、t;<"-------------------------------------------------------------------------------\n";</p><p>　　cout<<"\n\t\t";</p><p>　　cout<<"┏━━━━━━━━━━━━━━━━━━━━┓\n\

124、t\t";</p><p>　　cout<<"┃ 　　歡迎使用赫夫曼編碼解碼系統(tǒng) 　　　┃\n\t\t";</p><p>　　cout<<"┡━━━━━━━━━━━━━━━━━━━━┩\n\t\t";</p><p>　　cout<<"│　　i.初始化赫夫曼鏈表

125、 │\n\t\t";</p><p>　　cout<<"│　 w.編碼字符 　 　　│\n\t\t";</p><p>　　cout<<"│　　e.編 碼 　 　 　　 │\n\t\t";</p>&l

126、t;p>　　cout<<"│　　d.譯 碼　 　 　　 │\n\t\t";</p><p>　　cout<<"│　　p.打印編碼 　 　　 　 │\n\t\t";</p><p>　　cout<<"│　　t.打印赫夫曼樹　

127、 │\n\t\t";</p><p>　　cout<<"│　　q.退 出 　 　　　 │\n\t\t";</p><p>　　cout<<"└────────────────────┘\n\n";</p><p>　　cout<

128、<"===============================================================================\n";</p><p>　　if(flag==0)cout<<"\n請(qǐng)先初始化赫夫曼鏈表,輸入'i'"<<endl<<"------------

129、--------------------------------\n";</p><p>　　cout<<"請(qǐng)選擇你要進(jìn)行的操作:";</p><p><b>　　}</b></p><p><b>　　/*2．主程序*/</b></p><p>　　voi

130、d main()</p><p><b>　　{</b></p><p>　　char choice;</p><p>　　while(choice!='q')</p><p>　　{ printhead();</p><p>　　cin>>choice;&l

131、t;/p><p>　　switch(choice)</p><p><b>　　{</b></p><p>　　case 'i': </p><p>　　init(); //按下i則進(jìn)行初始化赫夫曼鏈表,</p><p><b>　　br

132、eak;</b></p><p>　　case 'w': //按下w編碼字符</p><p>　　inputcode();</p><p><b>　　break;</b></p><p>　　case 'e': //按下e編碼</p><

133、;p><b>　　encode();</b></p><p><b>　　break;</b></p><p>　　case 'd': //按下d譯碼</p><p><b>　　decode();</b></p><p><b>　　

134、break;</b></p><p>　　case 'p': //按下p打印編碼</p><p>　　printcode();</p><p><b>　　break;</b></p><p>　　case 't': //按下t打印赫夫曼樹</p>

135、;<p>　　printree(HT,2*n-1);</p><p><b>　　break;</b></p><p>　　case 'q': //按下q退出</p><p><b>　　break;</b></p><p><b>　　defau

136、lt:</b></p><p>　　cout<<"輸入錯(cuò)誤，請(qǐng)重新選擇"<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　free(z); //釋放z結(jié)點(diǎn)</p>