實(shí)驗(yàn)報(bào)告2-二叉樹及哈夫曼編碼

1、掙衛(wèi)推遂薯實(shí)驗(yàn)報(bào)告（2013/2014學(xué)年第二學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)A實(shí)驗(yàn)名稱實(shí)驗(yàn)二二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)泌、的實(shí)現(xiàn)實(shí)驗(yàn)時(shí)間2014年4月8日指導(dǎo)單位計(jì)算機(jī)學(xué)院計(jì)算機(jī)軟件教學(xué)中心指導(dǎo)教師朱立華學(xué)生姓名高怡馨班級學(xué)號B12140113學(xué)院（系）教育科學(xué)與技專業(yè)教育技術(shù)學(xué)術(shù)學(xué)院實(shí)驗(yàn)名稱實(shí)驗(yàn)二二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實(shí)現(xiàn)指導(dǎo)教師朱立華實(shí)驗(yàn)類型設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2014.4.8一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握二叉鏈表上實(shí)現(xiàn)二叉樹基本去處的方法。（2）學(xué)會設(shè)計(jì)基于遍歷的求解二叉樹應(yīng)用問題的遞歸算法。（3）理解哈夫曼樹的構(gòu)造算法，學(xué)習(xí)設(shè)計(jì)哈夫曼編碼和譯碼系統(tǒng)。二、實(shí)驗(yàn)環(huán)境（實(shí)驗(yàn)

2、設(shè)備）硬件：微型計(jì)算機(jī)軟件：MicrosoftVisualC+6.0三、實(shí)驗(yàn)原理及內(nèi)容實(shí)驗(yàn)題一：在一叉鏈表上實(shí)現(xiàn)一叉樹運(yùn)算（1）設(shè)計(jì)遞歸算法，實(shí)現(xiàn)下列二叉樹運(yùn)算：刪除一棵二叉樹、求一棵二叉樹的高度、求一棵二叉樹中葉子結(jié)點(diǎn)數(shù)、復(fù)制一棵二叉樹、父換一棵二叉樹的左右子樹。（2）設(shè)計(jì)算法，按自上到下，從左到右的順序，按層次遍歷一棵二叉樹。（3）設(shè)計(jì)main函數(shù)，測試上述每個(gè)運(yùn)算。內(nèi)容：1、建立頭文件BTree.H,在該文件中定義二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并編寫二叉樹的各種基本操作實(shí)現(xiàn)函數(shù)。冋時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件Test.cpp，編譯并調(diào)試程序，直到正確運(yùn)行。注意：需要用到隊(duì)列的有關(guān)操作。實(shí)驗(yàn)

3、報(bào)告實(shí)驗(yàn)報(bào)告 inttempi;inttempr;if(!t)return0;templ=GetHeight(t-lChild);tempr=GetHeight(t-rChild);if(templ+tempr+)returntempi;elsereturntempr;Test.Cpp：#includeBTree.hintmain()BinaryTreevchara,b,x,y,z;y.MakeTree(E,a,b);z.MakeTree(F,a,b);MakeTree(C,y,z);y.MakeTree(D,a,b);z.MakeTree(B,y,x);coutvv前序遍歷vvendl;z.

4、PreOrder(Visit);coutvvendl;coutvv中序遍歷vvendl;z.InOrder(Visit);coutvvendl;coutvv后序遍歷vvendl;乙PostOrder(Visit);coutvvendl;coutvv層次遍歷vvendl;z.LevelOrder(Visit);coutvvendl;coutvv結(jié)點(diǎn)數(shù)量:；coutvvz.Size()vvendl;z.Exchange();coutvv左右交換后的前序遍歷vvendl;實(shí)驗(yàn)題二：哈夫曼編碼和譯碼系統(tǒng)(1)所設(shè)計(jì)的系統(tǒng)重復(fù)顯示以下菜單項(xiàng)：B建樹：讀入字符集和各字符頻度，建立哈夫曼樹。T遍歷：先序和中

5、序遍歷二叉樹。E生成編碼：根據(jù)已建成的哈夫曼樹，產(chǎn)生各字符的哈夫曼編碼。C編碼：輸入由字符集中字符組成的任意字符串，利用已生成的哈夫曼編碼進(jìn)行編碼，顯示編碼結(jié)果，并將輸入的字符串及其編碼結(jié)果分別保存在磁盤文件textfile.txt和codefile.txt中。D譯碼：讀入codefile.txt,利用已建成的哈夫曼樹進(jìn)行譯碼，并將譯碼結(jié)果存入磁盤文件result.txt中。P打印：屏幕顯示文件textfile.txt、codefile.txt和result.txt。X退出。源代碼#includeviostream#include#include#includevqueue#includeus

