課程設(shè)計(jì)---哈夫曼編碼編程實(shí)現(xiàn)

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

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

3、三者順序進(jìn)行。</b></p><p><b>　　實(shí)現(xiàn)思路</b></p><p><b>　　1、字符統(tǒng)計(jì)：</b></p><p>　　字符統(tǒng)計(jì)是為了計(jì)算出字符的頻數(shù)，以之構(gòu)成哈夫曼樹(shù)葉子結(jié)點(diǎn)的權(quán)。在實(shí)現(xiàn)中，本人采用一個(gè)鏈表表示字符的統(tǒng)計(jì)信息。并把所有字符關(guān)聯(lián)到一起。這個(gè)鏈表在后面稱為承載統(tǒng)計(jì)字符鏈表。在

4、鏈表中的結(jié)點(diǎn)是一個(gè)結(jié)構(gòu)體。</p><p>　　struct information_node</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p>　　int frequency;</p><p>　　struct i

5、nformation_node *next;</p><p><b>　　} *head0;</b></p><p>　　其中ch用來(lái)記錄相應(yīng)的字符。frequency用來(lái)記錄字符出現(xiàn)的字符的頻數(shù)，最后用來(lái)構(gòu)成哈夫曼樹(shù)葉子結(jié)點(diǎn)的權(quán)重。以head0來(lái)指向該鏈表。其中，本人在這個(gè)鏈表中的表頭的結(jié)點(diǎn)，本人不用作統(tǒng)計(jì)字符的記錄。而以其表頭結(jié)點(diǎn)的frequancy來(lái)記錄該鏈表中

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

7、;/p><p>　　if (!find_record(ch))//如果在承載字符的鏈表中以有那個(gè)字符，就不記錄。退回調(diào)用函 //數(shù)。</p><p>　　recording(ch);//如果在承載字符的鏈表中沒(méi)那個(gè)字符，就向那個(gè)鏈表插入一個(gè)結(jié)點(diǎn) //來(lái)記錄那個(gè)字符。</p><p>&l

8、t;b>　　else</b></p><p>　　count(ch);// 由于有該字符，向承載統(tǒng)計(jì)字符鏈表中就該字符結(jié)點(diǎn)的個(gè)數(shù)記錄項(xiàng)加1.</p><p><b>　　}</b></p><p><b>　　2、構(gòu)建哈夫曼樹(shù)：</b></p><p>　　在構(gòu)建哈夫曼樹(shù)就用其構(gòu)建

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

10、個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)（其中n是統(tǒng)計(jì)的不同字符各數(shù)）。它們的相關(guān)數(shù)據(jù)來(lái)自承載統(tǒng)計(jì)字符鏈表中的相應(yīng)數(shù)據(jù)，一個(gè)葉子結(jié)點(diǎn)，就要讀取一個(gè)承載統(tǒng)計(jì)字符鏈表的一個(gè)結(jié)點(diǎn)的數(shù)據(jù)。而剩余的空間用來(lái)存放其它的結(jié)點(diǎn)，因?yàn)橐豢霉蚵鼧?shù)如果有n個(gè)葉子結(jié)點(diǎn)，那么這棵樹(shù)總共有2*n-1個(gè)結(jié)點(diǎn)。葉子結(jié)點(diǎn)以輸入，那就是存在如何構(gòu)樹(shù)的問(wèn)題了，本人采用雙親表示法來(lái)表示樹(shù)的結(jié)點(diǎn)。在每個(gè)結(jié)點(diǎn)是一個(gè)結(jié)構(gòu)體類型。</p><p>　　struct huffman_

11、number_node</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p><b>　　int data;</b></p><p>　　int parent;</p><p>　　int left

12、_child;</p><p>　　int right_child;</p><p><b>　　} *head;</b></p><p>　　ch為字符。data用來(lái)記錄權(quán)重。parent用來(lái)記錄該結(jié)點(diǎn)的位置，如果其無(wú)父結(jié)點(diǎn)，其值為-1，left_child來(lái)記錄其左子結(jié)點(diǎn)的位置，無(wú)左子樹(shù)，就記錄為0。ritht_child用來(lái)記錄右子結(jié)點(diǎn)的

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

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

