課程設計---哈夫曼編碼編程實現

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：16 大?。?31.50KB 人氣指數：12 舉報 版權申訴

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

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

文檔簡介

1、　　課程設計報告　　2011年12月　　課程設計課題：　　利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本，試設計一個哈夫曼編碼系統(tǒng)。功能要求：從鍵盤輸入

2、一段報文（如"what did you do that made you so happy"）或從文檔中讀取，輸出這段報文的哈夫曼編碼。　　課題分析：　　由課題的要求，在編程中要實現字符統(tǒng)計、哈夫曼樹的建立及該樹的哈夫曼編碼的讀取。　　這

3、三者順序進行。　　實現思路　　1、字符統(tǒng)計：　　字符統(tǒng)計是為了計算出字符的頻數，以之構成哈夫曼樹葉子結點的權。在實現中，本人采用一個鏈表表示字符的統(tǒng)計信息。并把所有字符關聯(lián)到一起。這個鏈表在后面稱為承載統(tǒng)計字符鏈表。在

4、鏈表中的結點是一個結構體。　　struct information_node　　{　　char ch;　　int frequency;　　struct i

5、nformation_node *next;　　} *head0;　　其中ch用來記錄相應的字符。frequency用來記錄字符出現的字符的頻數，最后用來構成哈夫曼樹葉子結點的權重。以head0來指向該鏈表。其中，本人在這個鏈表中的表頭的結點，本人不用作統(tǒng)計字符的記錄。而以其表頭結點的frequancy來記錄該鏈表中

6、字符和數。便于后面的函數實現。　　void statistics()　　{　　char ch;　　while((ch=cin.get())!='#')//從輸入流中斷獲取字符<

7、;/p>　　if (!find_record(ch))//如果在承載字符的鏈表中以有那個字符，就不記錄。退回調用函 //數。　　recording(ch);//如果在承載字符的鏈表中沒那個字符，就向那個鏈表插入一個結點 //來記錄那個字符。&l

8、t;b>　　else　　count(ch);// 由于有該字符，向承載統(tǒng)計字符鏈表中就該字符結點的個數記錄項加1.　　}　　2、構建哈夫曼樹：　　在構建哈夫曼樹就用其構建

9、的方法，即哈夫曼樹中樹從葉子結點開始建立。每次由無父結點的結點中選出兩個權重最小的兩結點，把它們的權重之和來構建一個新結點的權重，并且用那兩個結點要記錄它們的父結點就是那個新結點。再重復如上的操作，直到最后的樹的建成。而哈夫曼編碼的讀取，可用樹的遍歷的方法。這里，本人用樹的雙親表示法來表示樹的結構。　　創(chuàng)建了2*n-1哈夫曼樹結點空間，給存儲哈夫曼樹結點的那個空間的前n個空間輸入n個結點值，這n

10、個結點是葉子結點（其中n是統(tǒng)計的不同字符各數）。它們的相關數據來自承載統(tǒng)計字符鏈表中的相應數據，一個葉子結點，就要讀取一個承載統(tǒng)計字符鏈表的一個結點的數據。而剩余的空間用來存放其它的結點，因為一棵哈夫曼樹如果有n個葉子結點，那么這棵樹總共有2*n-1個結點。葉子結點以輸入，那就是存在如何構樹的問題了，本人采用雙親表示法來表示樹的結點。在每個結點是一個結構體類型。　　struct huffman_

11、number_node　　{　　char ch;　　int data;　　int parent;　　int left

12、_child;　　int right_child;　　} *head;　　ch為字符。data用來記錄權重。parent用來記錄該結點的位置，如果其無父結點，其值為-1，left_child來記錄其左子結點的位置，無左子樹，就記錄為0。ritht_child用來記錄右子結點的

13、位置。如果無右子結點就把它記錄為0。最后用head來指向那個存儲空間。這樣就能很好的指把所有的結點關聯(lián)起來，構成一棵樹。利用構成哈夫曼樹的方法，來構成一棵哈夫樹。　　enter_huffman_values( n);//哈夫曼樹葉子結點的輸入　　creat_huffman_tree(number,n);//創(chuàng)建哈夫曼樹<p&

14、gt;　　從哈夫曼樹中讀哈夫曼編碼：　　本人采用從以葉子結點開始，來讀哈夫曼碼元。讀的方法是從葉子結點開始，然后就順著葉子結點所記錄的父結點。訪問其父結點。在父結點中記錄其是左子樹，就向棧中輸入碼元0.否則是1.如此繼續(xù)下去，直到訪問到根結點。這時，這個葉子結點的哈夫曼編碼就可由前面讀取碼元的反向打印得來。在前面讀碼元中，本人用一個棧來存放讀到的0與1.這樣棧的輸出結果就是那上葉子結點的哈夫編碼

15、。　　編程代碼實現及詳盡解釋　　main.cpp　　#include <iostream>　　#include<fstream>　　#include<stdlib

16、.h>　　#include<stdio.h>　　#include<windows.h>　　using namespace std;　　bool find_record(char cha);//找出已存入的字符<p

17、>　　void recording(char ch);//插入新字符　　void particular_recording(char ch);//判斷字符是否在承載不同的字符的鏈表中出現與否。　　void statistics(void);//字符頻數統(tǒng)計的入口函數。　　void initializatio

18、n_of_head(void);//初始化一個以后用于字符輸入的鏈表頭結點,給它空間。　　int enter_huffman_values(int n);//哈夫曼樹葉子結點的輸入　　void creat_huffman_tree(int number,int n);//創(chuàng)建哈夫曼樹　　void go_furth

19、er_read(struct huffman_number_node *pointer);//從樹中讀相應字符的哈夫編碼　　void reading_code();//打印相應字符的哈夫編碼　　void read_huffman_code(void);//讀相應字符哈夫編碼的入口函數　　void read_fil

20、e(void);//從文件中讀取字符　　void view(void);//用于是從文件中讀取字符還是從鍵盤。　　struct information_node　　{　　char ch;</

21、p>　　int frequency;　　struct information_node *next;　　} *head0;　　//這是一個用來構建統(tǒng)計字符鏈表結點類型的結構體。其中ch用來記錄相應的字符。frequency用來記錄字符出現的字符的頻