6、ingnamespacestd;int*weightArray;strings;string*codeArray;templatestructBTNodeTelement;BTNode*lChild,*rChild;BTNode()lChild=rChild=NULL;BTNode(constT&x)element=x;lChild=rChild=NULL;BTNode(constT&x,BTNode*l,BTNode*r)element=x;lChild=l;rChild=r;templatevclassTclassBinaryTreepublic:BinaryTree()root=NULL

7、;BinaryTree()boolisEmpty()constreturnroot=NULL;voidclear()postClear(root);boolretRoot(T&x)const;voidmakeTree(const&x,BinaryTreevT&left,BinaryTreevT&right);voidbreakTree(T&x,BinaryTreevT&left,BinaryTreevT&right);voidpreOrder()preOrder(root);voidinOrder()inOrder(root);voidpostOrder()postOrder(root);BT

8、NodevT*copy(BTNode*t);intsize()returnsize(root);voidchange。change(root);voidbreathFirst()breathFirst(root);intheight()returnheight(root);voidleaf()prePrint(root);protected:BTNodevT*root;private:voidclear(BTNodevT*t);voidchange(BTNodevT*t);voidpostClear(BTNodevT*t);voidprePrint(BTNodevT*t);intsize(BT

9、NodevT*t);intheight(BTNode*t);voidpreOrder(BTNodevT*t);voidinOrder(BTNodevT*t);voidpostOrder(BTNodevT*t);voidbreathFirst(BTNodevT*t);voidvisit(T&x)coutx;templateboolBinaryTreevT:retRoot(T&x)constif(root)x=root-element;returntrue;elsereturnfalse;templatevoidBinaryTreevT:makeTree(const&x,BinaryTreevT&

10、left,BinaryTreevT&right)if(rootII&left=&right)return;root=newBTNode(x,left.root,right.root);left.root=right.root=NULL;templatevoidBinaryTree:breakTree(T&x,BinaryTreevT&left,BinaryTreevT&right)if(!rootII&left=&rightIIleft.rootIIright.root)return;x=root-element;left.root=root-lChild;right.root=root-rC

11、hild;deleteroot;root=NULL;templatevclassTvoidBinaryTreevT:preOrder(BTNodevT*t)if(t)visit(t-element);preOrder(t-IChild);preOrder(t-rChild);templatevoidBinaryTreevT:inOrder(BTNodevT*t)if(t)inOrder(t-lChild);visit(t-element);inOrder(t-rChild);templatevoidBinaryTreevT:postOrder(BTNodevT*t)if(t)postOrder

12、(t-lChild);postOrder(t-rChild);visit(t-element);templatevoidBinaryTreevT:clear(BTNodevT*t)deletet;t=NULL;templatevoidBinaryTreevT:postClear(BTNodevT*t)if(t)postClear(t-lChild);postClear(t-rChild);deletet;templatevclassTBTNodevT*BinaryTreevT:copy(BTNodevT*t)if(!t)returnNULL;BTNodevT*q=newBTNode(t-ele

13、ment);q-IChild=copy(t-IChild);q-rChild=copy(t-rChild);returnq;templateintBinaryTreevT:size(BTNodevT*t)if(!t)return0;elsereturnsize(t-lChild)+size(t-rChild);templatevoidBinaryTree:change(BTNode*t)if(!t)return;BTNode*q=copy(t-rChild);clear(t-rChild);t-rChild=t-lChild;t-lChild=q;change(t-lChild);change