15、。</p><p>　　編程代碼實(shí)現(xiàn)及詳盡解釋</p><p><b>　　main.cpp</b></p><p>　　#include <iostream></p><p>　　#include<fstream></p><p>　　#include<stdlib

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

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

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

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

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

21、p><p>　　int frequency;</p><p>　　struct information_node *next;</p><p><b>　　} *head0;</b></p><p>　　//這是一個(gè)用來(lái)構(gòu)建統(tǒng)計(jì)字符鏈表結(jié)點(diǎn)類型的結(jié)構(gòu)體。其中ch用來(lái)記錄相應(yīng)的字符。frequency用來(lái)記錄字符出現(xiàn)的字符的頻

22、數(shù)，最后用來(lái)構(gòu)成哈夫曼樹(shù)葉子結(jié)點(diǎn)的權(quán)重。</p><p>　　struct huffman_number_node</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p><b>　　int data;</b></p&

23、gt;<p>　　int parent;</p><p>　　int left_child;</p><p>　　int right_child;</p><p><b>　　} *head</b></p><p>　　;//這個(gè)用來(lái)構(gòu)建哈夫曼樹(shù)結(jié)點(diǎn)的類型。ch為字符。data用來(lái)記錄權(quán)重。parent用來(lái)

24、記//錄該結(jié)點(diǎn)的位置，如果其無(wú)父結(jié)點(diǎn)，其值為-1，left_child來(lái)記錄其左子結(jié)點(diǎn)的位置，無(wú)左子樹(shù)，就記錄為0。ritht_child 用來(lái)記錄右子結(jié)點(diǎn)的位置。如果無(wú)右子結(jié)點(diǎn)就把它記錄為0。</p><p>　　struct stack_data</p><p><b>　　{</b></p><p>　　int one_zeros;<

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

26、><p>　　} stack_operate;//建立一個(gè)棧來(lái)存放huffman code</p><p>　　int main(void)</p><p><b>　　{</b></p><p>　　initialization_of_head();//初始化承載不同字符及其頻數(shù)的鏈表的表頭結(jié)點(diǎn)。</p>&

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

28、就是，創(chuàng)建要構(gòu)建的樹(shù)的所有的結(jié)點(diǎn)空間 //并把葉子結(jié)點(diǎn)賦值。</p><p>　　creat_huffman_tree(n,n);//在上函數(shù)完成葉子結(jié)點(diǎn)的輸入的基礎(chǔ)上創(chuàng)建哈夫曼樹(shù)。</p><p>　　cout<<endl;</p><p>　　cout<<endl;</p>&

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

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

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

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

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

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

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

36、t;<p>　　//這個(gè)循環(huán)中訪問(wèn)存儲(chǔ)空間中的前head0->frequency 個(gè)葉子結(jié)點(diǎn)。并輸出各葉子結(jié)點(diǎn)的</p><p>　　ch數(shù)據(jù)項(xiàng)與huffman code.</p><p><b>　　{</b></p><p>　　if(pointer1->ch!=' '&&point

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

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

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

40、 feed)來(lái)代替顯示</p><p><b>　　}</b></p><p>　　go_further_read(pointer1);//進(jìn)入讀取相就字符的huffman code.</p><p>　　cout<<'\t'<<'\t';</p><p>　　po

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

42、 *pointer)</p><p>　　//這個(gè)函數(shù)中以葉子結(jié)點(diǎn)開(kāi)始，來(lái)讀哈夫曼碼元。讀的方法是從葉子結(jié)點(diǎn)開(kāi)始，然后就順著葉子結(jié)點(diǎn)所記錄的父結(jié)點(diǎn)。訪問(wèn)其父結(jié)點(diǎn)。在父結(jié)點(diǎn)中記錄其是左子樹(shù)，就向棧中輸入碼元0.否則是1.如此繼續(xù)下去，直到訪問(wèn)到根結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　stack_operate.base

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

44、;<p>　　stack_operate.top=stack_operate.base;//初始化棧。</p><p>　　while(pointer1->parent!=-1)</p><p>　　//由于輸入結(jié)點(diǎn)數(shù)據(jù)時(shí)，根結(jié)點(diǎn)的parent項(xiàng)記錄為-1,這是循環(huán)條件用來(lái)判斷是否訪問(wèn)到根結(jié)點(diǎn)</p><p><b>　　{</b

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

