(完整word版)應用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(哈夫曼樹)[1]

1、學號:0120803490117課程設(shè)計題目Huffman編/譯碼器學院管理學院專業(yè)信息管理與信息系統(tǒng)班級0801姓名王濤燕翔指導教師2010年 07月 09 日課程設(shè)計任務(wù)書系主任（或責任教師）簽名：2010年07月02日學生姓名:王濤專業(yè)班級： 信管0801指導教師:燕翔工作單位：管理學院題 目:Huffman編/譯碼器初始條件:利用Huffman編碼進行通信可以大大提高信道利用率.縮短信息傳輸時間，降低 傳輸成本，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的 數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個 完整的編/譯碼系統(tǒng)。試為這樣

2、的信息收發(fā)站寫一個Huffman碼的編/譯碼系統(tǒng)。要求完成的主要任務(wù)：（包括課程設(shè)計工作量及其技術(shù)要求、說明書撰寫等具體要求）一個完整的系統(tǒng)應具有以下功能：（l ） I :初始化。從終端讀入字符集大小 n,以及n個字符和n個權(quán)值，建立哈夫 曼樹，并將它存于文件 hfmTree中。（2） E：編碼。利用已建好的Huffman樹（如不在內(nèi)存，則從文件hfmTree中讀入）,對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3） D：譯碼。利用已建好的 Huffman樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile 中。（4） P:印代碼文件。將文

3、件CodeFile以緊湊格式顯示在終端上，每行50個代碼。TreePrint 中。（5）T:印哈夫曼樹。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式） 顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件時間安排:指導教師簽名:2010年07月02日序號設(shè)計內(nèi)容所用時間1問題分析和任務(wù)定義0.5天2數(shù)據(jù)類型和系統(tǒng)設(shè)計0.5天3編碼實現(xiàn)和靜態(tài)檢查3天4上機準備和上機調(diào)試2天5總結(jié)和整理設(shè)計報告1天合計7天71. 需求分析1.1程序的任務(wù):利用Huffman編碼進行通信可以大大提高信道利用率.縮短信息傳輸時間，降 低傳輸成本，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將 傳來的數(shù)

4、據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端 都需要一個完整的編/譯碼系統(tǒng)。此程序就是為這樣的信息收發(fā)站寫一個Huffman碼的編/譯碼系統(tǒng)。1.2程序的輸入和輸出：從終端讀入字符集大小n,以及n個字符及各個字符的權(quán)值，建立赫夫曼樹，并 將它存儲到文件hfmTree中；利用已建好的赫夫曼樹將文件中的字符編碼，如果赫 夫曼樹不在內(nèi)存中，則從文件hfmTree中讀取到內(nèi)存；將譯得的代碼存到文件Tree Print 中。CodeFile中；利用已建好的赫夫曼樹對 CodeFile中的代碼進行譯碼，將結(jié)果存入文 件TextFile中；最后將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹

5、入表形式）顯 示在終端上，同時將此字符形式的哈夫曼樹寫入文件1.3程序要達到的功能:用戶可以利用菜單根據(jù)自己的需要來選擇要進行編碼或是譯碼,并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應的文件里面。1.4測試數(shù)據(jù)如下表:（l ）利用教材中的數(shù)據(jù)調(diào)試程序。（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報 文的編碼和譯碼："THIS P ROGRAM IS MY FAVORITE"字符ABCDEFGHIJKLMNOPQRSTUVWXY :7頻度186 654 13 22 32 103 21 15i 4757153220576315148518023818116

6、1選擇 E， 輸入 THIS PROGRAMS MY FAVORITE， 屏幕 上顯示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同時文件codefile里面也出現(xiàn)相應的代碼選擇D,從codefile 中調(diào)入代碼，終端顯示 THIS PROGRAM IS MY FAVORTE并且文件textfile中也相應的存入了這段話。選擇P,文件CodeFile以緊湊格式顯示在終端上。選擇T，將已在內(nèi)存中的哈夫曼樹以

