應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--huffman編／譯碼器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：33 大小：958.47KB 人氣指數(shù)：12 舉報 版權(quán)申訴

應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--huffman編／譯碼器_第1頁

已閱讀1頁，還剩32頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè) 計　　課程設(shè)計任務(wù)書　　題目： Huffman編／譯碼器　　初始條件：　　利用Huffman編碼進行通信可以大大提高信

2、道利用率．縮短信息傳輸時間，降低傳輸成本，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編／譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個Huffman碼的編／譯碼系統(tǒng)。　　要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求、說明書撰寫等具體要求）　　一個完

3、整的系統(tǒng)應(yīng)具有以下功能：　　（l）I：初始化。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。　　（2）E：編碼。利用已建好的Huffman樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。

4、?。?）D：譯碼。利用已建好的Huffman樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。　?。?）P：印代碼文件。將文件CodeFile以緊湊格式顯示在終端上，每行50 個代碼。　　（5）T：印哈夫曼樹。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。

5、　　時間安排：　　需求分析　　程序的任務(wù)：　　利用Huffman編碼進行通信可以大大提高信道利用率．縮短信息傳輸時間，降低傳輸成本，這要求在發(fā)送端通過一個編碼

6、系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編／譯碼系統(tǒng)。此程序就是為這樣的信息收發(fā)站寫一個Huffman碼的編／譯碼系統(tǒng)。　　程序的輸入和輸出：　　從終端讀入字符集大小n，以及n個字符及各個字符的權(quán)值，建立赫夫曼樹，并將它存儲到文件hf

7、mTree中；利用已建好的赫夫曼樹將文件中的字符編碼，如果赫夫曼樹不在內(nèi)存中，則從文件hfmTree中讀取到內(nèi)存；將譯得的代碼存到文件CodeFile中；利用已建好的赫夫曼樹對CodeFile中的代碼進行譯碼，將結(jié)果存入文件TextFile中；最后將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　　程序要

8、達到的功能：　　用戶可以利用菜單根據(jù)自己的需要來選擇要進行編碼或是譯碼,并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應(yīng)的文件里面。　　測試數(shù)據(jù)如下表：　?。╨）利用教材中的數(shù)據(jù)調(diào)試程序。　?。?）用下表給出的字符集和頻

9、度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼："THIS PROGRAM IS MY FAVORITE"。　　選擇E，輸入THIS PROGRAM IS MY FAVORITE，屏幕上顯示11010001011000111111000100010100110000100101010110010111011000111111100101000111111100111

10、01011000001001001001101101010　　同時文件codefile里面也出現(xiàn)相應(yīng)的代碼　　選擇D，從codefile中調(diào)入代碼，終端顯示THIS PROGRAM IS MY FAVORITE，并且文件textfile中也相應(yīng)的存入了這段話。　　選擇P，文件CodeFile以緊湊格式顯示在終端上

11、。　　選擇T，將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　　選擇其他的字母，將出現(xiàn)出錯提示，并重新回到選擇菜單。　　概要設(shè)計　　ADT BinaryTre

