應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(哈夫曼樹)

1、學(xué)號(hào)：0120803490117課程設(shè)計(jì)題目Huffman編/譯碼命學(xué)院管理學(xué)院專業(yè)信息管理與信息系統(tǒng)班級(jí)0801姓名王濤指導(dǎo)教師燕翔課程設(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ù):（包括課程

2、設(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:印哈夫曼樹。

3、將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。時(shí)間安排：指導(dǎo)教師簽名:系主任（或責(zé)任教師）簽名:年07月02日在舁 廳P設(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)試r 2大5總結(jié)和整理設(shè)計(jì)報(bào)告1天合 計(jì)7天2010年07月02日1 .需求分析1.1 程序的任務(wù)：利用Huffman編碼進(jìn)行通信可以大大提高信道利用率.縮短信息傳輸時(shí)間，降 低傳輸成本，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將 傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道

4、（即可以雙向傳輸信息的信道），每端 都需要一個(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í)將此字符形式的哈夫曼樹寫入

5、文件TreePrint中。1.3 程序要達(dá)到的功能：用戶可以利用菜單根據(jù)自己的需要來選擇要進(jìn)行編碼或是譯碼，并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應(yīng)的文件里面。1.4 測(cè)試數(shù)據(jù)如下表：（l）利用教材中的數(shù)據(jù)調(diào)試程序。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào) 文的編碼和譯碼：THIS PROGRAM IS MY FAVORIT E字符ABCDEFGHIJKLMNOPQRSTUVW .XY Z頻度186 (54 13 212 32 103 21 15、4757153220576351485180238181161選擇 E , 輸入 THIS PROGRAMS MY

6、FAVORITE, 屏幕 上顯示 110100010110001111110001000101001100001001010101100101110110001111111001 0100011111110011101011000001001001001101101010同時(shí)文件codefile里面也出現(xiàn)相應(yīng)的代碼選擇D,從codefile 中調(diào)入代碼，終端顯示 THIS PROGRAM IS MY FAVORITE并且文件 textfile 中也相應(yīng)的存入了這段話。選才 P,文件CodeFile以緊湊格式顯示在終端上。選擇 T， 將已在內(nèi)存中的哈夫曼樹以直觀的方式 (樹或凹入表形式) 顯示在

7、終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。選擇其他的字母，將出現(xiàn)出錯(cuò)提示，并重新回到選擇菜單。2 . 概要設(shè)計(jì)ADT BinaryTree 數(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)的深度值之后和最小?；静僮鱌：InputHuffman(Huffman Hfm)操作結(jié)果：輸入并存儲(chǔ)字符和相應(yīng)權(quán)值。Select(HuffmanTree HT,int end,int *s1,int

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

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

10、e 已經(jīng)存在。操作結(jié)果：將已在內(nèi)存中的哈夫曼樹以凹入表的形式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。 ADT HuffmanTree2 . 2 主程序流程Void main()顯示菜單；Switch(k)I ：初始化E:編碼D:譯碼P:印代碼文件T:印哈夫曼樹Q退出運(yùn)行292.3程序調(diào)用模塊Main函數(shù)InitHuffmanEncodingDecodingPrintTreeprintQuit3 .詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)類型：typedef char *HuffmanCode;動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼表碼表typedef structunsigned int wei

11、ght;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼樹typedef structHuffmanTree HT;char *c;int length;HuffmanCode HC;Huffman;/分配數(shù)組存儲(chǔ)字符串及其對(duì)應(yīng)的霍夫曼樹Huffman Hfm;char k; /*控制循環(huán)的標(biāo)志*/3.2 偽碼算法：主程序main()InitHuffman(Huffman Hfm)；Encoding(Huffman Hfm)；Decoding(Huffman Hfm)；Print(Huffman Hfm)；Tr

12、eeprint(Huffman Hfm) ；其他模塊：/ 選擇 HT1i-1 中無雙void Select(HuffmanTree HT,int end,int *s1,int *s2) 親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1 ， s2FOR (i=1;i*s1IF(HTi.parent 是次最小的 )THEN HTi.parent*s2Huffman HuffmanCoding(Huffman Hfm) /w 存放 n 個(gè)字符的權(quán)值(均0) ，構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的構(gòu)造赫夫曼編碼HCFOR(i=n+1;i=2*n-1;+i) / 選擇 HT1i-1 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，

13、其序號(hào)為 s1， s2Select(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.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/ 從葉子到根逆向求編碼IF(c=Hfm.HTf.lchild) cd-start=0;ELSE cd-start=1;再?gòu)?cd 復(fù)制編碼到 Hfm.HCRETURN Hfm;Huffman InitHuffman(Huf

14、fman Hfm)/ 初始化赫夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值對(duì)文件 hfmTree 以讀文本的形式打開IF(fp=NULL)調(diào)用 InputHuffman 函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入赫夫曼數(shù)中ELSE輸出 The Huffmantree has already existed!nPlease choose again!nn);讀入 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 分別

15、賦值0Hfm=HuffmanCoding(Hfm);RETURN Hfm;void Encoding(Huffman Hfm) / 利用已建好的 Huffman 樹(如不在內(nèi)存，則從文件hfmTree 中讀入) ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。輸出 nn*Encoding*nnIF(ffp=fopen(ToBeTran,rt)=NULL)提示輸入 Please input the sentence:scanf(%s,ch);printf(n);以寫文本的形式打開CodeFileELSE讀入ToBeTran文件中的字符；WHILE(chj)

16、FOR(i=1;i0， rchild 1 來輸出入到文件TextFile 中 關(guān)閉文件void Print(Huffman Hfm) /將文件CodeFile以緊湊格式，示在終端上，每行 50個(gè)代FOR(i=1;iedseinpu ttlev/eicjhI ofthe匚hdf: 21yeaseinputtlechar: Gedeinpu ttleweigh I ufthechdr: 15easeinputtlechar: H獷easeinputtleweight ofthechar: 4 7yeaseinouttlechar: I.easeinptjltleweight oftheciter:

17、 57easeinputtlechdr: Jeaseinputtleweight ofth電char1 1Pleaseinputtheclidr: KPledgeinputtheghf ofthechar : 5PleaseinputLite仁hd： LPleaseinputtheMdighl ofthechor: 32inpu ttlechar: Keaseinputtweiqhl ofthech： 20J.easeinputtleclidr: NyeaseinputtrewciM ofthechar: 57edseinputtleclidr: 0）：easeinnult1ewei gh1

18、ofthechar: 63easeinputtlechar: Poasoi nou tt10weidhi oft heeh: 15PlPrlsAi np(ittlhpchar: Q3lettseinputIieweight oft hechar:13leaseinputilechar: Rleaseinput1leweight ofihechar:48JlcasoinputtICchar: SPleaseinputtheweight ofchar:51Pleasei nputthechar: T5leasenwti ttieweLuht ofI hechdr:80leaseinpuiiiech

19、ar* Uleaseinputtleweight ofthechar:23Pleaseinputihechar; VPleaseinputtheweight ofthechar:8Plea,sei nptit寸hachrir: U3leaseHWU tIieweight ufI hechar:18leaseinputtlechar: XleaseinputIleweight ofthechar:1Jlcaseinputthechar: VPleaseinputtheweight ofihechar:16PlPrlSPi nputthechar: 2Pleaseinputtheweight of

20、thechar:1圖4、5在字符個(gè)數(shù)處輸入“ 27”，之后依次輸入各字符及其權(quán)值。Jhank Vou To list; MV Huffman PruyrdwI.InitializationF, Fngdi ng l).kcoding P,Printing T.TreePrintQ.Ait!Pierisp Tnuuf ?our OptionEnethnjPl心口士已 ifiput thd i鈾rilitncn:在菜單界面選擇E,出現(xiàn)提示語句，要求輸入句子I Ih.mk Von Io 比： 修.并加 ProoronIII.InitializationC.EikocKiwDDficorlirwP.P

21、r ini ingF.TreefrintQ.ExitPI ease Ir巾ul Vour Un t i atiMFWW H WW+fli 暨*量*片* /Eric口 ding*1 胃洞” 8/-X1Mll1*%m州，*，:f：dsp inpLit the 工印Ibtie; IHIS PROGRFH IS NV FAVDRITfLieiwtai j noti jniiHuuy uoi in 呢 11 即如 i 州 i uio u uui jiiiBiiuBuniiiii aoiyiawuinLlUO8111O191lO00OOtOOlMinill 101910輸入“THIS_PROGRAM_IS

22、_MY_FAV。R|TE車之后，顯示出該句的哈夫曼編碼圖8將譯出的字符顯示出50個(gè)。結(jié)果如下圖:（此處為求簡(jiǎn)捷，將空格用下劃線“ _”作為代替）I Thank Von To Use MV Huffman Program jII.In i 11d1i1i onF.Fncodino DDecodiro P Print inn T,TreePrxnt!O.EHitiPlease Input Vour Option D口”口 d i ng1The file is : THIS PROGRAM IS MY FAVORITE在菜單界面選擇D,則對(duì)文件中已有的哈夫曼編碼進(jìn)行反譯, 來。| Thi?nk Yo

23、u To Lha MV Huffitin ProarLimI.Ini 1inlization|E.Encoding n.npcodirtoP.；Pri niingT.TrRePrint|JU.ExiliPlease JnpuI Vour Op I ionP圖 9在菜單界面選擇P,將文件中的哈夫曼編碼緊湊輸出，每行t th白LiMiH ui Lviifl ，rid三觸外科- 1 lor. _Ueiyiil.166CMet：111thw 11Nr i ih 1 -64Code;HUQ口ISUeiiL13CM&；制MM忡hflr ：MgM -22Codp 腳oneth Jr- Dlileidit l

24、32Code:10110?hdr 匚Weight;103Code 1eioihtfr- r21Cmle:1UMIHChrtr- G15CodR：i白俱貼iCfl.ir H加曲1klCo Ln hl：心IE1Jeigh-tlC l hT :版fllH/Ei, hrtf23ieiglrt-BIH1-11a禽 iylrt 二irihflluMt-2Jb i kx；34 1 g bt-44 iy ht=9Aigg17ihti前島:j qht：11Ae iflliltiK足 IghT：后 if|hl?翎.如知h*二b4j-3 jit-A72/LhM：屈 iqhrt：11/4詞 Lil ht- , hP-

25、Tircfi t 45nraiS心rm把Gt1 27Faremt4BIaremt 4：36IoJvtit 13writ：孤Firrmt i43Faruii* 二如fdJPVIlt 31F山附而二3Faif&nC iFdLFSflC =43FBiriri Z4434PAremt t20PFemt42rarefit 42Fnrsine 鼎白Fnrevit: S37I-a-rrm t -32K-a-rvtit -鳴FaJrvflt ：FdJPVlt :*11alTt 二2?3HFri PMIIlt M3口PiirAfl t ?31Paretrt i32：J5Pn曰iidt工3HFnreii.t：3薛

26、Paremt t4 3Farem t 黑49rnrefifrt41PrtFFIl t： m4Ia-Tffmt -45v七i4&rfljpvfie ：47P4rmt 47Lern t =48Pm ir 日料4 ：；-1 ?TjcMldUM Id iLehi Id； Lclii Id t Uhild： UhildT Lchild： Lcliild： Uhlldi uhi id； Uhildi Le hi hl iTiChild： Lchildi LcMldi UMlidi LrhildxLehi Id ： LchAldt UlsildT LchildT Uhild：Ida hud： LehilRc

27、hildL：MHclixlift：UIkJiill：恥lll心RciiildzBJklixld：勺融IM,艇 Hldh9Itehildl：等felhild：gRc)illd) =ARclhildl：ARcjhiltl：gRcliildL：修RcHIMmItelhlHzftUchi lii：0Rciixldz修JkJnldLHfell illsw曲 liilM：gftdilld.修ItoJilldL：Ilf曜R(shí)chilAs曾9Rell tig12ItehlM：31Iklillfl：ftMEnciiiiti：24Fkhllil:7Itehilrtz22Heli i Id?14jhiiildi13M

28、Zil士如llDtiildlsVUchi IdsRcMld =15lb圖14在菜單界面選擇T,打印處內(nèi)存中的哈夫曼樹各節(jié)點(diǎn)的值及其雙親節(jié)點(diǎn)和子節(jié)點(diǎn)TEXTFILE -記事本其鍬D期I西格式章看M糊畫|THI S_PRCKRAB_IS_MY_FAVDRITE圖15TEXTFILE.TX”本文件，記錄用戶輸入的需要進(jìn)行編碼的句子4匚8皿a事Mil Wrtra MMmcnoijiiiiimiiiiitn -ujiciciijiioiiOiQOKlimoikuici11utiquonLiniouiiojqihiliicwiii1咖ninMgLiiJLhw/Q圖16CODEFILE.TXT：本文件，記錄

29、TEXTFILE.TX位本文件中字符的哈弗曼編碼。一HfkfTR=E = OK*-*.I Q | 曰一文aH #垃 E； fcj.O) V)里助 H：一27_ 155 A 64 B 13 C 22 D 曉 E 103 F 21 C 15 H 47 I 57 J 1 E 5 L 32It 20 N 57 C 63 F 15 0 1 R 48 3 Ei I 80 Lr S3 V S W 18 X 1 Y 1& 工二圖17HFMTREE.TXT本文件，記錄輸入的各字符及其權(quán)值7.附錄記錄待編碼的句子 記錄哈夫曼編碼 記錄字符個(gè)數(shù)、名稱及權(quán)值源程序文件名清單：TEXTFILE.TXTCODEFILE.

30、TXTHFMTREE.TXT源代碼：#include #include #include #include#include#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char *HuffmanCode;/ 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/ 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹

31、typedef structHuffmanTree HT;char *c;int length;HuffmanCode HC;Huffman;/ 全局結(jié)構(gòu)體變量，來存儲(chǔ)字符與代碼void Select(HuffmanTree HT,int end,int *s1,int *s2)/選擇 HT1i-1 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1， s2int i;int min1=MAX_NUM;int min2;for (i=1;i=end;i+)/ 遍歷查找權(quán)值最小的結(jié)點(diǎn) S1if (HTi.parent=0&HTi.weightmin1)*s1=i;min1=HTi.weight;min

32、2=MAX_NUM;for(i=1;iHTi.weight)*s2=i;min2=HTi.weight;Huffman HuffmanCoding(Huffman Hfm) / 存放 n 個(gè)字符的權(quán)值(均0)，構(gòu)造哈夫曼樹HT,并求出n個(gè)字符的構(gòu)造哈夫曼編碼 HCint i,n,m,s1,s2,start;int c,f;char *cd;n=Hfm.length;if(n=1) return Hfm;m=2*n-1;for(i=n+1;i=m;+i)/ 選擇 HT1i-1 中無雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)， 其序號(hào)為 s1 ， s2Select(Hfm.HT,i-1,&s1,&s2);Hfm.H

33、Ts1.parent=i;/修改父親位置Hfm.HTs2.parent=i;Hfm.HTi.lchild=s1;/修改孩子位置Hfm.HTi.rchild=s2;Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/ 父親結(jié)點(diǎn)權(quán)值 為左右孩子權(quán)值之和/ 從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/ 分配 n 個(gè)字符編碼的 頭指針向量cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/ 編碼結(jié)束符for(i=1

34、;i=n;+i)/ 逐個(gè)字符求哈夫曼編碼start=n-1;/ 編碼結(jié)束符位置for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/從葉子到根逆向求編碼if(c=Hfm.HTf.lchild) cd-start=0;else cd-start=1;Hfm.HCi=(char *)malloc(n-start)*sizeof(char);strcpy(Hfm.HCi,&cdstart);/從 cd 復(fù)制編碼到 Hfm.HCfree(cd);/ 釋放工作空間return Hfm;Huffman InputHuffman(Huffman Hfm)/ 輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值int i,n;pr