數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：哈夫曼樹(shù)應(yīng)用 專(zhuān) 業(yè) ： 軟件工程 班 級(jí) ： 軟件 學(xué) 生 ： 學(xué) 號(hào) ： 指導(dǎo)教師 ： 羅作民 / 張翔 起止時(shí)間 ：2011-07-042011-07-08 2011 年 春季 學(xué)期目 錄一具體任務(wù).2 1功能.2 2分步實(shí)施.2. 3要求.2二哈夫曼編碼21問(wèn)題描述22.基本要求33實(shí)現(xiàn)提示3三設(shè)計(jì)流程圖4 1建立哈夫曼樹(shù).4 2編碼.5 3譯碼.6 4主程序.7四設(shè)計(jì)概要81問(wèn)題哈夫曼的定義.8.2所實(shí)現(xiàn)的功能函數(shù)如下.83功能模塊.8五源程序9六調(diào)試分析15七心得與體會(huì)18八參考文獻(xiàn)18一、任務(wù)題目：哈夫曼樹(shù)應(yīng)用1.功能： 1從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹(shù)以直觀(guān)的方式（比如樹(shù)）顯示在終端上；2利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件htmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrint中。3利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。2.分步實(shí)施：1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對(duì)話(huà)的界面，確定函數(shù)個(gè)數(shù)；2） 完成最低要求：完成功能1；3） 進(jìn)一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。3.要求：1）界面友好，函數(shù)功能要?jiǎng)澐趾?）總體設(shè)計(jì)應(yīng)畫(huà)一流程圖3）程序要加必要的注釋4） 要提供程序測(cè)試方案5） 程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來(lái)，不能運(yùn)行的程序是沒(méi)有價(jià)值的。二、哈夫曼編碼1. 問(wèn)題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫(xiě)一個(gè)赫夫曼碼的編/譯碼系統(tǒng)。2. 基本要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件hfmTree中。(2) E：編碼（Encoding）。利用已建好的赫夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。3. 實(shí)現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。(2) 用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶(hù)鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶(hù)選擇了“Q”為止。(3) 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I， D或C命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。三、設(shè)計(jì)流程圖建立哈夫曼樹(shù)：開(kāi)始n,<=1Renturn 0m=2*n-1i=1;i<=n;+iWhile(getchar()=”/n”輸入字符與權(quán)值HTi.ch=zHTi.weight=wHTi.parent=0HTi.lchild=0HTi.rchild=0編碼：開(kāi)始cdstart=”1”i=1;i<=n;+istart=n-1cdstart=”0”c=I;f=HTi.parent; f!=0;f=HTf.parentHTf.child=l結(jié)束譯碼：開(kāi)始L=k!output_file!cout”cant open file”Return 1Cout”cant open file”Strcmp(Hi.hlchild=0結(jié)束i=1;i<n;i+while(hk!=”0”)j=0;j<strlen(hi);j+;l+K=0hj=”0”輸出譯碼主程序：開(kāi)始main建立哈夫曼樹(shù)choice=”I”|choice=”I”結(jié)束編碼return 0choice=”E”|choice=”e”choice=”D”|choice=”d”choice=”Q”|choice=”q”編碼四、概要設(shè)計(jì)1）問(wèn)題哈夫曼的定義：1.哈夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義為：typedef struct /赫夫曼樹(shù)的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2）所實(shí)現(xiàn)的功能函數(shù)如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹(shù)，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹(shù)。此函數(shù)塊調(diào)用了Select（）函數(shù)。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)3、 int main()主函數(shù)： 利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒(méi)有要編碼的字符，則鍵盤(pán)讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。4、Encoding 編碼功能：對(duì)輸入字符進(jìn)行編碼5、Decoding譯碼功能： 利用已建好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。Print() 打印功能函數(shù)：輸出哈夫曼樹(shù)，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。6.主函數(shù)的簡(jiǎn)要說(shuō)明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語(yǔ)句，讓用戶(hù)挑選所實(shí)現(xiàn)的功能。使用鏈樹(shù)存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來(lái)實(shí)現(xiàn)功能。3）功能模塊：哈夫曼編碼/譯碼器初始化哈夫曼樹(shù)編碼譯碼打印哈夫曼樹(shù)打印編碼五、源程序#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct /哈夫曼樹(shù)的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i; /選出最小的節(jié)點(diǎn)for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&HTi.parent=0&&x!=i)y=i; /選出次小的節(jié)點(diǎn)if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建哈夫曼樹(shù)HT，并求出n個(gè)字符的哈夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i<=n;+i) /初始化n個(gè)葉子結(jié)點(diǎn)printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i);scanf("%c%d",&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i) /建立哈夫曼樹(shù)Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i<=n;+i) /給n個(gè)字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n"cout<<" "<<"軟件092班"<<" "<<"姓名:張耀飛"<<" "<<"學(xué)號(hào)：3090921040n" ;while(choice!=Q&&choice!=q) /當(dāng)choice的值不為q且不為Q時(shí)循環(huán)cout<<" "<<"*哈夫曼編碼/譯碼器*n" cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exitn" cout<<"請(qǐng)輸入您要操作的步驟："cin>>choice; if(choice=I|choice=i) /初始化赫夫曼樹(shù)cout<<"請(qǐng)輸入字符個(gè)數(shù)："cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"cant open file!"<<endl;return 1;for(i=1;i<=n;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();cout<<"哈夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl; else if(choice=E|choice=e) /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf("請(qǐng)輸入字符：");gets(str);output_file.open("ToBeTree.txt");if(!output_file)cout<<"cant open file!"<<endl;return 1;output_file<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file)cout<<"cant open file!"<<endl;return 1;for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n"input_file.open("CodeFile.txt"); /從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)cout<<"cant open file!"<<endl;return 1;input_file>>code;cout<<"編碼碼值為："<<code<<endl;input_file.close(); else if(choice=D|choice=d) /讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入Textfile.txt中input_file.open("CodeFile.txt");if(!input_file)cout<<"cant open file!"<<endl;return 1;input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file)cout<<"cant open file!"<<endl;return 1;k=0;while(hk!=0) /先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("Textfile.txt");if(!input_file)cout<<"cant open file!"<<endl;return 1;input_file>>h; cout<<h<<endl;input_file.close();cout<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！"<<endl; else if(choice=Q|choice=q) /退出程序 exit(0); else /如果選了選項(xiàng)之外的就讓用戶(hù)重新選擇cout<<"您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！"<<endl;cout<<endl;return 0;六、調(diào)試分析編碼譯碼退出七、實(shí)驗(yàn)心得與體會(huì) 在我自己課程設(shè)計(jì)中，就在編寫(xiě)好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過(guò)分析，我學(xué)到了：在定義頭文件時(shí)可多不可少，即我們可多寫(xiě)些頭文件，肯定不會(huì)出錯(cuò)，但是若沒(méi)有定義所引用的相關(guān)頭文件，必定調(diào)試不通過(guò)；在執(zhí)行譯碼操作時(shí)，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號(hào)連接起來(lái)，而是按順序直接放在一起，視覺(jué)效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒(méi)有像老師要求的那樣完成編一個(gè)文件的功能，這是我們?cè)O(shè)計(jì)的失敗之處。 通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫曼樹(shù)及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問(wèn)題就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題，只要按照以上的步驟，必定會(huì)順利地做出來(lái)。這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù)，對(duì)文件的操作也很生疏。在不斷分析后明確并改正了錯(cuò)誤和疏漏，我的程序有了更高的質(zhì)量。八參考文獻(xiàn)： 1 譚浩強(qiáng). C 程序設(shè)計(jì)(第二版) M . 北京:清華大學(xué)出版社,1999. 161 - 163.2 譚浩強(qiáng),張基溫,唐永炎. C 語(yǔ)言程序設(shè)計(jì)教程(第二版) M . 北京:高等教育出版社,1998. 113 - 115.3 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版) M . 北京:清華大學(xué)出版社,2002. 55 - 58.4 李士峰,張謝華,孫清滇. ActiveX文檔技術(shù)在VB 程序設(shè)計(jì)網(wǎng)絡(luò)課件制作中的應(yīng)用 5 王穎,王正洲. 漢諾塔問(wèn)題迭代算法實(shí)現(xiàn)和分析J . 合肥聯(lián)合大學(xué)學(xué)報(bào),1999 , 考核成績(jī)?cè)u(píng)定：簽字：年 月 日 19