數(shù)據結構課程設計報告---赫夫曼編碼

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

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

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

文檔簡介

1、　　數(shù)據結構課程設計 　　題目：赫夫曼編碼　　院、系：計算機科學與工程學院　　學科專業(yè)：計算機科學與技術 　　學生： 　　學

2、號： 　　指導教師： 　　2010年12月　　目錄　　1課程設計的題目----------------------- 0 頁&l

3、t;/p>　　2課程設計的目的（設計要解決的問題）-------2頁　　3概要設計（函數(shù)劃分、總體設計）--------- 2頁　　4詳細設計（各函數(shù)算法、流程圖、程序）-----3頁　　5調試結果--------------------------------23頁</p&g

4、t;　　6課程設計總結----------------------------24頁　　7心得體會------------------------------- 24頁　　課程設計的目的：　　了解利用赫夫曼樹求解給定權值的字符串的赫夫曼編碼的算法思想；&

5、lt;/p>　　學習利用計算機程序語言實現(xiàn)赫夫曼樹構造的算法；　　利用構造好的赫夫曼樹對任一字符串求解其赫夫曼編碼，以此熟悉赫夫曼編碼的整個求解過程；　　概要設計:　　函數(shù)劃分：功能模塊總共分為四個塊，由四個主要的函數(shù)來實現(xiàn)，分別為：</p&

6、gt;　　linklist calculation(char temp[],int n)-------統(tǒng)計字符種類及各個字符在字符串中出現(xiàn)次數(shù)的函數(shù)：用temp[]接收用戶輸入的字符串，將字符串存入一個鏈表當中，鏈表的每個結點存儲字符串的一個字符，然后用兩個指針p和t，查找字符串中相同的字符，將相同的字符結點刪除，只保留一個，并且在保留的那個字符結點中統(tǒng)計當前字符的權值（即其在字符串中出現(xiàn)的次數(shù)），統(tǒng)計完成后將鏈表

7、的頭結點返回；　　status auto_calculation(linklist L)-------自動統(tǒng)計權值的函數(shù)，以每個字符在字符串中出現(xiàn)的次數(shù)作為其權值：將calculation()中統(tǒng)計的各個字符在字符串中出現(xiàn)的次數(shù)作為權值存儲到全局數(shù)組w中；　　status input_weight(linklist L)--------手動輸入各個字符權

8、值的函數(shù)：對之前建立好的存儲字符串中每種字符信息的鏈表的結點進行操作，手動輸入每個字符的權值，并將其對應的存儲在每個結點的權值變量weight中，待鏈表中所有字符權值手動輸入完畢后，再將鏈表中存儲的每種字符的權值賦給存儲權值的全局數(shù)組w中；　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)------根據字符串中每個字符的權值構造赫夫

9、曼樹的函數(shù)：利用之前用于存儲存儲字符串中每種字符信息的鏈表，統(tǒng)計出字符種類個數(shù)n（即鏈表的結點數(shù)），然后開辟長度為2n的存儲空間構造赫夫曼樹，這其中還需要調用選擇權值最小的兩個結點的select()函數(shù)；　　void text_code(HuffmanTree HT,linklist head,int n)-------根據構造好的赫夫曼樹求解字符串中每個字符的編碼的函數(shù)：將之前構造好的赫夫曼樹

10、，由葉子結點向根結點求每個字符的赫夫曼編碼，并且將得到的編碼保存與相應字符對應的一個數(shù)組中，這個數(shù)組是Code這個結構體的一個成員，它其中還包括存儲每個字符及其權值的變量；　　void Calculte_code(char temp[],linklist head)------輸出每個字符以及整個字符串的赫夫曼編碼的函數(shù)：將每個字符輸出，同時逆序輸出求解得到的編碼，即是其對應的赫夫曼編碼，然后輸

11、出整個字符串的赫夫曼編碼；　　選擇權值最小的兩個結點的函數(shù)--------void select(HuffmanTree &HT,int nn,int *s11,int *s22)，這是輔助建造赫夫曼樹的函數(shù)。　　總體設計：　　求解一個字符串的赫夫曼編碼的算法主要是根