14、(t-rChild);templatevoidBinaryTreevT:breathFirst(BTNodevT*t)if(!t)return;queuevBTNodevT*ql;ql.push(t);BTNode*node;while(!q1.empty()node=q1.front();visit(node-element);q1.pop();if(node-lChild)q1.push(node-lChild);if(node-rChild)q1.push(node-rChild);templateintBinaryTree:height(BTNode*t)if(t=NULL)retur

15、n0;elseintm=height(t-lChild);intn=height(t-rChild);return(mn)?(m+1):(n+1);templatevclassTvoidBinaryTreevT:prePrint(BTNodevT*t)if(t)if(t-lChild=NULL)&(t-rChild=NULL)visit(t-element);return;prePrint(t-lChild);prePrint(t-rChild);templatevclassTclassPrioQueuepublic:PrioQueue(intmSize=20);PrioQueue()dele

16、teq;boolIsEmpty()constreturnn=0;boolIsFull()constreturnn=maxSize;voidAppend(constT&x);voidServe(T&x);private:voidAdjustDown(intr,intj);voidAdjustUp(intj);T*q;intn,maxSize;templatePrioQueue:PrioQueue(intmSize)maxSize=mSize;n=0;q=newTmaxSize;templatevclassTvoidPrioQueuevT:AdjustUp(intj)inti=j;Ttemp=qi

17、;while(i0&tempvq(i-l)qi=q(i-l)/2;i=(i-1)/2;qi=temp;templatevoidPrioQueuevT:Append(constT&x)if(IsFull()coutvvOverflow;return;qn+=x;AdjustUp(n-1);templatevoidPrioQueuevT:Serve(T&x)if(IsEmpty()coutvvUnderflow;return;x=q0;q0=q-n;AdjustDown(0,n-1);templatevclassTvoidPrioQueuevT:AdjustDown(intr,intj)intch

18、ild=2*r+1;Ttemp=qr;while(childv=j)if(childvj)&(qchildqchild+1)child+;if(tempv=qchild)break;q(child-1)/2=qchild;child=2*child+1;q(child-1)/2=temp;templatevclassTclassHfmTree:publicBinaryTreevTpublic:operatorT()constreturnweight;TgetW()returnweight;voidputW(constT&x)weight=x;voidSetNull()root=NULL;voi

19、dcode(string&c)code(root,c);voiddecode(strings);private:Tweight;voidcode(BTNode*t,string&c);templatevoidHfmTree:decode(stringdecodeString)if(codeArray=NULL)cout尚未編碼！endl;return;BTNode*searchNode=root;for(inti=0;idecodeString.length();i+)if(decodeStringi!=0&decodeStringi!=1)cout所給碼格式不正確！lChild=NULL&s

20、earchNode-rChild=NULL)Tvalue=searchNode-element;for(intj=0;js.length();j+)if(value=weightArrayj)coutlChild;if(decodeStringi=T)searchNode=searchNode-rChild;if(searchNode-lChild=NULL&searchNode-rChild=NULL)Tvalue=searchNode-element;for(intj=0;js.length();j+)if(value=weightArrayj)coutsj;break;coutendl;

21、templatevoidHfmTreevT:code(BTNodevT*t,string&c)if(t)if(t-lChild=NULL&t-rChild=NULL)for(inti=0;ielement=weightArrayi)codeArrayi=c;哈弗曼編碼是/coutNOi;哈弗曼編碼是cout字符vvsi的權(quán)重是”weightArrayi,lChild!=NULL)stringls;ls.assign(c);ls.append(O);code(t-lChild,ls);if(t-rChild!=NULL)stringrs;rs.assign(c);rs.append(l);cod

22、e(t-rChild,rs);templateHfmTreevTCreateHfmTree(T*w,intn)PrioQueuepq(n);/空優(yōu)先權(quán)隊(duì)列HfmTreevTx,y,z;/空哈夫曼樹for(inti=0;ivn;i+)構(gòu)造n棵只有一個(gè)結(jié)點(diǎn)的哈夫曼樹乙makeTree(wi,x,y);z.putW(wi);pq.Append(z);z.SetNull();for(i=1;i&p)couts;weightArray=newints.length();codeArray=newstrings.length();for(inti=0;is.length();i+)cout請輸入第(i+1

23、)個(gè)字符的權(quán)值：”weightArrayi;p=CreateHfmTree(weightArray,s.length();p.postOrder();voidcreateCode(HfmTreevint&p)if(codeArray=NULL)coutencodeString;coutvvn經(jīng)過編碼的碼值為：;for(inti=0;ivencodeString.length();i+)for(intj=0;jvs.length();j+)if(sj=encodeStringj)coutvvcodeArrayj;break;coutvvendl;voidmain()boolflag=true;H

24、fmTreevintp;stringdecodeString;while(flag)coutvvB建樹vv”T遍歷vv”E生成編碼vvendl;coutvvC編碼vv”D譯碼vv”X退出vvendl;coutvv請輸入指令：;charc;cinc;coutvvendl;switch(c)caseB:input(p);break;caseT:if(p!=NULL)cout前序遍歷：p.preOrder();coutendl;coutp.inOrder();coutendl;cout后序遍歷：;p.postOrder();coutendl;cout廣度優(yōu)先遍歷：;p.breathFirst();coutendl;elsecoutdecodeString;p.decode(decodeString);break;caseX: