數(shù)據(jù)結構課程設計哈夫曼樹的應用

《數(shù)據(jù)結構課程設計哈夫曼樹的應用》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構課程設計哈夫曼樹的應用（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 武漢理工大學華夏學院 課程設計報告書 課程名稱： 數(shù)據(jù)結構課程設計 題 目： 哈夫曼樹的應用 系 名： 信息工程系 專業(yè)班級： 計算機科學與技術 姓 名： 學 號： 指導教師: 2011 年 7 月 1 日

2、 課程設計任務書 學生姓名： 專業(yè)班級： 計算機 指導教師： 工作單位： 信息工程系 題 目: 哈夫曼樹的應用 初始條件： 理論：學習了《數(shù)據(jù)結構》課程，掌握了基本的數(shù)據(jù)結構和常用的算法； 實踐：信息工程系實驗室提供計算機及軟件開發(fā)環(huán)境。 要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求） 1、系統(tǒng)應具備的功能： （1）輸入一組數(shù)據(jù)建立哈夫曼樹 （2）設計哈夫曼碼 （3）實現(xiàn)譯碼 2、數(shù)據(jù)結構設計； 3、主要算法設計； 4、編

3、程及上機實現(xiàn)； 5、撰寫課程設計報告，包括： （1）設計題目； （2）摘要和關鍵字； （3）正文，包括引言、需求分析、數(shù)據(jù)結構設計、算法設計、程序實現(xiàn)及測試等； （4）結束語； （5）參考文獻。 時間安排： 2011年6月27日－2011年7月1日 （第19周） 星期一 查閱資料 星期二 系統(tǒng)設計，數(shù)據(jù)結構設計，算法設計 星期三-星期四 編程并上機調試 星期五 撰寫報告 星期五 驗收程序，提交設計報告書。 指導教師簽名： 2011年6月27日 系主任（或責任教師）簽名：

4、 2011年6月27日 目 錄 1 引言 ………………………………………………………… 4 2 需求分析 ………………………………………………… 4 3 數(shù)據(jù)結構與算法設計 3.1數(shù)據(jù)結構設計 ………………………………………… 5 3.2算法設計 ……………………………………………… 5 4 程序的實現(xiàn) ………………………………… ……………………………… 8 5 程序測試 ………………………………… ……………………………… 14 6 結束語 6.1設計體會 ……………………………………………… 16 6.2心得體

5、會 ……………………………………………… 16 參考文獻 ………………………………… 16 1. 引言 數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，它不僅是計算機學科的核心課程，學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構及其相應的算法并初步掌握算法的時間分析和空間分析的技術。 數(shù)據(jù)結構課程主要是研究非數(shù)值計算的程序設計問題中所出現(xiàn)的計算機操作對象以及它們之間的關系和操作的學科。數(shù)據(jù)結構是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設計、數(shù)據(jù)庫、操作

6、系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領域。 學習數(shù)據(jù)結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業(yè)素質的提高。而此次課程設計通過對哈夫曼樹的概念、構造算法的理解，進行編碼，從而掌握赫夫曼樹的編碼原則。 2.需求分析 數(shù)據(jù)的讀入﹑存儲，生成文件，將鍵盤輸入的信息存入指定的文件中；設計一程序求解此問題．霍夫曼（Huffman）編碼原理是一種利用二叉樹實現(xiàn)的編碼原理 霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統(tǒng)計編碼。屬于無損壓縮編碼。 霍夫曼

7、編碼的碼長是變化的，對于出現(xiàn)頻率高的信息，編碼的長度較短；而對于出現(xiàn)頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。 鍛煉我們的編碼能力，真正理解數(shù)據(jù)結構的編碼思想,并且鍛煉我們的動手能力和成員間的配合，提高程序編寫能力。 在信息傳遞時，希望長度能盡可能短，即采用最短碼。赫夫曼編碼的應用，就是采用這種有效的數(shù)據(jù)壓縮技術可以節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡的傳送時間。 3.數(shù)據(jù)結構與算法設計 3.1數(shù)據(jù)結構設計 ,,為包含的庫函數(shù) #define NAMEMAX 20