12、據字符串中各個字符的權值構造赫夫曼樹來進行編碼的，對于字符的權值，我采用了自動統(tǒng)計和手動輸入兩種方式得到，這樣可以方便用戶的各種需求。　　對于自動統(tǒng)計各個字符的權值這一功能，主要是依據各個字符在字符串中出現(xiàn)的次數(shù)作為它的權值。因為字符串中會有重復出現(xiàn)的字符，而它們的權值是每種字符出現(xiàn)的次數(shù)即可，即只需將統(tǒng)計得到的權值存儲在一個字符的信息中即可，因此，我采用了鏈表這種數(shù)據結構，將用戶輸入的字符串的

13、每個字符分別保存在一個鏈表的每個結點中，然后查找鏈表中字符相同的結點，用一個指針p從鏈表的第一個結點開始，再用一個查找指針t指向p的下一個結點，然后讓指針t從p的下一個結點開始，查找p后面的所有結點，如果找到與p中的字符相同結點，就將t所指的結點從鏈表中刪除，p所指的結點的權值加1，t繼續(xù)向下查找，直至查找完最后一個結點，然后將p指向下一個待查找的字符，t繼續(xù)從p的下一個結點開始，重復上述過程，直至將鏈表中的所有結點都查找一遍，最后，鏈

14、表中存儲的就是字符串中不同的字符及它們各自在字符串中的出現(xiàn)次數(shù)。　　對于手動輸入各個字符權值這一功能模塊，同樣需要先統(tǒng)計出字符串中不同字符的個數(shù)，然后給每個字符手動賦上相應的權值，因此，同樣利用統(tǒng)計各個字符在字符串中出現(xiàn)次數(shù)的鏈表，手動給每個結點中的字符賦權值，覆蓋掉原先的出現(xiàn)次數(shù)即可。　　待自動統(tǒng)計或者通過手動輸入的方式給每個字符賦上相應的權值以后，將

15、鏈表中的權值對應的存儲到一個全局數(shù)組w中，w數(shù)組定義為全局變量的原因是整個程序運行過程中，多個函數(shù)都會訪問它，因此定義為全局變量可以方便每個函數(shù)的訪問。然后，統(tǒng)計出字符串中不同字符的個數(shù)n，開辟2n個連續(xù)的存儲單元來建立赫夫曼樹，其中這段存儲空間中的0號單元不使用，而作為后面判斷每個結點是否存在雙親或者左右孩子使用。開始構造赫夫曼樹，先將n個字符的權值對應存儲到1～n號存儲單元中，并且將它們的左右孩子以及雙親都初始化為0號單元，即沒有雙

16、親和左右孩子，然后從現(xiàn)有的權值表中選出兩個雙親為0且權值最小的相加后，添加到n+1～2n單元中，更新權值表，重復上述過程，建立赫夫曼樹。赫夫曼樹構造完成后，將此存儲空間的頭指針通過宏引帶回，方便后續(xù)的操作。　　調用一個text_code()函數(shù)對建立好的赫夫曼樹有葉子結點向根結點逆向求每個葉子結點的編碼，并將編碼存儲在一個結構體成員數(shù)組中，這個結構體還包含存儲字符的變量，以及存儲字符權值的變量，

17、這樣就可以將每個字符與它的權值和編碼對應起來。　　最后，利用之前用于統(tǒng)計字符種類及其每個字符出現(xiàn)次數(shù)的鏈表倒序輸出每個字符的編碼，即得到它的赫夫曼編碼，然后，在輸出整個字符串的赫夫曼編碼。　　詳細設計　　各函數(shù)算法：

18、　　Linklist calculation(char temp[],int n)：字符數(shù)組temp接收用戶輸入的字符串，整型變量n為字符串中字符的個數(shù)。若接收到的字符串不為空，則創(chuàng)建一個存儲字符串的鏈表head，用一個for循環(huán)將字符串中的每個字符及其權值等相關信息存儲在鏈表中的每個結點中，并且初始化每個字符的權值為1。鏈表建立完畢后，用一個指針p指向鏈表的第一個結點，同時用一個指針t指向p的下一個結點，然后讓指

19、針t從p的下一個結點開始，查找p后面的所有結點，如果找到與p中的字符相同結點，就將t所指的結點從鏈表中刪除，同時p所指的結點的權值加1，t繼續(xù)向下查找，直至查找完最后一個結點，然后將p指向下一個待查找的字符，t繼續(xù)從p的下一個結點開始，重復上述過程，直至將鏈表中的所有結點都查找一遍，最后，鏈表中存儲的就是字符串中不同的字符及它們各自在字符串中的出現(xiàn)次數(shù)，以上操作完成后，將鏈表的頭指針返回，算法結束；<p&g