12、e{　　數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素集合。　　數(shù)據(jù)關(guān)系R：　　若D為空，則R為空，稱Huffmantree為空霍夫曼樹；　　若D不為空，則R={H}，H是如下的二元關(guān)系：　　1、 H

13、滿足二叉樹的所有要求；　　2、 H中所有數(shù)乘以該數(shù)所在節(jié)點的深度值之后和最小。　　基本操作P：　　InputHuffman(Huffman Hfm) 　　操作結(jié)果：輸入并存儲字符和相應(yīng)權(quán)值。

14、　Select(HuffmanTree HT,int end,int *s1,int *s2)　　初始條件：頻率數(shù)組已經(jīng)建立。　　操作結(jié)果：選擇HT[1....i-1]中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2。　　HuffmanCoding(Huffman Hfm)

15、;　　初始條件：頻率數(shù)組已經(jīng)建立。　　操作結(jié)果：w存放n個字符的權(quán)值（均>0），構(gòu)造赫夫曼樹HT，并求出n個字符的構(gòu)造赫夫曼編碼HC。　　InitHuffman(Huffman Hfm)　　初始條件：頻率數(shù)組已經(jīng)建立。　　操作結(jié)果：要求用戶輸入字符和相應(yīng)權(quán)值，初

16、始化赫夫曼數(shù)　　Encoding(Huffman Hfm)　　初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。　　操作結(jié)果：利用已建好的Huffman樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。<p&

17、gt;　　Decoding(Huffman Hfm)　　初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。　　操作結(jié)果：利用已建好的Huffman樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。　　Print(Huffman Hfm)　　初始條件

18、：霍夫曼樹HoffmanTree已經(jīng)存在。　　操作結(jié)果：將文件CodeFile以緊湊格式顯示在終端上，每行50 個代碼。　　Treeprint(Huffman Hfm)　　初始條件：霍夫曼樹HuffmanTree已經(jīng)存在。　　操作結(jié)果：將已在內(nèi)存中的哈夫曼樹以凹入表的形式

19、顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　　}ADT HuffmanTree　　2 主程序流程　　Void main()　　{<p&g

20、t;　　顯示菜單；　　Switch(k)　　{ 　　I：初始化　　E：編碼<

21、/p>　　D：譯碼　　P：印代碼文件　　T：印哈夫曼樹　　Q：退出運行

22、} 　　}　　程序調(diào)用模塊　　詳細(xì)設(shè)計　　3.1數(shù)據(jù)類型： 　　typedef char

23、**HuffmanCode;//動態(tài)分配數(shù)組存儲霍夫曼表碼表　　typedef struct{　　unsigned int weight;　　unsigned int parent,lchild,rchild;　　}HTNode,*HuffmanTree;//動態(tài)

24、分配數(shù)組存儲霍夫曼樹　　typedef struct{　　HuffmanTree HT;　　char *c;　　int length;　　HuffmanCode HC;<

25、p>　　}Huffman;//分配數(shù)組存儲字符串及其對應(yīng)的霍夫曼樹　　Huffman Hfm;　　char k; /*控制循環(huán)的標(biāo)志*/　　3.2 偽碼算法：　　主程序

26、　　main()　　{　　InitHuffman(Huffman Hfm)；　　Encoding(Huffman Hfm)；　　Decoding(Huffman Hfm)；&l

27、t;/p>　　Print(Huffman Hfm)；　　Treeprint(Huffman Hfm)；　　}　　其他模塊：　　void Select(HuffmanTr

28、ee HT,int end,int *s1,int *s2)//選擇HT[1....i-1]中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2　　FOR (i=1;i<=end;i++)　　{　　IF(HT[i].parent是最小的)<p&

29、gt;　　THEN HT[i].parent——>*s1　　IF(HT[i].parent是次最小的)　　THEN HT[i].parent——>*s2　　}　　Huffman HuffmanCoding(Huffma

30、n Hfm) //w存放n個字符的權(quán)值（均〉0），構(gòu)造赫夫曼樹HT，并求出n個字符的構(gòu)造赫夫曼編碼HC　　{　　FOR(i=n+1;i<=2*n-1;++i) //選擇HT[1....i-1]中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2　　{<

31、;/b>　　Select(Hfm.HT,i-1,&s1,&s2);　　修改父親位置； 　　修改孩子位置；　　父親結(jié)點權(quán)值為左右孩子權(quán)值之和；　　}&

32、lt;/b>　　//從葉子結(jié)點到根逆向求每個字符的赫夫曼編碼　　FOR(i=1;i<=n;++i)　　//逐個字符求赫夫曼編碼　　{ start=n-1;//編碼結(jié)束符位置　　for(c=i,f=Hfm.HT[i].p

33、arent;f!=0;c=f,f=Hfm.HT[f].parent)　　//從葉子到根逆向求編碼　　{　　IF(c==Hfm.HT[f].lchild) cd[--start]='0';　　ELSE cd[--sta

34、rt]='1';　　}　　再從cd復(fù)制編碼到Hfm.HC　　}　　RETURN Hfm;　　}<

