數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告(赫夫曼編碼)(1) 2

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼學(xué) 院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 學(xué) 生： 學(xué) 號(hào)： 指導(dǎo)教師： 2013年4月16日 目錄1、 課程設(shè)計(jì)的目的、功能及要求-12、 主要功能模塊流程圖-23、 算法的基本思想-34、 系統(tǒng)測(cè)試-65、 結(jié)論-76、 源程序-8第 0 頁(yè) 共 21 頁(yè) 一、課程設(shè)計(jì)的目的、功能及要求目的：1. 解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力； 2. 件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能； 3. .合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力； 4. 用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟

2、件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。功能： 1首先讀入待壓縮源文件； 2然后建立并分析字母表，對(duì)每種字符的出現(xiàn)頻度進(jìn)行統(tǒng)計(jì)，以頻度作為建立Huffman 樹(shù)的權(quán)值； 3頻度表建好后，就可以根據(jù)算法建立Huffman 樹(shù)，對(duì)出現(xiàn)的每種字符進(jìn)行Huffman編碼； 4此時(shí)，再次讀入源文件，逐字節(jié)編碼，將得到的編碼流寫入到磁盤文件，并且計(jì)算壓縮率。要求：1、核心數(shù)據(jù)結(jié)構(gòu)用到的結(jié)構(gòu)體要采用動(dòng)態(tài)內(nèi)存分配和鏈表結(jié)構(gòu)。 2 、不同的功能使用不同的函數(shù)實(shí)現(xiàn)（模塊化），對(duì)每個(gè)函數(shù)的功能和調(diào)用接口要注釋清楚。對(duì)程序其它部分也進(jìn)行必要的注釋。 3 、對(duì)系統(tǒng)進(jìn)行功能模塊分析、畫出總流程圖和各模塊流程圖。 4 、用

3、戶界面要求使用方便、簡(jiǎn)潔明了、美觀大方、格式統(tǒng)一。 5 所有程序需調(diào)試通過(guò)。 二、主要功能模塊流程圖開(kāi)始編碼信息讀取文檔輸入并存入文檔計(jì)算壓縮率統(tǒng)計(jì)頻率生成哈夫曼編碼編碼文件譯碼信息結(jié)束譯碼文件 三、算法的基本思想（1）構(gòu)造Hufffman樹(shù)的方法Hufffman算法構(gòu)造Huffman樹(shù)步驟：I. 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj。II. 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和III. 在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中。IV. 重復(fù)上述兩步，直到只含一棵樹(shù)

4、為止，這棵樹(shù)即哈夫曼樹(shù)。（2）Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹(shù)，然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列。流程圖：開(kāi)始讀入各字符的權(quán)重尋找權(quán)值最小的字符將兩個(gè)字符分別作為左右孩子節(jié)點(diǎn)建立Huffman樹(shù)計(jì)算從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑得出編碼輸出Huffman編碼結(jié)束部分程序：（1） 構(gòu)造哈夫曼樹(shù)void HaffmanTree(HNodeType HuffNodeMAXNODE) int i,j,m1,m2,x1,