7、直觀的方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件Tree Print中。選擇其他的字母，將出現(xiàn)出錯提示，并重新回到選擇菜單。2. 概要設(shè)計ADT BinaryTree 數(shù)據(jù)對象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é)點的深度值之后和最小。 基本操作P:Inp utHuffman(Huffman Hfm)操作結(jié)果：輸入并存儲字符和相應權(quán)值。Select(HuffmanTree HT,int end,int

8、 *s1,int *s2)初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：選擇HT1.i-1中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2。HuffmanCoding(Huffman Hfm) 初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：w存放n個字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT, 并求出n個字符的構(gòu)造赫夫曼編碼HC。InitHuffman(Huffman Hfm)初始條件：頻率數(shù)組已經(jīng)建立。操作結(jié)果：要求用戶輸入字符和相應權(quán)值，初始化赫夫曼數(shù)Encoding(Huffman Hfm)初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。操作結(jié)果：利用已建好的Huffman樹(如不在內(nèi)存，則從文件hfmTr

9、ee中讀入)，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存 入文件CodeFile中。Decoding(Huffman Hfm)初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。操作結(jié)果：利用已建好的Huffman樹將文件CodeFile中的代碼進 行譯碼，結(jié)果存入文件TextFile中。Print(Huffman Hfm)初始條件：霍夫曼樹HoffmanTree已經(jīng)存在。操作結(jié)果：將文件CodeFile以緊湊格式顯示在終端上，每行50個 代碼。Tree print(Huffman Hfm)初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。操作結(jié)果：將已在內(nèi)存中的哈夫曼樹以凹入表的形式

10、顯示在終端 上，同時將此字符形式的哈夫曼樹寫入文件Tree Print中。 ADT HuffmanTree2. 2主程序流程Void mai n()顯示菜單;Switch(k)E:D:P:T:初始化編碼譯碼印代碼文件 印哈夫曼樹 退出運行2.3程序調(diào)用模塊Main函數(shù)InitHuffman EncodingDecodingPrintTree printQuit3. 詳細設(shè)計3.1數(shù)據(jù)類型:動態(tài)分配數(shù)組存儲霍夫曼表碼表typ edef char *Huffma nCode;/typ edef structun sig ned int weight;un sig ned int paren t,l

11、child,rchild;HTNode,*HuffmanTree;/動態(tài)分配數(shù)組存儲霍夫曼樹 typ edef structHuffma nTree HT;char *c;intlen gth;Huffma nCode HC;Huffman;/分配數(shù)組存儲字符串及其對應的霍夫曼樹Huffma n Hfm;char k; /* 控制循環(huán)的標志*/3.2偽碼算法:主程序mai n()Ini tHuffma n(Huffman Hfm) En cod in g(Huffma n Hfm)； Decoding(Huffman Hfm)； Prin t(Huffma n Hfm)； Tree prin

12、t(Huffma n Hfm) /選擇HT1.i-1 中無雙其他模塊:void Select(Huffma nTree HT,i nt en d,i nt *s1,i nt *s2)親且權(quán)值最小的兩個節(jié)點，其序號為s1 , s2FOR (i=1;i<=e nd;i+)IF(HTi. pare nt是最小的)THEN HTi. pare nt >*s1 IF(HTi. pare nt 是次最小的)THEN HTi. parent >*s2 Huffman HuffmanCoding(Huffman Hfm) /w 存放 n 個字符的權(quán)值(均0),構(gòu)造赫夫 曼樹HT,并求出n個字

13、符的構(gòu)造赫夫曼編碼HC選擇HT1.i-1中無雙親且權(quán)值最小的兩個節(jié)點,FOR(i=n+1;iv=2* n-1;+i)/其序號為s1，s2Select(Hfm.HT,i-1,&s1,&s2);修改父親位置；修改孩子位置；父親結(jié)點權(quán)值為左右孩子權(quán)值之和；/從葉子結(jié)點到根逆向求每個字符的赫夫曼編碼FOR(i=1;i<=n;+i)/逐個字符求赫夫曼編碼 start=n-1;/編碼結(jié)束符位置for(c=i,f=Hfm.HTi. paren t;f!=0;c=f,f=Hfm.HTf. parent) /從葉子到根逆向求編碼IF(c=Hfm.HTf.lchild) cd-start=&