35、;/p>　　Huffman InitHuffman(Huffman Hfm)//初始化赫夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值　　{　　對文件hfmTree以讀文本的形式打開　　IF(fp==NULL)　　調(diào)用

36、InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入赫夫曼數(shù)中　　ELSE　　輸出"The Huffmantree has already existed!\nPlease choose again!\n\n");　　讀入hfmTree中文本 &l

37、t;/p>　　FOR(i=1;i<=n;i++)　　作為獨立結(jié)點對結(jié)點的parent，lchild，rchild分別賦值0　　FOR(;i<=2*n-1;++i)　　作為獨立結(jié)點對結(jié)點的weight，parent，lchild，rchild分別賦值0 </p&g

38、t;　　Hfm=HuffmanCoding(Hfm);　　RETURN Hfm;　　}　　void Encoding(Huffman Hfm)//利用已建好的Huffman樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行

39、編碼，然后將結(jié)果存入文件CodeFile中。　　{　　輸出"\n\n*******************Encoding**************************\n\n"　　IF((ffp=fopen("ToBeTran"

40、,"rt"))==NULL)　　提示輸入"Please input the sentence: "　　scanf("%s",ch);　　printf("\n");　　以寫文本的形式打開Code

41、File　　ELSE　　讀入ToBeTran文件中的字符;　　WHILE(ch[j])　　FOR(i=1;i<=n;i++)　　IF(ch[j]==Hfm.c[i])

42、　　分別在終端和文件CodeFile輸入Hfm.HC[i]　　void Decoding(Huffman Hfm)//利用已建好的Huffman樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。　　{ 定義char d[500]　　輸出"\n\n******

43、************Decoding************************\n\n"　　IF((fp=fopen("CodeFile","rt"))==NULL)　　輸出Please input the code:;　　ELSE

44、 　　將文件Codefile中的內(nèi)容讀到d數(shù)組中　　輸出The file is :　　以寫文本的方式打開TextFile　　WHILE(d[j])　　根到葉子結(jié)點遍歷，并按照lchild——>0，rch

45、ild——>1來輸出　　入到文件TextFile中　　關(guān)閉文件　　}　　void Print(Huffman Hfm)//將文件CodeFile以緊湊格式，示在終端上，每行50 個代碼。&l

46、t;/p>　　{　　FOR(i=1;i<=n;i++)　　輸出Hfm.c[i]　　輸出Hfm.HT[i].weight　　以只讀二進制的方式打開CodeFile文件<p&

47、gt;　　while ( feof(fprint)==0 )　　逐個輸出　　IF (m%50==0)　　輸出"\n"　　關(guān)閉文件</

48、p>　　}　　void Treeprint(Huffman Hfm)//將已在內(nèi)存中的哈夫曼樹以凹入表的形式顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　　{　　打開hfmTree文件

49、　　將字符及其對應(yīng)的代碼賦給變量Hfm.c[i]和Hfm.c[i][j]　　輸出Hfm.c[i]，對Hfm.c[i][j]進行判斷，不是\n則輸出*，否則停止輸出　　}　　3.3函數(shù)調(diào)用關(guān)系圖

50、　　調(diào)試分析　　4.1 調(diào)試過程中遇到的問題：　　第一個問題是一直比較棘手的問題就是文件的調(diào)用與寫入，因為文件方面的知識一直就掌握的不是很好，在寫代碼時產(chǎn)生很大困難，所以在解決這個問題的時候我把文件部分系統(tǒng)的看了一下，這才從自身角度解決了這個問題。而實際中遇到的問題就是如何判斷已經(jīng)有了hfmtree這個文件，并且怎么

51、調(diào)用到內(nèi)存中來。　　解決方案：設(shè)置一個全局結(jié)構(gòu)體變量來存放已經(jīng)在文件中存放的霍夫曼樹。　　第二個問題是關(guān)于界面的美觀設(shè)計方面，因為很多代碼在文本中編輯時是比較整齊美觀的，但是在程序運行中卻出現(xiàn)很多問題，不對齊等等。還有就是換行符的使用，一不小心就會產(chǎn)生偏差。　　解決方案：進入程序進行調(diào)試，檢查每段輸出代碼的顯示。

