應用數(shù)據(jù)結構課程設計--huffman編／譯碼器

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

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、} 　　}　　程序調用模塊　　詳細設計　　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ù)組存儲字符串及其對應的霍夫曼樹　　Huffman Hfm;　　char k; /*控制循環(huán)的標志*/　　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]中無雙親且權值最小的兩個節(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個字符的權值（均〉0），構造赫夫曼樹HT，并求出n個字符的構造赫夫曼編碼HC　　{　　FOR(i=n+1;i<=2*n-1;++i) //選擇HT[1....i-1]中無雙親且權值最小的兩個節(jié)點，其序號為s1，s2　　{<

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

32、lt;/b>　　//從葉子結點到根逆向求每個字符的赫夫曼編碼　　FOR(i=1;i<=n;++i)　　//逐個字符求赫夫曼編碼　　{ start=n-1;//編碼結束符位置　　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復制編碼到Hfm.HC　　}　　RETURN Hfm;　　}<

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

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

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

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

39、編碼，然后將結果存入文件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中的代碼進行譯碼，結果存入文件TextFile中。　　{ 定義char d[500]　　輸出"\n\n******

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

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

45、ild——>1來輸出　　入到文件TextFile中　　關閉文件　　}　　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"　　關閉文件</

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

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

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

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

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

53、t;　　算法的時間復雜度：　　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)驗與體會：　　整個程序在編的時候思路是很明朗的，包括菜單的設置都是很清晰的，但是如何通過一個菜單將所有涉及到的文件與終端聯(lián)系起來還有打印哈夫曼樹都是比較困難的問題，由于

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

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

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

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

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

61、b>　　圖7　　輸入“THIS_PROGRAM_IS_MY_FAVORITE”，回車之后，顯示出該句的哈夫曼編碼。　?。ù颂帪榍蠛喗荩瑢⒖崭裼孟聞澗€“_”作為代替）　　圖8　　在菜單界面選擇D，則對文件中已有

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

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

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

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

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

67、夫曼編碼　　HFMTREE.TXT 記錄字符個數(shù)、名稱及權值　　源代碼：　　#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;//全局結構體變量，來存儲字符與代碼<

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

73、1=MAX_NUM;　　int min2;　　for (i=1;i<=end;i++)//遍歷查找權值最小的結點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外權值最小的結點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個字符的權值（均〉0），構造哈夫曼樹HT，并求出n個字符的構造哈夫曼編碼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]中無雙親且權值最小的兩個節(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;//父親結點權值為左右孩子權值之和　　}　　//從葉子結點到根逆向求每個字符的哈夫曼編碼　　Hfm.HC=(HuffmanCode)malloc((

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

83、t;　　{　　start=n-1;//編碼結束符位置　　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復制編碼到Hfm.HC　　}　　free(cd);//釋放工作空間　　return Hfm;&

86、lt;b>　　}　　Huffman InputHuffman(Huffman Hfm)//輸入函數(shù)，控制用戶輸入字符和相應權值　　{　　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ù)，要求用戶輸入字符和相應權值　　{　　int n,i,x;　　FILE *fp;　　fp=fopen("hfmTree","rt&qu

96、ot;);//對文件hfmTree以讀文本的形式打開　　if(fp==NULL)　　{　　Hfm=InputHuffman(Hfm);//調用InputHuffman函數(shù)，用戶輸入字符和相應權值存入哈夫曼數(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);//調用InputHuff

100、man函數(shù)，用戶輸入字符和相應權值存入哈弗曼數(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)在文件中的字符和其對應的權重輸入到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樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件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中的代碼進行譯碼，結果存入文件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++)//顯示每一個字符對應的哈夫曼編碼　　{　　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)的標志*/　　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è)設計

溫馨提示

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

應用數(shù)據(jù)結構課程設計--huffman編／譯碼器

文檔簡介

溫馨提示

最新文檔

評論

應用數(shù)據(jù)結構課程設計--huffman編／譯碼器

文檔簡介

溫馨提示

最新文檔

評論

免費下載