8、#define CODEMAX 30 定義最大值 typedef unsigned int UINT; typedef char NAME[NAMEMAX]; typedef char CODE[CODEMAX]; 定義各量類型 void menu(); /* 定義menu菜單 */ void input(); /* 輸入函數(shù) */ void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n)建立哈夫曼樹 int HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n)

9、構建哈夫曼編碼 typedef struct { NAME name; /* 字符 */ CODE code; /* 編碼 */ UINT weight; /* 權值 */ UINT parent,lchild,rchild; /* */ }HTNode,*HuffmanTree; 3.2算法設計 哈夫曼樹編碼算法： void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) { int i,s1,s2,start; unsigned c,f; HuffmanTree p; c

10、har *cd; if(n<=1||n>CODEMAX)return; *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode)); for(p=*HT+1,i=1;i<=n;++i,++p,++w) { strcpy((*p).name,str[i-1]); (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<=2*n-1;++i,++p)(*p).parent=0; for(i=n+1;i<2*n;++i) { se

11、lect(*HT,i-1,&s1,&s2); (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]=0; for(i=1;i<=n;i++) { start=n-1; for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f]

12、.parent) { if((*HT)[f].lchild==c)cd[--start]=0; else cd[--start]=1; } strcpy((*HT)[i].code,&cd[start]); } free(cd); } 輸入字符，權值算法：輸入一些字符,然后再輸入相對應數(shù)量的權值,建哈夫曼樹,然后進行編碼,并得到相對應的哈夫曼編碼。 void input() { HuffmanTree HT; int *w,n,i; NAME *str; char temp[50]; system("cls"); /* 清屏

13、*/ printf("請輸入權值的個數(shù)(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int)); str=(NAME*)malloc(n*sizeof(NAME)); printf("請依次輸入%d個符號(回車分隔):\n",n); for(i=0;i

14、); for(i=1;i<=n;i++)printf("%s---%s\n",HT[i].name,HT[i].code); printf("請輸入你要查的字符\n"); scanf("%s",temp); for(i=1;i<=n;i++) if(!strcmp(HT[i].name,temp))printf("%s\n",HT[i].code); printf("請輸入你要查的編碼\n"); scanf("%s",temp); for(i=1;i<=n;i++) if(!strcmp(HT[i].code,temp))printf("%

15、s\n",HT[i].name); printf("\n按回車鍵返回主菜單……\n"); getch(); menu(); } 4.程序的實現(xiàn) #include #include #include #define NAMEMAX 20 #define CODEMAX 30 typedef unsigned int UINT; typedef char NAME[NAMEMAX]; typedef char CODE[CODEMAX]; typedef struct {

16、 NAME name; CODE code; UINT weight; UINT parent,lchild,rchild; }HTNode,*HuffmanTree; void menu(); /* 定義menu菜單 */ void input(); /* 輸入函數(shù) */ void menu() { int select; system("cls"); printf("\t\t\t哈夫曼樹的應用\n"); printf("***************************\n"); printf("*

17、 * \n"); printf("*[1]輸入哈弗曼樹的基本情況并查找 \n"); printf("*[2]退出 \n"); printf("* * \n"); printf("***************************\n"); printf("請輸入你的選項(1--2)："); scanf("%d",&select); switch(select) /* 判斷選擇 */ { case 1:input();

18、break; case 2:exit(0);break; } } void input() { HuffmanTree HT; int *w,n,i; NAME *str; char temp[50]; system("cls"); /* 清屏 */ printf("請輸入權值的個數(shù)(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int)); str=(NAME*)malloc(n*sizeof(NAME)); printf("請依次輸入%d個符號

19、(回車分隔):\n",n); for(i=0;i

20、HT[i].name,temp))printf("%s\n",HT[i].code); printf("請輸入你要查的編碼\n"); scanf("%s",temp); for(i=1;i<=n;i++) if(!strcmp(HT[i].code,temp))printf("%s\n",HT[i].name); printf("\n按回車鍵返回主菜單……\n"); getch(); menu(); } int minnode(HuffmanTree t,int i) { int j,flag; unsigned int

21、k=0xffffffff; for(j=1;j<=i;j++) if(t[j].weight*s2) { j=*s1; *s1=*s2; *s2=j

22、; } } int HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) { int i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1||n>CODEMAX)return; *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode)); for(p=*HT+1,i=1;i<=n;++i,++p,++w) { strcpy((*p).name,str[i-1]);

23、(*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<=2*n-1;++i,++p)(*p).parent=0; for(i=n+1;i<2*n;++i) { select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT

24、)[s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]=0; for(i=1;i<=n;i++) { start=n-1; for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) { if((*HT)[f].lchild==c)cd[--start]=0; else cd[--start]=1; } strcpy((*HT)[i].code,&cd[start]); } free(cd);