22、數，最后用來構成哈夫曼樹葉子結點的權重。　　struct huffman_number_node　　{　　char ch;　　int data;</p&

23、gt;　　int parent;　　int left_child;　　int right_child;　　} *head　　;//這個用來構建哈夫曼樹結點的類型。ch為字符。data用來記錄權重。parent用來

24、記//錄該結點的位置，如果其無父結點，其值為-1，left_child來記錄其左子結點的位置，無左子樹，就記錄為0。ritht_child 用來記錄右子結點的位置。如果無右子結點就把它記錄為0。　　struct stack_data　　{　　int one_zeros;<

25、;/p>　　};　　struct stack　　{　　struct stack_data *base;　　struct stack_data *top;</p

26、>　　} stack_operate;//建立一個棧來存放huffman code　　int main(void)　　{　　initialization_of_head();//初始化承載不同字符及其頻數的鏈表的表頭結點。&

27、lt;p>　　view();　　int n=head0->frequency;//把完成統(tǒng)計后，承載字符的鏈表中的總字符個數賦值給一個整 //數n,用以做參數傳遞，完成后面函數的功能。　　enter_huffman_values(n);//該函數的主要功能性

28、就是，創(chuàng)建要構建的樹的所有的結點空間 //并把葉子結點賦值。　　creat_huffman_tree(n,n);//在上函數完成葉子結點的輸入的基礎上創(chuàng)建哈夫曼樹。　　cout<<endl;　　cout<<endl;&

29、lt;p>　　read_huffman_code();//把哈夫曼編碼打印出來　　cout<<endl;　　system("pause");　　return 0;　　}</

30、b>　　void view(void)　　{　　cout<<"**************************************************"<<endl;　　c

31、out<<" 1、from the file reading characters "<<endl;　　cout<<" 2、from the keyboard reading characters "<<endl;　　cout<

32、;<"please select the corresponding option ."<<endl;　　int select_number;　　cin>>select_number;　　switch(select_number)<p

33、>　　{　　case 1:read_file();system("cls");break;　　case 2:statistics();system("cls");break;　　default:exit(0);

34、　　}　　}　　void read_huffman_code(void)//打印哈夫曼編碼　　{　　cout<<"

35、 display huffman code in following"<<endl<<endl;　　struct huffman_number_node *pointer1=head;//用pointer來訪問哈夫曼樹。　　for(int i=0;i<head0->frequency;i++)</p&g

36、t;　　//這個循環(huán)中訪問存儲空間中的前head0->frequency 個葉子結點。并輸出各葉子結點的　　ch數據項與huffman code.　　{　　if(pointer1->ch!=' '&&point