20、t;　　status auto_calculation(linklist L）：L為之前建立好的鏈表的頭結點指針，如果鏈表不為空，則用p指向頭結點的下一個結點，然后用一個for循環(huán)輸出鏈表中各個結點中的字符及其對應的權值（這里為字符在字符串中的出現(xiàn)次數(shù)為其權值），同時用一個變量n統(tǒng)計出不同字符的個數(shù)，然后給一個指向整型變量的全局指針w開辟n個連續(xù)的存儲整型數(shù)據的內存單元，將開辟好的存儲空間的首地址返回給w，然后用一個指針p從鏈表的第一個

21、結點開始，循環(huán)的將各個結點中的權值賦到w的每個存儲單元中。如果鏈表為空，輸出“統(tǒng)計錯誤”的提示信息。最后返回一個狀態(tài)值；　　status input_weight(linklist L)：L為之前建立好的鏈表的頭結點指針，將指針p指向鏈表頭結點的下一個結點（即第一個結點），如果鏈表不為空，p從第一個結點開始直至最后一個，循環(huán)的得到用戶給當前結點中字符賦的權值，同時用一個整型變量n統(tǒng)計鏈表的結點數(shù)

22、，根據n的大小開辟一段存儲整型數(shù)據的連續(xù)存儲單元，并將此段存儲空間的首地址返回給全局指針變量w，然后將鏈表中每個結點的權值賦到w這個數(shù)組的每個存儲單元中。如果鏈表為空，則輸出相應的提示信息，最后返回一個狀態(tài)值;　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)：L為之前建立好的鏈表的頭結點的指針，HT用來返回構造好的赫夫曼樹的頭指針。

23、首先，用一個指針temp_p指向L的下一個結點（即鏈表的第一個結點），然后用一個n統(tǒng)計出鏈表的結點數(shù)，即得到字符串中不同字符的個數(shù)，如果n<=1，則算法結束，因為一個字符無法構造赫夫曼樹，否則，開辟一段2n個連續(xù)的存儲HTnode這個結構體的內存單元，并且把首地址返回給HT，這段存儲空間的0號存儲單元不用，其中這段存儲空間中的0號單元不使用，而作為后面判斷每個結點是否存在雙親或者左右孩子使用，HTnode這個結構體包含三個成員，分