25、 } int main() { menu(); } 5.程序測試 5-1圖 menu菜單圖 圖5-2 輸入各值并生成編碼圖 圖5-3 查找字符相對應的編碼以及譯碼圖 5-4圖 menu退出運行圖 6.結束語 6.1設計體會 當剛拿到程序課題時，一看，感覺都挺容易的，都是我們學過的一些內容，應該很容易完成，于是就從中選了一個哈夫曼樹的應用。結果一作才知道，并不如我們想的那么容易。對于建立哈夫曼樹，創(chuàng)建哈夫曼編碼等算法，總是因一點不對而編譯不成功。 在int HuffmanC

26、oding(HuffmanTree *HT,NAME *str,int *w,int n)中，其中的那個說明總是弄不對或是落東西。 而在主函數(shù)main() { menu(); } 中，其中menu的調用更是老是編譯不成功，導致運行不成功或出錯。 6.2心得體會 忙碌了一個星期，終于順利完成了對此程序的編譯及試運行。 通過數(shù)據(jù)結構課程設計，我的c語言水平有了比較大的提高，其中c語言關于指針，文件的操作理解的比以前深刻不少。另外是數(shù)據(jù)結構方面的提高，對哈夫曼樹的構造，及哈夫曼碼方面也有不少的提高。 在項目中也出現(xiàn)了很多的問題，最大的問題就是對程序設

27、計框架結構的不了解，在實現(xiàn)代碼與功能的連接時經常會出現(xiàn)各種不同的錯誤，在實現(xiàn)一些功能時系統(tǒng)常常會報錯。許多錯誤不知從哪修改，以致托了整個設計的后腿。課程設計中，既回顧了很多以前的東西，也發(fā)現(xiàn)了很多的問題，以前都沒遇見過的，收獲很大。 通過本次數(shù)據(jù)結構的課程設計，我學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關于哈夫曼編碼的知識， 此次哈夫曼樹的應用系統(tǒng)的設計讓自己對數(shù)據(jù)結構的了解更深入。 參考文獻 [1]魏江江 李瑋琪 編著《數(shù)據(jù)結構》（C語言版），清華大學出版社，2009年9月 [2]譚浩強 著《C程序設計》（第三版），清

28、華大學出版社，2005年7月 [3]徐孝凱 《數(shù)據(jù)結構實用教程》[M]， 清華大學出版社，1999年 [4] 寧正元 易金聰 《數(shù)據(jù)結構學習輔導》，清華大學出版社，2005年 本科生課程設計成績評定表 班級：計算機 　 姓名： 　　學號： 序號 評分項目 滿分 實得分 1 學習態(tài)度認真、遵守紀律 10 2 設計分析合理性 10 3 設計方案正確性、可行性、創(chuàng)造性 20 4 設計結果正確性 40 5 設計報告的規(guī)范性 10 6 設計驗收 10 總得分/等級 評語： 該生在數(shù)據(jù)結構課程設計過程中，態(tài)度認真，遵守紀律。 數(shù)據(jù)結構設計合理，算法設計正確，設計結果正確，報告撰寫較為規(guī)范，通過了設計驗收。 注：最終成績以五級分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、 及格（60-69分）、60分以下為不及格 　　　　　　　　　　　　　　　指導教師簽名： 　　　　　　　　　　　　　　　　　　2011 年7月2日 18