數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告學(xué)號(hào)：20091002527姓名：金學(xué)玉班級(jí)：116092—10【實(shí)習(xí)一】線性表及其應(yīng)用【問題描述】大數(shù)運(yùn)算——計(jì)算n的階乘（n>=20）?！净疽蟆浚?）數(shù)據(jù)的表示和存儲(chǔ)；（1.1）累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果的數(shù)據(jù)類型要求是整型——這是問題本身的要求；（1.2）試設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)，要求每個(gè)元素或節(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值。（2）數(shù)據(jù)的操作及其實(shí)現(xiàn)：基于設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)乘法操作，要求從鍵盤上輸入n值，在屏幕上顯示最終計(jì)算結(jié)果?！緶y(cè)試數(shù)據(jù)】（1）n＝20，n?。?432902008176640000（2）n＝30，n?。?65252859812191058636308480000000算法思想：首先設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，本題只能采用整型表示累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果，故設(shè)計(jì)一個(gè)動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)。對(duì)數(shù)據(jù)的操作及其實(shí)現(xiàn)，該題中兩個(gè)乘數(shù)的運(yùn)算要考慮到：乘數(shù)的各位數(shù)都要與被乘數(shù)進(jìn)行乘法運(yùn)算，乘法過程中的進(jìn)位問題及其實(shí)現(xiàn)，因每個(gè)元素或節(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值，故當(dāng)元素或節(jié)點(diǎn)中的數(shù)值大于999，需向前一個(gè)元素或節(jié)點(diǎn)進(jìn)位。綜上所述：本題可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)——普通單鏈表，其長(zhǎng)度可以擴(kuò)充，每一個(gè)數(shù)據(jù)元素占用一個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)由兩個(gè)域組成，一個(gè)域存放數(shù)據(jù)元素，其數(shù)據(jù)類型由問題決定，本體數(shù)據(jù)類型為實(shí)型，一個(gè)域存放指向該鏈表中下一個(gè)結(jié)點(diǎn)的指針，給出下一個(gè)結(jié)點(diǎn)的開始存儲(chǔ)地址。需要注意的是：每個(gè)節(jié)點(diǎn)存儲(chǔ)三位數(shù)據(jù)，進(jìn)行運(yùn)算時(shí)，從頭節(jié)點(diǎn)開始乘，所得數(shù)據(jù)暫存在節(jié)點(diǎn)data域中，如果它大于999，則向前進(jìn)位，進(jìn)位為data/1000，如果前位為空，則新建一個(gè)節(jié)點(diǎn)，新建節(jié)點(diǎn)的data為該data/1000，只要某一位有進(jìn)位，則從該點(diǎn)依次向檢查，如果因加了進(jìn)位后使自己data大于999，則繼續(xù)向前進(jìn)位，直到每位節(jié)點(diǎn)數(shù)據(jù)都小于999，輸出結(jié)果時(shí)：如果節(jié)點(diǎn)數(shù)據(jù)域的值不足三位，應(yīng)注意在前補(bǔ)0以補(bǔ)足三位。程序?qū)崿F(xiàn)代碼：#if!defined_CHAIN_#define_CHAIN_#include"stdafx.h"#include"xcept.h"http://循環(huán)鏈表模板template<classT>classChainNode{public: T data; ChainNode<T>* link; ChainNode<T>* back;};template<classT>classChain{public: Chain(); ~Chain(); bool IsEmpty()const { returnfirst->link==first; } int Length()const; bool Find(intk,T&x)const; int Search(constT&x)const; Chain<T>& Delete(intk,T&x); Chain<T>& Insert(intk,constT&x); ChainNode<T>* Iterator(intk); T* ExData(intk); Chain<T>& ChData(ChainNode<T>*p,constT&x); void Output();private: ChainNode<T>* first; //指向第一個(gè)節(jié)點(diǎn)的指針 int length;// ChainNode<T>* pCurSel;// int nCurSel;};template<classT>Chain<T>::Chain(){ first=newChainNode<T>; first->link=first; first->back=first; length=0;}template<classT>Chain<T>::~Chain(){ ChainNode<T>* p=first->link; ChainNode<T>* q; while(p!=first) { q=p; p=p->link; deleteq; } deletefirst;}template<classT>int Chain<T>::Length()const{ returnlength;}template<classT>bool Chain<T>::Find(intk,T&x)const{ if(k<1||k>length) returnfalse; x=Iterator(k)->data; returntrue;}template<classT>int Chain<T>::Search(constT&x)const{ ChainNode<T>* current=first->link; int index=1; first->data=x; while(current->data!=x) { current=current->link; index++; } return((current==first)?0:index);}template<classT>Chain<T>& Chain<T>::Delete(intk,T&x){ if(k<1||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k-1); ChainNode<T>* p; if(k==1) q=first; p=q->link; q->link=p->link; p->link->back=q; x=p->data; deletep; length--; return*this;}template<classT>Chain<T>& Chain<T>::Insert(intk,constT&x){ if(k<0||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k); ChainNode<T>* p; p=q->link; ChainNode<T>* y=newChainNode<T>; y->data=x;q->link=y; y->link=p;p->back=y; y->back=q; length++; return*this;}template<classT>ChainNode<T>* Chain<T>::Iterator(intk){ ChainNode<T>* current=first; if(k<=length/2) { for(inti=0;i<k;i++) current=current->link; } else { for(inti=0;i<length-k+1;i++) current=current->back; } returncurrent;}template<classT>T* Chain<T>::ExData(intk){ if(k<1||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k); return &(q->data);}template<classT>Chain<T>& Chain<T>::ChData(ChainNode<T>*q,constT&x){ q->data=x%10000; if(x>9999) { if(q->link==first) Insert(length,0); int m=q->link->data; m+=x/10000; ChData(q->link,m); } return*this;}template<classT>void Chain<T>::Output(){}template<classT>classChainIterator{public: T* Initialize(constChain<T>&c) { location=c.first->link; if(c.first) return&location->data; return0; } T* Next() { if(!c.first) return0; location=location->link; if(location!=first) return&location->data; return0; }private: ChainNode<T> *location;};#endif#if!defined_XCEPT_#define_XCEPT_#include"stdafx.h"classOutOfBounds{public: OutOfBounds() {}};#include"stdafx.h"#include"xcept.h" //異常處理頭文件#include"Chain.h" //循環(huán)鏈表頭文件#include"time.h"#include<iostream>usingnamespacestd;void Factorial(Chain<int>&A,intn);void Output(Chain<int>&A);int_tmain(intargc,_TCHAR*argv[]){ long t_Sta,t_End; Chain<int> A; int n; cout<<"階乘計(jì)算，請(qǐng)輸入n："; cin>>n; try { t_Sta=clock(); Factorial(A,n); t_End=clock(); cout<<"計(jì)算用時(shí)："<<double(t_End-t_Sta)/CLK_TCK<<"秒"<<endl; t_Sta=clock(); cout<<n<<"的階乘為："; Output(A); cout<<endl; t_End=clock(); cout<<"輸出用時(shí)："<<double(t_End-t_Sta)/CLK_TCK<<"秒"<<endl; } catch(...) { cerr<<"警告：越界，訪問了不存在的元素！"<<endl; } return0;}void Factorial(Chain<int>&A,intn){ int i,j,k; long m; ChainNode<int>* current; A.Insert(0,1); for(i=2;i<=n;i++) { k=A.Length(); current=A.Iterator(0); current=current->back; for(j=k;j>=1;j--) { m=*A.ExData(j); m=m*i; A.ChData(current,m); current=current->back; } }}void Output(Chain<int>&A){ int i,k,Num,m,l; k=A.Length(); for(i=k;i>0;i--) { l=*A.ExData(i); if(i==k) { cout<<l; continue; } m=l; Num=0; while(m) { m=m/10; Num++; } for(intj=0;j<4-Num;j++) cout<<'0'; if(l) cout<<l; }}程序運(yùn)行效果：【實(shí)習(xí)二】題目一：數(shù)組和矩陣1、擴(kuò)充Array1D類，重載操作符<<(輸入一個(gè)數(shù)組)、+、*=、/=和-=。并編寫程序?qū)崿F(xiàn)。2、設(shè)計(jì)一個(gè)三維數(shù)組類Array3D<T>。并編寫程序?qū)崿F(xiàn)。3、擴(kuò)充Matrix類，增加一個(gè)轉(zhuǎn)置矩陣的功能。并編寫程序?qū)崿F(xiàn)。4、請(qǐng)比較Matrix類和Array2D類的減法和乘法所需時(shí)間的性能。程序?qū)崿F(xiàn)代碼：#pragmaonce#include"xcept.h"template<classT>classArray1D{public: Array1D(intsz=0); Array1D(constArray1D<T>&v); ~Array1D(){delete[]element;} intSize(){returnsize;} T&operator[](inti)const; Array1D<T>&operator=(constArray1D<T>&v); Array1D<T>&ReSize(intsz);private: int size; //數(shù)組大小 T *element; //一維數(shù)組};template<classT>Array1D<T>::Array1D(intsz){ if(sz<0) throwBadInitializers(); size=sz; element=newT[sz];}template<classT>Array1D<T>::Array1D(constArray1D<T>&v){ size=v.size; element=newT[size]; for(inti=0;i<size;i++) element[i]=v.element[i];}template<classT>T&Array1D<T>::operator[](inti)const{ if(i<0||i>=size) throwOutOfBounds(); returnelement[i];}template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&v){ if(this!=&v) { size=v.size; delete[]element; element=newT[size]; for(inti=0;i<size;i++) element[i]=v.element[i]; } return*this;}template<classT>Array1D<T>&Array1D<T>::ReSize(intsz){ if(size!=sz) { size=sz; delete[]element; element=newT[size]; } return*this;}#pragmaonce#include"xcept.h"#include"Array1D.h"http://Array1Dtemplate<classT>classArray2D{public: Array2D(intr=0,intc=0); Array2D(constArray2D<T>&m); ~Array2D(){delete[]element;} int Rows()const{returnrows;} int Columns()const{returncols;} Array1D<T>&operator[](inti)const; Array2D<T>&operator=(constArray2D<T>&m); Array2D<T>&ReSize(intr,intc);private: int rows,cols; Array1D<T> *element;};template<classT>Array2D<T>::Array2D(intr,intc){ if(r<0||c<0) throwBadInitializers(); if((!r||!c)&&(r||c)) throwBadInitializers(); rows=r; cols=c; element=newArray1D<T>[r]; for(inti=0;i<r;i++) element[i].ReSize(c);}template<classT>Array2D<T>::Array2D(constArray2D<T>&m){ rows=m.rows; cols=m.cols; element=newArray1D<T>[rows]; for(inti=0;i<rows;i++) element[i]=m.element[i];}template<classT>Array1D<T>&Array2D<T>::operator[](inti)const{ if(i<0||i>rows) throwOutOfBounds(); returnelement[i];}template<classT>Array2D<T>&Array2D<T>::operator=(constArray2D<T>&m){ if(this!=&v) { rows=v.rows; cols=v.cols; delete[]element; element=newArray1D<T>[rows]; for(inti=0;i<rows;i++) element[i]=v.element[i]; } return*this;}template<classT>Array2D<T>&Array2D<T>::ReSize(intr,intc){ if(rows!=r||cols!=c) { rows=r; cols=c; delete[]element; element=newArray1D<T>[rows]; for(inti=0;i<r;i++) element[i].ReSize(c); } return*this;}#pragmaonce#include"Array2D.h"http://Array1Dtemplate<classT>classArray3D{public: Array3D(intr=0,intc=0,inth=0); Array3D(constArray2D<T>&m); ~Array3D(){delete[]element;} int Rows()const{returnrows;} int Columns()const{returncols;} intHight()const{returnhights;} Array2D<T>&operator[](inti)const; Array3D<T>&operator=(constArray2D<T>&m);private: int rows,cols,hights; Array2D<T> *element;};template<classT>Array3D<T>::Array3D(intr,intc,inth){ if(r<0||c<0||h<0) throwBadInitializers(); if((!r||!c||!h)&&(r||c||h)) throwBadInitializers(); rows=r; cols=c; hights=h; element=newArray2D<T>[h]; for(inti=0;i<h;i++) element[i].ReSize(r,c);}template<classT>Array3D<T>::Array3D(constArray2D<T>&m){ rows=m.rows; cols=m.cols; hights=m.hights; element=newArray2D<T>[hights]; for(inti=0;i<hights;i++) element[i]=m.element[i];}template<classT>Array2D<T>&Array3D<T>::operator[](inti)const{ if(i<0||i>hights) throwOutOfBounds(); returnelement[i];}template<classT>Array3D<T>&Array3D<T>::operator=(constArray2D<T>&m){ if(this!=&v) { rows=v.rows; cols=v.cols; hights=v.hights; delete[]element; element=newArray1D<T>[hights]; for(inti=0;i<hights;i++) element[i]=v.element[i]; } return*this;}#include"stdafx.h"#include"Array3D.h"#include<iostream>usingnamespacestd;int_tmain(intargc,_TCHAR*argv[]){ Array3D<int> A(8,8,8); intx,y,z; cout<<"***Array3D***"<<endl; try { A[2][3][4]=5; cout<<A[2][3][4]<<endl; } catch(...) { cout<<"Error!"<<endl; } return0;}運(yùn)行結(jié)果：【實(shí)習(xí)二】題目二：算術(shù)表達(dá)式求值【問題描述】對(duì)一個(gè)合法的中綴表達(dá)式求值。假設(shè)表達(dá)式只包含+、-、*、/四個(gè)雙目運(yùn)算符，并且允許有括號(hào)出現(xiàn)，運(yùn)算符本身不具有二義性。例如：3.5*(7+2)/(-6)【基本要求】正確解釋表達(dá)式；符合四則運(yùn)算規(guī)則：先乘除、后加減從左到右運(yùn)算先括號(hào)內(nèi)，后括號(hào)外輸出最后的計(jì)算結(jié)果算法思想：為實(shí)現(xiàn)算符優(yōu)先算法，該題目建立兩個(gè)工作站，一個(gè)為OPTR，另一個(gè)為OPND，用以寄存操作數(shù)和運(yùn)算結(jié)果。首先，置操作數(shù)棧為空，表達(dá)式起始符#為運(yùn)算符棧的棧底元素；其次，一次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符，則和和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。程序?qū)崿F(xiàn)代碼：#include<stdlib.h>#include<string.h>#defineDEBUG#defineNULL0#defineERROR-1#defineSTACKSIZE #include<stdio.h>#include<tchar.h>#include"stdafx.h"classOutOfBounds{public: OutOfBounds() { }};#endif#if!defined_LINKEDSTACK_#define_LINKEDSTACK_#include"xcept.h"template<classT>classNode{public: T data; Node<T> *link;};template<classT>classLinkedStack{public: //構(gòu)造與析構(gòu)函數(shù) LinkedStack() { top=0; } ~LinkedStack(); bool IsEmpty()const//如果堆棧為空，則返回true，否則返回false { returntop==0; } bool IsFull()const;//如果堆棧滿，則返回true，否則返回false T Top()const;//返回棧頂元素 LinkedStack<T>& Add(constT&x);//向堆棧中添加元素x LinkedStack<T>& Delete(T&x);//刪除棧頂元素，并將它的值傳遞給x LinkedStack<T>& Delete();//刪除棧頂元素private: Node<T> *top; //指向棧頂?shù)墓?jié)點(diǎn)};template<classT>LinkedStack<T>::~LinkedStack(){ Node<T> *next; while(top) { next=top->link; deletetop; top=next; }}template<classT>bool LinkedStack<T>::IsFull()const{}template<classT>T LinkedStack<T>::Top()const{ if(IsEmpty()) throwOutOfBounds(); returntop->data;}template<classT>LinkedStack<T>& LinkedStack<T>::Add(constT&x){ Node<T> *p=newNode<T>; p->data=x; p->link=top; top=p; return*this;}template<classT>LinkedStack<T>& LinkedStack<T>::Delete(T&x){ if(IsEmpty()) throwOutOfBounds(); x=top->data; Node<T> *p=top; top=top->link; deletep; return*this;}template<classT>LinkedStack<T>& LinkedStack<T>::Delete(){ if(IsEmpty()) throwOutOfBounds(); Node<T> *p=top; top=top->link; deletep; return*this;}#endif//Expression.cpp:定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#include"stdafx.h"#include"LinkedStack.h"#include<iostream>#include<string>usingnamespacestd;boolIsNumber(charch){ return(ch>='0'&&ch<='9')||ch=='.';//如果字符為數(shù)字，則返回true，否則返回false}boolIsOperator(charch)//如果字符為運(yùn)算符，則返回true，否則返回false{ switch(ch) { case'+': case'-': case'*': case'/': returntrue; default: returnfalse; }}boolLowerPriority(chara,charb)//如果a的優(yōu)先級(jí)低于b，則返回true，否則返回false{ if((a=='+'||a=='-')&&(b=='*'||b=='/')) returntrue; else returnfalse;}boolIsOpenparen(charch)//如果字符為'('，則返回true，否則返回false{ returnch=='(';}boolIsCloseparen(charch)//如果字符為')'，則返回true，否則返回false{ returnch==')';}boolTransformer(string&inExpr,string&outExpr)//中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法實(shí)現(xiàn){ string::size_type idx,size; LinkedStack<char> st; char ch; idx=0; size=inExpr.size(); while(idx<size) { ch=inExpr.at(idx); if(IsNumber(ch)) { outExpr+=ch; if(idx!=size-1) { if(!IsNumber(inExpr.at(idx+1))) outExpr+=''; } else outExpr+=''; } elseif(IsOperator(ch)) { while(!st.IsEmpty()&&!IsOpenparen(st.Top())&&!LowerPriority(st.Top(),ch)) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } st.Add(ch); } elseif(IsOpenparen(ch)) { st.Add(ch); } elseif(IsCloseparen(ch)) { if(st.IsEmpty()) { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } while(!st.IsEmpty()&&!IsOpenparen(st.Top())) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } if(IsOpenparen(st.Top())) { st.Delete(); } else { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } } idx++; } if(idx==size) { while(!st.IsEmpty()&&!IsOpenparen(st.Top())) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } if(!st.IsEmpty()) { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } } returntrue;}//后綴式四則計(jì)算算法實(shí)現(xiàn)doubleCalculate(string&outExpr){ LinkedStack<double> st; string::size_type idx,size; string NumBuff; char ch; double Num=0; idx=0; size=outExpr.size(); while(idx<size) { ch=outExpr.at(idx); if(IsNumber(ch)) { if(outExpr.at(idx+1)!='') { NumBuff+=ch; } else { NumBuff+=ch; Num=atof(NumBuff.c_str()); st.Add(Num); Num=0; NumBuff=""; } } if(IsOperator(ch)) { double Operand1,Operand2; if(!st.IsEmpty()) st.Delete(Operand1); else { cerr<<"ERROR!"; return0; } if(!st.IsEmpty()) st.Delete(Operand2); else { cerr<<"ERROR!"; return0; } switch(ch) { case'+': Operand1=Operand2+Operand1; break; case'-': Operand1=Operand2-Operand1; break; case'*': Operand1=Operand2*Operand1; break; case'/': Operand1=Operand2/Operand1; break; default: break; } st.Add(Operand1); } idx++; } returnst.Top();}int_tmain(intargc,_TCHAR*argv[]){ stringinExpr,outExpr; cout<<"請(qǐng)輸入表達(dá)式（操作數(shù)支持多位數(shù)整數(shù)）："; cin>>inExpr; if(Transformer(inExpr,outExpr)) { cout<<outExpr<<endl; } else { cerr<<"wrongexpression_r!"<<endl; } cout<<"表達(dá)式計(jì)算結(jié)果："; cout<<Calculate(outExpr)<<endl; return0;}程序運(yùn)行結(jié)果：運(yùn)行結(jié)果：【實(shí)習(xí)三】二叉樹及其應(yīng)用題目一：二叉樹基本算法的實(shí)現(xiàn)題目二：確定一棵二叉樹功能要求：實(shí)現(xiàn)Create方法，要求鍵盤輸入二叉樹結(jié)點(diǎn)序列，創(chuàng)建一棵二叉樹（提示：前序遞歸）實(shí)現(xiàn)SwapTree方法，以根結(jié)點(diǎn)為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子樹和右子樹（提示：前序遞歸）增加InorderTree方法，采用非遞歸方法實(shí)現(xiàn)二叉樹的中序遍歷，可以選擇：對(duì)BinaryTree模板進(jìn)行功能擴(kuò)充；自己定義并實(shí)現(xiàn)二叉樹類二叉樹的創(chuàng)建要求：要求鍵盤輸入二叉樹結(jié)點(diǎn)序列結(jié)點(diǎn)序列可以是前序，也可以是層次空結(jié)點(diǎn)以#表示程序?qū)崿F(xiàn)代碼：#ifndefNode_#defineNode_template<classT>classLinkedStack;template<classT>classLinkedQueue;template<classT>classNode{friendLinkedStack<T>;friendLinkedQueue<T>;private:Tdata;Node<T>*link;};#endif#ifndefStack_#defineStack_#include"xcept.h"template<classT>classStack{public:Stack(intMaxStackSize=30);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stack<T>&Add(constT&x);Stack<T>&Delete(T&x);private:inttop;//currenttopofstackintMaxTop;//maxvaluefortopT*stack;//elementarray};template<classT>Stack<T>::Stack(intMaxStackSize){MaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}template<classT>TStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();//Topfailsreturnstack[top];}template<classT>Stack<T>&Stack<T>::Add(constT&x){if(IsFull())throwNoMem();//addfailsstack[++top]=x;return*this;}template<classT>Stack<T>&Stack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();//deletefailsx=stack[top--];return*this;}#endif#ifndefxcept_#definexcept_#include<new.h>classBadInitializers{public: BadInitializers(){}};classNoMem{public: NoMem(){}};intmy_new_handler(size_tx){ throwNoMem(); return0;};_PNHOld_Handler_=_set_new_handler(my_new_handler);classOutOfBounds{public: OutOfBounds(){}};classSizeMismatch{public: SizeMismatch(){}};classMustBeZero{public: MustBeZero(){}};classBadInput{public: BadInput(){}};#endifclassBinaryTree;classBinaryTreeNode{ friendBinaryTree;public: BinaryTreeNode(){LeftChild=RightChild=0;} BinaryTreeNode(constint&e) { data=e; LeftChild=RightChild=0; } BinaryTreeNode(constint&e,BinaryTreeNode*l,BinaryTreeNode*r) { data=e; LeftChild=l; RightChild=r; }private: chardata; BinaryTreeNode*LeftChild,*RightChild;};#ifndeflqueue_#definelqueue_#include"Node.h"#include"xcept.h"template<classT>classLinkedQueue{LinkedQueue(){front=rear=0;}//constructor~LinkedQueue();//destructorboolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;//returnfirstelementTLast()const;//returnlastelementLinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);private:Node<T>*front;//pointertofirstnodeNode<T>*rear;//pointertolastnode};template<classT>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front->link;deletefront;front=next;}}template<classT>boolLinkedQueue<T>::IsFull()const{Node<T>*p;try{p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}template<classT>TLinkedQueue<T>::First()const{if(IsEmpty())throwOutOfBounds();returnfront->data;}template<classT>TLinkedQueue<T>::Last()const{if(IsEmpty())throwOutOfBounds();returnrear->data;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=0;if(front)rear->link=p;//queuenotemptyelsefront=p;//queueemptyrear=p;return*this;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=front->data;Node<T>*p=front;front=front->link;deletep;return*this;}#endif#ifndefBinaryTree_#defineBinaryTree_#include"BinaryTreeNode.h"#include"xcept.h"#include"lqueue.h"#include"Stack.h"int_count;#include<iostream>usingnamespacestd;classBinaryTree{public: BinaryTree(){root=0;} ~BinaryTree(){} boolIsEmpty()const {return((root==0)?false:true);} boolRoot(char&x)const; voidMakeTree(constchar&element,BinaryTree&left,BinaryTree&right); voidBreakTree(char&element,BinaryTree&left,BinaryTree&right); voidPreOrder(void(*Visit)(BinaryTreeNode*u)) {PreOrder(Visit,root);} voidInOrder(void(*Visit)(BinaryTreeNode*u)) {InOrder(Visit,root);} voidPostOrder(void(*Visit)(BinaryTreeNode*u)) {PostOrder(Visit,root);} voidLevelOrder(void(*Visit)(BinaryTreeNode*u)); voidPreOutput() { PreOrder(Output,root); cout<<endl; } voidInOutput() { InOrder(Output,root); cout<<endl; } voidPostOutput() { PostOrder(Output,root); cout<<endl; } voidLevelOutput() { LevelOrder(Output); cout<<endl; } voidDelete() { PostOrder(Free,root); root=0; }intHeight()const {returnHeight(root);} intSize() { _count=0; PreOrder(Add1,root); return_count; }voidCreat(chara[],BinaryTreeNode*&t,intn);//創(chuàng)建一個(gè)二叉樹 BinaryTree&Creat(chara[],intn);//函數(shù)調(diào)用，實(shí)現(xiàn)返回 voidSwapTree(BinaryTreeNode*&t);//交換二叉樹左右孩子 BinaryTree&SwapTree();//調(diào)用函數(shù)，實(shí)現(xiàn)返回 voidInOrder();//中序非遞歸輸出private: BinaryTreeNode*root;voidPreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t); voidInOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t); voidPostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);staticvoidOutput(BinaryTreeNode*t) {cout<<t->data<<'';} staticvoidFree(BinaryTreeNode*t) {deletet;} intHeight(BinaryTreeNode*t)const; staticvoidAdd1(BinaryTreeNode*t) {_count++;}};boolBinaryTree::Root(char&x)const{ if(root) { x=root->data; returntrue; } else returnfalse;}voidBinaryTree::MakeTree(constchar&element,BinaryTree&left,BinaryTree&right){ root=newBinaryTreeNode(element,left.root,right.root); left.root=right.root=0;}voidBinaryTree::BreakTree(char&element,BinaryTree&left,BinaryTree&right){ if(!root) throwBadInput(); element=root->data; left.root=root->LeftChild; right.root=root->RightChild; deleteroot; root=0;}voidBinaryTree::PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild); }}voidBinaryTree::InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { InOrder(Visit,t->LeftChild); Visit(t); InOrder(Visit,t->RightChild); }}voidBinaryTree::PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { PostOrder(Visit,t->LeftChild); PostOrder(Visit,t->RightChild); Visit(t); }}voidBinaryTree::LevelOrder(void(*Visit)(BinaryTreeNode*u)){ LinkedQueue<BinaryTreeNode*>Q; BinaryTreeNode*t; t=root; while(t) { Visit(t); if(t->LeftChild) Q.Add(t->LeftChild); if(t->RightChild) Q.Add(t->RightChild); try { Q.Delete(t); } catch(OutOfBounds) { return; } }}intBinaryTree::Height(BinaryTreeNode*t)const{ if(!t) return0; inthl=Height(t->LeftChild); inthr=Height(t->RightChild); if(hl>hr) return++hl; else return++hr;}//創(chuàng)建二叉樹inti=-1;//數(shù)組的下標(biāo) voidBinaryTree::Creat(chara[],BinaryTreeNode*&t,intn){ i++; if(i>n) return; if(a[i]=='#')//孩子節(jié)點(diǎn)不能為空 { t=NULL; return; } else { t=newBinaryTreeNode(a[i]); Creat(a,t->LeftChild,n); Creat(a,t->RightChild,n); }}BinaryTree&BinaryTree::Creat(chara[],intn){ this->Creat(a,root,n); return*this;}//交換二叉樹左右孩子voidBinaryTree::SwapTree(BinaryTreeNode*&t){ if(t) { BinaryTreeNode*temp=NULL; temp=t->LeftChild; t->LeftChild=t->RightChild; t->RightChild=temp; SwapTree(t->RightChild); SwapTree(t->LeftChild); }}BinaryTree&BinaryTree::SwapTree(){ this->SwapTree(root); return*this;}voidBinaryTree::InOrder(){ Stack<BinaryTreeNode*>s;//二叉樹指針型的棧 BinaryTreeNode*c; BinaryTreeNode*t=root; while(t) { s.Add(t); t=t->LeftChild; }s.Delete(c); while(c) { printf("%c",c->data); c=c->RightChild; if(c) { while(c) { s.Add(c); c=c->LeftChild; } } if(!c&&!s.IsEmpty()) s.Delete(c); }}#endif#include<iostream>#include"BinaryTree.h"usingnamespacestd;intcount=0;BinaryTreea,x,y,z;voidct(BinaryTreeNode*t){ count++;}BinaryTreeX;#definer100//輸入字符的最大長(zhǎng)度voidmain(){ intm; y.MakeTree('M',a,a); z.MakeTree('N',a,a); x.MakeTree('F',y,z); y.MakeTree('G',x,a); y.PreOrder(ct); printf("Thesizeis:%d\n",count); printf("逐層遍歷得："); y.LevelOutput(); printf("前序遍歷得："); y.PreOutput(); printf("中序遍歷得："); y.InOutput(); printf("后序遍歷得："); y.PostOutput(); m=y.Height(); printf("樹的高度為：%d\n",m); charc; intn=0; charar[r]; printf("請(qǐng)輸入二叉樹的前序序列，空結(jié)點(diǎn)以#表示"); while((c=getchar())!='\n')//得到屏幕能夠輸入的每個(gè)字符，賦值給一個(gè)數(shù)組 { ar[n]=c; n++; } X.Creat(ar,n);//創(chuàng)建一個(gè)二叉樹 X.PreOutput();//前序輸出這個(gè)二叉樹 X.SwapTree();//交換二叉樹左右孩子，并輸出 X.PreOutput();printf("輸出中序序列為："); X.InOutput(); printf("輸出非遞歸中序序列為："); X.InOrder();//實(shí)現(xiàn)中序序列 cout<<endl; system("pause");}運(yùn)行結(jié)果： 【實(shí)習(xí)四】?jī)?yōu)先隊(duì)列及BST一，優(yōu)先隊(duì)列基本要求：對(duì)Huffman樹的方法進(jìn)行擴(kuò)充，實(shí)現(xiàn)如下功能：1）鍵盤輸入一個(gè)字符串，統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率；2）輸出每個(gè)字符的Huffman編碼3）計(jì)算并輸出WPL提高要求：改鍵盤輸入為讀文件（任何類型）二，對(duì)BST樹的方法進(jìn)行擴(kuò)充，實(shí)現(xiàn)如下功能：1）給定一個(gè)節(jié)點(diǎn)，尋找并返回：以它為根的子樹中，關(guān)鍵值最大的一個(gè)節(jié)點(diǎn)；TreeMax2）給定一個(gè)節(jié)點(diǎn)，尋找并返回：以它為根的子樹中，關(guān)鍵值最小的一個(gè)節(jié)點(diǎn)；TreeMin3）尋找并返回：從小到大排序后下標(biāo)為i的節(jié)點(diǎn)，i從0開始；GetByIndex4）給定一個(gè)節(jié)點(diǎn)，尋找并返回：它在中序遍列中的下一個(gè)節(jié)點(diǎn)；TreeNext5）給定一個(gè)節(jié)點(diǎn)，尋找并返回：它在中序遍列中的前一個(gè)節(jié)點(diǎn)；TreePrev6）把樹中節(jié)點(diǎn)按照關(guān)鍵字由小到大的順序，放進(jìn)一個(gè)數(shù)組ToArray一，算法思想：程序?qū)崿F(xiàn)代碼：#defineWIN32_LEAN_AND_MEAN #include<stdio.h>#include<tchar.h>#pragmaonce#include"stdafx.h"classOutOfBounds{public: OutOfBounds(){}};#pragmaonceclassBaseChar{public: BaseChar(){BitCode=0;CodeLength=0;} void AddBitCode(constboolb);//向編碼尾加入一位，參數(shù)為true則加入一位1，反之//加入一位0 int DeleteBitCode();//返回編碼頭的一位，并刪除這一位 int GetBitCode(intn)const;//獲取允許范圍內(nèi)的一位編碼public: int BitCode; //Huffman編碼(二進(jìn)制) int CodeLength; //bit中編碼長(zhǎng)度 char AscIIchar; //對(duì)應(yīng)字符};classCharManager{public: CharManager(); ~CharManager(); void InsertChar(charch);//插入一個(gè)字符 //根據(jù)參數(shù)字符返回對(duì)應(yīng)的BaseChar對(duì)象 BaseChar& GetBaseChar(charch);public: BaseChar* Char_Array; int* Char_Weight; int CurrentSize;};#pragmaonce#include"CharManager.h"template<classT>classBinaryTree;template<classT>classBinaryTreeNode{ friendclassBinaryTree<T>; friendvoidGetHuffmanCode(CharManager&CM,BinaryTree<int>&tree);public: BinaryTreeNode() { LeftChild=RightChild=NULL; } BinaryTreeNode(constT&e) { data=e; LeftChild=RightChild=NULL; } BinaryTreeNode(constT&e,BinaryTreeNode*l,BinaryTreeNode*r) { data=e; LeftChild=l; RightChild=r; }private: T data; BinaryTreeNode<T> *LeftChild, //Leftsubtree *RightChild; //Rightsubtree};//DefinedBinaryTreetemplate<classT>classBinaryTree{ friendvoidGetHuffmanCode(CharManager&CM,BinaryTree<int>&tree);public: BinaryTree() { root=NULL; } BinaryTree(BinaryTree<T>&ref); ~BinaryTree(); BinaryTree<T>& operator=(BinaryTree<T>&tree); bool IsEmpty()const{return((root)?false:true);} bool Root(T&x)const; BinaryTreeNode<T>*GetpRoot(){returnroot;} bool Create(constchar*str); bool MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right); bool BreakTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right); void PreOrder(void(*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);} void InOrder(void(*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);} void PostOrder(void(*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}private: BinaryTreeNode<T> *root; //根節(jié)點(diǎn)指針 void PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); void InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); void PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); staticvoidDestructor(BinaryTreeNode<T>*t) { if(t!=NULL) { deletet; t=NULL; } }};template<classT>BinaryTree<T>::BinaryTree(BinaryTree<T>&ref){ root=ref.root; ref.root=NULL;}template<classT>BinaryTree<T>::~BinaryTree(){ PostOrder(Destructor,root); root=NULL;}template<classT>bool BinaryTree<T>::Root(T&x)const{ if(root) { x=root->data; returntrue; } else returnfalse;}template<classT>bool BinaryTree<T>::Create(constchar*str){ if(!rool) { root=newnewBinaryTreeNode<T>(element); returntrue; } else returnfalse;}template<classT>bool BinaryTree<T>::MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){ root=newBinaryTreeNode<T>(element,left.root,right.root); left.root=right.root=NULL; returntrue;}template<classT>bool BinaryTree<T>::BreakTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){ if(!root) returnfalse; element=root->data; left.root=