數(shù)據(jù)結(jié)構(gòu)課程設(shè)計哈夫曼樹的應(yīng)用

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

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

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

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

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

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

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

7、編碼的碼長是變化的，對于出現(xiàn)頻率高的信息，編碼的長度較短；而對于出現(xiàn)頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。 鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想,并且鍛煉我們的動手能力和成員間的配合，提高程序編寫能力。 在信息傳遞時，希望長度能盡可能短，即采用最短碼。赫夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間。 3.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計 3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計 ,,為包含的庫函數(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、構(gòu)建哈夫曼編碼 typedef struct { NAME name; /* 字符 */ CODE code; /* 編碼 */ UINT weight; /* 權(quán)值 */ UINT parent,lchild,rchild; /* */ }HTNode,*HuffmanTree; 3.2算法設(shè)計 哈夫曼樹編碼算法： 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); } 輸入字符，權(quán)值算法：輸入一些字符,然后再輸入相對應(yīng)數(shù)量的權(quán)值,建哈夫曼樹,然后進行編碼,并得到相對應(yīng)的哈夫曼編碼。 void input() { HuffmanTree HT; int *w,n,i; NAME *str; char temp[50]; system("cls"); /* 清屏

13、*/ printf("請輸入權(quán)值的個數(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哈夫曼樹的應(yīng)用\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("請輸入權(quán)值的個數(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 查找字符相對應(yīng)的編碼以及譯碼圖 5-4圖 menu退出運行圖 6.結(jié)束語 6.1設(shè)計體會 當(dāng)剛拿到程序課題時，一看，感覺都挺容易的，都是我們學(xué)過的一些內(nèi)容，應(yīng)該很容易完成，于是就從中選了一個哈夫曼樹的應(yīng)用。結(jié)果一作才知道，并不如我們想的那么容易。對于建立哈夫曼樹，創(chuàng)建哈夫曼編碼等算法，總是因一點不對而編譯不成功。 在int HuffmanC

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

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

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