14、#39;0'ELSE cd-start='1'再從cd復制編碼到Hfm.HCRETURN Hfm;Huffman InitHuffman(Huffman Hfm)/初始化赫夫曼數(shù)，要求用戶輸入字符和相應權(quán)值對文件hfmTree以讀文本的形式打開IF(fp=NULL)調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應權(quán)值存入赫夫曼數(shù)中ELSE輸出"The Huffma ntree has already existed!' nPI ease choose agai n!nn");讀入hfmTree中文本FOR(i=1;iv=n;i+)作為獨立

15、結(jié)點對結(jié)點的 pare nt，lchild ，rchild 分別賦值0FOR(;i<=2* n-1;+i)作為獨立結(jié)點對結(jié)點的 weight，pare nt，lchild ，rchild 分別賦值0Hfm=Huffma nCodi ng(Hfm);RETURN Hfm;void Encoding(Huffman Hfm)/利用已建好的Huffman樹(如不在內(nèi)存，則從文件hfmTree中讀入)，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。輸出"nn*E ncod in g*nn"IF(ffp二fopen ("ToBeTra

16、n","rt")=NULL)提示輸入"Please input the sentence:"scan f("%s",ch);prin tf("n");以寫文本的形式打開CodeFileELSE讀入ToBeTran文件中的字符；WHILE(chj)FOR(i=1;i<=n;i+)IF(chj=Hfm.ci)分別在終端和文件CodeFile輸入Hfm.HCivoid Decoding(Huffman Hfm) /利用已建好的 Huffman樹將文件 CodeFile中的代碼進 行譯碼，結(jié)果存入文件Tex

17、tFile中。定義 char d500出"nn*Decod in g*nn"IF(fp=fo pen( "CodeFile","rt")=NULL) 輸出 PI ease input the code:;ELSE將文件Codefile中的內(nèi)容讀到d數(shù)組中輸出 The file is :以寫文本的方式打開TextFileWHILE(dj)>0, rchild>1來輸出根到葉子結(jié)點遍歷，并按照lchild入到文件TextFile 中 關(guān)閉文件void Prin t(Huffma n Hfm) /碼。FOR(i=1;iv=n;i

18、+) 輸出 Hfm.ci 輸出 Hfm.HTi.weight 以只讀二進制的方式打開 while ( feoffprin t)=0 ) 逐個輸出IF (m%50=0) 輸出"n"關(guān)閉文件將文件CodeFile以緊湊格式，示在終端上，每行 50個代CodeFile 文件void Tree prin t(Huffma n Hfm)上，同時將此字符形式的哈夫曼樹寫入文件打開hfmTree文件將字符及其對應的代碼賦給變量Hfm.ci和Hfm.cij輸出Hfm.ci，對Hfm.cij進行判斷，不是n/將已在內(nèi)存中的哈夫曼樹以凹入表的形式顯示在終端TreePrint 中。則輸出*，否則

19、停止輸出3.3函數(shù)調(diào)用關(guān)系圖4. 調(diào)試分析4.1調(diào)試過程中遇到的問題:第一個問題是一直比較棘手的問題就是文件的調(diào)用與寫入，因為文件方面的知識一直就掌握的不是很好，在寫代碼時產(chǎn)生很大困難，所以在解決這個問題的時候我把文件 部分系統(tǒng)的看了一下，這才從自身角度解決了這個問題。而實際中遇到的問題就是如何 判斷已經(jīng)有了 hfmtree這個文件，并且怎么調(diào)用到內(nèi)存中來。解決方案：設(shè)置一個全局結(jié)構(gòu)體變量來存放已經(jīng)在文件中存放的霍夫曼樹。第二個問題是關(guān)于界面的美觀設(shè)計方面，因為很多代碼在文本中編輯時是比較整齊美觀的，但是在程序運行中卻出現(xiàn)很多問題，不對齊等等。還有就是換行符的使用，一 不小心就會產(chǎn)生偏差。解決

20、方案：進入程序進行調(diào)試，檢查每段輸出代碼的顯示。第三個問題是Huffman樹的打印，方式為凹入式打印，由于在當時學習的時候這部 分內(nèi)容沒有留意，根本沒有概念，所以在編寫程序過程中出現(xiàn)了嚴重的問題。導致該項 功能無法完成。解決方案：尚未完善解決，只是將內(nèi)存中的哈夫曼樹中各節(jié)點的值及其孩子輸出。4.2算法的時空分析：算法的時間復雜度:0(n)0( n2)0(n)0(n)0(n)0(n)0(n)Select(Huffma nTree HT,i nt en d,i nt *s1,i nt *s2)Huffma nCodi ng(Huffma n Hfm)Inpu tHuffma n(Huffman H

21、fm)In itHuffma n(Huffman Hfm)En cod in g(Huffma n Hfm)Decodi ng(Huffma n Hfm)Prin t(Huffma n Hfm)4.3經(jīng)驗與體會：整個程序在編的時候思路是很明朗的，包括菜單的設(shè)置都是很清晰的，但是如何通過一 個菜單將所有涉及到的文件與終端聯(lián)系起來還有打印哈夫曼樹都是比較困難的問題，由于文件這一章節(jié)我們以前學習的時候并沒有很重視，所以在運用的時候遇到了很大的困難，同時通過這次的設(shè)計我也看到其實文件這一章是很重要的，我們做了一個程序，必 須要把有些必要的數(shù)據(jù)進行保存，如果只是停留在內(nèi)存中那就很難在以后被重復利用，會很

22、大程度上提高我們調(diào)試的效率； 另外凹入式打印哈夫曼樹更是讓我頭疼了一整天的問題，由于根本不知道其概念是什么，更不用說去編寫代碼了。同時我也覺得有些細節(jié)問題是很重要的，不管是一個整型變量還是一個結(jié)構(gòu)體變量，有時候?qū)φ麄€程序起著至關(guān)重要的作用。5. 用戶使用說明1.本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：hfmtree.exe。2.運行程序后出現(xiàn)選擇菜單。3. 根據(jù)提示選擇相應的操作，初始化，編碼，譯碼，印代碼文件，印哈夫曼樹退出，每次選擇完，都會再次彈出選擇菜單供用戶選擇。結(jié)束符為回車鍵。6. 測試結(jié)果在進入系統(tǒng)以后，選擇第一個初始化，按要求鍵入要求的字符及其頻度字符ABCDEFGHIJK