46、</b></p><p>　　stack_operate.top->one_zeros=0;//是左子結(jié)點(diǎn)就向棧中輸入0</p><p>　　stack_operate.top++;</p><p><b>　　}</b></p><p><b>　　else</b></p&

47、gt;<p><b>　　{</b></p><p>　　stack_operate.top->one_zeros=1;//是右子結(jié)點(diǎn)就向棧中輸入1</p><p>　　stack_operate.top++;</p><p><b>　　}</b></p><p>　　poin

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

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

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

51、 enter_huffman_values(int n)</p><p><b>　　{</b></p><p>　　head=new struct huffman_number_node[2*n-1];</p><p>　　//由于哈夫曼樹(shù)中，有n個(gè)葉子結(jié)點(diǎn)，哈夫曼樹(shù)就應(yīng)有2*n-1個(gè)結(jié)點(diǎn)。于是就創(chuàng)建2*n-1個(gè)空間來(lái)用于存放相應(yīng)的結(jié)點(diǎn)數(shù)據(jù)并

52、把該空間的地址給head.</p><p>　　struct huffman_number_node *pointer=head;</p><p>　　//創(chuàng)建一個(gè)同哈夫曼樹(shù)結(jié)點(diǎn)同類型的指針，用來(lái)向那個(gè)空間輸入相應(yīng)的數(shù)據(jù)。</p><p>　　struct information_node *pointer1=head0->next;</p>&

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

54、lt;b>　　{</b></p><p>　　pointer->ch=pointer1->ch;</p><p>　　//這個(gè)葉子結(jié)點(diǎn)讀取一個(gè)承載統(tǒng)計(jì)字符鏈表的一個(gè)結(jié)點(diǎn)的字符數(shù)據(jù)項(xiàng)。</p><p>　　pointer->data=pointer1->frequency;</p><p>　　//這個(gè)

55、葉子結(jié)點(diǎn)繼續(xù)讀取承載統(tǒng)計(jì)字符鏈表那個(gè)結(jié)點(diǎn)的字符個(gè)數(shù)統(tǒng)計(jì)數(shù)據(jù)項(xiàng)。</p><p>　　pointer->parent=-1;</p><p>　　//由于還沒(méi)有構(gòu)成哈夫曼樹(shù)，所以把該葉子結(jié)點(diǎn)的父結(jié)點(diǎn)的位置記為-1.父結(jié)點(diǎn)的位置指的是其父結(jié)點(diǎn)所在結(jié)點(diǎn)存儲(chǔ)空間的位置，存儲(chǔ)空間的第一個(gè)結(jié)點(diǎn)位置為1.</p><p>　　pointer->left_child=0

56、;</p><p>　　//以0來(lái)表示，該結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)。如果有的話，就是其左子結(jié)點(diǎn)的存儲(chǔ)空間位置。</p><p>　　pointer->right_child=0;//同上，只是這里是右子結(jié)點(diǎn)。</p><p>　　pointer++;</p><p>　　pointer1=pointer1->next;</p>

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

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

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

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

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

62、->frequency;i++)</p><p>　　//這里就用到鏈表表頭中的字符總數(shù)記錄，來(lái)判斷要訪問(wèn)多少個(gè)結(jié)點(diǎn)。</p><p><b>　　{</b></p><p>　　if(pointer->ch==cha)</p><p>　　//判斷訪問(wèn)到的結(jié)點(diǎn)是不是有要查找的字符。有就向調(diào)用函數(shù)回答是。&l

63、t;/p><p><b>　　{</b></p><p>　　pointer->frequency+=1;//由于有該字符，就向該字符的個(gè)數(shù)記錄項(xiàng)加1.</p><p>　　return true;</p><p><b>　　}</b></p><p>　　pointer

64、=pointer->next;</p><p><b>　　}</b></p><p>　　return false;//最后還是沒(méi)找到就，向調(diào)用函數(shù)返回否。</p><p><b>　　}</b></p><p><b>　　}</b></p><p

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

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

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

68、gt;next->frequency=1;//同時(shí)，記錄這個(gè)字符的個(gè)數(shù)以有了一個(gè)。</p><p>　　pointer->next->next=NULL;//把這個(gè)表尾的結(jié)點(diǎn)的指針域賦為NULL，用于以后的判斷。</p><p><b>　　}</b></p><p>　　void particular_recording(c

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

70、b></p><p>　　recording(ch);</p><p>　　//如果在承載字符的鏈表中沒(méi)那個(gè)字符，就向那個(gè)鏈表插入一個(gè)結(jié)點(diǎn)來(lái)記錄那個(gè)字符。</p><p><b>　　}</b></p><p>　　void statistics()//字符頻數(shù)統(tǒng)計(jì)的入口函數(shù)。</p><p&g

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

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

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

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

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

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

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

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

79、truct huffman_number_node *pointer=head,*pointer1,*pointer2;</p><p>　　//創(chuàng)建的pointer用來(lái)訪問(wèn)樹(shù)結(jié)點(diǎn)存儲(chǔ)空間.pointer1,pointer2用于分別指向存儲(chǔ)空間中結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)最小與次之的兩個(gè)結(jié)點(diǎn)，并且這兩個(gè)結(jié)點(diǎn)parent數(shù)據(jù)項(xiàng)無(wú)父結(jié)點(diǎn)記錄的。</p><p>　　data是記錄字符的權(quán)重，也就是由

80、統(tǒng)計(jì)部分統(tǒng)計(jì)出的相應(yīng)字符在輸入的字符集中的頻數(shù)。</p><p>　　int min=0,sec=0,maximum;</p><p>　　//定義min用來(lái)指出pointer1指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。初始為0。定義sec用來(lái)指出pointer2指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。初始為0。申明maximun,是為的存min與sec中的最大的值。</p><p>　　w

81、hile((min==0||sec==0)&&((pointer-head)<number))</p><p>　　//這個(gè)循環(huán)中是為了找出前兩個(gè)無(wú)父結(jié)點(diǎn)記錄的結(jié)點(diǎn)，分別用pointer1與pointer2來(lái)指向。其中pointer1指向data數(shù)據(jù)項(xiàng)是最小的那個(gè)結(jié)點(diǎn)。這個(gè)循環(huán)的條件中,都要min 與sec不為0。也就是說(shuō)要pointer1與pointer2都要有指向，前兩個(gè)結(jié)點(diǎn)找出。(po

82、inter-head)<number是指，其查找應(yīng)在一定的范圍，這個(gè)范圍是結(jié)點(diǎn)空間前面的有數(shù)據(jù)錄入的結(jié)點(diǎn)。它們的數(shù)據(jù)項(xiàng)ch。</p><p><b>　　//不為'#'.</b></p><p><b>　　{</b></p><p>　　if(pointer->parent==-1&&

83、amp;min==0)</p><p>　　//如果第一次找到滿足條件的結(jié)點(diǎn)。就第一個(gè)用pointer1來(lái)指向，與min記錄位置。</p><p><b>　　{</b></p><p>　　min=pointer-head+1;</p><p>　　pointer1=pointer;</p><p&

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