5、x2;for(i=0;i<MAXNODE;i+)HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;for(i=0;i<num-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<num+i;j+)if(HuffNodej.parent=-1&&HuffNodej.weight<m1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(HuffNodej.parent=-1&&HuffNodej.weight&l

6、t;m2)m2=HuffNodej.weight;x2=j;HuffNodex1.parent=num+i;HuffNodex2.parent=num+i;HuffNodenum+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNodenum+i.lchild=x1;HuffNodenum+i.rchild=x2;（2）哈夫曼編碼LinkList Bianma(LinkList l,Code codeMAXNODE) /寫編碼文件LinkList p,q,p1,p2;int i,j;p=l->next ;q=new LNode;q->

7、;next=NULL;p1=new LNode;p2=q;while(p)for(i=0;i<num;i+)if(p->data=codei.data) j=0;while(codei.bitj!='0')p1->data=codei.bitj;j+;p2->next=p1;p2=p1;p1=new LNode;p=p->next ;p2->next=NULL;return q;SeqStack Init()SeqStack s;s=new StackNode;s->top=-1;return s;void HaffmanCode(HN

8、odeType HuffNodeMAXNODE,HCodeType HuffCodeMAXLEAF) /哈夫曼編碼算法int i,j,c,p;HCodeType cd;for(i=0;i<num;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent ;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start='0'elsecd.bitcd.start='1'cd.start -;c=p;p=HuffNodec.parent;for(j=cd.start+1;j<MAXBIT;j

9、+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start ;四、系統(tǒng)測(cè)試1、主界面2、輸入并保存編碼 五、結(jié)論 本次課程設(shè)計(jì)的目的是：把一個(gè)隨機(jī)輸入的字符串中不同字符作為葉子結(jié)點(diǎn)元素，把其在該字符串中出現(xiàn)的次數(shù)作為權(quán)值構(gòu)造一個(gè)赫夫曼樹(shù)，并得到各個(gè)葉子結(jié)點(diǎn)的赫夫曼編碼和整個(gè)輸入的字符串的赫夫曼編碼。在寫代碼前，首先，對(duì)問(wèn)題進(jìn)行了分析，明確了目標(biāo)，列出了大的框架，然后逐漸細(xì)化，劃分出不同的功能模塊，由具體的子函數(shù)去實(shí)現(xiàn)，先在紙上編寫代碼，寫好后進(jìn)行了反復(fù)的邏輯推理，發(fā)現(xiàn)并解決邏輯問(wèn)題，然后，上機(jī)調(diào)試，方法是：一個(gè)一個(gè)功能模塊分開(kāi)進(jìn)行調(diào)試，主要看調(diào)試的模塊能

10、否達(dá)到預(yù)期的結(jié)果，這樣可以縮小排錯(cuò)的范圍，便以糾錯(cuò)和提高編程的效率，當(dāng)每個(gè)功能模塊都調(diào)試好后，就把各個(gè)部分組合起來(lái)，再進(jìn)行調(diào)試，主要檢查各函數(shù)接口是否正確，當(dāng)達(dá)到預(yù)期的結(jié)果，調(diào)試結(jié)束，編程部分完成，然后按實(shí)驗(yàn)要求完成實(shí)驗(yàn)報(bào)告。由于寫代碼前做了充分的準(zhǔn)備工作，所以寫起代碼來(lái)比較順利，使編程的效率有不少的提高并且最終達(dá)到實(shí)驗(yàn)預(yù)期的結(jié)果。心得體會(huì)：每一次的課程設(shè)計(jì)對(duì)我來(lái)說(shuō)都是一個(gè)不小的提高，哲學(xué)上說(shuō)：“實(shí)踐是檢驗(yàn)真理正確性的唯一標(biāo)準(zhǔn)”，尤其是學(xué)編程，自己不動(dòng)手操作，只看書永遠(yuǎn)都編不出像Windows之類的東西，正如老師說(shuō)的那樣，課程設(shè)計(jì)非常鍛煉人，每完成一個(gè)項(xiàng)目，不僅是知識(shí)體系的完善和知識(shí)的驗(yàn)證，更

11、是編程技術(shù)的提升，當(dāng)自己編的多了，就會(huì)開(kāi)始摸索編程的捷徑，想著用更高效的方法去完成一個(gè)個(gè)項(xiàng)目，就這樣在一次次的鍛煉中自己會(huì)從一個(gè)菜鳥(niǎo)迅速的成長(zhǎng)，終將成為一個(gè)優(yōu)秀的軟件工程師。一個(gè)成功的項(xiàng)目必須在寫代碼前，先要對(duì)課題有充分的思考和規(guī)劃，否則即使完成了項(xiàng)目也會(huì)浪費(fèi)很多的時(shí)間和精力，我認(rèn)為科學(xué)合理的編程方法是我這次課程設(shè)計(jì)的最大收獲。六、源程序#include<iostream>#include<fstream>#include"heads.h"#define NULL 0#define MAXVALUE 10000 /最大權(quán)值#define MAXLEA

12、F 100 /葉子結(jié)點(diǎn)個(gè)數(shù)#define MAXNODE MAXLEAF*2-1 /哈夫曼樹(shù)結(jié)點(diǎn)個(gè)數(shù)#define MAXBIT 12 /最大長(zhǎng)度using namespace std;int num;int power(int x)/2的x次方int i;for(i=1;i<=x;i+)i*=2;return i;float pration(int a,int b)/計(jì)算壓縮率,a為壓縮前字長(zhǎng)，b為壓縮后字長(zhǎng)float s;s=(float)(float)b/(float)a);return s;void Show(LinkList l) /輸出LinkList p=l->nex

13、t;while(p)cout<<p->data ;p=p->next;cout<<endl;LinkList Create() /寫入字符串 int total=0;int x=1,y;int p=0;LinkList l,p1,p2;l=new LNode;l->next=NULL;cout<<"請(qǐng)輸入:"<<endl<<endl;cout<<"1.輸入并存入文檔n2.從文檔讀取,并計(jì)算出壓縮率!"<<endl<<endl;cout<

14、<"請(qǐng)輸入要進(jìn)行的操作:"<<endl;int choose;cin>>choose;if(choose!=1&&choose!=2)cout<<"輸入錯(cuò)誤,請(qǐng)重新輸入!"<<endl;cin>>choose; if(choose=1)ofstream outfile;outfile.open("code.txt",ios:out);if(!outfile)cout<<"輸出時(shí)打開(kāi)code文檔出錯(cuò)!"<<end

15、l;exit(1);cout<<"請(qǐng)輸入所要編譯的字符串,以#結(jié)束:"<<endl; p1=new LNode; p2=l; cin>>p1->data;outfile<<p1->data; while(p1->data!='#') p2->next=p1; p2=p1; p1=new LNode; cin>>p1->data;outfile<<p1->data; p2->next=NULL; p2=l; return l; else ifstr

16、eam infile("wenjian.txt",ios:in);if(!infile)cout<<"輸出時(shí)打開(kāi)文檔出錯(cuò)!n或文檔不存在!"<<endl;cout<<"請(qǐng)確認(rèn)本目錄下有相關(guān)文件后再重試!"<<endl;exit(1);l=Read("wenjian.txt");p1=new LNode; p2=l; infile>>p1->data; while(infile.eof() p2->next=p1; p2=p1; p1=new L

17、Node; infile>>p1->data;p1->data='#'p1->next=NULL;infile.close();printf("讀取完成！n");Show(l);/*以下計(jì)算壓縮率*/p2=l;while(p2)total+;p2=p2->next;for(;power(x)<total;)x+;p=x; /記錄正常編碼一個(gè)字符需要的比特位數(shù)y=(total-1)*x;/正常所需的總比特?cái)?shù)printf("y is %dn",y);/*編碼后的位數(shù)計(jì)算*/int c; FILE *f

18、p; if(fp=fopen("Code.txt","rb")=NULL) printf("文件打開(kāi)失??！n"); exit(0); while(!feof(fp)c=fgetc(fp);x=x+1;printf("x is %d",x);/*計(jì)算完成*/printf("壓縮率為%4.2f%",pration(y,x)*100);return l; void Write(LinkList l,char wenjian)LinkList p1;ofstream outfile(wenjian,io

19、s:out);p1=l->next ;while(p1)outfile<<p1->data;p1=p1->next;outfile<<"#"outfile.close();LinkList Read(char wenjian) /讀文件中字符串LinkList l,p1,p2;l=new LNode;l->next=NULL;p1=new LNode;p2=l;ifstream infile(wenjian,ios:in);if(!infile)cout<<"打開(kāi)文檔出錯(cuò)!n或文檔不存在!"&l

20、t;<endl;cout<<"請(qǐng)確認(rèn)本目錄下有相關(guān)文件后再重試!"<<endl;exit(1);infile>>p1->data;while(p1->data!='#')p2->next=p1;p2=p1;p1=new LNode;infile>>p1->data;p2->next=NULL;infile.close();return l;void Create(HNodeType aMAXNODE,LinkList l) /統(tǒng)計(jì)字符個(gè)數(shù),做出哈夫曼樹(shù)的結(jié)點(diǎn) LinkList

21、 p;int i;p=l->next ; /全局變量num在這里的作用while(p)for(i=0;i<num;i+)if(ai.data=p->data)ai.weight+;break; if(i=num)ai.data=p->data;ai.weight=1;num+;p=p->next;/printf("num is %d ",num);可以看到num在這里的作用for(i=0;i<num;i+)ai.lchild=NULL;ai.rchild=NULL;ai.parent=-1;void HaffmanTree(HNodeTy

22、pe HuffNodeMAXNODE) /構(gòu)造哈夫曼樹(shù)int i,j,m1,m2,x1,x2;for(i=0;i<MAXNODE;i+)HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;for(i=0;i<num-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<num+i;j+)if(HuffNodej.parent=-1&&HuffNodej.weight<m1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(Huf

23、fNodej.parent=-1&&HuffNodej.weight<m2)m2=HuffNodej.weight;x2=j;HuffNodex1.parent=num+i;HuffNodex2.parent=num+i;HuffNodenum+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNodenum+i.lchild=x1;HuffNodenum+i.rchild=x2;/哈夫曼編碼LinkList Bianma(LinkList l,Code codeMAXNODE) /寫編碼文件LinkList p,q,p1,

24、p2;int i,j;p=l->next ;q=new LNode;q->next=NULL;p1=new LNode;p2=q;while(p)for(i=0;i<num;i+)if(p->data=codei.data) j=0;while(codei.bitj!='0')p1->data=codei.bitj;j+;p2->next=p1;p2=p1;p1=new LNode;p=p->next ;p2->next=NULL;return q;SeqStack Init()SeqStack s;s=new StackNode

25、;s->top=-1;return s;void HaffmanCode(HNodeType HuffNodeMAXNODE,HCodeType HuffCodeMAXLEAF) /哈夫曼編碼算法int i,j,c,p;HCodeType cd;for(i=0;i<num;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent ;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start='0'elsecd.bitcd.start='1'cd.start -;c=p;p=HuffN

26、odec.parent;for(j=cd.start+1;j<MAXBIT;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start ;void bianma(HCodeType HuffCodeMAXLEAF,HNodeType aMAXNODE,Code codeMAXNODE) /字符編碼int i,j,k;for(i=0;i<num;i+) codei.data=ai.data;for(j=HuffCodei.start+1,k=0;j<MAXBIT;j+,k+)codei.bitk=HuffCodei.bitj;codei

27、.bitk='0'int panduan(char aMAXBIT,char bMAXBIT)if(strcmp(a,b)=0)return 1;elsereturn 0;void bianma(Code codeMAXNODE,LinkList l)/讀取編碼int i,flag;SeqStack s;s=Init();LinkList p;p=l->next;while(p)s->top+;flag=0;s->datas->top=p->data;s->datas->top+1='0'for(i=0;i<num

28、;i+)if(panduan(s->data,codei.bit)=1) cout<<codei.data;flag=1;break;if(flag)s=Init();p=p->next;cout<<endl;void ShowTree(HNodeType nodeMAXNODE)printf("輸出");int i;cout.width(8);cout.setf(ios:left);cout<<"統(tǒng)計(jì)字符頻率結(jié)果為:"<<endl;cout<<"頻率 "cout

29、.width(8);cout<<"字符"<<endl;for(i=0;i<num;i+)cout.width(8);cout<<nodei.weight;cout.width(8);cout<<nodei.data<<endl;cout<<endl;cout<<"哈弗曼樹(shù)編碼為:"<<endl;cout<<"字符"cout<<" "cout<<"編碼"cout

30、<<endl;void ShowCode(Code coodMAXNODE)for(int i=0;i<num;i+)cout<<coodi.data<<"t"<<coodi.bit<<endl;void bianma(HNodeType nodeMAXNODE,HCodeType codeMAXLEAF,Code CODEMAXNODE)LinkList l,c;l=Create(); /寫字符串Write(l,"wenjian.txt");l=Read("wenjian.txt");cout<<"文件內(nèi)容:"&l