數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

《空間數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》課程實(shí)習(xí)報(bào)告（測繪10級(jí)）姓名班級(jí)學(xué)號(hào)環(huán)境與測繪學(xué)院1C++面向?qū)ο蟪绦蛟O(shè)計(jì)基礎(chǔ)【實(shí)驗(yàn)簡介】學(xué)會(huì)用算法語言C++描述抽象數(shù)據(jù)類型，使用模板建立數(shù)據(jù)結(jié)構(gòu)。理解數(shù)據(jù)結(jié)構(gòu)的組成分為兩部分，第一部分是數(shù)據(jù)集（數(shù)據(jù)元素），第二部分是在此數(shù)據(jù)集上的操作。從面向?qū)ο蟮挠^點(diǎn)看，這兩部分代表了對(duì)象的屬性和方法。掌握用C++描述數(shù)據(jù)結(jié)構(gòu)的基本方法，即通過建立類來描述抽象數(shù)據(jù)類型。類的數(shù)據(jù)成員提供對(duì)象屬性，成員函數(shù)提供操作方法，方法是公共接口，用戶通過調(diào)用方法實(shí)現(xiàn)對(duì)屬性的訪問?！緦?shí)驗(yàn)內(nèi)容】定義三維空間的坐標(biāo)點(diǎn)TPoint描述三維空間的球TBall，實(shí)現(xiàn)其主要操作(如計(jì)算體積和表面積，輸出空間坐標(biāo)等)?！局饕a】#include<iostream>usingnamespacestd;doubleconstPI=3.14;template<classT>classTPoint{protected:Tx,y,z;public:TPoint(){x=0;y=0;z=0;}TPoint(Ta,Tb,Tc){x=a;y=b;z=c;}};template<classT>classTBall:publicTPoint<T>{private:Tr;public:TBall(){r=0;}TBall(Ta,Tb,Tc,Td){x=a;y=b;z=c;r=d;}voidoutput_S();voidoutput_V();voidoutput_P();};template<classT>voidTBall<T>::output_P(){coutvv"球心的坐標(biāo)〃vvxvv""vvyvv""<<z<<endl;}template<classT>voidTBall<T>::output_S(){coutvv"球的表面積"<<4*Pl*r*rvvendl;}templatevclassT>voidTBallvT>::output_V(){coutvv〃球的體積為"vvPl*r*r*r*4/3vvendl;}voidmain(){inta,b,c,d;coutvv"請(qǐng)輸入球心坐標(biāo)"vv"x=";cin>>a;」〃〃coutvvy-;cin>>b;」〃〃coutvvz-;cin>>c;coutvv〃請(qǐng)輸入半徑〃vv〃r-〃；cin>>d;TBallvint>ball(a,b,c,d);ball.output_S();ball.output_V();ball.output_P();}【實(shí)驗(yàn)過程】⑴首先定義一個(gè)點(diǎn)的類作為一個(gè)基類，在定義個(gè)球的類，并且公共繼承點(diǎn)類⑵將球的類的公共函數(shù)作為一個(gè)調(diào)用類的私有成員的接口⑶具體公共函數(shù)的實(shí)現(xiàn)在類的外面。⑷使用公共模版類請(qǐng)輸人球心坐標(biāo)〃1g請(qǐng)魏入半徑尸2琲的表面積50.24球的休積為33.4933抹心’坐標(biāo)］11Pressanykeytocontinue【實(shí)驗(yàn)體會(huì)】通過這次實(shí)驗(yàn)我掌握了點(diǎn)的類定義、空間中一個(gè)球體的定義和從點(diǎn)到球體公有繼承的方法以及輸入輸出的方法！實(shí)驗(yàn)里首先定義一個(gè)PI，接著在實(shí)驗(yàn)中就能很好的簡化實(shí)驗(yàn)操作步驟和代碼量！2鏈表的建立、合并與拆分【實(shí)驗(yàn)簡介】鏈表是用鏈接存儲(chǔ)的方式來表達(dá)線性表，它用指針表示結(jié)點(diǎn)間的邏輯關(guān)系，鏈表適用于插入或刪除頻繁，存儲(chǔ)空間需求不定的情形。【實(shí)驗(yàn)內(nèi)容】定義一個(gè)鏈表存儲(chǔ)的線性表，除已給出的表元素插入、刪除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在應(yīng)用程序中建立兩個(gè)整型的單鏈表對(duì)象 A和B，應(yīng)用線性表的基本操作對(duì)表的實(shí)例對(duì)象進(jìn)行操作測試。設(shè)線性鏈表A=(a1,a2,…，am),B=(b1,b2,???bm)按下列規(guī)則合并A,B為線性表C的算法，即使得C=(a1,b1,…，am,bm,b(m+1),^,bn)當(dāng)m<=n或C=(a1,b1,…,an,bn,a(n+1), …，am當(dāng)m>nC表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。將C表原地逆置。將C表的中偶數(shù)和奇數(shù)分別鏈接為兩個(gè)循環(huán)鏈表說 D和E。明：每一次合并、拆分和逆置等操作的結(jié)果均要輸出?！局饕a】#include<iostream.h>tempiate<classT>structLinkNode{ //定義在"LinkedList.h"Tdata; 〃鏈表結(jié)點(diǎn)類的定義LinkNodevT>*link; //數(shù)據(jù)域LinkNode(LinkNodevT>*ptr=NULL){link=ptr;} //構(gòu)造函}；數(shù)LinkNode(constT&item,LinkNodevT>*ptr=NULL)

