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

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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告 題 目： 哈夫曼樹應(yīng)用 學(xué)生姓名： 謝輝 學(xué) 號(hào)： 201317010201 專業(yè)班級(jí)： 計(jì)科13102 同組姓名： 趙麗娜 指導(dǎo)教師： 徐曉蓉 設(shè)計(jì)時(shí)間： 2014年下學(xué)期第18周 指導(dǎo)老師意見: 評(píng)定成績(jī): 簽名: 日期: 目錄 一、 需求分析 2 1. 分析問題 2 2. 確定解決方案 2 3. 輸入的形式和輸入值的范圍 3 4.輸出的形式 3 5.程序所能達(dá)到的功能 3 二、概要設(shè)計(jì) 4 1. 主程序的流程圖： 4 2．程序中數(shù)據(jù)類型的定義： 4 3．各程序模塊之間的層次(調(diào)用)關(guān)系： 4 三、 詳細(xì)設(shè)計(jì) 5 1． 哈夫曼樹存儲(chǔ)及類的定義： 5 2.哈夫曼樹的基本操作: 6 3.主函數(shù) 7 四、 調(diào)試分析和測(cè)試結(jié)果. 9 1. 測(cè)試數(shù)據(jù)及其輸出結(jié)果： 9 2. 調(diào)試過程中遇到的問題及解決辦法: 13 五、 總結(jié) 14 六、 參考文獻(xiàn) 14 七、 致謝 14 八、 附錄 14 一、 需求分析 1. 分析問題 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。 2. 確定解決方案 設(shè)計(jì)建立帶權(quán)的哈夫曼樹，確定哈夫曼樹的類與成員函數(shù)，以及各函數(shù)之間的調(diào)用關(guān)系，采用動(dòng)態(tài)數(shù)組的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)所需要的數(shù)據(jù)，通過不同的函數(shù)來實(shí)現(xiàn)編碼，譯碼以及打印二進(jìn)制編碼、哈夫曼樹，把不同的數(shù)據(jù)存入不同的txt文件中，通過主函數(shù)調(diào)用來實(shí)現(xiàn)功能檢測(cè)。 3. 輸入的形式和輸入值的范圍 手動(dòng)或者從文本中讀入數(shù)據(jù)的形式初始化哈夫曼樹，從鍵盤中或者文件中讀入數(shù)據(jù)，以字母A-Z代表結(jié)點(diǎn)，以自然數(shù)代表權(quán)值，字符串提示使用者所要執(zhí)行的操作。 4.輸出的形式 在顯示器界面上或者以文本的形式來實(shí)現(xiàn)程序調(diào)試的輸出。 5.程序所能達(dá)到的功能 （1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。 （2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。 （3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。 （4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。 測(cè)試數(shù)據(jù)： （1） 利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。 （2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 頻度 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 實(shí)現(xiàn)提示： （1） 編碼結(jié)果以文本方式存儲(chǔ)在文件CodeFile中。 （2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。 （3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或E命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。 二、概要設(shè)計(jì) I.初始化 E.編碼 D.譯碼 P.打印編碼代碼 Q.退出 請(qǐng)重新輸入選項(xiàng) 判斷選項(xiàng) 是否正確 選擇菜單項(xiàng) 主菜單 開始 1. 主程序的流程圖： 是 否 圖一：主程序流程圖 2．程序中數(shù)據(jù)類型的定義： 用到三組結(jié)構(gòu)體，分別是哈夫曼樹的動(dòng)態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)*HuffmanTree，哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu)HuffmanCode，字符結(jié)點(diǎn)的動(dòng)態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)wElem以及哈夫曼樹類定義classHuffman。 3．各程序模塊之間的層次(調(diào)用)關(guān)系： 主函數(shù)main（）調(diào)用初始化，編碼，譯碼，打印二進(jìn)制編碼，打印哈夫曼樹這五個(gè)子函數(shù)；進(jìn)入初始化功能后調(diào)用手動(dòng)輸入，文本讀入，默認(rèn)文本這三個(gè)函數(shù)；進(jìn)入編碼功能后調(diào)用手動(dòng)編碼，文本讀入編碼這兩個(gè)函數(shù)；進(jìn)入譯碼功能后調(diào)用手動(dòng)譯碼，文本讀入譯碼這兩個(gè)函數(shù)(如圖2所示)。 手動(dòng)輸入 圖二:各程序模塊之間的層次（調(diào)用）關(guān)系 默認(rèn)文本 主函數(shù) 初始化 編碼 譯碼 打印編碼代碼 退出 從文件讀入 從文件讀入 三、 詳細(xì)設(shè)計(jì) 1． 哈夫曼樹存儲(chǔ)及類的定義： #include #include #include #include #include using namespace std; #define MAXN 60 #define INF 9999 int date[40]={INF,64,13,22,32,103,21,15,47,57,1,5,32, 20,57,63,15,1,48,51,80,23,8,18,1,6,1,INF,INF,INF,INF,INF,INF,INF,186}; //字符c的頻率存放在date[65-c+i]中 int n=27; typedef struct node{ int fa,lchild,rchild,w; //父親，左孩子，右孩子，權(quán)值； }hfmTree; char info[30]; typedef struct{ char code[50]; int start; }Hfmcode; Hfmcode hfmcode[MAXN]; //哈夫曼編碼 hfmTree hfmtree[MAXN]; //哈夫曼樹 void inithead(int n,char d[]) ; //初始化表 void initialization(int n,char d[]); //建樹 void encoding(int n) ; //編碼 void decoding(); //譯碼 void print() //打印編碼代碼 2.哈夫曼樹的基本操作: void inithead(int n,char d[]) //初始化表 void initialization(int n,char d[]) //建樹 void encoding(int n) //編碼 void decoding(); //譯碼 void print() //打印編碼代碼 void face() //輸出菜單界面 3.主函數(shù) int main() { char c; face(); int fi,fe,fd; fi=fe=fd=0; printf("數(shù)據(jù)從“sourceChar.txt”文件中輸入!\n"); while(1) { printf("->"); cin>>c; if(c>=a&&c<=z) c-=32; if(c==Q) break; switch(c) { case I: fi=1; init(); printf("初始化完畢！\n"); break; case E: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } fe=1; encoding(n); printf("將“ToBeTran.txt”中的正文"); printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中\(zhòng)n"); break; case D: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } if(fe==0) { printf("請(qǐng)先進(jìn)行編碼操作！\n"); break; } fd=1; printf("譯碼成功,譯碼結(jié)果為：\n"); decoding(); break; case P: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } if(fe==0) { printf("請(qǐng)先進(jìn)行編碼操作！\n"); break; } print(); printf("編碼結(jié)果已保存在文件“CodePrin.txt”中\(zhòng)n"); break; default: printf("輸入有誤，請(qǐng)重新輸入\n"); } } return 0; } 四、 調(diào)試分析和測(cè)試結(jié)果. 測(cè)試數(shù)據(jù)及其輸出結(jié)果： (1) 進(jìn)入主菜單界面： 用戶可以選擇所要執(zhí)行的操作，比如：初始化<建立哈夫曼樹>，編碼，譯碼，打印二進(jìn)制編碼代碼。在執(zhí)行編碼、譯碼操作前，請(qǐng)先初始化默認(rèn)的哈夫曼樹(如圖3所示)。 圖3：主菜單界面 當(dāng)輸入錯(cuò)誤的指令時(shí)（如圖4所示）: 圖4 當(dāng)未進(jìn)行初始化時(shí)進(jìn)行編碼是輸出（如圖5所示）： 圖5 (2) 進(jìn)入初始化界面（如圖6所示）： 圖6 (3) 進(jìn)入編碼界面（如圖7所示）： 圖7 (4) 進(jìn)入譯碼界面（如圖8所示）： 圖8 (5) 進(jìn)入打印編碼代碼界面(如圖9所示)： 圖9 （6） 退出系統(tǒng)（如圖10所示）： 1.調(diào)試過程中遇到的問題及解決辦法: 在此系統(tǒng)中，我負(fù)責(zé)的是編碼，赫夫曼樹的建立在譯碼之前，數(shù)據(jù)從文件“SourceChar.txt”中輸入，對(duì)26個(gè)英文字母以及空格進(jìn)行編碼。分別存入hfmcode[1-26]中，空格的編碼存入hfmcode[27]中。 五、 總結(jié) 一周的課程設(shè)計(jì)結(jié)束了。在此過程中，我們小組齊心協(xié)力，互相幫助，分工明確，相互學(xué)習(xí)和探討。 完成這次的課程設(shè)計(jì)任務(wù)，我們要做好以下準(zhǔn)備： (1)首先要熟練掌握二叉樹的性質(zhì)、先序遍歷二叉樹、最優(yōu)二叉樹的構(gòu)建、字符串匹配等，然后在此基礎(chǔ)上掌握理解huffman樹和編碼和譯碼。 (2)完成哈夫曼編譯器，我們要考慮如何把文件當(dāng)中的英文字母編成二進(jìn)制代碼，如何將二進(jìn)制代碼翻譯成英文字母以及如何構(gòu)建一棵哈夫曼樹。 每次出現(xiàn)問題我們都一起討論，研究解決和改進(jìn)的方法。這次課程設(shè)計(jì)的成功，可以說是我們組員一起努力的成果。我們小組由兩個(gè)人組成，每個(gè)人都有自己在小組中的作用。我負(fù)責(zé)譯碼部分和界面函部分，另一組員負(fù)責(zé)初始化和編碼部分。我們總是在不斷地調(diào)試程序和改進(jìn)程序的功能，最后終于在自己的努力和老師的辛勤指導(dǎo)下順利完成了這次課程設(shè)計(jì)。 六、 參考文獻(xiàn) 1《數(shù)據(jù)結(jié)構(gòu)》（c++語言版），嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社 2《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏編著，清華大學(xué)出版社 七、 致謝 感謝這次課程設(shè)計(jì)中老師的細(xì)心和耐心指導(dǎo)，小組成員的的幫助，團(tuán)結(jié)合作才能使這次任務(wù)圓滿完成。 八、 附錄 源程序： #include #include #include #include #include using namespace std; #define MAXN 60 #define INF 9999 int date[40]={INF,64,13,22,32,103,21,15,47,57,1,5,32, 20,57,63,15,1,48,51,80,23,8,18,1,6,1,INF,INF,INF,INF,INF,INF,INF,186}; //字符c的頻率存放在date[65-c+i]中 int n=27; typedef struct node{ int fa,lchild,rchild,w; //父親，左孩子，右孩子，權(quán)值； }hfmTree; char info[30]; typedef struct{ char code[50]; int start; }Hfmcode; Hfmcode hfmcode[MAXN]; //哈夫曼編碼 hfmTree hfmtree[MAXN]; //哈夫曼樹 void inithead(int n,char d[]) //初始化表 { for(int i=1;i<=n;i++) { hfmtree[i].fa=-1; hfmtree[i].lchild=hfmtree[i].rchild=-1; if(d[i]== ) hfmtree[27].w=186; else hfmtree[i].w=date[ d[i]-64]; } for(int j=n+1;j<=2*n-1;j++) { hfmtree[j].fa=-1; hfmtree[j].lchild=hfmtree[j].rchild=hfmtree[j].w=-1; } } void initialization(int n,char d[]) //建樹成功 { int s1,s2,rnode,min1,min2; inithead(n,d); for(int i=n+1;i<=n*2-1;i++) { min1=INF; min2=INF; s1=s2=-1; for(int k=1;k<=i-1;k++) { if(hfmtree[k].fa==-1) { if(hfmtree[k].wmin1) { min2=hfmtree[k].w; s2=k; } } } hfmtree[i].w=hfmtree[s1].w+hfmtree[s2].w; hfmtree[i].lchild=s1s2?s1:s2; hfmtree[s1].fa=i; hfmtree[s2].fa=i; } } void encoding(int n) //編碼完成 { int c,fa; Hfmcode hcode; //對(duì)A~Z字符編碼 結(jié)果存入hfmcode中。 for(int i=1;i<=n;i++) { c=i; hcode.start=n; fa=hfmtree[i].fa; while(fa!=-1) { if(hfmtree[fa].lchild==c) hcode.code[hcode.start--]=0; else hcode.code[hcode.start--]=1; c=fa; fa=hfmtree[fa].fa; } hcode.start++; hfmcode[i]=hcode; } //對(duì)ToBeTran.txt中的字符編碼！結(jié)果存入CodeFile.txt文件中。 char s; ifstream in; ofstream out; in.open("ToBeTran.txt"); out.open("CodeFile.txt"); //讀入字符串存入str字符數(shù)組中。 char str; while(in.get(str)) { if(str!= ) { int start=hfmcode[str-64].start; for(int i=start;i<=n;i++) out.put(hfmcode[str-64].code[i]); } else { int start=hfmcode[27].start; for(int i=start;i<=n;i++) out.put(hfmcode[27].code[i]); } out.put(\n); } } void print() { ifstream in; ofstream out; out.open("CodePrin.txt"); char str; in.open("CodeFile.txt"); int i=0; while(in.get(str)) { if(str==\n) continue; i++; cout<"); cin>>c; if(c==Q) break; switch(c) { case I: fi=1; init(); printf("初始化完畢！\n"); break; case E: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } fe=1; encoding(n); printf("將“ToBeTran.txt”中的正文"); printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中\(zhòng)n"); break; case D: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } if(fe==0) { printf("請(qǐng)先進(jìn)行編碼操作！\n"); break; } fd=1; printf("譯碼成功,譯碼結(jié)果為：\n"); decoding(); break; case P: if(fi==0) { printf("請(qǐng)先初始化操作！\n"); break; } if(fe==0) { printf("請(qǐng)先進(jìn)行編碼操作！\n"); break; } print(); printf("編碼結(jié)果已保存在文件“CodePrin.txt”中\(zhòng)n"); break; default: printf("輸入有誤，請(qǐng)重新輸入\n"); } } return 0; }