37、er1->ch!='\n')　　//由于字符中可能會出現空格與換行符，于它們的ch數據項的顯示特殊化處理。　　cout<<pointer1->ch<<'=';//如果，ch數據項不是空格與換行符，就直接打印。　　else<

38、/b>　　{　　if(pointer1->ch==' ')//是空格符就用(a bland space)來代替顯示　　{　　cout<<"(a b

39、land space)"<<'=';　　}　　else　　cout<<"(line feed)"<<'=';//如果是換行符，就用(line

40、 feed)來代替顯示　　}　　go_further_read(pointer1);//進入讀取相就字符的huffman code.　　cout<<'\t'<<'\t';　　po

41、inter1++;　　if((i+1)%2==0) cout<<endl;　　}　　}　　void go_further_read(struct huffman_number_node

42、 *pointer)　　//這個函數中以葉子結點開始，來讀哈夫曼碼元。讀的方法是從葉子結點開始，然后就順著葉子結點所記錄的父結點。訪問其父結點。在父結點中記錄其是左子樹，就向棧中輸入碼元0.否則是1.如此繼續(xù)下去，直到訪問到根結點　　{　　stack_operate.base

43、=new struct stack_data[head0->frequency];　　//創(chuàng)建一個棧來存儲相就的哈夫曼編碼　　struct huffman_number_node *pointer1=pointer,*pointer2;　　//輔助訪問指針pointer1與pointer2

44、;　　stack_operate.top=stack_operate.base;//初始化棧。　　while(pointer1->parent!=-1)　　//由于輸入結點數據時，根結點的parent項記錄為-1,這是循環(huán)條件用來判斷是否訪問到根結點　　{</b

45、>　　pointer2=head+(pointer1->parent-1);//pointer2指向pointer1的父結點。　　if((pointer1-head+1)==pointer2->left_child)//判斷pointer1是父結點的左子結點還是右子結點。　　{

46、　　stack_operate.top->one_zeros=0;//是左子結點就向棧中輸入0　　stack_operate.top++;　　}　　else</p&

47、gt;　　{　　stack_operate.top->one_zeros=1;//是右子結點就向棧中輸入1　　stack_operate.top++;　　}　　poin

48、ter1=pointer2;　　}　　reading_code();//進入讀棧函數　　}　　void reading_code()//用棧的讀取方法讀取碼元就那個字符的哈夫曼編碼。</p&

49、gt;　　{　　struct stack_data *pointer;　　for(;stack_operate.top-stack_operate.base>0; stack_operate.top--)　　{

50、　　pointer=stack_operate.top-1;　　cout<<pointer->one_zeros;　　}　　}　　int

51、 enter_huffman_values(int n)　　{　　head=new struct huffman_number_node[2*n-1];　　//由于哈夫曼樹中，有n個葉子結點，哈夫曼樹就應有2*n-1個結點。于是就創(chuàng)建2*n-1個空間來用于存放相應的結點數據并

52、把該空間的地址給head.　　struct huffman_number_node *pointer=head;　　//創(chuàng)建一個同哈夫曼樹結點同類型的指針，用來向那個空間輸入相應的數據。　　struct information_node *pointer1=head0->next;&

53、lt;p>　　//創(chuàng)建一個訪問承載統(tǒng)計字符鏈表的指針。　　for(int i=0;i<n;i++)　　//用循環(huán)來給存儲哈夫曼樹結點的那個空間的前n個空間輸入n個結點值，這n個結點是葉子結點。它們的相關數據來自承載統(tǒng)計字符鏈表中的相應數據，一個葉子結點，就要讀取一個承載統(tǒng)計字符鏈表的一個結點的數據。&

54、lt;b>　　{　　pointer->ch=pointer1->ch;　　//這個葉子結點讀取一個承載統(tǒng)計字符鏈表的一個結點的字符數據項。　　pointer->data=pointer1->frequency;　　//這個

55、葉子結點繼續(xù)讀取承載統(tǒng)計字符鏈表那個結點的字符個數統(tǒng)計數據項。　　pointer->parent=-1;　　//由于還沒有構成哈夫曼樹，所以把該葉子結點的父結點的位置記為-1.父結點的位置指的是其父結點所在結點存儲空間的位置，存儲空間的第一個結點位置為1.　　pointer->left_child=0

56、;　　//以0來表示，該結點沒有左子結點。如果有的話，就是其左子結點的存儲空間位置。　　pointer->right_child=0;//同上，只是這里是右子結點。　　pointer++;　　pointer1=pointer1->next;

57、　　}　　for(int i=n;i<2*n-1;i++)//這個部分是把存儲空間的其它沒有存儲數據的空間初始化。　　{　　pointer->ch='#';<

58、p>　　pointer->parent=-1;　　pointer->left_child=0;　　pointer->right_child=0;　　pointer++;　　}<p&