24、別為weight(權值）、lchild(左孩子）、rchild(右孩子）以及parent(雙親）。然后開始構造赫曼樹，首先將n個字符的權值對應存儲到1～n號存儲單元中，并且將它們的左右孩子以及雙親都初始化為0號單元，即沒有雙親和左右孩子，然后調用select()函數(shù)從現(xiàn)有的權值表中選出兩個雙親為0且權值最小的相加后的權值，添加到n+1～2n單元中，并且將這兩個權值最小的單元的序號s1和s　　vo

25、id select(HuffmanTree &HT,int nn,int *s11,int *s22)：HT為建立好的赫夫曼樹的首地址，nn為搜索的權值表中存儲單元的最大序號，s11和s22分別帶回搜索到的權值最小的兩個結點所在表中的序號，定義一個臨時變量temp=0，然后，將表中第一個雙親為0的結點的權值賦給temp，然后再用一個for循環(huán)從1～nn號單元中找到雙親為0，且比temp小的結點，把它的權值賦給temp，直至找完n

26、n個存儲單元后，temp中存儲的就是最小的權值，同時將此權值所在存儲單元的序號k賦給指針s11所指的存儲單元，由s11帶回這個序號，同理，查找另一個權值最小的結點也采用相同方法，只是查找時附加一個條件是，找到的序號不能等于*s11，最后，同樣賦給*s22，有s22帶回第二小的權值所在的存儲單元的序號；　　void text_code(HuffmanTree HT,linklist head,in

27、t n)：HT為赫夫曼樹的首地址，head為之前建立好的鏈表的頭結點的指針，n為鏈表的結點數(shù)。從葉子結點向根結點逆向求其編碼,從雙親不為0的葉子結點開始，一直查找到雙親為0的根結點為止，在由葉子結點向根結點逆向求編碼的過程中，先判斷當前結點的雙親結點是否為0，如果不為0，則在判斷當前結點是其雙親結點的左孩子還是右孩子，如果是左孩子，就將字符0賦到鏈表中對應的結點的存儲編碼的字符數(shù)組中，若是右孩子就將字符1賦值到存儲編碼的數(shù)組中，然后，再

28、向上查找，再次按照上述步驟判斷，直到查找到根結點（雙親為0的結點），這樣就完成了一個葉子結點的編碼過程，再對下一個葉子結點重復上述步驟進行編碼即可。最后，鏈表的每個結點中的字符數(shù)組存儲的就是赫夫曼編碼的倒序。　　void Calculate_Code(char temp[],linklist head)：字符數(shù)組temp存儲的是用戶輸入的字符串，在主函數(shù)中調用此函數(shù)時，通過主函數(shù)中定義的字符數(shù)組

29、s傳遞數(shù)組首地址給它，head為之前建立的鏈表的頭結點指針。將指針p指向頭結點的下一個結點，然后用p循環(huán)將鏈表中每個結點中字符及其對應的編碼輸出，由于開始求解每個字符赫夫曼編碼的時候是由葉子結點向根結點逆向求的編碼，因此，存儲編碼的數(shù)組c中存儲的是赫夫曼編碼的倒序，因此輸出的時候采用逆序輸出，就可得到赫夫曼編碼了。然后，再從鏈表的頭結點的下一個結點開始，將字符串中的第一個字符到第n個字符，依次與鏈表中每個結點中的字符相比較，如果找到相同

30、字符的結點，就將結點中的編碼輸出，依此循環(huán)，直至字符串中的每個字符的編碼都輸出，這樣就得到了整個字符串的編碼。　　流程圖：　　Linklist calculation(char temp[],int n)：統(tǒng)計字符種類及各個字符在字符串中出現(xiàn)的次數(shù)的函數(shù)　　status au

31、to_calculation(linklist L)：自動統(tǒng)計權值的函數(shù)，以每個字符在字符串中出現(xiàn)的次數(shù)為權值　　status input_weight(linklist L)：手動輸入各個字符權值的函數(shù)　　void select(HuffmanTree &HT,int nn,int *s11,int *s22):在構造赫夫曼樹的順序表中選出雙親

32、為0，且權值最小的兩個結點，并用s11和s22返回這兩個結點所在順序表中的序號　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)：建立赫夫曼樹的函數(shù)　　void text_code(HuffmanTree HT,linklist head,int n):從葉子結點向根結點逆向求編碼</p

33、>　　void Calculte_Code(char temp[],linklist head)：輸出各個字符及整個字符串編碼的函數(shù)　　源程序：(由于采用了C++中的引用形參，因此必須采用.cpp為擴展名的源文件編譯）　　//HuffmanCoding.cpp　　#include<

34、;stdio.h>　　#include<string.h>　　#include<stdlib.h>　　#define length 100;　　#define OK 1;　　#define error

35、 0;　　typedef int status;　　typedef struct　　{　　unsigned int weight;　　unsigned int lchild ,rchild ,

36、parent;　　}HTnode,*HuffmanTree;　　typedef struct　　{　　char code;　　unsigned int weight;&

37、lt;p>　　char c[10];　　}Code,*Code_p;　　typedef struct Lnode　　{　　Code a;　　stru

38、ct Lnode *next;　　}Node,*linklist;　　typedef char **HuffmanCode;　　int *w; //w存放n個字符的相應權值　　linklist calculation(char temp[],int n) //統(tǒng)計字符種

39、類及各個字符在字符串中出現(xiàn)次數(shù)的函數(shù)，n表示字符串的個數(shù)　　{　　int i=0;　　linklist p;　　linklist t;　　linklist

40、 head;　　//創(chuàng)建一個字符串鏈表　　head=(linklist)malloc(sizeof(Node)); //創(chuàng)建一個帶頭結點的鏈表　　head->next=NULL;　　p=head;<

41、p>　　if(n!=0)　　{　　//將字符串存儲到一個鏈表中，每個結點存儲一個字符，方便后續(xù)統(tǒng)計字符的種類個數(shù)及其各個字符的權值　　for(i=0;i<n;i++)

42、　　{　　t=(linklist)malloc(sizeof(Node));　　t->a.code=temp[i];　　t->a.weight=1; //權值先初始化為1　　p->next=t;

43、;　　t->next=NULL;　　p=p->next;　　}　　/***對鏈表進行處理，字符串中的每種字符只保留一個，同時統(tǒng)計每種字符在字符串中出現(xiàn)的次數(shù)，如果采用自動統(tǒng)計權值的話，　　就以每個字符在字符串中出現(xiàn)的次數(shù)作

44、為其權值***/　　linklist p1;　　p=head->next;　　linklist temp_p;　　while(p!=NULL)　　{<p&g

45、t;　　t=p->next;　　p1=p;　　while(t!=NULL)　　{　　if(p->a.code==t->a.code)&l

46、t;b>　　{　　p->a.weight++;　　p1->next=t->next;　　temp_p=t;　　t=t->next;　　free

47、(temp_p);　　}　　else　　{　　p1=t;　　t=t->n

48、ext;　　}　　}　　p=p->next;　　}　　}</p&g

49、t;　　else　　printf("沒有字符！");　　return head;　　}　　status auto_calculation(linklist

50、 L) //自動統(tǒng)計權值的函數(shù)，以每個字符在字符串中出現(xiàn)的次數(shù)作為其權值　　{　　printf("各字符權值統(tǒng)計如下：\n");　　linklist p=L->next;　　if(p)&

51、lt;/b>　　{　　int n=0;　　for(;p!=NULL;p=p->next)　　{　　pri

52、ntf("%c : %d",p->a.code,p->a.weight);　　printf("\n");　　n++;　　}　　w=(int *)

53、malloc(n*sizeof(int));　　p=L->next;　　int i;　　for(i=0;i<n&&p!=NULL;i++,p=p->next)　　w[i]=p->a.weight

54、;　　return OK;　　}　　else　　{　　printf("統(tǒng)計錯誤，沒有字符！\n"

55、);　　return error;　　}　　}　　status input_weight(linklist L) //手動輸入各個字符權值的函數(shù)<

56、b>　　{　　linklist p=L->next;　　if(p!=NULL)　　{　　int n=0;　　printf(

57、"請輸入各個字符的權值：\n");　　for(p=L->next;p!=NULL;p=p->next)　　{　　printf("%c:",p->a.code);　　scanf(

58、"%d",&p->a.weight);　　n++;　　}　　w=(int *)malloc(n*sizeof(int));　　p=L->next;</

59、p>　　int i=0;　　for(i=0;i<n&&p!=NULL;i++,p=p->next)　　w[i]=p->a.weight;　　return OK;<b&

60、gt;　　}　　else　　{　　printf("沒有字符！\n");　　return error;<b&g

61、t;　　}　　}　　void select(HuffmanTree &HT,int nn,int *s11,int *s22)　　{　　int temp=0;</

62、p>　　HuffmanTree p=HT;　　int k;　　for(k=1;k<=nn;k++)　　{　　if(!p[k].parent)

63、　　{　　temp=p[k].weight;　　*s11=k;　　break;　　}</p&g

64、t;　　}　　for(k=1;k<=nn;k++)　　{　　if(!p[k].parent)　　{<

65、p>　　if(p[k].weight<temp)　　{　　temp=p[k].weight;　　*s11=k;　　}<

66、;p>　　}　　}　　for(k=1;k<=nn;k++)　　{　　if(!p[k].parent&&k!=*s11)</p

67、>　　{　　temp=p[k].weight;　　*s22=k;　　break;　　}<

68、;/p>　　}　　for(k=1;k<=nn;k++)　　{　　if(!p[k].parent&&k!=*s11)　　{<

69、/b>　　if(p[k].weight<temp)　　{　　temp=p[k].weight;　　*s22=k;　　}<

70、;/b>　　}　　}　　if(*s11>*s22)　　{　　temp=*s11;

71、　　*s11=*s22;　　*s22=temp;　　}　　}　　//建立赫夫曼樹　　void Cr

72、eat_HuffmanTree(HuffmanTree &HT,linklist L)　　{　　int n=0;　　linklist temp_p=L->next;　　for(;te

73、mp_p!=NULL;temp_p=temp_p->next) //統(tǒng)計字符串中不同字符的個數(shù)　　n++;　　if(n<=1)　　return;

74、　int m=2*n-1;　　int i;　　HuffmanTree p;　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTnode)); //零號單元未用　　for(p=HT,i=1;i<=n;i

75、++) //給它賦上相應的權值　　{　　p[i].weight=w[i-1];　　p[i].lchild=0;　　p[i].rchild=0;　　p[i].parent=0;

76、;　　}　　for(;i<=m;i++)　　{　　p[i].weight=0;　　p[i].parent=0;　　p[i].l

77、child=0;　　p[i].rchild=0;　　}　　int s1,s2;　　//建立huffman樹　　for(i=n+1;i<=m;i++)<p&g