52、　　第三個問題是Huffman樹的打印，方式為凹入式打印，由于在當(dāng)時學(xué)習(xí)的時候這部分內(nèi)容沒有留意，根本沒有概念，所以在編寫程序過程中出現(xiàn)了嚴(yán)重的問題。導(dǎo)致該項功能無法完成。　　解決方案：尚未完善解決，只是將內(nèi)存中的哈夫曼樹中各節(jié)點的值及其孩子輸出。　　4.2 算法的時空分析：<p&g

53、t;　　算法的時間復(fù)雜度：　　Select(HuffmanTree HT,int end,int *s1,int *s2) O(n)　　HuffmanCoding(Huffman Hfm) O(n2)　　InputHuffman(Huffm

54、an Hfm) O(n)　　InitHuffman(Huffman Hfm) O(n)　　Encoding(Huffman Hfm) O(n)　　Decoding(Huffman Hfm)

55、 O(n)　　Print(Huffman Hfm) O(n)　　4.3 經(jīng)驗與體會：　　整個程序在編的時候思路是很明朗的，包括菜單的設(shè)置都是很清晰的，但是如何通過一個菜單將所有涉及到的文件與終端聯(lián)系起來還有打印哈夫曼樹都是比較困難的問題，由于

56、文件這一章節(jié)我們以前學(xué)習(xí)的時候并沒有很重視，所以在運用的時候遇到了很大的困難，同時通過這次的設(shè)計我也看到其實文件這一章是很重要的，我們做了一個程序，必須要把有些必要的數(shù)據(jù)進行保存，如果只是停留在內(nèi)存中那就很難在以后被重復(fù)利用，會很大程度上提高我們調(diào)試的效率；另外凹入式打印哈夫曼樹更是讓我頭疼了一整天的問題，由于根本不知道其概念是什么，更不用說去編寫代碼了。同時我也覺得有些細(xì)節(jié)問題是很重要的，不管是一個整型變量還是一個結(jié)構(gòu)體變量，有時候?qū)?/p>

57、整個程序起著至關(guān)重要的作用。　　用戶使用說明　　1．本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：hfmtree.exe。　　2. 運行程序后出現(xiàn)選擇菜單。　　3．根據(jù)提示選擇相應(yīng)的操作，初始化，編碼，譯碼，印代碼文件，印哈夫曼樹&l

58、t;/p>　　退出，每次選擇完，都會再次彈出選擇菜單供用戶選擇。結(jié)束符為回車鍵。　　測試結(jié)果　　在進入系統(tǒng)以后，選擇第一個初始化，按要求鍵入要求的字符及其頻度　　截圖如下所示：<p

59、>　　圖1　　進入程序，顯示的菜單界面　　圖2　　輸入I，選擇進行初始化　　圖3　　初始化時對字符的個數(shù)進行限

60、制，不得少于2個。　　圖4、5　　在字符個數(shù)處輸入“27”，之后依次輸入各字符及其權(quán)值。　　圖6　　在菜單界面選擇E，出現(xiàn)提示語句，要求輸入句子。<

61、b>　　圖7　　輸入“THIS_PROGRAM_IS_MY_FAVORITE”，回車之后，顯示出該句的哈夫曼編碼。　?。ù颂帪榍蠛喗?，將空格用下劃線“_”作為代替）　　圖8　　在菜單界面選擇D，則對文件中已有

62、的哈夫曼編碼進行反譯，將譯出的字符顯示出來。　　圖9　　在菜單界面選擇P，將文件中的哈夫曼編碼緊湊輸出，每行50個。結(jié)果如下圖：　　圖10、11　　該程序中，我加入了將初始化的各字符的編碼輸出的語

63、句，可以看到各個字符的哈弗曼編碼。　　圖12　　這3行數(shù)字便是緊湊輸出哈夫曼編碼的結(jié)果。　　圖13　　同時，不同的人使用本程序進行不同的哈夫曼編碼時，由于前一位使用者初始化的數(shù)據(jù)后一位不一定同樣適