85、>　　{</b></p><p>　　if(pointer1->data>pointer->data)</p><p>　　//如果這個(gè)結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)與第一個(gè)結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)要小，就用pointer1指向這個(gè)數(shù)據(jù)項(xiàng)，而pointer2指向第一個(gè)。</p><p><b>　　{</b></p&

86、gt;<p><b>　　sec=min;</b></p><p>　　pointer2=pointer1;</p><p>　　pointer1=pointer;</p><p>　　min=pointer-head+1;</p><p><b>　　}</b></p>

87、<p>　　else//否則，就用pointer指向這個(gè)結(jié)點(diǎn)，同sec記錄該結(jié)點(diǎn)的位置。</p><p><b>　　{</b></p><p>　　sec=pointer-head+1;</p><p>　　pointer2=pointer;</p><p><b>　　}</b>&l

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

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

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

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

92、ata數(shù)據(jù)比pointer2指向的結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)小。就用pointer1與pointer2中的其中一個(gè)指向它，如果它的data數(shù)據(jù)比pointer1的data數(shù)據(jù)項(xiàng)還小，就用pointer1來(lái)指向它，pointer2指向pointer1以前指向的結(jié)點(diǎn)。否則，就用pointer2來(lái)指向它。同時(shí)，min與sec也要相應(yīng)的改變記錄。</p><p><b>　　{</b></p>

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

94、pointer;</p><p><b>　　min=m;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　pointer2=

95、pointer;</p><p><b>　　sec=m;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　pointer++;</p><p><b>　　}</b>&l