59、gt;　　return n;　　}　　bool find_record(char cha)//找出已存入的字符　　{　　struct information_

60、node *pointer;　　//創(chuàng)建一個同承載字符鏈表的結點同類型的指針，用于訪問那個鏈表。　　if(head0->frequency==0) return false;　　//如果還沒那個鏈表中還沒有字符的插入，就向調用函數返回沒有這個字符的記錄。<b&

61、gt;　　else　　{　　pointer=head0->next;　　//如果鏈表中有字符，就用pointer來訪問查找，把查找的開始位置告訴pointer.　　for(int i=0;i<head0

62、->frequency;i++)　　//這里就用到鏈表表頭中的字符總數記錄，來判斷要訪問多少個結點。　　{　　if(pointer->ch==cha)　　//判斷訪問到的結點是不是有要查找的字符。有就向調用函數回答是。&l

63、t;/p>　　{　　pointer->frequency+=1;//由于有該字符，就向該字符的個數記錄項加1.　　return true;　　}　　pointer

64、=pointer->next;　　}　　return false;//最后還是沒找到就，向調用函數返回否。　　}　　}<p

65、>　　void recording(char ch)//插入新字符　　{　　struct information_node *pointer=head0;　　//創(chuàng)建一個與承載統(tǒng)計字符的鏈表的表頭結點同類型的指針并指向那個頭結點。

66、;　　while(pointer->next!=NULL)　　//循環(huán)的方式來找到承載統(tǒng)計字符的鏈表的表尾結點。用以插入一個新的結點，來存儲新的結點。　　pointer=pointer->next;　　head0->frequency+=1;　　//由于

67、，插入在承載統(tǒng)計字符的鏈表中插入了一個新的結點，也就是有了一個新的字符，那就在其表結點的字符統(tǒng)計中加1.　　pointer->next=new struct information_node;//創(chuàng)建新的結點，用以記錄新的字符。　　pointer->next->ch=ch;　　pointer-&

68、gt;next->frequency=1;//同時，記錄這個字符的個數以有了一個。　　pointer->next->next=NULL;//把這個表尾的結點的指針域賦為NULL，用于以后的判斷。　　}　　void particular_recording(c

69、har ch)//判斷字符是否在承載不同的字符的鏈表中出現與否。　　{　　if(find_record(ch)==true);　　//如果在承載字符的鏈表中以有那個字符，就不記錄。退回調用函數。　　else</

70、b>　　recording(ch);　　//如果在承載字符的鏈表中沒那個字符，就向那個鏈表插入一個結點來記錄那個字符。　　}　　void statistics()//字符頻數統(tǒng)計的入口函數。<p&g

71、t;　　{　　char ch;　　cout<<"if you want to compute statistical data about the number of letters,please enter letters then enter'

72、#' end enter "<<endl;　　while((ch=cin.get())!='#')//從輸入流中斷獲取字符，直到碰到字符'#'為止。　　particular_recording(ch);//深入進入統(tǒng)計。　　}<

73、/b>　　void read_file()//從文件中讀取字符。　　{　　ifstream infile("data.txt",ios::in);　　if(!infile)<p&

74、gt;　　{　　cout<<"open error! ";　　exit(0);　　}　　char ch;&l

75、t;/b>　　while((ch=infile.get())!=EOF)　　particular_recording(ch);　　infile.close();　　}　　void ini

76、tialization_of_head(void)//初始化一個以后用于字符輸入的鏈表頭結點,給它空間。　　{　　head0=new struct information_node;　　head0->ch='#';

77、;　　head0->frequency=0;//這個是用于記錄鏈表中字符的總個數，給該鏈表加入一個字符，它就加1.　　head0->next=NULL;　　}　　void creat_huffman_tree(int number,int n)//構造哈夫曼樹。&