template<classT>classList{protected:LinkNode<//單鏈i表類定template<classT>classList{protected:LinkNode<//單鏈i表類定public: 義List(){first二newLinkNode<T>;}List(constT&X){first=List(List<T>&L);~List(){makeEmpty();}voidmakeEmpty();intLength()const;LinkNode<T>*getHead()constLinkNode<T>LinkNode<T>getData(intsetData(int*Search(TX);*Locate(inti);booli,T&X);voidi,T&X);boolInsert針//構(gòu)造函數(shù)newLinkNode<T>(X);}//復(fù)制構(gòu)造函數(shù)〃析構(gòu)函數(shù)〃將鏈表置為空表〃計(jì)算鏈表的長度{returnfirst;}//搜索含X元素〃定位第i個(gè)元素〃取出第i元素值〃更新第i元素值〃在第i元素后插入X//刪除第1個(gè)元素，X返回該元素值(inti,T&X);boolRemove(inti,T&X);booluniom(List<T>&A,List<T>&B,List<T>&C);表C,C利用A和B的存儲(chǔ)空間voidchangeover();〃將(inti,T&X);boolRemove(inti,T&X);booluniom(List<T>&A,List<T>&B,List<T>&C);表C,C利用A和B的存儲(chǔ)空間voidchangeover();〃將L鏈表原地逆轉(zhuǎn)boolIsEmpty()const 〃判表空否{returnfirst->link=二NULL?true:false;}voidSort(); 〃排序voidinput();voidoutput();List<T>&operator=(List<T>&L););voidmain(){List<int>A,B;}voidList<T>::classify(List<T>&C,List<T>&D,List<T>&E){D.makeEmpty();E.makeEmpty();LinkNode<T>〃置空D、E鏈表*current二C.first;LinkNode<T>*p=current->link；LinkNode<T>*pd=D.first;LinkNode<T>*pe=E.first;while(p!=null)循環(huán)鏈表D和E中 〃循環(huán)地分別連接C中的結(jié)點(diǎn)到

｝；current->link=p->link;if((p->data)%2==0){pd->link=p;pd=｝；current->link=p->link;if((p->data)%2==0){pd->link=p;pd=pd->link;

pd->link=D.first;}

else{pe->link=p;pe=pe->link;

pe->link=E.first;}

p=current->link;〃拿出p結(jié)點(diǎn)八、、//D鏈表存放偶數(shù)結(jié)點(diǎn)八、、//E鏈表存放奇數(shù)結(jié)點(diǎn)八、、//p結(jié)點(diǎn)后移一個(gè)template<classT>boolList<T>::changeover(){LinkNode<T>*aq,*pr;aq=first->link;first->link=null;while(aq!=null){aq=pr;pr=aq->link;aq->link=first;first=aq;aq=pr;//把C轉(zhuǎn)置);template<classT>boolList<T>::uniom(List<T>&A,List<T>&B);List<T>C=A;intm,n,min,i=1,min=(m<=n?m:n)m=A.length();n=B.length();LinkNode<T>*p=A.first;while(i<=min){LinkNode<T>*current=B.first;LinkNode<T>*aiq=current->link;current->link=aiq->link;//拿出aiq結(jié)點(diǎn)LinkNode<T>*pt=A.locate(i);aiq->link=pt->link;pt->link=aiq;〃把a(bǔ)iq結(jié)點(diǎn)插入到A的第i個(gè)結(jié)點(diǎn)后

i++；}i++；}調(diào)整if(m<=n){aiq->link=B.first->link；}if(C.length()=m+n)returntrue；elsereturnfalse；//A鏈表比B鏈表長的情況不用再//B鏈表比A鏈表長的情況；template<classT>voidList<T>::makeEmpty()whileNULL){q=whileNULL){q=first->link//保存被刪結(jié)點(diǎn)//保存被刪結(jié)點(diǎn)//從鏈上摘下該結(jié)點(diǎn)//刪除first->link；=q->link；deleteq；}}；template<classT>intList<T>::Length()const{ListNode<T>*p=first->link;intcount=0;while(p!=NULL) 〃逐個(gè)結(jié)點(diǎn)檢測{p=p->link;count++;}returncount;}template<classT>LinkNode<T>*List<T>::Search(Tx){〃在表中搜索含數(shù)據(jù)X的結(jié)點(diǎn)，搜索成功時(shí)函數(shù)返該結(jié)點(diǎn)地址；否則返回NULL。LinkNode<T>*current=first->link;while(current!=NULL&¤t->data!=X) current=current->link;returncurrent；}；template<classT>LinkNode<T>*List<T>::Locate(inti)(//函數(shù)返回表中第i個(gè)元素的地址。若i<0或i超出表中結(jié)點(diǎn)個(gè)數(shù)，則返回NULL。if(i<0)returnNULL;//i不合理LinkNode<T>*current=first；intk=0；while(current!=NULL&&k<i){current=current->link;k++; }returncurrent;//返回第i號(hào)結(jié)點(diǎn)地址或NULL};template<classT>boolListvT>::getData(inti,T&x) 〃取出鏈表中第i個(gè)兀素的值{if(i<=0)returnfalse;LinkNode<T>*current=Locate(i);if(cunent==NULL)returnfalse;else{x=current->data;returntrue;}template<classT>voidList<T>::setData(inti,T&x)〃給鏈表中第i個(gè)兀素的賦值x{if(i<=0)return;LinkNode<T>*current=Locate(i);if(cunent==NULL)return;elsecurrent->data=x;}template<classT>boolList<T>::Insert(inti,T&x)//將新元素x插入在鏈表中第i個(gè)結(jié)點(diǎn)之后。LinkNode<T>*current=Locate(i);if(current==NULL)returnfalse;//無插入位置LinkNode<T>*newNode=newLinkNode<T>(x);if(newNode==NULL){cerrvv"內(nèi)存分配錯(cuò)誤！"<<endl;newNode->link=current->link;current->link=newNode;returntrue;exit(1);}; }//鏈入template<classT> 〃插入成功boolList<T>::Remove(inti,T&x)〃刪除鏈表第i個(gè)元素,通過引用參數(shù)x返回元素值{LinkNode<T>*current=Locate(i-1);if(current==NULL||current->link==NULL)returnfalse;〃刪除不成功LinkNode<T>*del=current->link;current->link=del->link;x=del->data;deletedel;returntrue;);template<classT>voidList<T>::output(){LinkNode<T>*current二first->link;while(current!=NULL){cout<<current->data<<endl;current二current->link;}template<classT>voidList<T>::inputFront(TendTag){LinkNode<T>*newNode;Tval;makeEmpty();cin>>val;while(val!=endTag){newNode=newLinkNode<T>(val);if(newNode==NULL){ cerr<<"內(nèi)存分配錯(cuò)誤！"<<endl;exit(1);}newNode->link=first->link;〃插在表前端first->link=newNode;cin>>val;});【實(shí)驗(yàn)過程】對(duì)實(shí)驗(yàn)內(nèi)容進(jìn)仃分析，由】)設(shè)線性鏈表A=(a1,a2,…,am),,B=(b1,b2,…bm),按下列規(guī)則合并A,B為線性表C的算法，即使得C=(a1,b1,…，am,bm,b(m+1),^,bn)當(dāng)m<=n或C=(a1,b1,…,an,bna(n+1),…,am)當(dāng)m>n設(shè)計(jì)出函數(shù)uniom;由2)將C表原地逆置，設(shè)計(jì)出了函數(shù)changeove;r由3)將c表的中偶數(shù)和奇數(shù)分別鏈接為兩個(gè)循環(huán)鏈表D和E設(shè)計(jì)出了函數(shù)classify。然后再設(shè)計(jì)主函數(shù)，逐步進(jìn)行調(diào)試?！緦?shí)驗(yàn)體會(huì)】通過該實(shí)驗(yàn)，我能了解鏈表的概念、功能及應(yīng)用。鏈表是用鏈接存儲(chǔ)的方式來表達(dá)線性表，它用指針表示結(jié)點(diǎn)間的邏輯關(guān)系，鏈表適用于插入或刪除頻繁，存儲(chǔ)空間需求不定的情形。6圖元識(shí)別和替換(用隊(duì)列實(shí)現(xiàn))【問題描述】對(duì)于點(diǎn)陣式的圖，在程序中可以用二維數(shù)組來表示。圖中一片連續(xù)的具有相同顏色的點(diǎn)稱為“圖元”?，F(xiàn)給出的問題是，對(duì)圖中指定的圖元用另一種顏色來替換。用隊(duì)列實(shí)現(xiàn)。輸入輸出界面與實(shí)驗(yàn)指導(dǎo)書中算法實(shí)現(xiàn)—程序3.1相同。【主要代碼】#include<iostream.h>#include<stdlib.h>#defineQMAX30//設(shè)?？臻g最大為30單元#defineM8 //設(shè)方陣大小為8行8列typedefstruct{//像素結(jié)構(gòu)introw;intcol;}Pixel; //像素的行下標(biāo)Pixel //像素的列下標(biāo)offset[4]; //像素類型名//矩陣中四個(gè)方向的移動(dòng)修正classStack{ 表private:Pixelst[QMAX];//像素類型的棧空間inttop;//棧頂public:Stack(){top=0;}voidpush(Pixel&e);//像素e進(jìn)棧Pixelpop();//出棧一個(gè)像素intIsEmpty();//判斷棧是否為空，若空則返回1，否則返回0);voidStack::push(Pixel&e){//像素e進(jìn)棧if(top==QMAX)exit(0);st[top].row=e.row;st[top].col=e.col;top++;}PixelStack::pop(){//出棧一個(gè)像素，由e返回Pixele;if(top==0)exit(0);top--;e.row=st[top].row;e.col=st[top].col;returne;}intStack::IsEmpty(){//判斷棧是否為空if(top<=0)return1;elsereturn0;}voidInit(Pixelpos[]){// 初始化移動(dòng)修正表數(shù)組，pos[]即offset[4]pos[0].row=0;pos[0].col=1;//right pos[1].row=1;pos[1].col=0;pos[2].row=0;pos[2].col=-1;//down pos[3].row=-1;pos[3].col=0;//left} //upintseekp(intarra[][8],int ai,intaj,intx,inty){//使用棧的圖元替換算法Pixelnbr,here;//進(jìn)棧變量和出棧變量Stackms;//棧inti,ni,nj;〃工作變量，下一個(gè)工作點(diǎn)的行下標(biāo)和列下標(biāo)cout<<"搜索到的圖元像素："<<endl;cout<<ai<<','<<aj<<','<<arra[ai][aj]<<endl;arra[ai][aj]=x;arra[ai][aj+1]=x; //替return1; 換//} 替換voidmain(){intarra[8][8]={//存儲(chǔ)圖的數(shù)組初始化0,0,0,0,0,0,0,0,0,0,3,3,0,5,2,0,0,0,3,3,0,0,2,0,0,6,2,3,8,8,8,0,0,0,2,3,8,0,0,0,0,2,2,8,8,7,3,0,0,0,2,5,8,3,3,0,0,0,0,0,0,0,0,0};inti,j,x,//四周設(shè)一圈圍墻(值為0)以保證數(shù)據(jù)處理的可靠性y;Init(offset);//初始化移動(dòng)修正表數(shù)cout<<"像素矩 組"<<endl;陣： //輸出圖矩陣for(i=0;i<M;i++){for(j=0;j<M;j++)cout<<arra[i][j]<<'';cout<<endl;}coutvv"請(qǐng)輸入指定圖元的坐標(biāo)和新像素值(ijx用空格分隔)："；cin>>i>>j>>x;//輸入數(shù)據(jù)用空格分隔y=arra[i][j];〃取指定像素的值if(y!=x){seekp(arra,i,j,x,y);//進(jìn)行圖兀替換coutvv"替換后的像素矩陣:"<<endl;for(i=0;ivM;i++){//輸出圖矩陣for(j=0;jvM;j++)coutvvarra[i][j]vv'';coutvvendl;}coutvv'圖兀替換完畢！"<<endl;}elsecoutvv味做替換!〃vvendl;//未進(jìn)行替換操作}ooe00000000eooe00000000e050S073O00a989oa93a0e?B?嘛舍甫i夏魏坐標(biāo)和新橡素值Gj〃用空格分隔）：24e2?4.e八鷺"換后的燔素矩陣］0099PressonykeykeytocontLnucPressonykeykeytocontLnuc1aa1aaaaaa&&02?022e濁a|2|Eeae7e3B^乎圖吒的坐標(biāo)和新像素值（iJK屈空格分隔）淪40P>*essanykeytocontinue.【實(shí)驗(yàn)體會(huì)】在二叉樹中正確地理解和應(yīng)用遞歸思想是很重要。由于二叉樹的結(jié)構(gòu)的特殊性，所以能充分發(fā)揮遞歸函數(shù)的強(qiáng)大功能。9字符串【實(shí)驗(yàn)簡介】字符串是由零個(gè)或多個(gè)字符的順序排列所組成的數(shù)據(jù)結(jié)構(gòu)，字符串在計(jì)算機(jī)處理中使用非常廣泛。通過本次實(shí)驗(yàn)理解字符串運(yùn)算的原理，掌握主要算法的實(shí)現(xiàn)?！緦?shí)驗(yàn)內(nèi)容】建立字符串類，并實(shí)現(xiàn)求子串、字符串賦值、字符串連接等運(yùn)算符重載函數(shù)，實(shí)現(xiàn)字符串的模式匹配功能。編寫一個(gè)能夠統(tǒng)計(jì)字符串中各個(gè)字符出現(xiàn)頻度的函數(shù)?！局饕a】#include<iostream>usingnamespacestd;#include<string.h>intconstdefaultSize=128;//常量classAString{public:AString();//構(gòu)造函數(shù)AString(constchar*init);//構(gòu)造函數(shù)AString(constAString&ob);//復(fù)制構(gòu)造函數(shù)~AString(){delete[]ch;}//析構(gòu)函數(shù)intLength()const{returncurLength;}//取長度AStringoperator()(intpos,intlen);//取子串函數(shù)AString&operator=(constAString&ob);//賦值函數(shù)AString&operator+=(constAString&ob);//連接函數(shù)char&operator[](inti);//取特定位子的函數(shù)voidoutput();//輸出字符串函數(shù)voidinput(char*init);//輸入字符串函數(shù)intFind(AString&pat,intk);//匹配函數(shù)voidchar_count();//統(tǒng)計(jì)各個(gè)字符函數(shù)private:char*ch;//字符串指針intcurLength;//當(dāng)前長度intmaxSize;//可用長度);AString::AString(){//沒有參數(shù)的構(gòu)造函數(shù)maxSize=defaultSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=0;ch[0]='\0';);AString::AString(constchar*init){//有參數(shù)的構(gòu)造函數(shù)intlen;len=strlen(init);maxSize=(len>defaultSize)?len:defaultSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=len;strcpy(ch,init);}AString::AString(constAString&ob){//賦值構(gòu)造函數(shù)maxSize=ob.maxSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=ob.curLength;strcpy(ch,ob.ch);}AStringAString::operator()(intpos,intlen){//取子串函數(shù)的實(shí)現(xiàn)AStringtemp;if(pos<0||pos+len-1>=maxSize||len<0){temp.curLength=0;temp.ch[0]='\0';}else{if(pos+len-1>=curLength)len=curLength-pos;temp.curLength=len;for(inti=0,j=pos;i<len;i++,j++)temp.ch[i]=ch[j];temp.ch[len]='\0';}returntemp;}AString&AString::operator=(constAString&ob){//賦值函數(shù)的實(shí)現(xiàn)if(&ob!=this){delete[]ch;ch=newchar[ob.maxSize];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=ob.curLength;strcpy(ch,ob.ch);}elsecout<<"ERROR"<<endl;return*this;}AString&AString::operator+=(constAString&ob){//連接函數(shù)的實(shí)現(xiàn)char*temp=ch;intn=curLength+ob.curLength;intm=(maxSize>=n)?maxSize:n;ch=newchar[m];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}maxSize=m,curLength=n;strcpy(ch,temp);strcat(ch,ob.ch);delete[]temp;return*this;}char&AString::operator[](inti){//取特定位置字符函數(shù)的實(shí)現(xiàn)if(i<0||i>=curLength){cout<<"overrange"<<endl;exit(1);}returnch[i];}intAString::Find(AString&pat,intk){//inti,j;for(i=k;i<=curLength-pat,curLength;i++){for(j=0;j<pat.curLength;j++)if(ch[i+j]!=pat.ch[j])break;if(j==pat.curLength)returni;}return-1;}voidAString::output(){//輸出字符串函數(shù)的實(shí)現(xiàn)inti;for(i=0;i<curLength;i++){cout<<ch[i]<<"";}cout<<endl;}voidAString::input(char*init){//輸入字符串的函數(shù)實(shí)現(xiàn)intlen=strlen(init);curLength=len;strcpy(ch,init);}voidAString::char_count(){//統(tǒng)計(jì)各個(gè)字符的函數(shù)的實(shí)現(xiàn)intchar_let,char_num,char_other;char_let=char_num=char_other=0;for(inti=0;i<curLength;i++){if(ch[i]<='Z'&&ch[i]>='A'||ch[i]<'z'&&ch[i]>='a'){char_let++;}elseif(ch[i]<='9'&&ch[i]>=T'){char_num++;}elsechar_other++;}coutvv"字母有"vvchar_letvvendl;coutvv"數(shù)字有"vvchar_numvvendl;coutvv"其他有"vvchar_othervvendl;}voidmain(){//charstr[100];coutvv"請(qǐng)輸入一串字符串"vvendl;cin.getline(str,100);AStringmainStr;mainStr.input(str);mainStr.output();intpos,len;coutvv"請(qǐng)輸入要取出的子串的位置"vvendl;cin>>pos>>len;AStringsub_mainStr;sub_mainStr=mainStr(pos,len);sub_mainStr.output();mainStr+=sub_mainStr;coutvv"將取出的子串連接到主串后面為"<<endl;mainStr.output();intlocation;location=mainStr.Find(sub_mainStr,0);coutvv"子串的位置為"vvlocationwendl;mainStr.char_count();【實(shí)驗(yàn)過程】⑴重新定義一個(gè)字符串類⑵在類中構(gòu)造函數(shù)和各個(gè)功能函數(shù)的聲明⑶在類的私有成員中為字符串和字符串的長度和空間的大?、雀鱾€(gè)成員函數(shù)的實(shí)現(xiàn)⑸主函數(shù)的實(shí)現(xiàn)請(qǐng)輸入一串字符串!Laf125s上F誑盤safArefsfl25請(qǐng)輸入要取出的子串的位置t4勺將取出的子串連接到主串后面為魏字<3safarefsfl25s子串的勺將取出的子串連接到主串后面為魏字<3safarefsfl25s子串的位置為1苴他有空Ppessanykeytocontinue【實(shí)驗(yàn)體會(huì)】在這一個(gè)實(shí)驗(yàn)中，以字符串味載體，再一次鞏固了類的學(xué)習(xí)。同時(shí)也掌握了字符串的特性，通過封裝成類和運(yùn)算符的重載，使字符串的函數(shù)更加好用，這也是C++語言的強(qiáng)大之處。7二叉樹的操作【實(shí)驗(yàn)簡介】二叉樹是樹形結(jié)構(gòu)的一種重要類型。通過本次實(shí)驗(yàn)，熟悉二叉樹結(jié)點(diǎn)的結(jié)構(gòu)，掌握二叉樹的基本操作以及具體實(shí)現(xiàn)，學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。【實(shí)驗(yàn)內(nèi)容】編寫程序，實(shí)現(xiàn)對(duì)二叉樹的以下操作：建立二叉樹。按任一種遍歷次序輸出二叉樹中的所有結(jié)點(diǎn)。求二叉樹的深度。求二叉樹中的所有節(jié)點(diǎn)數(shù)。求二叉樹中的所有葉子節(jié)點(diǎn)數(shù)。6. 清除二叉樹，使之編程一只空樹?！局饕a】#includeviostream>Usingnamespacetemplate<classT>structBinTreeNode //二叉樹結(jié)點(diǎn)類定義(Tdata; ii數(shù)據(jù)域BinTreeNode<T>*leftChild,*rightChild;II左子女、右子女鏈域{leftChild={leftChild=NULL;rightChild=NULL;}〃構(gòu)造函數(shù)BinTreeNode()〃構(gòu)造函數(shù)BinTreeNode(Tx,BinTreeNode<T>*left=NULL,BinTreeNode<T>*right=NULL)rightChild=right;} };{data=x; leftChild=left;template<classT>classBinaryTree{public:BinaryTree(){root=NULL; //二叉樹類定義BinaryTree(Tvalue){RefValue=value;root=NULL; //構(gòu)造函數(shù)BinaryTree(){destroy(root);}bool //構(gòu)造函數(shù)IsEmpty(){returnroot==NULL;}//int}Height(){returnHeight(root);}int //析構(gòu)函數(shù)判二Size()(returnSize(root);} 叉樹空否〃求樹BinTreeNode<T>*getRoot()const 高度{returnroot;}BinTreeNode<T>札eftChild //求結(jié)點(diǎn)數(shù)(BinTreeNode<T>*cur)//返回左子女{return(cur!=NULL)？cur->leftChild:NULL;}BinTreeNode<T>*RightChild(BinTreeNode<T>*cur)//返回右子女{return(cur!=NULL)？cur->rightChild:NULL;}protected:BinTreeNode<T>*root; //二叉樹的根指針TRefValue; //數(shù)據(jù)輸入停止標(biāo)志voidCreateBinTree(istream&in,BnTreeNode<T>*&subTree);//從文件讀入建樹voiddestroy(BinTreeNode<T>*&subTree); //刪除intHeight(BinTreeNode<T>*subTree);//返回樹高度intSize(BinTreeNode<T>*subTree); //返回結(jié)點(diǎn)數(shù)BinTreeNode<T>*Parent(BinTreeNode<T>*subTree,BinTreeNode<T>*cur);返回父結(jié)點(diǎn)//template<classT>voidBinaryTree<T>::destroy(BinTreeNode<T>*subTree)//私有函數(shù)：刪除根為subTree的子樹{if(subTree!=NUL