78、t;　　{　　s1=0;　　s2=0;　　select(HT,i-1,&s1,&s2);　　HT[s1].parent=i;

79、;　　HT[s2].parent=i;　　HT[i].lchild=s1;　　HT[i].rchild=s2;　　HT[i].weight=HT[s1].weight+HT[s2].weight;　　}</

80、p>　　int j;　　for(j=1;j<m;j++)　　{　　printf("%d weight=%d,parent=%d,lchild=%d,rchild=%d",j,HT[j]

81、.weight,HT[j].parent,HT[j].lchild,HT[j].rchild);　　printf("\n");　　}　　}　　//---從葉子向根節(jié)點逆向求赫夫

82、曼編碼----　　void text_code(HuffmanTree HT,linklist head,int n)　　{　　HuffmanTree p=HT;　　linklist tp;

83、　tp=head->next;　　int m;　　int k;　　int j;　　int i;

84、　　for(i=1;i<=n&&tp!=NULL;i++,tp=tp->next)　　{　　k=i;　　for(j=1,m=p[k].parent; m!=0; k=m,m=p[k].pa

85、rent,j++)　　{　　if(p[m].lchild==k)　　tp->a.c[j-1]='0';　　else　　tp->

86、a.c[j-1]='1';　　}　　for(;j-1<10;j++)　　tp->a.c[j-1]='\0';　　}<p&g

87、t;　　}　　void Calculte_Code(char temp[],linklist head)　　{　　int n;　　linklist p=hea

88、d->next;　　printf("各個字符的編碼如下：\n");　　for(;p!=NULL;p=p->next)　　{　　printf("%c:",p->a.code);&

89、lt;/p>　　n=0;　　for(int i=0;p->a.c[i]!='\0';i++)　　n++;　　for(int i=n-1;i>=0;i--)&l

90、t;p>　　printf("%c",p->a.c[i]);　　printf("\n");　　}　　printf("電文的編碼：");　　int

91、m=0;　　for(int k=0;temp[k]!='\0';k++)　　m++;　　int i,j;　　for(i=0;i<m;i++)</p&

92、gt;　　{　　for(p=head->next;p!=NULL;p=p->next)　　{　　if(p->a.code==temp[i])

93、;　　{　　n=0;　　for(j=0;p->a.c[j]!='\0';j++)　　n++;　　for(j=n-1;j>=0;j--)</p&

94、gt;　　printf("%c",p->a.c[j]);　　}　　}　　}　　printf("\n&

95、quot;);　　}　　void main()　　{　　char s[100];　　int n=0;</p&g

96、t;　　HuffmanTree HT=NULL;　　linklist L;　　printf("請輸入一串電文：");　　scanf("%s",&s);　　for(int i=0;s[i]!='\

97、0';i++)　　n++;　　if(n!=1) //一個結點無法構造赫夫曼樹，無赫夫曼編碼　　{　　L=calculation(s,n);　　i

98、nt num=0;　　char choice;　　do　　{　　choice='n';　　printf("\t1.自動統(tǒng)計字符權

99、值（以每個字符在字符串中出現(xiàn)的次數(shù)作為其權值）\n\t2.手動輸入字符的權值\n)");　　printf("\t\t請選擇：");　　scanf("%d",&num);　　switch(num)

100、　{　　case 1:　　auto_calculation(L);　　break;　　case 2:<p&g

101、t;　　input_weight(L);　　break;　　default:　　printf("選項輸入錯誤，重新選擇(Y/N)？\n");　　scanf("%c&q

102、uot;,&choice);　　}　　}while(choice=='y'||choice=='Y');　　Creat_HuffmanTree(HT,L);　　text_code(HT,L,n)

103、;　　Calculte_Code(s,L);　　}　　else　　printf("只有一個字符，無法構造赫夫曼樹,無赫夫曼編碼！\n");<p&g

104、t;　　}　　調試結果　　自動統(tǒng)計的調試結果（截圖）：　　手動輸入權值的調試結果（截圖）：　　課程設計總結：　　赫夫

