學(xué)號(hào)：

個(gè)人資料整理 僅限學(xué)習(xí)使用0120803490117課程設(shè)計(jì)題目Huffman編／譯碼器學(xué)院管理學(xué)院專業(yè)信息管理與信息系統(tǒng)班級(jí)0801姓名王濤指導(dǎo)教師燕翔2018 年 07 月 09 日個(gè)人資料整理 僅限學(xué)習(xí)使用課程設(shè)計(jì)任務(wù)書學(xué)生姓名：

王濤

專業(yè)班級(jí)：

信管

0801指導(dǎo)教師：

燕翔

工作單位：

管理學(xué)院題 目：

Huffman編／譯碼器初始條件：利用Huffman編碼進(jìn)行通信可以大大提高信道利用率．縮短信息傳輸時(shí)間，降低傳輸成本，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼<復(fù)原）。對(duì)于雙工信道 <即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編／譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)Huffman碼的編／譯碼系統(tǒng)。要求完成的主要任務(wù) :<包括課程設(shè)計(jì)工作量及其技術(shù)要求、說明書撰寫等具體要求）一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：<l）I：初始化。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。<2）E：編碼。利用已建好的Huffman樹<如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。<3）D：譯碼。利用已建好的Huffman樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。<4）P：印代碼文件。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。<5）T：印哈夫曼樹。將已在內(nèi)存中的哈夫曼樹以直觀的方式<樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。時(shí)間安排：序號(hào)設(shè)計(jì)內(nèi)容所用時(shí)間1問題分析和任務(wù)定義0.5天2數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)0.5天3編碼實(shí)現(xiàn)和靜態(tài)檢查3天4上機(jī)準(zhǔn)備和上機(jī)調(diào)試2天5總結(jié)和整理設(shè)計(jì)報(bào)告1天合計(jì)7天指導(dǎo)教師簽名：2018年07月02日系主任<或責(zé)任教師）簽名：2018年07月02日個(gè)人資料整理 僅限學(xué)習(xí)使用需求分析1.1 程序的任務(wù)：利用Huffman編碼進(jìn)行通信可以大大提高信道利用率．縮短信息傳輸時(shí)間，降低傳輸成本，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼<復(fù)原）。對(duì)于雙工信道 <即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編／譯碼系統(tǒng)。此程序就是為這樣的信息收發(fā)站寫一個(gè)Huffman碼的編／譯碼系統(tǒng)。1.2 程序的輸入和輸出：從終端讀入字符集大小 n，以及n個(gè)字符及各個(gè)字符的權(quán)值，建立赫夫曼樹，并將它存儲(chǔ)到文件hfmTree中；利用已建好的赫夫曼樹將文件中的字符編碼，如果赫夫曼樹不在內(nèi)存中，則從文件hfmTree中讀取到內(nèi)存；將譯得的代碼存到文件CodeFile中；利用已建好的赫夫曼樹對(duì)CodeFile中的代碼進(jìn)行譯碼，將結(jié)果存入文件TextFile中；最后將已在內(nèi)存中的哈夫曼樹以直觀的方式<樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。1.3 程序要達(dá)到的功能：用戶可以利用菜單根據(jù)自己的需要來選擇要進(jìn)行編碼或是譯碼 ,并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應(yīng)的文件里面。1.4 測試數(shù)據(jù)如下表：<l）利用教材中的數(shù)據(jù)調(diào)試程序。<2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)字符

文的編碼和譯碼："THISPROGRAMISMYFAVORITE"。A B C D E F GHI JKL MN OPQR

S T

UVWXYZ頻度1866413223210321154757