78、lt;/p>　　{　　if(number<2*n-1)//判斷錄入數據樹的結點是否小于2*n-1　　{　　int m;　　s

79、truct huffman_number_node *pointer=head,*pointer1,*pointer2;　　//創(chuàng)建的pointer用來訪問樹結點存儲空間.pointer1,pointer2用于分別指向存儲空間中結點的data數據項最小與次之的兩個結點，并且這兩個結點parent數據項無父結點記錄的。　　data是記錄字符的權重，也就是由

80、統(tǒng)計部分統(tǒng)計出的相應字符在輸入的字符集中的頻數。　　int min=0,sec=0,maximum;　　//定義min用來指出pointer1指向的結點在存儲空間的位置。初始為0。定義sec用來指出pointer2指向的結點在存儲空間的位置。初始為0。申明maximun,是為的存min與sec中的最大的值。　　w

81、hile((min==0||sec==0)&&((pointer-head)<number))　　//這個循環(huán)中是為了找出前兩個無父結點記錄的結點，分別用pointer1與pointer2來指向。其中pointer1指向data數據項是最小的那個結點。這個循環(huán)的條件中,都要min 與sec不為0。也就是說要pointer1與pointer2都要有指向，前兩個結點找出。(po

82、inter-head)<number是指，其查找應在一定的范圍，這個范圍是結點空間前面的有數據錄入的結點。它們的數據項ch。　　//不為'#'.　　{　　if(pointer->parent==-1&&

83、amp;min==0)　　//如果第一次找到滿足條件的結點。就第一個用pointer1來指向，與min記錄位置。　　{　　min=pointer-head+1;　　pointer1=pointer;<p&

84、gt;　　}　　else　　{　　if(pointer->parent==-1&&sec==0)//找到第二個滿足條件的結點。<b

85、>　　{　　if(pointer1->data>pointer->data)　　//如果這個結點的data數據項與第一個結點的data數據項要小，就用pointer1指向這個數據項，而pointer2指向第一個。　　{</p&

86、gt;　　sec=min;　　pointer2=pointer1;　　pointer1=pointer;　　min=pointer-head+1;　　}

87、　　else//否則，就用pointer指向這個結點，同sec記錄該結點的位置。　　{　　sec=pointer-head+1;　　pointer2=pointer;　　}&l

88、t;/p>　　}　　}　　pointer++;　　}　　if(sec>min)&l

89、t;b>　　{　　maximum=sec;　　}　　else　　{　　maximum=mi

90、n;　　}　　for(int i=0;i<number-maximum;i++)　　//這個循環(huán)的目的是為了在可查找的結點范圍中找出data數據項最小與次之的兩個結點的位置且有pointer1與pointer2記錄它們。<

91、b>　　{　　m=pointer-head+1;//這里的m記錄每訪問的結點的存儲位置。　　if(pointer->parent==-1&&(pointer->data<pointer2->data))　　//如果訪問的結點無父結點記錄，又結點的d

92、ata數據比pointer2指向的結點的data數據項小。就用pointer1與pointer2中的其中一個指向它，如果它的data數據比pointer1的data數據項還小，就用pointer1來指向它，pointer2指向pointer1以前指向的結點。否則，就用pointer2來指向它。同時，min與sec也要相應的改變記錄。　　{

93、　　if(pointer->data<pointer1->data)　　{　　sec=min;　　pointer2=pointer1;　　pointer1=

94、pointer;　　min=m;　　}　　else　　{　　pointer2=

95、pointer;　　sec=m;　　}　　}　　pointer++;　　}&l

96、t;/p>　　pointer->data=pointer1->data+pointer2->data;　　//在這里pointer是出了查找范圍的，在范圍外其指向的結點是待錄入數據的結點于是向這個結點錄入數據。其data項是pointer1與pointer2的data項的和這是哈夫曼構樹的方法。因為哈夫曼構樹中樹從葉子結點開始建立。每次由無父結點的結

97、點中選出兩個權重最小的兩結點，把它們的權重之和來構建一個新結點的權重，并且那兩個結點要記錄它們的父結點就是那個新結點。再重復如上的操作，直到最后的樹的建成。　　pointer->left_child=min;　　//指出樹的新結點的左子結點所在的位置。這里指向提貢data數據項最小的那個結點。　　point

98、er->right_child=sec;　　//指出樹的新結點的右子結點所在的位置。這是指向提貢data數據項次之的那個結點。　　pointer1->parent=number+1;//既然pointer1指向的結點的父結點了，就記錄下來。　　pointer2->parent=number+1;

99、//既然pointer2指向的結點的父結點了，就記錄下為。　　creat_huffman_tree(number+1,n);　　//如果還有兩個或兩個以上結點無父結點記錄，這就說明了還要繼續(xù)構樹。于是遞歸調用。到下一個函數去判斷。這里的number+1說明的是，2*n-1中結點中有number+1個結點　　以錄入