105、曼樹作為一種最優(yōu)二叉樹，它的特點就是樹的n個葉子結點的帶權路徑長度最短，樹的帶權路徑長度也是最短的，因此，赫夫曼樹在解決最佳判定問題以及最短編碼問題等領域有著重要的應用。　　本次課程設計就是利用赫夫曼樹對一段已知權值的字符串進行赫夫曼編碼的應用，赫夫曼編碼的特點是編碼最短，且在譯碼過程中不會產生歧義，當用戶輸入一段字符串以后，我們可以根據用戶對每個字符賦的權值，或者可以根據統(tǒng)計出的每個字符在字符

106、串中出現(xiàn)的次數(shù)作為權值對每個字符求解赫夫曼編碼。　　在整個程序設計中，我設計了兩個功能模塊供用戶選擇：一個是利用每個字符在字符串中出現(xiàn)的次數(shù)作為其權值對其進行編碼；另一個就是根據用戶對每個字符自定義的權值對其進行編碼。在程序設計中，我利用到了鏈表這種數(shù)據結構對字符串中的字符種類個數(shù)進行統(tǒng)計，同時通過查找鏈表結點，得到每個字符在字符串中出現(xiàn)的次數(shù)，這個次數(shù)可以作為自動統(tǒng)計權值這一功能模塊的權值，如