96、t;/p><p>　　pointer->data=pointer1->data+pointer2->data;</p><p>　　//在這里pointer是出了查找范圍的，在范圍外其指向的結(jié)點(diǎn)是待錄入數(shù)據(jù)的結(jié)點(diǎn)于是向這個(gè)結(jié)點(diǎn)錄入數(shù)據(jù)。其data項(xiàng)是pointer1與pointer2的data項(xiàng)的和這是哈夫曼構(gòu)樹(shù)的方法。因?yàn)楣蚵鼧?gòu)樹(shù)中樹(shù)從葉子結(jié)點(diǎn)開(kāi)始建立。每次由無(wú)父結(jié)點(diǎn)的結(jié)

97、點(diǎn)中選出兩個(gè)權(quán)重最小的兩結(jié)點(diǎn)，把它們的權(quán)重之和來(lái)構(gòu)建一個(gè)新結(jié)點(diǎn)的權(quán)重，并且那兩個(gè)結(jié)點(diǎn)要記錄它們的父結(jié)點(diǎn)就是那個(gè)新結(jié)點(diǎn)。再重復(fù)如上的操作，直到最后的樹(shù)的建成。</p><p>　　pointer->left_child=min;</p><p>　　//指出樹(shù)的新結(jié)點(diǎn)的左子結(jié)點(diǎn)所在的位置。這里指向提貢data數(shù)據(jù)項(xiàng)最小的那個(gè)結(jié)點(diǎn)。</p><p>　　point

98、er->right_child=sec;</p><p>　　//指出樹(shù)的新結(jié)點(diǎn)的右子結(jié)點(diǎn)所在的位置。這是指向提貢data數(shù)據(jù)項(xiàng)次之的那個(gè)結(jié)點(diǎn)。</p><p>　　pointer1->parent=number+1;//既然pointer1指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下來(lái)。</p><p>　　pointer2->parent=number+1;

99、//既然pointer2指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下為。</p><p>　　creat_huffman_tree(number+1,n);</p><p>　　//如果還有兩個(gè)或兩個(gè)以上結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄，這就說(shuō)明了還要繼續(xù)構(gòu)樹(shù)。于是遞歸調(diào)用。到下一個(gè)函數(shù)去判斷。這里的number+1說(shuō)明的是，2*n-1中結(jié)點(diǎn)中有number+1個(gè)結(jié)點(diǎn)</p><p>　　以錄入

100、數(shù)據(jù)。只要number1小于2*n-1.就說(shuō)明還有兩個(gè)或兩個(gè)以上結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄。</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　程序執(zhí)行</b></p><p>　　程序執(zhí)行的第一界面：</p>&l

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

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

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

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

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

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

107、局變量指針。用它們分別指向承載統(tǒng)計(jì)字符鏈表與哈夫曼樹(shù)結(jié)點(diǎn)存儲(chǔ)空間。它們的大小是隨輸入字符的不同總數(shù)決定的。如輸入n個(gè)字符，對(duì)于承載統(tǒng)計(jì)字符鏈表就要(n+1）*9 個(gè)字節(jié)的存儲(chǔ)空間;對(duì)于哈夫曼樹(shù)的結(jié)點(diǎn)的存儲(chǔ)空間來(lái)說(shuō)，其需要（2*n-1)*17個(gè)字節(jié)的空間。同時(shí)，還有一個(gè)代表?xiàng)５淖兞俊＿@個(gè)變量要的存儲(chǔ)空間是小于或等于4*（1+n)個(gè)字節(jié)。這些都是根據(jù)它們的結(jié)點(diǎn)類型計(jì)算得來(lái)。而其它的變量都是局部變量。每一個(gè)函數(shù)中，調(diào)用局部變量用的存儲(chǔ)空間不會(huì)

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

109、曼編碼。并打印出來(lái)。在這個(gè)程序中，本人認(rèn)為用鍵盤(pán)輸入的字符中有一個(gè)字符‘#’沒(méi)有納入哈夫曼編碼中，其是還不是完善的。</p><p><b>　　資料參考</b></p><p>　　⑴ 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu). 清華大學(xué)出版社, 2007.4</p><p>　?、?錢(qián)能. C++程序設(shè)計(jì)教程（第二版）. 清華大學(xué)出版社, 2005.9