23、LMNOPQRSTUVWXYZ頻度186 64 13 22 32 10)3 2115475715322057635 148518023 (8181161截圖如下所示:QTCPFTAHUFFWftN.EXEThank Vmi To Use MV Huff耳加 ProgranII.tI. Ini I itil iznlipnIE.EncodingD.Dfrcodinfl(P.Rrintinar.Treeprintfl.FkilPleei三已 Input Your Upt ion進入程序，顯示的菜單界面35 C;1TIZPROMMHUFFMANQE汀h腫kTo Use H7 Huffman Prog

24、ram |I.InitializationE"EncodingD.DecodingP.Pcinting f"freePrintO.ExitPlease Input Vour Optiont i日1 i胡 t ion*I he chars and freights will bein the file : hfmT 廣 gsPlease input the number of the chars: _圖29Please input the number of the chars:初始化時對字符的個數(shù)進行限制,不得少于 2個。Please Please Please '

25、lease lease lease 1g 日 se lease 'lease lease Please Please Please Please Please Please Please Please "ease lease lease le日占e 'lease 'lease lease Please Please Please Please Please Please Please Please Please Pleaseinput inputinput mput input mput input input input wput input input i

26、npuL input input input input inputinput r(put input input input mput input mput inpu L input input input input input inijutehh11e e a h hh 111p-G e hh hh hh111111CJnumber of char: _ weight of char: A weight of char: B weight of char: C weight of ch”； D weight of char; E weight of char: F weight of c

27、har: G weight of char: H weight of char: I weight of char: J we i gh t of char : K Height of char: L weight of char: H weight oF char: N weight of char: 0 weight of char: P weitiht ofthethethethethethethethethethethethethethethethethethechars: 27char:char:char:char:char:char:char:char:char :char :18

28、664132232103211557char : 1chr :char :char;char :char:char:3220576315輸入I，選擇進行初始化L Idi iZd Lion*The chars and weights will be saved in the file :hfmTree Please input the number of the chars: 1Only One Char?There Is No Need For Coding?Pleaseinputthechar:0Pleaseinputtheweightofthechar:1Pleaseinputthecha

29、r:RPleaseinputtheweightofthechar:48Pleaseinputthechar:SUeaseinputtheweightofthechar:51leaseinputthechar:TPleaseinputtheweightofthechar:80Pleaseinputthechar;Uleaseinputtheweightofthechar:23leaseinputthechar:VPleaseinputtheweightofthechdr:8leaseinputthechar:Hleaseinputtheweightofthechar:18Pleaseinputt

30、hechar:KPleaseinputtheweightofthechar:1leaseinputthechar:V'leaseinputtheweightofthechar:16Pleaseinputthechar:ZPleasein puttheweightofthechar:1圖4、511在字符個數(shù)處輸入“ 27”，之后依次輸入各字符及其權(quán)值。! Thank Vou To Use HV Huffwsn Program !IFUPT0InitializdtionFncoding Decoding Printina TreePr int ExitPlease Input Vour O

31、ption IEPlease input the sentence:在菜單界面選擇E,出現(xiàn)提示語句，要求輸入句子。Thank Vou To Use HV Huffnan Pr兩r日m 1I.Initial運ationE.EncodingD.DecodingP.Printing T.TreePrintQ ExitPlease Input Vour OptionEncodingrleflse input the sentence: IHlS_PKIGRflM_lS_MV_KflVORl(E潮器牒粘腸aa嚮翩護叫0"吶L如1咖叫迦咖"輸入“ THIS_PROGRAM_IS_MY_

32、FAVORIT回車之后，顯示出該句的哈夫曼編碼。 （此處為求簡捷，將空格用下劃線“ _”作為代替）Thank Vou To Use HV Huffman 卩rogramIjI.InitializationIE.Encodingi0.DecodingjP.Printing!T.TreePrint1O.FxitPlease Intjut Vour Option IDw«* w w * WWWw * w Dec 0 d i ng *#«*#« *# * *The file is : THIS PROGRAM IS MY FAVORITE13將譯出的字符顯示出在菜單界面選

33、擇D,則對文件中已有的哈夫曼編碼進行反譯,圖10、11#來。I Thank Vou To Use MV Huffman Program II,InitializationE.EncodingO.DecodingP.PrintingT,TreePrinlQ.ExitPlease Inpul VourPOption*-*ljulpulthe <:ode of the chars-*-*-*Chdr:_ Weight:iseCode:111Char:R Weigh-t:zCode:1010Chiir;e Weight:13Code;imeeChdr:C Weight:22Code:00000C

34、hdr:D Ueiflh-t:32Code:10110Char:匚 Weigh-t:103Code:010Char;F Weight:21Code:110011Char:G Weight：15Co<le:100001Char:H Ueiflhl:i?Code:0001Char:1 Weigh-t:57Code;0110Chcir;J Weight;1Code;1100001000Chiir;J Weight:1Code;1100001000Char:K Weight:5Code:11000011Chftr：I. Weight；32Code；1011JChar;H Weight:20Cod

35、e:110010ChdnH Weight:57Cods;amChijr:0 Weight:63Cesde;1001Char :P Weight:15Code:leoBioChiir；Q Height;1Etxk；llRflOfllRfllChar:H Weight:48Code:Char:S Weight:51Cods:aeiiChijr;T Weigh I;80Cyde;1101Char:U Weight:23Code:96001Chiir：V Weight:&CfidA：H腑腑計Char:H Weight;ISCode:11O0U1ChdP：X Weight:1Code:11000

36、01010Cher：V WeiahU16Cude：100011Char; Z Weight: 1Cade; 11000010111161000101100011111100010001010011006010010101011001011101100011111110010100011111110611101011000001001001001101101010在菜單界面選擇P，野 CTCPPDtTAHUFFUAWniE將文件中的哈夫曼編碼緊湊輸出，每行50個。結(jié)果如下圖:該程序中，我加入了將初始化的各字符的編碼輸出的語句，可以看到各個字符的哈弗曼編碼。圖1211010001011000111

37、11100010001010011000010010101011 00101110110001111111001010G01111111001110101100000 1001001001101101010這3行數(shù)字便是緊湊輸出哈夫曼編碼的結(jié)果。i Thank Vou Io Use MV Huffnan ProgranI.Ini t ifllLzation E,EncodingD.Decoding PTrintingTJreePrint q.Exit17Please Input You廠 IIt he Huff mantree has Do Voii Want To HakeOptionalr

38、eady existed* ft Nm OneVrVorNJ*當斗* w*w*w*當*禪i t ial iza t i on* * *圖13The chars and weights will be sayed in the file :hfnTree Please input the number of the chars:同時，不同的人使用本程序進行不同的哈夫曼編碼時，由于前一位使用者初始化的 數(shù)據(jù)后一位不一定同樣適用，為了避免這種情況，因此當已經(jīng)初始化后再進行初始化時會出現(xiàn)提示是否重新初始化的信息提示，如上圖所示。leiht >ight relffht iff lit telffh

39、t 氐呂M 屜対ht heUht Inight relffht Misht height knight leig-ht hi呂猷 >eipht height ight Je-ipht>cisht ?hf Ififht ight hi 呂 ht rhelfrht 胚対ht Jfl-ight fhe ItfhC telght /right lelfrht ki呂ht ihf ItfhC 局対hr64133210321B3257t3S180藥IS17 罰 JI354115ST6476T2 99114123P<Lrv-n-t ； PAJWFlt ? Pnmt rPajwnt t Pc

40、rcX : Pdrert；PiUWFlt ?P9rent: Parv-n-t ：- PAl*«rt t Pdunt: Paren-t i-PCTWt frann 時: PSPCfft: Parent ；PflPCPt f Hartr t L Pa>*«ht : Papcfft: Hjrert : Pa>*er>C = Papcpt: Har«-nt : Parent: Papcfft: Harent: Puffnt = PaPCPt: Harent: Pdfrnt: Papcpt: rareid:； PufrDt: Parcpt: raren-t

41、: Pdfrnt: ParftPt: PftTfrFlt 5斗呂333739483t33帕2ft3i3¥3t43-H t: 3-128373£35393-129303U31323S38384e dldt-17dSLchild Lchlld Lchilrt Lchlld Lchlld Lchiia Lchlld Lchlld LehiId Il 匚 hJ. ill Lchlld Lezhild LEhlld Lchlld LehiId LEhlld Lchlld LehiId L匚hild Lchlld LehiId Li 匚 hild Lchlld LehiId Luhil

42、d Lchlld LehiId Luhild Lchlld LehiId Luhild Lchlld LehiId Lchild Lchlld LehiId Li: hild Lchlld LehiId Luhild Lhlld LehiId Lu hi 1ftB112S38302J317321413 S171910IttAl二 hildz 0 Bchiljd± 9 Aphiid： n Achild; 0 HchiU Acliild Achild HchiU Acliild Achild Bchiljd Aclhild AchLId Bchiljd Tichild Hz hLId B

43、chiU Bcinld H匚hild BchiU Bcldid Schild Bchiljd Bcinld JHchild Bchiljd Behild Bchild BchiU Hcinld 尺匚liild Bchiljd He Mid Hcliild Bchiljd Hchlld Hchild BchiU Hchlld Hchild BchiU Bchlld RErLlHIB2912116朋247:H13時£915圖14在菜單界面選擇T,打印處內(nèi)存中的哈夫曼樹各節(jié)點的值及其雙親節(jié)點和子節(jié)點。1 TEXTFILE -記事本文件(B 輛輯©式(0)查看M 稱助®i

44、rHI3_PR0GIM_I S_HY_FAVORITE圖15TEXTFILE.TXT文本文件，記錄用戶輸入的需要進行編碼的句子。0 CDCEFILI 迅T立剛町 注初I屯？:冋 童加 叭HJ tiioiKioioiiKioaiiiiiWQiwoioiOftiiOMoio&ioioioiiMioiiiQaiOMiiiiiiiwuiKMCaiiiiiiotniiDioiiMWDioQawiODiKnioion)圖16CODEFILE.TX文本文件，記錄TEXTFILE.TXT文本文件中字符的哈弗曼編碼。izzi I igjZHFMT班E-記事本f -丈拌里超0 卿1 理V 映M)2廠9 R

45、 4E S 51 T E0 U 23 V 3 W 13 X 1 T 16 2 11E6 A 64 B 13 C 22 D 32 E 103 F 21 G 15 H 47 I E? J 1 E 5 L 32M 20 N 5? 63 P 15 Q 1圖17HFMTREE.TX文本文件,記錄輸入的各字符及其權(quán)值7.附錄源程序文件名清單:TEXTFILE.TXT記錄待編碼的句子CODEFILE.TXT記錄哈夫曼編碼HFMTREE.TXT記錄字符個數(shù)、名稱及權(quán)值源代碼:#i nclude <stdio.h>#i nclude <stri ng.h>#in clude <ma

46、lloc.h>#in cludevstdlib.h>#in clude<ct yp e.h>#defi ne NULL 0#defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -2#defi ne MAX_NUM 32767#defi ne MAX 60typ edef char *Huffma nCode;/動態(tài)分配數(shù)組存儲哈夫曼表碼表typ edef structun sig ned int weight;un sig ned int paren t,lchild,rchild;HTNode,*HuffmanTree;/動態(tài)分

47、配數(shù)組存儲哈夫曼樹typ edef structHuffma nTree HT;c;charintlen gth;Huffma nCode HC;選擇 HT1.i-1 中Huffman;ll全局結(jié)構(gòu)體變量，來存儲字符與代碼void Select(Huffma nTree HT,i nt en d,i nt *s1,i nt *s2)/無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1, s2int i;int mi n仁MAX_NUM;int min2;for (i=1;i<=e nd;i+)/遍歷查找權(quán)值最小的結(jié)點S1if (HTi. pare nt=0&&H Ti.weight

48、vmi n1)*s1=i;min 1=HTi.weight;min 2=MAX_NUM;for(i=1;i<=e nd;i+)/遍歷查找除S1外權(quán)值最小的結(jié)點S2if(HTi. pare nt=O&&(*s1!=i)&&mi n2>HTi.weight)*s2=i;mi n2=HTi.weight;Huffman HuffmanCoding(Huffman Hfm) / 存放 n 個字符的權(quán)值(均0),構(gòu)造哈 夫曼樹HT,并求出n個字符的構(gòu)造哈夫曼編碼 HCint i,n, m,s1,s2,start;int c,f;char *cd;n=H fm.

49、le ngth;if(nv=1) return Hfm;m=2* n-1;for(i=n+1;iv=m;+i)/選擇HT1.i-1中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1, s2仃Select(Hfm.HT,i-1,&s1,&s2);Hfm.HTi.lchild=s1;/Hfm.HTi.rchild=s2;修改父親位置修改孩子位置Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/為左右孩子權(quán)值之和父親結(jié)點權(quán)值/從葉子結(jié)點到根逆向求每個字符的哈夫曼編碼Hfm.HC=(Huffma nCode)malloc( n+1)*sizeof(

50、char *);/頭指針向量分配n個字符編碼的cd=(char *)malloc( n*sizeof(char);/分配求編碼的工作空間cd n-1='0'/編碼結(jié)束符for(i=1;i<=n;+i)/逐個字符求哈夫曼編碼23從葉子到根start=n-1;/編碼結(jié)束符位置for(c=i,f=Hfm.HTi. pare nt;f!=0;c=f,f=Hfm.HTf. pare nt)/逆向求編碼if(c=Hfm.HTf.lchild) cd-start='0'else cd-start-1'Hfm.HCi=(char *)malloc( n-start

51、)*sizeof(char);strc py(Hfm.HCi,&cdstart);/從cd復制編碼到Hfm.HCfree(cd);/釋放工作空間return Hfm;Huffman Inp utHuffma n(Huffman Hfm)/輸入函數(shù)，控制用戶輸入字符和相應權(quán)值int i,n;printf("nn*lnitialization*n");printf("Thechars and weights will be saved in the file :hfmTree n");printf("PI ease input the nu

52、 mber of the chars:");sca nf("%d",&n);若只有一個數(shù)if(nv=1) prin tf("O niy One Char!There Is No Need For Codi ng!");/值則無需編碼prin tf("n");prin tf(" PI ease input the nu mber of the chars:");sea nf("%d",&n);Hfm.HT=(Huffma nTree)malloc(2* n)*sizeof(HTNode);Hfm.c=(char *)malloc( (n+1)*sizeof(char);for(i=1;i<=n ;i+)prin tf(" PI ease input the char:");scan f("%s",&H