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

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

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

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

文檔簡介

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

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

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

4、鏈表中的結(jié)點是一個結(jié)構(gòu)體。　　struct information_node　　{　　char ch;　　int frequency;　　struct i

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

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

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

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

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

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

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

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

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

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

15、。　　編程代碼實現(xiàn)及詳盡解釋　　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);//判斷字符是否在承載不同的字符的鏈表中出現(xiàn)與否。　　void statistics(void);//字符頻數(shù)統(tǒng)計的入口函數(shù)。　　void initializatio

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

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

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

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

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

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

24、記//錄該結(jié)點的位置，如果其無父結(jié)點，其值為-1，left_child來記錄其左子結(jié)點的位置，無左子樹，就記錄為0。ritht_child 用來記錄右子結(jié)點的位置。如果無右子結(jié)點就把它記錄為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();//初始化承載不同字符及其頻數(shù)的鏈表的表頭結(jié)點。&

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

28、就是，創(chuàng)建要構(gòu)建的樹的所有的結(jié)點空間 //并把葉子結(jié)點賦值。　　creat_huffman_tree(n,n);//在上函數(shù)完成葉子結(jié)點的輸入的基礎(chǔ)上創(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 個葉子結(jié)點。并輸出各葉子結(jié)點的　　ch數(shù)據(jù)項與huffman code.　　{　　if(pointer1->ch!=' '&&point

37、er1->ch!='\n')　　//由于字符中可能會出現(xiàn)空格與換行符，于它們的ch數(shù)據(jù)項的顯示特殊化處理。　　cout<<pointer1->ch<<'=';//如果，ch數(shù)據(jù)項不是空格與換行符，就直接打印。　　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)　　//這個函數(shù)中以葉子結(jié)點開始，來讀哈夫曼碼元。讀的方法是從葉子結(jié)點開始，然后就順著葉子結(jié)點所記錄的父結(jié)點。訪問其父結(jié)點。在父結(jié)點中記錄其是左子樹，就向棧中輸入碼元0.否則是1.如此繼續(xù)下去，直到訪問到根結(jié)點　　{　　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)　　//由于輸入結(jié)點數(shù)據(jù)時，根結(jié)點的parent項記錄為-1,這是循環(huán)條件用來判斷是否訪問到根結(jié)點　　{</b

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

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

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

48、ter1=pointer2;　　}　　reading_code();//進入讀棧函數(shù)　　}　　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個葉子結(jié)點，哈夫曼樹就應(yīng)有2*n-1個結(jié)點。于是就創(chuàng)建2*n-1個空間來用于存放相應(yīng)的結(jié)點數(shù)據(jù)并

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

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

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

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

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

57、　　}　　for(int i=n;i<2*n-1;i++)//這個部分是把存儲空間的其它沒有存儲數(shù)據(jù)的空間初始化。　　{　　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)建一個同承載字符鏈表的結(jié)點同類型的指針，用于訪問那個鏈表。　　if(head0->frequency==0) return false;　　//如果還沒那個鏈表中還沒有字符的插入，就向調(diào)用函數(shù)返回沒有這個字符的記錄。<b&

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

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

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

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

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

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

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

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

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

70、b>　　recording(ch);　　//如果在承載字符的鏈表中沒那個字符，就向那個鏈表插入一個結(jié)點來記錄那個字符。　　}　　void statistics()//字符頻數(shù)統(tǒng)計的入口函數(shù)。<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)//初始化一個以后用于字符輸入的鏈表頭結(jié)點,給它空間。　　{　　head0=new struct information_node;　　head0->ch='#';

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

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

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

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

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

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

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

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

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

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

87、　　else//否則，就用pointer指向這個結(jié)點，同sec記錄該結(jié)點的位置。　　{　　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)的目的是為了在可查找的結(jié)點范圍中找出data數(shù)據(jù)項最小與次之的兩個結(jié)點的位置且有pointer1與pointer2記錄它們。<

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

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

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是出了查找范圍的，在范圍外其指向的結(jié)點是待錄入數(shù)據(jù)的結(jié)點于是向這個結(jié)點錄入數(shù)據(jù)。其data項是pointer1與pointer2的data項的和這是哈夫曼構(gòu)樹的方法。因為哈夫曼構(gòu)樹中樹從葉子結(jié)點開始建立。每次由無父結(jié)點的結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載