64、用，為了避免這種情況，因此當(dāng)已經(jīng)初始化后再進行初始化時會出現(xiàn)提示是否重新初始化的信息提示，如上圖所示。　　圖14　　在菜單界面選擇T，打印處內(nèi)存中的哈夫曼樹各節(jié)點的值及其雙親節(jié)點和子節(jié)點。　　圖15

65、;　　TEXTFILE.TXT文本文件，記錄用戶輸入的需要進行編碼的句子。　　圖16　　CODEFILE.TXT文本文件，記錄TEXTFILE.TXT文本文件中字符的哈弗曼編碼。　　圖17　　HF

66、MTREE.TXT文本文件，記錄輸入的各字符及其權(quán)值　　附錄　　源程序文件名清單：　　TEXTFILE.TXT 記錄待編碼的句子　　CODEFILE.TXT 記錄哈

67、夫曼編碼　　HFMTREE.TXT 記錄字符個數(shù)、名稱及權(quán)值　　源代碼：　　#include <stdio.h>　　#include <string.h><p&g

68、t;　　#include <malloc.h>　　#include<stdlib.h>　　#include<ctype.h>　　#define NULL 0　　#define OK 1　　#de

69、fine ERROR 0　　#define OVERFLOW -2　　#define MAX_NUM 32767　　#define MAX 60　　typedef char **HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼表碼表<p&g

70、t;　　typedef struct{　　unsigned int weight;　　unsigned int parent,lchild,rchild;　　}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹　　typedef struct{&

71、lt;/p>　　HuffmanTree HT;　　char *c;　　int length;　　HuffmanCode HC;　　}Huffman;//全局結(jié)構(gòu)體變量，來存儲字符與代碼<

72、;p>　　void Select(HuffmanTree HT,int end,int *s1,int *s2)//選擇HT[1....i-1]中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2　　{　　int i;　　int min

73、1=MAX_NUM;　　int min2;　　for (i=1;i<=end;i++)//遍歷查找權(quán)值最小的結(jié)點S1　　{　　if (HT[i].parent==0&&HT[

74、i].weight<min1)　　{　　*s1=i;　　min1=HT[i].weight;　　}<b&

75、gt;　　}　　min2=MAX_NUM;　　for(i=1;i<=end;i++)//遍歷查找除S1外權(quán)值最小的結(jié)點S2　　{　　if(HT[i].parent==0&&(*s1!=i)&a

76、mp;&min2>HT[i].weight)　　{　　*s2=i;　　min2=HT[i].weight;　　}<

77、p>　　}　　}　　Huffman HuffmanCoding(Huffman Hfm) //存放n個字符的權(quán)值（均〉0），構(gòu)造哈夫曼樹HT，并求出n個字符的構(gòu)造哈夫曼編碼HC　　{</p

78、>　　int i,n,m,s1,s2,start;　　int c,f;　　char *cd;　　n=Hfm.length;　　if(n<=1) return H

79、fm;　　m=2*n-1;　　for(i=n+1;i<=m;++i) //選擇HT[1....i-1]中無雙親且權(quán)值最小的兩個節(jié)點，其序號為s1，s2　　{　　Select(Hfm.HT,i

80、-1,&s1,&s2);　　Hfm.HT[s1].parent=i;//修改父親位置　　Hfm.HT[s2].parent=i;　　Hfm.HT[i].lchild=s1;//修改孩子位置　　Hfm.HT[i].rchild=s2;

81、　　Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父親結(jié)點權(quán)值為左右孩子權(quán)值之和　　}　　//從葉子結(jié)點到根逆向求每個字符的哈夫曼編碼　　Hfm.HC=(HuffmanCode)malloc((

82、n+1)*sizeof(char *));//分配n個字符編碼的頭指針向量　　cd=(char *)malloc(n*sizeof(char));//分配求編碼的工作空間　　cd[n-1]='\0';//編碼結(jié)束符　　for(i=1;i<=n;++i)//逐個字符求哈夫曼編碼</p&g

