空間數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

《空間數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》課程實(shí)習(xí)報(bào)告（測繪09級）姓名李冬偉 班級采礦09-9班學(xué)號07092951礦業(yè)與工程學(xué)院三維空間球【實(shí)驗(yàn)?zāi)康摹苛私鈴?fù)合數(shù)據(jù)結(jié)構(gòu)的描述方法。球是一個(gè)包含坐標(biāo)點(diǎn)的復(fù)合數(shù)據(jù)結(jié)構(gòu)，在C++程序中將坐標(biāo)點(diǎn)和球分別定義為具有繼承關(guān)系的兩個(gè)類，即定義球類Tball為Point的派生類。使用派生類的形式定義一個(gè)數(shù)據(jù)結(jié)構(gòu)，其主要目的是提高基類的代碼利用率，并使派生類的結(jié)構(gòu)得到簡化?；惡团缮惖亩x體現(xiàn)了C++繼承機(jī)制的運(yùn)用，最大程度地提高了數(shù)據(jù)結(jié)構(gòu)的利用率?！締栴}描述】定義三維空間的坐標(biāo)點(diǎn)TPoint并且描述三維空間的球Tball?！緮?shù)據(jù)結(jié)構(gòu)】定義Tpoint類和Tball類?！局饕δ堋繉?shí)現(xiàn)其主要操作：計(jì)算體積和表面積，輸出空間坐標(biāo)等?！境绦虼a】#include<iostream.h>constdoublePI=3.14159;classTPoint{protected: doublex; doubley; doublez;public: TPoint(){x=0;y=0;z=0;} TPoint(doublepx,doublepy,doublepz){x=px;y=py;z=pz;} doubleGetx(){returnx;} doubleGety(){returny;} doubleGetz(){returnz;} voidMove(doublemx,doublemy,doublemz); voidShow(){cout<<"x="<<x<<"y="<<y<<"z="<<z<<endl;}};classTBall:publicTPoint{ doubler;public: TBall(doublea):TPoint(){r=a;} TBall(doubleb,doublec,doubled,doublee):TPoint(b,c,d){r=e;} doubleArea(){return4*PI*r*r;} doubleVolume(){return4*PI*r*r*r/3;} voidShow(); voidinput();};voidTBall::Show(){ cout<<"球的球心坐標(biāo)為："<<"("<<x<<","<<y<<","<<z<<")"<<endl; cout<<"球的體積為："<<Volume()<<endl; cout<<"球的表面積為："<<Area()<<endl;}voidmain(){ TBallB1(1,2,3,4); TBallB2(4); B1.Show(); B2.Show();}【實(shí)現(xiàn)界面】【實(shí)踐體會(huì)】三維空間球的程序代碼我原本是僅由原有代碼稍加修改后得到的，但在執(zhí)行時(shí)，輸出的數(shù)據(jù)出現(xiàn)了錯(cuò)誤，球的面積和體積計(jì)算出的結(jié)果出現(xiàn)了負(fù)數(shù)，所以我對原有的程序代碼進(jìn)行了簡化和修改，重新進(jìn)行了編輯。鏈表的建立、合并、逆轉(zhuǎn)和拆分【實(shí)驗(yàn)?zāi)康摹勘纠o出了較完整的順序表的抽象數(shù)據(jù)類型定義，通過C++類模板的應(yīng)用體現(xiàn)了數(shù)據(jù)抽象原理?！締栴}描述】定義一個(gè)鏈表存儲(chǔ)的線性表，除已給出的表元素插入、刪除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在應(yīng)用程序中建立兩個(gè)整型的單鏈表對象A和B，應(yīng)用線性表的基本操作對表的實(shí)例對象進(jìn)行操作測試?！緮?shù)據(jù)結(jié)構(gòu)】定義一個(gè)鏈表結(jié)點(diǎn)類LinkNode和一個(gè)線性鏈表類List，提供表元素的插入、刪除、查找和以下操作。1.設(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)成。2.將C表原地逆置。3.將C表的中偶數(shù)和奇數(shù)分別鏈接為兩個(gè)循環(huán)鏈表D和E?！局饕δ堋靠梢暂斎胍粋€(gè)單鏈表，實(shí)現(xiàn)單鏈表的合并、拆分和逆置等操作，且每次結(jié)果均可輸出?！境绦虼a】#include<iostream.h>#include<stdlib.h>template<classT>structLinkNode{ Tdata; LinkNode<T>*link; LinkNode(LinkNode<T>*ptr=NULL){link=ptr;} LinkNode(constT&item,LinkNode<T>*ptr=NULL) { data=item; link=ptr; }};template<classT>classList{ public: List(){h=newLinkNode<T>;} List(constT&x){h=newLinkNode<T>(x);} List(List<T>&L); ~List(){makeEmpty();} voidmakeEmpty(); intLength()const; LinkNode<T>*getHead()const{returnh;} LinkNode<T>*Search(Tx); LinkNode<T>*Locate(inti); boolgetData(inti,T&x)const; voidsetData(inti,T&x); boolInsert(inti,T&x); boolRemove(inti,T&x); boolIsEmpty()const {returnh->link==NULL?true:false;} boolIsFull()const{returnfalse;} voidreverse(); voidinput(TendTag); voidoutput(); List<T>&operator=(List<T>&L); protected: LinkNode<T>*h;};template<classT>List<T>::List(List<T>&L){ Tvalue; LinkNode<T>*srcptr=L.getHead(); LinkNode<T>*desptr=h=newLinkNode<T>; while(srcptr->link!=NULL) { value=srcptr->link->data; desptr->link=newLinkNode<T>(value); desptr=desptr->link; srcptr=srcptr->link; } desptr->link=NULL;}template<classT>voidList<T>::makeEmpty(){ LinkNode<T>*q; while(h->link!=NULL) { q=h->link; h->link=q->link; deleteq; }}template<classT>intList<T>::Length()const{ LinkNode<T>*p=h->link; intcount=0; while(p!=NULL) {p=p->link;count++;} returncount;}template<classT>LinkNode<T>*List<T>::Search(Tx){ LinkNode<T>*current=h->link; while(current!=NULL) if(current->data==x)break; elsecurrent=current->link; returncurrent;}template<classT>LinkNode<T>*List<T>::Locate(inti){ if(i<0)returnNULL; LinkNode<T>*current=h; intk=0; while(current!=NULL&&k<i) {current=current->link;k++;} returncurrent;}template<classT>boolList<T>::getData(inti,T&x)const{ if(i<=0)returnNULL; LinkNode<T>*current=Locate(i); if(current==NULL)returnfalse; else{x=current->data;returnture;}}template<classT>voidList<T>::setData(inti,T&x){ if(i<=0)return; LinkNode<T>*current=Locate(i); if(current==NULL)return; elsecurrent->data=x;}template<classT>boolList<T>::Insert(inti,T&x){ LinkNode<T>*current=Locate(i); if(current==NULL)returnfalse; LinkNode<T>*newNode=newLinkNode<T>(x); if(newNode==NULL) {cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl;exit(1);} newNode->link=current->link; current->link=newNode; returntrue;}template<classT>boolList<T>::Remove(inti,T&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=h->link; cout<<endl; while(current!=NULL) { cout<<current->data<<""; current=current->link; } cout<<endl;}template<classT>List<T>&List<T>::operator=(List<T>&L){ Tvalue; LinkNode<T>*srcptr=L.getHead(); LinkNode<T>*desptr=h=newLinkNode<T>; while(srcptr->link!=NULL) { value=srcptr->link->data; desptr->link=newLinkNode<T>(value); desptr=desptr->link; srcptr=srcptr->link; } desptr->link=NULL; return*this;}template<classT>voidList<T>::input(TendTag){ LinkNode<T>*newNode,*last; Tval; makeEmpty(); cout<<"輸入單鏈表的數(shù)據(jù)（輸入零結(jié)束）"<<endl; cin>>val; last=h; while(val!=endTag) { newNode=newLinkNode<T>(val); if(newNode==NULL) {cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl;exit(1);} last->link=newNode; last=newNode; cin>>val; } last->link=NULL;}template<classT>voidList<T>::reverse(){ LinkNode<T>*last,*led,*q; last=h->link; led=h->link; while(last->link!=NULL) { last=last->link; } while(last!=led) { q=led; led=led->link; h->link=led; q->link=last->link; last->link=q; }}voidUnion(List<int>&A,List<int>&B){ intm=A.Length(); intn=B.Length(); LinkNode<int>*scrptr=A.getHead(); LinkNode<int>*destptr=B.getHead(); LinkNode<int>*p=scrptr->link; LinkNode<int>*q=destptr->link; if(m>n) { while(q!=NULL) { destptr->link=q->link; q->link=p->link; p->link=q; p=p->link->link; q=destptr->link; } } else { for(inti=1;i<m;i++) { destptr->link=q->link; q->link=p->link; p->link=q; p=p->link->link; q=destptr->link; } while(q!=NULL) { destptr->link=q->link; q->link=p->link; p->link=q; q=destptr->link; p=p->link; } } }voidSplit(List<int>&L){ intvalue; List<int>D; List<int>E; LinkNode<int>*led=L.getHead(); LinkNode<int>*scrptr=D.getHead(); LinkNode<int>*destptr=E.getHead(); while(led->link!=NULL) { value=led->link->data; if(value%2==0) { scrptr->link=newLinkNode<int>(value); scrptr=scrptr->link; } elseif(value%2==1) { destptr->link=newLinkNode<int>(value); destptr=destptr->link; } led=led->link; } scrptr->link=NULL; destptr->link=NULL; cout<<"原鏈表拆分成D、E兩個(gè)鏈表"<<endl; cout<<"D表元素全為偶數(shù)，依次是："<<endl; D.output(); cout<<"E表元素全為奇數(shù)，依次是："<<endl; E.output();}voidmain(){ List<int>A; List<int>B; A.input(0); B.input(0); Union(A,B); List<int>C(A);cout<<"兩鏈表合成后，單鏈表的元素依次是："<<endl; C.output(); C.reverse(); cout<<"鏈表逆轉(zhuǎn)后的元素依次是："<<endl; C.output(); Split(C);}【實(shí)現(xiàn)界面】【實(shí)踐體會(huì)】程序的代碼在編輯時(shí)，在鏈表的合并和拆分上，程序的邏輯結(jié)構(gòu)我沒有分析明了，開始設(shè)計(jì)代碼時(shí)沒有成功，之后參考了同學(xué)的算法設(shè)計(jì)才編出代碼，同時(shí)在主函數(shù)的編輯時(shí)，有關(guān)函數(shù)的調(diào)用我還是不很清楚，也是詢問同學(xué)后編譯出的。中綴轉(zhuǎn)后綴【實(shí)驗(yàn)?zāi)康摹恐芯Y轉(zhuǎn)后綴問題可借助棧來處理。本實(shí)驗(yàn)題有助于掌握棧的應(yīng)用技術(shù)?！締栴}描述】表達(dá)式轉(zhuǎn)換。輸入的中綴表達(dá)式為字符串，轉(zhuǎn)換得到的后綴表達(dá)式存入字符數(shù)組中并輸出。例如：a*(x+y)/(b-x)轉(zhuǎn)換后得：axy+*bx-/【數(shù)據(jù)結(jié)構(gòu)】定義一個(gè)暫時(shí)存放運(yùn)算符的轉(zhuǎn)換工作棧opst。中綴表達(dá)式字符串char*infix;后綴表達(dá)式字符串char*postfix;【主要功能】輸入一個(gè)中綴表達(dá)式，輸出的是該算法的后綴表達(dá)式?！境绦虼a】#include<assert.h>#include<iostream.h>#include<stdlib.h>constintstackIncreament=20;template<classT>classOpst{ public: Opst(intsz=50); ~Opst(){delete[]elements;} voidPush(constT&x); boolPop(T&x); boolgetTop(T&x); boolIsEmpty()const{return(top==-1)?true:false;} boolIsFull()const{return(top==maxSize-1)?true:false;} intgetSize()const{returntop+1;} voidmakeEmpty(){top=-1;} friendostream&operator<<(ostream&os,Opst<T>&s); private: T*elements; inttop; intmaxSize; voidoverflowProcess();};template<classT>Opst<T>::Opst(intsz):top(-1),maxSize(sz){ elements=newT[maxSize]; assert(elements!=NULL);}template<classT>voidOpst<T>::overflowProcess(){*newArray=newT[maxSize+stackIncreament]; if(newArray=NULL){cerr<<"存貯分配失??！"<<endl;exit(1);} for(inti=0;i<=top;i++)newArray[i]=elements[i]; maxSize=maxSize+stackIncreament; delete[]elements; elements=newArray;}template<classT>voidOpst<T>::Push(constT&x){if(IsFull()==true)overflowProcess(); elements[++top]=x;}template<classT>boolOpst<T>::Pop(T&x){if(IsEmpty()==true)returnfalse; x=elements[top--]; returntrue;}template<classT>boolOpst<T>::getTop(T&x){ if(IsEmpty()==true)returnfalse; x=elements[top]; returntrue;}template<classT>ostream&operator<<(ostream&os,Opst<T>&s){ os<<"top="<<s.top<<endl; for(inti=0;i<=s.top;i++) os<<i<<":"<<s.elements[i]<<endl; returnos;}intisdigit(charch){ switch(ch) { case'+':case'-':case'*':case'/':case'(':case')': return0; break; default:return1;break; } }intisp(charch){ switch(ch) { case'#':return0;break; case'(':return1;break; case'*':return5;break; case'/':return5;break; case'%':return5;break; case'+':return3;break; case'-':return3;break; case')':return6;break; default:break; }}inticp(charch){switch(ch) { case'#':return0;break; case'(':return6;break; case'*':return4;break; case'/':return4;break; case'%':return4;break; case'+':return2;break; case'-':return2;break; case')':return1;break; default:break; }}voidpostfix(Opst<char>&s){charch='#',ch1,op; s.Push(ch);cin.get(ch); cout<<"后綴表達(dá)式為："<<endl; while(s.IsEmpty()==false&&ch!='#') {if(isdigit(ch)==1){cout<<ch;cin.get(ch);} else { s.getTop(ch1); if(isp(ch1)<icp(ch)) {s.Push(ch);cin.get(ch);} elseif(isp(ch1)>icp(ch)) {s.Pop(op);cout<<op;} else { s.Pop(op); if(op=='(')cin.get(ch); } } } s.Pop(op);cout<<op;}voidmain(){ Opst<char>infix; cout<<"請輸入中綴表達(dá)式："<<endl; postfix(infix);}【實(shí)現(xiàn)界面】【實(shí)踐體會(huì)】中綴轉(zhuǎn)后綴的實(shí)現(xiàn)與教材中的程序代碼大部分是相同的，但需要自行使用switch語句編輯三個(gè)函數(shù)，icp，isp，isdigit，三個(gè)函數(shù)中的isdigit也可以不單獨(dú)用函數(shù)表示而是使用直接判斷語句執(zhí)行，只需將postfix中的isdigit(ch)==1替換為ch<=’Z’||ch>=’A’||ch<=’z’||ch>=’a’||ch<=’9’||ch>=’0’,效果相同。順序表的定義與應(yīng)用【實(shí)驗(yàn)?zāi)康摹渴炀氄莆枕樞虮淼亩x與應(yīng)用，通過上機(jī)實(shí)踐加深對順序表概念的理解，訓(xùn)練學(xué)生利用順序表來解決具體應(yīng)用問題的實(shí)踐能力?！締栴}描述】設(shè)有兩個(gè)整數(shù)類型的順序表A（有m個(gè)元素）和B（有n個(gè)元素），其元素均從小到大排列。試編寫一個(gè)函數(shù)，將這兩個(gè)順序表合并成一個(gè)順序表C，要求C的元素也從小到大排列。【數(shù)據(jù)結(jié)構(gòu)】定義SeqList類【主要功能】1.實(shí)現(xiàn)順序表的類定義。2.實(shí)現(xiàn)順序表的重要成員函數(shù)。3.使用類模板?！敬a】#include<iostream.h>#include<stdlib.h>constintdefaultSize=100;template<classT>classSeqList{ protected: T*data; intmaxSize; intlast; voidreSize(intnewSize); public: SeqList(intsz=defaultSize); SeqList(SeqList<T>&L); ~SeqList(){delete[]data;} T*dizhi(){returndata;} intSize()const{returnmaxSize;} intLength()const{returnlast+1;} intSearch(T&x)const; intLocate(inti)const; boolgetData(inti,T&x)const { if(i>0&&i<=last+1) { x=data[i-1]; returntrue; } else returnfalse; } voidsetData(inti,T&x) { if(i>0&&i<=last+1) data[i-1]=x; } boolInsert(inti,T&x); boolRemove(inti,T&x); boolIsEmpty() { return(last==-1)?true:false; } boolIsFull() { return(last==maxSize-1)?true:false; } voidinput(); voidoutput(); SeqList<T>operator=(SeqList<T>&L);};template<classT>SeqList<T>::SeqList(intsz){ if(sz>0) { maxSize=sz; last=-1; data=newT[maxSize]; if(data==NULL) {cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl; exit(1); } }}template<classT>SeqList<T>::SeqList(SeqList<T>&L){ maxSize=L.Size(); last=L.Length()-1; Tvalue; data=newT[maxSize]; if(data==NULL) { cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl; exit(1); } for(inti=1;i<=last+1;i++) { L.getData(i,value); data[i-1]=value; }}template<classT>voidSeqList<T>::reSize(intnewSize){ if(newSize<=0) { cerr<<"無效的數(shù)組大??！"<<endl; return; } if(newSize!=maxSize) { T*newarray=newT[newSize]; if(newarray==NULL) { cerr<<"存儲(chǔ)分配錯(cuò)誤！"<<endl; exit(1); } intn=last+1; T*srcptr=data; T*destptr=newarray; while(n--)*destptr++=*srcptr++; delete[]data; data=newarray; maxSize=newSize; }}template<classT>intSeqList<T>::Search(T&x)const{ for(inti=0;i<=last;i++) if(data[i]==x) returni+1; return0;}template<classT>intSeqList<T>::Locate(inti)const{ if(i>=1&&i<=last+1) return1; else return0;}template<classT>boolSeqList<T>::Insert(inti,T&x){ if(last==maxSize-1) returnfalse; if(i<0||i>last+1) returnfalse; for(intj=last;j>=i;j--) data[j+1]=data[j]; data[i]=x; last++; returntrue;}template<classT>boolSeqList<T>::Remove(inti,T&x){ if(last==-1) returnfalse; if(i<1||i>last+1) returnfalse; x=data[i-1]; for(intj=i;j<=last;j++) data[j-1]=data[j]; last--; returntrue;}template<classT>voidSeqList<T>::input(){ cout<<"開始建立順序表，請輸入表中元素個(gè)數(shù)："; while(1) { cin>>last; last--; if(last<=maxSize-1) break; cout<<"表元素個(gè)數(shù)輸入有誤，范圍不能超過"<<maxSize<<":"; } for(inti=0;i<=last;i++) { cout<<"請輸入第"<<i+1<<"個(gè)元素"<<endl; cin>>data[i]; }}template<classT>voidSeqList<T>::output(){ for(inti=0;i<=last;i++) cout<<"#"<<i+1<<":"<<data[i]<<endl;}voidUnion(SeqList<int>&LA,SeqList<int>&LB){ intn=LA.Length(),m=LB.Length(),i,k,x; for(i=1;i<=m;i++) { LB.getData(i,x); k=LA.Search(x); if(k==0) { LA.Insert(n,x); n++; } }}voidsort(int*a,intn){ inti,j,min,t; for(j=0;j<n-1;j++) { min=j; for(i=j;i<n;i++) if(a[min]>a[i]) min=i; t=a[min]; a[min]=a[j]; a[j]=t; }}voidmain(){ SeqList<int>A,B; intm,n,l; A.input(); B.input(); A.IsEmpty(); A.IsFull(); B.IsEmpty(); B.IsFull(); n=A.Length(); m=B.Length(); int*x1=A.dizhi(); int*x2=B.dizhi(); sort(x1,n); sort(x2,m); Union(A,B); //A.output(); //B.output(); SeqList<int>C(A); C.IsEmpty(); C.IsFull(); int*x3=C.dizhi(); l=C.Length(); sort(x3,l); cout<<"順序表C為："<<endl; C.output();}【輸入、輸出界面效果】【上機(jī)總結(jié)】通過編程我熟練掌握了順序表的定義與應(yīng)用，通過上機(jī)實(shí)踐加深了對順序表概念的理解，基本可以利用順序表來解決具體應(yīng)用問題的實(shí)踐能力了。打印楊輝三角形【實(shí)驗(yàn)?zāi)康摹客ㄟ^上機(jī)實(shí)踐使得學(xué)生進(jìn)一步了解運(yùn)算受限的線性表——隊(duì)列的應(yīng)用特點(diǎn)與使用方式。掌握隊(duì)列的類定義，實(shí)現(xiàn)隊(duì)列的基本操作。并能夠應(yīng)用該數(shù)據(jù)結(jié)構(gòu)解決一些應(yīng)用問題?！締栴}描述】使用隊(duì)列打印二項(xiàng)展開式（a+b）i的系數(shù)?！緮?shù)據(jù)結(jié)構(gòu)】定義鏈表結(jié)點(diǎn)類【主要功能】1.定義SeqQueue類或LinkedQueue類，實(shí)現(xiàn)其主要成員函數(shù)。2.使用隊(duì)列模擬從第n行系數(shù)求得第n+1行系數(shù)的方法。3.根據(jù)輸入的n值，打印前n行（a+b）n的系數(shù)?！敬a】#include<iostream.h>#include<stdio.h>template<classT>//定義在“LinkedList.h”structLinkNode//鏈表結(jié)點(diǎn)類的定義{Tdata; //數(shù)據(jù)域LinkNode<T>*link;//鏈指針域LinkNode(LinkNode<T>*ptr=NULL){}LinkNode(constT&item,LinkNode<T>*ptr=NULL){ data=item;link=ptr;}};template<classT>classLinkedQueue{ private:LinkNode<T>*front,*rear;//隊(duì)頭、隊(duì)尾指針public:LinkedQueue():rear(NULL),front(NULL){}~LinkedQueue(){}; boolEnQueue(constT&x);boolDeQueue(T&x); boolGetFront(T&x); voidmakeEmpty();//實(shí)現(xiàn)與~LinkedQueue()同boolIsEmpty()const{returnfront==NULL;}intgetSize()const;};template<classT>voidLinkedQueue<T>::makeEmpty()//置空隊(duì)列，釋放連表中所有結(jié)點(diǎn){LinkNode<T>*p;while(front!=NULL)//逐個(gè)結(jié)點(diǎn)釋放{p=front;front=front->link;deletep;}}template<classT>boolLinkedQueue<T>::EnQue