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

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

3、4 程序的實(shí)現(xiàn) 85 程序測試 146 結(jié)束語 6.1設(shè)計體會 16 6.2心得體會 16參考文獻(xiàn) 161. 引言數(shù)據(jù)結(jié)構(gòu)是計算機(jī)程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機(jī)學(xué)科的核心課程，學(xué)會分析研究計算機(jī)加工的數(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)的計算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間的一門計算機(jī)專業(yè)的核心課程，它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各

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

5、。這樣，處理全部信息的總碼長一定小于實(shí)際信息的符號長度。鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想,并且鍛煉我們的動手能力和成員間的配合，提高程序編寫能力。在信息傳遞時，希望長度能盡可能短，即采用最短碼。赫夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲空間和計算機(jī)網(wǎng)絡(luò)的傳送時間。3.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計,為包含的庫函數(shù)#define NAMEMAX 20#define CODEMAX 30 定義最大值typedef unsigned int UINT;typedef char NAMENAMEMAX;typedef char CODECODEMAX;

6、定義各量類型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)構(gòu)建哈夫曼編碼typedef struct NAME name; /* 字符 */ CODE code; /* 編碼 */ UINT weight; /* 權(quán)值 */ UINT parent,lchild,rchild; /* */HTNode

7、,*HuffmanTree; 3.2算法設(shè)計哈夫曼樹編碼算法：void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) int i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(nCODEMAX)return; *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode); for(p=*HT+1,i=1;i=n;+i,+p,+w) strcpy(*p).name,stri-1); (*p).weight=*w; (*p).parent=0; (*

8、p).lchild=0; (*p).rchild=0; for(;i=2*n-1;+i,+p)(*p).parent=0; for(i=n+1;i2*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)s2.weight; cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i1): ); scanf(%d,&n); w=(int*)

9、malloc(n*sizeof(int); str=(NAME*)malloc(n*sizeof(NAME); printf(請依次輸入%d個符號(回車分隔):n,n); for(i=0;in;i+)scanf(%s,stri); printf(請依次輸入%d個權(quán)值(整型):n,n); for(i=0;in;i+)scanf(%d,w+i); HuffmanCoding(&HT,str,w,n); for(i=1;i=n;i+)printf(%s-%sn,HTi.name,HTi.code); printf(請輸入你要查的字符n); scanf(%s,temp); for(i=1;i=n;i+

10、) if(!strcmp(HTi.name,temp)printf(%sn,HTi.code); printf(請輸入你要查的編碼n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(HTi.code,temp)printf(%sn,HTi.name); printf(n按回車鍵返回主菜單n); getch(); menu(); 4.程序的實(shí)現(xiàn)#include#include#include#define NAMEMAX 20#define CODEMAX 30typedef unsigned int UINT;typedef char NAMENAME

11、MAX;typedef char CODECODEMAX; typedef struct 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(ttt哈夫曼樹的應(yīng)用n); printf(*n); printf(* * n); printf(*1輸入哈弗曼樹的基本情況并查找 n); printf(*

12、2退出 n); printf(* * n); printf(*n); printf(請輸入你的選項(1-2)：); scanf(%d,&select); switch(select) /* 判斷選擇 */ case 1:input();break; case 2:exit(0);break; void input() HuffmanTree HT; int *w,n,i; NAME *str; char temp50; system(cls); /* 清屏 */ printf(請輸入權(quán)值的個數(shù)(1): ); scanf(%d,&n); w=(int*)malloc(n*sizeof(int);

13、 str=(NAME*)malloc(n*sizeof(NAME); printf(請依次輸入%d個符號(回車分隔):n,n); for(i=0;in;i+)scanf(%s,stri); printf(請依次輸入%d個權(quán)值(整型):n,n); for(i=0;in;i+)scanf(%d,w+i); HuffmanCoding(&HT,str,w,n); for(i=1;i=n;i+)printf(%s-%sn,HTi.name,HTi.code); printf(請輸入你要查的字符n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(HTi.name

14、,temp)printf(%sn,HTi.code); printf(請輸入你要查的編碼n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(HTi.code,temp)printf(%sn,HTi.name); printf(n按回車鍵返回主菜單n); getch(); menu(); int minnode(HuffmanTree t,int i) int j,flag; unsigned int k=0xffffffff; for(j=1;j=i;j+) if(tj.weight*s2) j=*s1; *s1=*s2; *s2=j; int Huf

15、fmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) int i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(nCODEMAX)return; *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode); for(p=*HT+1,i=1;i=n;+i,+p,+w) strcpy(*p).name,stri-1); (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i=2*n-

16、1;+i,+p)(*p).parent=0; for(i=n+1;i2*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)s2.weight; cd=(char*)malloc(n*sizeof(char); cdn-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)

17、if(*HT)f.lchild=c)cd-start=0; else cd-start=1; strcpy(*HT)i.code,&cdstart); free(cd);int main() menu();5.程序測試5-1圖 menu菜單圖圖5-2 輸入各值并生成編碼圖圖5-3 查找字符相對應(yīng)的編碼以及譯碼圖5-4圖 menu退出運(yùn)行圖6.結(jié)束語6.1設(shè)計體會當(dāng)剛拿到程序課題時，一看，感覺都挺容易的，都是我們學(xué)過的一些內(nèi)容，應(yīng)該很容易完成，于是就從中選了一個哈夫曼樹的應(yīng)用。結(jié)果一作才知道，并不如我們想的那么容易。對于建立哈夫曼樹，創(chuàng)建哈夫曼編碼等算法，總是因一點(diǎn)不對而編譯不成功。在int H

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

19、種不同的錯誤，在實(shí)現(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)的了解更深入。參考文獻(xiàn)1魏江江 李瑋琪 編著數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2009年9月2譚浩強(qiáng) 著C程序設(shè)計（第三版），清華大學(xué)出版社，2005年7月3徐孝凱 數(shù)據(jù)結(jié)構(gòu)實(shí)用教程M， 清華大學(xué)出版社，1999年4 寧正元 易金聰 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)，清華大學(xué)出版社，2005年本科生課程設(shè)計成績評定表班級：計算機(jī) 姓名： 學(xué)號： 序號評分項目滿分實(shí)得分1學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律102設(shè)計分析合理性103設(shè)計方案正確性、可行性、創(chuàng)造性204設(shè)計結(jié)果正確性405設(shè)計報告的規(guī)范性106設(shè)計驗(yàn)收10總得分/等級評語： 該生在數(shù)據(jù)結(jié)構(gòu)課程設(shè)計過程中，態(tài)度認(rèn)真，遵守紀(jì)律。數(shù)據(jù)結(jié)構(gòu)設(shè)計合理，算法設(shè)計正確，設(shè)計結(jié)果正確，報告撰寫較為規(guī)范，通過了設(shè)計驗(yàn)收。注：最終成績以五級分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下為不及格指導(dǎo)教師簽名：2011 年7月2日18