107、果用戶選擇自定義每個字符的權值，直接對鏈表中每個結點中的權值重新賦值即可，因此，這個作為統(tǒng)計使用的鏈表在整個程序設計中起到了至關重要的作用，包括后續(xù)根據構造好的赫夫曼樹對每個字符進行編碼以及最后輸出編碼都使用到了這個鏈表。　　通過本次課程設計，我對構造赫夫曼樹的整個過程以及利用赫夫曼樹求解赫夫曼編碼的原理也有了一個完整和全面的掌握，對于以后相關編碼原理的學習也打下了堅實的基礎，更重要的是在課程設

108、計中，我享受到了把自己腦袋中的想法變成現(xiàn)實以后的欣喜。　　心得體會　　通過這次課程設計，我的編程能力不僅得到了一個較大的提升，再一次鍛煉了我分析問題和解決問題的能力，因為我自小做事便喜歡追求完美，對于老師提出的只是手動對每個字符賦權值的這一要求，我感覺并不是很完美，因此，我想到增加一個讓字符串自動獲得權值這一功能，并

109、且用戶可以自己選擇一種權值獲得方法。心中有了想法和思路以后，我便開始動手設計，我先設計了程序的大體框架，然后將每個功能實現(xiàn)細分到每個函數(shù)上以后，我便開始動手編寫程序，由于對赫夫曼樹的構造以及編碼的算法還算比較了解，加上編程能力還算不錯，因此整個算法的實現(xiàn)上幾乎沒有遇到什么困難，在較短的時間內就把它做完了。　　但是，這次課程設計花費我大量精力和時間的環(huán)節(jié)是最后的課程設計報告，由于平時很少動手畫流程

110、圖，而課程設計報告要求提供算法流程圖，為了畫出一個清晰明了的算法流程圖，我花了很多精力和時間，總共有七個流程圖，起初畫前兩個的時候，總是感覺畫得不夠好，別人有可能看不懂，而且又花了很多很多時間，便有點耐不住心了，但又為了做好整個課程設計，又強迫自己耐心繼續(xù)畫，在畫圖的過程中，我慢慢摸索出了一些簡便且效果很好的制圖方法，就是利用word中提供的制表功能可以快速簡潔地制作出清晰明了的N-S流程圖，這是我以前沒有發(fā)現(xiàn)的，因為以前做課程設計報告

111、畫N-S流程圖時，使用的總是通過一些矩形框和直線構造一個N-S流程圖，這樣畫出來的效果不僅不美觀，而且為了對其線條，會花去大量的時間，而發(fā)現(xiàn)利用制表功能可以快速畫出美觀的N-S流程圖后，以前對N-S流程圖的恐懼感一下就沒了，在短短幾小時中，就完成了整個程序流程圖的繪制，并且效果比起原來的要好出了很多，感覺心里充滿著成就感和喜悅之情，相信在以后工作中，需要在項目設計報告中添加流程圖時，我也可以快速準確的寫出讓老板和客戶滿意的報告，這應該算

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

溫馨提示

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

數(shù)據結構課程設計報告---赫夫曼編碼

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據結構課程設計報告---赫夫曼編碼

文檔簡介

溫馨提示

最新文檔

評論

免費下載