153220576315 1485180238181161選擇E，輸入THISPROGRAMISMYFAVORITE，屏幕上顯示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同時(shí)文件codefile 里面也出現(xiàn)相應(yīng)的代碼選擇D，從codefile 中調(diào)入代碼，終端顯示 THISPROGRAMISMYFAVORITE，并且文件textfile 中也相應(yīng)的存入了這段話。個(gè)人資料整理 僅限學(xué)習(xí)使用選擇P，文件CodeFile以緊湊格式顯示在終端上。選擇T，將已在內(nèi)存中的哈夫曼樹以直觀的方式 <樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。選擇其他的字母，將出現(xiàn)出錯(cuò)提示，并重新回到選擇菜單。概要設(shè)計(jì)ADTBinaryTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素集合。數(shù)據(jù)關(guān)系R：若D為空，則R為空，稱Huffmantree為空霍夫曼樹；若D不為空，則R={H}，H是如下的二元關(guān)系：1、H滿足二叉樹的所有要求；2、H中所有數(shù)乘以該數(shù)所在節(jié)點(diǎn)的深度值之后和最小。基本操作P：InputHuffman(HuffmanHfm>操作結(jié)果：輸入并存儲(chǔ)字符和相應(yīng)權(quán)值。Select(HuffmanTreeHT,intend,int*s1,int*s2>初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：選擇 HT[1....i-1] 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2。HuffmanCoding(HuffmanHfm>初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：w存放n個(gè)字符的權(quán)值<均>0），構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的構(gòu)造赫夫曼編碼HC。InitHuffman(HuffmanHfm>初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：要求用戶輸入字符和相應(yīng)權(quán)值，初始化赫夫曼數(shù)Encoding(HuffmanHfm>初始條件：霍夫曼樹 HuffmanTree已經(jīng)存在。操作結(jié)果：利用已建好的 Huffman樹<如不在內(nèi)存，則從文件 hfmTree個(gè)人資料整理 僅限學(xué)習(xí)使用中讀入），對(duì)文件 ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。Decoding(HuffmanHfm>初始條件：霍夫曼樹 HuffmanTree已經(jīng)存在。操作結(jié)果：利用已建好的Huffman樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。Print(HuffmanHfm>初始條件：霍夫曼樹 HoffmanTree已經(jīng)存在。操作結(jié)果：將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。Treeprint(HuffmanHfm>初始條件：霍夫曼樹 HuffmanTree已經(jīng)存在。操作結(jié)果：將已在內(nèi)存中的哈夫曼樹以凹入表的形式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。}ADTHuffmanTree2主程序流程Voidmain(>{顯示菜單；Switch(k>{：初始化E：編碼D：譯碼P：印代碼文件T：印哈夫曼樹Q：退出運(yùn)行}}個(gè)人資料整理 僅限學(xué)習(xí)使用2.3 程序調(diào)用模塊Main函數(shù)InitHuffman Encoding Decoding Print Treeprint Quit詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)類型：typedefchar**HuffmanCode 。//typedefstruct{unsignedint weight 。unsignedint parent,lchild,rchild

動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼表碼表。}HTNode,*HuffmanTree。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼樹typedefstruct{HuffmanTreeHT 。char *c 。int length 。HuffmanCodeHC。}Huffman。//分配數(shù)組存儲(chǔ)字符串及其對(duì)應(yīng)的霍夫曼樹HuffmanHfm。chark。/*控制循環(huán)的標(biāo)志*/3.2 偽碼算法：主程序main(>{InitHuffman(HuffmanHfm> ；Encoding(HuffmanHfm>；Decoding(HuffmanHfm>；Print(HuffmanHfm> ；Treeprint(HuffmanHfm> ；}其他模塊：個(gè)人資料整理 僅限學(xué)習(xí)使用voidSelect(HuffmanTreeHT,intend,int*s1,int*s2> //選擇 HT[1....i-1] 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1，s2FOR(i=1。i<=end。i++>{IF(HT[i].parent 是最小的>THENHT[i].parent ——>*s1IF(HT[i].parent 是次最小的>THENHT[i].parent ——>*s2}HuffmanHuffmanCoding(HuffmanHfm>//w存放n個(gè)字符的權(quán)值<均〉0），構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的構(gòu)造赫夫曼編碼HC{FOR(i=n+1。i<=2*n-1。++i>// 選擇HT[1....i-1] 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2{Select(Hfm.HT,i-1,&s1,&s2> 。修改父親位置；修改孩子位置；父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和；}從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的赫夫曼編碼FOR(i=1。i<=n。++i>逐個(gè)字符求赫夫曼編碼{start=n-1。//編碼結(jié)束符位置for(c=i,f=Hfm.HT[i].parent。f!=0。c=f,f=Hfm.HT[f].parent>//從葉子到根逆向求編碼{IF(c==Hfm.HT[f].lchild>cd[--start]='0' 。ELSEcd[--start]='1' 。}再從cd復(fù)制編碼到Hfm.HC}RETURNHfm。}HuffmanInitHuffman(HuffmanHfm> //初始化赫夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)個(gè)人資料整理 僅限學(xué)習(xí)使用值{對(duì)文件hfmTree以讀文本的形式打開IF(fp==NULL>調(diào)用

InputHuffman

函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入赫夫曼數(shù)中ELSE輸出"TheHuffmantreehasalreadyexisted!\nPleasechooseagain!\n\n">讀入hfmTree中文本FOR(i=1。i<=n。i++>

。作為獨(dú)立結(jié)點(diǎn)對(duì)結(jié)點(diǎn)的

parent

，lchild

，rchild

分別賦值

0FOR(。i<=2*n-1。++i>作為獨(dú)立結(jié)點(diǎn)對(duì)結(jié)點(diǎn)的

weight

，parent

，lchild

，rchild

分別賦值

0Hfm=HuffmanCoding(Hfm>。RETURNHfm。}voidEncoding(HuffmanHfm>

//利用已建好的

Huffman

樹<如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。{輸出"\n\n*******************Encoding**************************\n\n"IF((ffp=fopen("ToBeTran","rt">>==NULL>提示輸入"Pleaseinputthesentence:"scanf("%s",ch> 。printf("\n"> 。以寫文本的形式打開 CodeFileELSE讀入ToBeTran文件中的字符。WHILE(ch[j]>FOR(i=1。i<=n。i++>IF(ch[j]==Hfm.c[i]>分別在終端和文件 CodeFile輸入Hfm.HC[i]voidDecoding(HuffmanHfm>//利用已建好的Huffman樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。{ 定義chard[500]輸出"\n\n******************Decoding************************\n\n"IF((fp=fopen("CodeFile","rt">>==NULL>輸出Pleaseinputthecode: 。ELSE將文件Codefile 中的內(nèi)容讀到d數(shù)組中輸出Thefileis:以寫文本的方式打開 TextFileWHILE(d[j]>根到葉子結(jié)點(diǎn)遍歷，并按照 lchild ——>0，rchild ——>1來輸出個(gè)人資料整理 僅限學(xué)習(xí)使用入到文件TextFile 中關(guān)閉文件}voidPrint(HuffmanHfm> //將文件 CodeFile 以緊湊格式，示在終端上，每行 50個(gè)代碼。{FOR(i=1。i<=n。i++>輸出Hfm.c[i]輸出Hfm.HT[i].weight以只讀二進(jìn)制的方式打開 CodeFile文件while(feof(fprint>==0>逐個(gè)輸出IF(m%50==0>輸出"\n"關(guān)閉文件}voidTreeprint(HuffmanHfm> //將已在內(nèi)存中的哈夫曼樹以凹入表的形式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件

TreePrint

中。{打開hfmTree文件將字符及其對(duì)應(yīng)的代碼賦給變量輸出Hfm.c[i] ，對(duì)Hfm.c[i][j]

Hfm.c[i] 和Hfm.c[i][j]進(jìn)行判斷，不是\n則輸出*，否則停止輸出}3.3函數(shù)調(diào)用關(guān)系圖InitHuffman(HuffmanHfm>初始化Select< ） 供InputHuffman(HuffmanHfm>HuffmanCoding(>接收數(shù)據(jù)調(diào)用調(diào) 用HuffmanCoding(>構(gòu)造哈夫曼樹編 碼 調(diào)Encoding(>

用

譯 碼 調(diào) 用Decoding<）

打 印Print(>

編 碼

打印哈夫曼樹Treeprint(>個(gè)人資料整理 僅限學(xué)習(xí)使用調(diào)試分析4.1 調(diào)試過程中遇到的問題：第一個(gè)問題是一直比較棘手的問題就是文件的調(diào)用與寫入，因?yàn)槲募矫娴闹R(shí)一直就掌握的不是很好，在寫代碼時(shí)產(chǎn)生很大困難，所以在解決這個(gè)問題的時(shí)候我把文件部分系統(tǒng)的看了一下，這才從自身角度解決了這個(gè)問題。而實(shí)際中遇到的問題就是如何判斷已經(jīng)有了hfmtree這個(gè)文件，并且怎么調(diào)用到內(nèi)存中來。解決方案：設(shè)置一個(gè)全局結(jié)構(gòu)體變量來存放已經(jīng)在文件中存放的霍夫曼樹。第二個(gè)問題是關(guān)于界面的美觀設(shè)計(jì)方面，因?yàn)楹芏啻a在文本中編輯時(shí)是比較整齊美觀的，但是在程序運(yùn)行中卻出現(xiàn)很多問題，不對(duì)齊等等。還有就是換行符的使用，一不小心就會(huì)產(chǎn)生偏差。解決方案：進(jìn)入程序進(jìn)行調(diào)試，檢查每段輸出代碼的顯示。第三個(gè)問題是Huffman樹的打印，方式為凹入式打印，由于在當(dāng)時(shí)學(xué)習(xí)的時(shí)候這部分內(nèi)容沒有留意，根本沒有概念，所以在編寫程序過程中出現(xiàn)了嚴(yán)重的問題。導(dǎo)致該項(xiàng)功能無法完成。解決方案：尚未完善解決，只是將內(nèi)存中的哈夫曼樹中各節(jié)點(diǎn)的值及其孩子輸出。4.2 算法的時(shí)空分析：算法的時(shí)間復(fù)雜度：Select(HuffmanTreeHT,intend,int*s1,int*s2> O(n>HuffmanCoding(HuffmanHfm>O(n2>InputHuffman(HuffmanHfm>O(n>InitHuffman(HuffmanHfm>O(n>Encoding(HuffmanHfm>O(n>Decoding(HuffmanHfm>O(n>Print(HuffmanHfm>O(n>4.3 經(jīng)驗(yàn)與體會(huì)：整個(gè)程序在編的時(shí)候思路是很明朗的，包括菜單的設(shè)置都是很清晰的，但是如何通過一個(gè)菜單將所有涉及到的文件與終端聯(lián)系起來還有打印哈夫曼樹都是比較困難的問題，由于文件這一章節(jié)我們以前學(xué)習(xí)的時(shí)候并沒有很重視，所以在運(yùn)用的時(shí)候遇到了很大的困難，同時(shí)通過這次的設(shè)計(jì)我也看到其實(shí)文件這一章是很重要的，我們做了一個(gè)程序，必須要把有些必要的數(shù)據(jù)進(jìn)行保存，如果只是停留在內(nèi)存中那就很難在以后個(gè)人資料整理 僅限學(xué)習(xí)使用被重復(fù)利用，會(huì)很大程度上提高我們調(diào)試的效率；另外凹入式打印哈夫曼樹更是讓我頭疼了一整天的問題，由于根本不知道其概念是什么，更不用說去編寫代碼了。同時(shí)我也覺得有些細(xì)節(jié)問題是很重要的，不管是一個(gè)整型變量還是一個(gè)結(jié)構(gòu)體變量，有時(shí)候?qū)φ麄€(gè)程序起著至關(guān)重要的作用。用戶使用說明1．本程序的運(yùn)行環(huán)境為 DOS操作系統(tǒng)，執(zhí)行文件為： hfmtree.exe。運(yùn)行程序后出現(xiàn)選擇菜單。3．根據(jù)提示選擇相應(yīng)的操作，初始化，編碼，譯碼，印代碼文件，印哈夫曼樹退出，每次選擇完，都會(huì)再次彈出選擇菜單供用戶選擇。結(jié)束符為回車鍵。測試結(jié)果在進(jìn)入系統(tǒng)以后，選擇第一個(gè)初始化，按要求鍵入要求的字符及其頻度字符— A B C D E F GH I JKL MN OP QR S T U VWXY Z頻度18664132232103211547571532205763151485180238181161截圖如下所示：圖1進(jìn)入程序，顯示的菜單界面?zhèn)€人資料整理 僅限學(xué)習(xí)使用圖2輸入I，選擇進(jìn)行初始化圖3初始化時(shí)對(duì)字符的個(gè)數(shù)進(jìn)行限制，不得少于 2個(gè)。個(gè)人資料整理 僅限學(xué)習(xí)使用圖4、5在字符個(gè)數(shù)處輸入“27”，之后依次輸入各字符及其權(quán)值。圖6在菜單界面選擇E，出現(xiàn)提示語句，要求輸入句子。圖7輸入“THIS_PROGRAM_IS_MY_FAVORITE”，回車之后，顯示出該句的哈夫曼編碼。<此處為求簡捷，將空格用下劃線“_”作為代替）個(gè)人資料整理 僅限學(xué)習(xí)使用圖8在菜單界面選擇 D，則對(duì)文件中已有的哈夫曼編碼進(jìn)行反譯，將譯出的字符顯示出來。圖9在菜單界面選擇P，將文件中的哈夫曼編碼緊湊輸出，每行 50個(gè)。結(jié)果如下圖：個(gè)人資料整理 僅限學(xué)習(xí)使用圖10、11該程序中，我加入了將初始化的各字符的編碼輸出的語句，可以看到各個(gè)字符的哈弗曼編碼。圖12這3行數(shù)字便是緊湊輸出哈夫曼編碼的結(jié)果。圖13同時(shí)，不同的人使用本程序進(jìn)行不同的哈夫曼編碼時(shí)，由于前一位使用者初始化的數(shù)據(jù)后一位不一定同樣適用，為了避免這種情況，因此當(dāng)已經(jīng)初始化后再進(jìn)行初始化時(shí)會(huì)出現(xiàn)提示是否重新初始化的信息提示，如上圖所示。個(gè)人資料整理 僅限學(xué)習(xí)使用圖14在菜單界面選擇T，打印處內(nèi)存中的哈夫曼樹各節(jié)點(diǎn)的值及其雙親節(jié)點(diǎn)和子節(jié)點(diǎn)。圖15TEXTFILE.TXT文本文件，記錄用戶輸入的需要進(jìn)行編碼的句子。圖16CODEFILE.TXT文本文件，記錄 TEXTFILE.TXT文本文件中字符的哈弗曼編碼。圖17HFMTREE.TXT文本文件，記錄輸入的各字符及其權(quán)值個(gè)人資料整理 僅限學(xué)習(xí)使用附錄源程序文件名清單：TEXTFILE.TXTCODEFILE.TXTHFMTREE.TXT

記錄待編碼的句子記錄哈夫曼編碼記錄字符個(gè)數(shù)、名稱及權(quán)值源代碼：#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#include<ctype.h>#defineNULL0#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX_NUM32767#defineMAX60個(gè)人資料整理 僅限學(xué)習(xí)使用typedefchar**HuffmanCode 。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表typedefstruct{unsignedint weight 。unsignedint parent,lchild,rchild 。}HTNode,*HuffmanTree。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedefstruct{HuffmanTreeHT 。char *c 。int length 。HuffmanCodeHC。}Huffman。//全局結(jié)構(gòu)體變量，來存儲(chǔ)字符與代碼voidSelect(HuffmanTreeHT,intend,int*s1,int*s2>// 選擇HT[1....i-1] 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1，s2{inti 。intmin1=MAX_NUM。intmin2 。for(i=1 。i<=end。i++>//遍歷查找權(quán)值最小的結(jié)點(diǎn) S1個(gè)人資料整理 僅限學(xué)習(xí)使用{if(HT[i].parent==0&&HT[i].weight<min1>{*s1=i 。min1=HT[i].weight 。}}min2=MAX_NUM。for(i=1 。i<=end。i++>//遍歷查找除S1外權(quán)值最小的結(jié)點(diǎn) S2{if(HT[i].parent==0&&(*s1!=i>&&min2>HT[i].weight>{*s2=i 。min2=HT[i].weight 。}}}個(gè)人資料整理 僅限學(xué)習(xí)使用HuffmanHuffmanCoding(HuffmanHfm>//存放n個(gè)字符的權(quán)值<均〉0），構(gòu)造哈夫曼樹HT，并求出n個(gè)字符的構(gòu)造哈夫曼編碼HC{inti,n,m,s1,s2,start 。intc,f 。char*cd 。n=Hfm.length 。if(n<=1>returnHfm 。m=2*n-1。for(i=n+1 。i<=m。++i>// 選擇HT[1....i-1] 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2{Select(Hfm.HT,i-1,&s1,&s2> 。Hfm.HT[s1].parent=i 。//修改父親位置Hfm.HT[s2].parent=i 。Hfm.HT[i].lchild=s1 。//修改孩子位置Hfm.HT[i].rchild=s2 。Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight 。//父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和}從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼個(gè)人資料整理 僅限學(xué)習(xí)使用Hfm.HC=(HuffmanCode>malloc((n+1>*sizeof(char*>> 。//分配n個(gè)字符編碼的頭指針向量cd=(char*>malloc(n*sizeof(char>> 。//分配求編碼的工作空間cd[n-1]='\0' 。//編碼結(jié)束符for(i=1 。i<=n。++i>//逐個(gè)字符求哈夫曼編碼{start=n-1 。//編碼結(jié)束符位置for(c=i,f=Hfm.HT[i].parent 。f!=0。c=f,f=Hfm.HT[f].parent>// 從葉子到根逆向求編碼{if(c==Hfm.HT[f].lchild>cd[--start]='0' 。elsecd[--start]='1' 。}Hfm.HC[i]=(char*>malloc((n-start>*sizeof(char>> 。strcpy(Hfm.HC[i],&cd[start]> 。//從cd復(fù)制編碼到Hfm.HC}free(cd> 。//釋放工作空間returnHfm 。}個(gè)人資料整理 僅限學(xué)習(xí)使用HuffmanInputHuffman(HuffmanHfm>// 輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值{inti,n 。printf("\n\n********************Initialization*********************\n"> 。printf("Thecharsandweightswillbesavedinthefile:\hfmTree\\n">。printf("Pleaseinputthenumberofthechars:"> 。scanf("%d",&n> 。if(n<=1>{printf("OnlyOneChar!ThereIsNoNeedForCoding!"> 。//若只有一個(gè)數(shù)值則無需編碼printf("\n"> 。printf("Pleaseinputthenumberofthechars:"> 。scanf("%d",&n> 。}Hfm.HT=(HuffmanTree>malloc((2*n>*sizeof(HTNode>> 。Hfm.c=(char*>malloc((n+1>*sizeof(char>> 。for(i=1 。i<=n。i++>{printf("Pleaseinputthechar:"> 。scanf("%s",&Hfm.c[i]> 。個(gè)人資料整理 僅限學(xué)習(xí)使用printf("Pleaseinputtheweightofthechar:"> 。scanf("%d",&Hfm.HT[i].weight> 。Hfm.HT[i].parent=0 。Hfm.HT[i].lchild=0 。Hfm.HT[i].rchild=0 。}for( 。i<=2*n-1。++i>{Hfm.HT[i].weight=0 。Hfm.HT[i].parent=0 。Hfm.HT[i].lchild=0 。Hfm.HT[i].rchild=0 。}Hfm.length=n 。returnHfm 。}HuffmanInitHuffman(HuffmanHfm>// 初始化哈夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值個(gè)人資料整理 僅限學(xué)習(xí)使用{intn,i,x 。FILE*fp 。fp=fopen("hfmTree","rt"> 。//對(duì)文件hfmTree以讀文本的形式打開if(fp==NULL>{Hfm=InputHuffman(Hfm>。//調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中fp=fopen("hfmTree","wt"> 。fprintf(fp,"%d\n",Hfm.length> 。for(i=1 。i<=Hfm.length 。i++>fprintf(fp,"%c%d",Hfm.c[i],Hfm.HT[i].weight> 。rewind(fp> 。}else{printf("TheHuffmantreehasalreadyexisted!\nDoYouWantToMakeANewOne?('Y'or'N'>\n\n">。//詢問是否重新初始化scanf("%s",&x> 。if(x=='Y'>{Hfm=InputHuffman(Hfm>。//調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中fp=fopen("hfmTree","w+"> 。個(gè)人資料整理 僅限學(xué)習(xí)使用fprintf(fp,"%d\n",Hfm.length> 。for(i=1 。i<=Hfm.length 。i++>fprintf(fp,"%c%d",Hfm.c[i