100、數據。只要number1小于2*n-1.就說明還有兩個或兩個以上結點無父結點記錄。　　}　　}　　程序執(zhí)行　　程序執(zhí)行的第一界面：&l

101、t;p>　　有兩個選項，現在選1就會把一個文件中的字符進行哈夫曼編碼。就進入結果界面中，每一個字符與它的哈夫編碼行等于號連起來，指明它的相應的哈夫曼編碼。這里，也把文件中的空格與換行符也統(tǒng)計進來了，這是本人的想法。本人認為那樣可以使信息在傳輸時能完整的保存信息開始的風格。但本人也認識到，它也會議帶來信息的多余。（如下）：　　在程序執(zhí)行的第一界面中選擇第二個選項。于是進入了用戶自己輸入字符，

102、再統(tǒng)計，再哈夫曼編碼的輸出。程序執(zhí)行結果界面如下：　　字符輸入界面，字符輸入完，以字符'#'結束。　　繼上的結果界面　　時間復雜度分析　　該程序中，影響程序執(zhí)行時間的基本運算是賦值

103、運算。由字符統(tǒng)計部分的輸入規(guī)模決定。主要從三個部分的函數進行時間的復雜度分析。其分別是統(tǒng)計部分的函數、構建哈夫曼樹部分的函數與哈夫曼編碼讀取的函數,這里假如輸入的字符個數為N,而其中的總不同字符為n.　　統(tǒng)計部分的時間復雜度分析及該部分要分析函數是如下函數。　　bool find_record(char cha)//找出已存入的字符

104、　　void recording(char ch)//插入新字符　　void statistics()//字符頻數統(tǒng)計的入口函數。　　字符由statistics()輸入。進行了N次賦值。這N個函數還要進入find_record()函數中進行判斷。最后會有n個字符進入record()函數中插入鏈表。在find_record()函數中要進

105、行查找進行而進行的賦值，這里查找平均的次數要小于(n-1)/2,也就是在find_record函數中進行的賦值的平均次數要小于N*((n-1)/2);,在recording（）函數中，經計算會有(n-1)*n/2+5*n 次賦值運算。由于，在N很大情況下，這一部分的賦值運算總次數也就是這部分的時間的復雜度為T(N)=Θ(N).如果，N不是很大，其時間復雜度就為：T(N)=Θ(1)；　　構建哈夫曼

106、樹部分的函數與哈夫曼編碼讀取的函數時間復雜度分析。　　由于，不同的字符是有限可數，那么這里的時間復雜度變?yōu)椋篢(N)=Θ(1)。　　綜合時間復雜度分析，該程序的時間復雜度為T(N)=Θ(N)。　　空間復雜度分析　　程序中主要用到兩個全

107、局變量指針。用它們分別指向承載統(tǒng)計字符鏈表與哈夫曼樹結點存儲空間。它們的大小是隨輸入字符的不同總數決定的。如輸入n個字符，對于承載統(tǒng)計字符鏈表就要(n+1）*9 個字節(jié)的存儲空間;對于哈夫曼樹的結點的存儲空間來說，其需要（2*n-1)*17個字節(jié)的空間。同時，還有一個代表棧的變量。這個變量要的存儲空間是小于或等于4*（1+n)個字節(jié)。這些都是根據它們的結點類型計算得來。而其它的變量都是局部變量。每一個函數中，調用局部變量用的存儲空間不會

108、超出28個字節(jié)。其中在函數creat_huffman_tree(int number,int n)/中用的局部變量存儲空間最大，其為28字節(jié)。所以，程序的存儲空間最大是（n+1)*9+（2*n-1)*17+4*(1+n)+28.　　編程總結　　該程序能完成從文件中已存字符或從鍵盤要求輸入的所有字符的統(tǒng)計，最后完成哈夫

109、曼編碼。并打印出來。在這個程序中，本人認為用鍵盤輸入的字符中有一個字符‘#’沒有納入哈夫曼編碼中，其是還不是完善的。　　資料參考　?、?嚴蔚敏, 吳偉民. 數據結構. 清華大學出版社, 2007.4　　⑵ 錢能. C++程序設計教程（第二版）. 清華大學出版社, 2005.9

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

溫馨提示

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

課程設計---哈夫曼編碼編程實現

文檔簡介

溫馨提示

最新文檔

評論

課程設計---哈夫曼編碼編程實現

文檔簡介

溫馨提示

最新文檔

評論

免費下載