83、t;　　{　　start=n-1;//編碼結(jié)束符位置　　for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//從葉子到根逆向求編碼　　{

84、　　if(c==Hfm.HT[f].lchild) cd[--start]='0';　　else cd[--start]='1';　　}　　Hfm.HC[i]=(char *)malloc((n-start)*sizeo

85、f(char));　　strcpy(Hfm.HC[i],&cd[start]);//從cd復(fù)制編碼到Hfm.HC　　}　　free(cd);//釋放工作空間　　return Hfm;&

86、lt;b>　　}　　Huffman InputHuffman(Huffman Hfm)//輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值　　{　　int i,n;　　printf(

87、"\n\n********************Initialization*********************\n");　　printf("The chars and weights will be saved in the file :\hfmTree\ \n");　　printf("Plea

88、se input the number of the chars: ");　　scanf("%d",&n);　　if(n<=1) 　　{printf("Only One Char!There Is No Need For Coding!");

89、//若只有一個數(shù)值則無需編碼　　printf("\n");　　printf("Please input the number of the chars: ");　　scanf("%d",&n);}　　Hf

90、m.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));　　Hfm.c=(char *)malloc((n+1)*sizeof(char));　　for(i=1;i<=n;i++)　　{

91、printf("Please input the char: ");　　scanf("%s",&Hfm.c[i]);　　printf("Please input the weight of the char: ");　　scanf("%

92、d",&Hfm.HT[i].weight);　　Hfm.HT[i].parent=0;　　Hfm.HT[i].lchild=0;　　Hfm.HT[i].rchild=0;　　}

93、;　　for(;i<=2*n-1;++i)　　{　　Hfm.HT[i].weight=0;　　Hfm.HT[i].parent=0;　　Hfm.HT[i].lchild=0;　　Hfm.

94、HT[i].rchild=0;　　}　　Hfm.length=n;　　return Hfm;　　} 　　Huffman InitHuffman(Huffm

95、an Hfm)//初始化哈夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值　　{　　int n,i,x;　　FILE *fp;　　fp=fopen("hfmTree","rt&qu

96、ot;);//對文件hfmTree以讀文本的形式打開　　if(fp==NULL)　　{　　Hfm=InputHuffman(Hfm);//調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中　　fp=fopen(&q

97、uot;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

98、].weight);　　rewind(fp);　　}　　else　　{printf("The Huffmantree has already existed!\nDo You Want

99、To Make A New One?('Y'or'N')\n\n");//詢問是否重新初始化　　scanf("%s",&x);　　if(x=='Y')　　{ Hfm=InputHuffman(Hfm);//調(diào)用InputHuff

100、man函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中　　fp=fopen("hfmTree","w+");　　fprintf(fp,"%d\n",Hfm.length);　　for(i=1;i<=Hfm.length;i++)&

101、lt;p>　　fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);　　rewind(fp);　　}　　else　　{fscan

102、f(fp,"%d\n",&n);　　Hfm.c=(char *)malloc((n+1)*sizeof(char));　　Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));　　for(i=1;i<=n;i++)

103、　　fscanf(fp,"%s %d ",&Hfm.c[i],&Hfm.HT[i].weight);//將已經(jīng)在文件中的字符和其對應(yīng)的權(quán)重輸入到Hfm.c[i]和&Hfm.HT[i].weight中　　for(i=1;i<=n;i++)//對每個節(jié)點初始化　　{

104、 　　Hfm.HT[i].parent=0;　　Hfm.HT[i].lchild=0;　　Hfm.HT[i].rchild=0;　　}　　for(;i<=2*

105、n-1;++i)　　{　　Hfm.HT[i].weight=0;　　Hfm.HT[i].parent=0;　　Hfm.HT[i].lchild=0;　　Hfm.HT[i].rchild=0;&

106、lt;/p>　　}　　Hfm.length=n;　　}　　}　　fclose(fp);

107、　Hfm=HuffmanCoding(Hfm);　　return Hfm;　　}　　void Encoding(Huffman Hfm)//利用已建好的Huffman樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件Co

108、deFile中。　　{　　int i=0,j=0,n;　　char ch[MAX];　　FILE *fp,*fw;　　n=Hfm.length;　　p

109、rintf("\n\n*******************Encoding**************************\n\n");　　if((fw=fopen("ToBeTran","r+"))==NULL)//嘗試打開ToBeTran　　{&l

110、t;/p>　　printf("\nPlease input the sentence: ");　　scanf("%s",ch);　　printf("\n");　　fp=fopen("CodeFile",&q

111、uot;wt+");　　}　　else　　{　　fscanf(fw,"%s",ch);

112、　　fclose(fw);　　}　　while(ch[j])　　{　　for(i=1;i<=n;i++)　　if(ch[j]==Hfm.c[i])&

113、lt;/p>　　{　　printf("%s",Hfm.HC[i]);　　fprintf(fp,"%s",Hfm.HC[i]);　　break;&l

114、t;p>　　}　　j++;　　}　　printf("\n");　　rewind(fp);

115、　fclose(fp);　　}　　void Decoding(Huffman Hfm)//利用已建好的Huffman樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。　　{

116、　　HuffmanTree p;　　int i,n;　　int j=0;　　char d[500];　　FILE *fp;<p&

117、gt;　　n=Hfm.length;　　printf("\n\n******************Decoding************************\n\n");　　if((fp=fopen("CodeFile","r+"))==NULL)

118、;　　{　　printf("Please input the code:");　　scanf("%s",d);　　}　　else</

119、b>　　{　　fscanf(fp,"%s",d);//將文件中的字符輸入到數(shù)組d中　　fclose(fp);　　}　　print

120、f("\nThe file is : ");　　fp=fopen("TextFile","wt+");//以寫入文件的形式打開TextFile　　while(d[j])　　{

121、　　p=&Hfm.HT[2*n-1];　　while(p->lchild||p->rchild)　　{　　if(d[j]=='0')　　{ i=p->lchild; p=&Hfm.H

122、T[i]; }　　else　　{ i=p->rchild; p=&Hfm.HT[i]; }　　j++;　　}<p

123、>　　printf("%c",Hfm.c[i]);　　fprintf(fp,"%c",Hfm.c[i]);　　}　　printf("\n");　　fclose(fp);

124、　　}　　void Print(Huffman Hfm)//將文件CodeFile以緊湊格式顯示在終端上，每行50 個代碼。　　{　　int i,n;<

125、/p>　　int m=1;//計數(shù)器　　char ch;　　FILE* fprint;　　n=Hfm.length;　　printf("\n\n******************Output t

126、he code of the chars****************\n\n");　　for(i=1;i<=n;i++)//顯示每一個字符對應(yīng)的哈夫曼編碼　　{　　printf("\n");

127、printf("Char: %c\t",Hfm.c[i]);　　printf("Weight: %d\t",Hfm.HT[i].weight);　　printf("Code: ");　　puts(Hfm.HC[i]);<p&

128、gt;　　}　　fprint=fopen("CodeFile","rb");　　while ( feof(fprint)==0 )　　{　　ch=fgetc

129、(fprint);　　printf("%c",ch);　　m++;　　if (m%50==0)//保證每一行輸出50個字符　　printf("\n");

130、　　}　　printf("\n");　　fclose(fprint);　　}　　void main()　　{ &l

131、t;/b>　　Huffman Hfm;　　char k; /*控制循環(huán)的標(biāo)志*/　　while(1)　　{ printf(" --------------------------------------\n"

135、it |\n");　　printf(" --------------------------------------\n");　　printf(" Please Input Your Option\n");　　scanf(&q

136、uot;%c",&k);　　k=toupper(k);　　switch(k)　　{ case 'I': Hfm=InitHuffman(Hfm); getchar();break;　　case

137、9;E': Encoding(Hfm); getchar();break;　　case 'D': Decoding(Hfm); getchar();break;　　case 'P': Print(Hfm); getchar();break;&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--huffman編／譯碼器

文檔簡介

溫馨提示

最新文檔

評論

應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--huffman編／譯碼器

文檔簡介

溫馨提示

最新文檔

評論

免費下載