空间数据结构上机实验报告

《空间数据结构基础》上机实验报告（2010级）姓名班级学号环境与测绘学院1.顺序表的定义与应用（课本P85习题）【实验目的】熟练掌握顺序表的定义与应用，通过上机实践加深对顺序表概念的理解。【实验内容】设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均从小到大排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也从小到大排列。【主要代码】 #include<iostream.h>//定义在头文件“SeqList.h”中 #include<stdlib.h> constintdefaultSize=100; template<classT> classSeqList{ protected: T*data;//存放数组 intmaxSize;//最大可容纳表象的项数 intLast;//当前已存表象的项数 voidreSize(intnewSize);//改变data数组空间大小 public: SeqList(intsz=defaultSize); SeqList(SeqList<T>&L); ~SeqList(){delete[]data;} intSize()const{returnmaxSize;} intLength()const{returnLast+1;} intSearch(T&x)const; intLocate(inti)const; TgetData(inti)const; boolsetData(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); friendvoidrank(SeqList<int>&L); friend voidhebing(SeqList<int>&LA,SeqList<int>&LB); }; //构造函数，通过指定参数sz定义数组的长度 template<classT> SeqList<T>::SeqList(intsz){ if(sz>0){ maxSize=sz; Last=-1; data=newT[maxSize]; if(data==NULL) {cerr<<"存储分配错误"<<endl;exit(1);} } } //复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表 template<classT> SeqList<T>::SeqList(SeqList<T>&L){ maxSize=L.Size(); Last=L.Length()-1; data=newT[maxSize]; if(data==NULL) {cerr<<"存储分配错误"<<endl;exit(1);} for(inti=1;i<=Last+1;i++) data[i-1]=L.getData(i); } //用于取第i个表项的值 template<classT> TSeqList<T>::getData(inti)const{ if(i<1||i>Last+1){cerr<<"存储分配错误"<<endl;exit(1);} elsereturndata[i-1]; } //私有函数，扩充顺序表的存储空间大小，新数组的元素个数为newsize template<classT> voidSeqList<T>::reSize(intnewSize) { if(newSize<=0) {cerr<<"无效的数组大小"<<endl;return;} if(newSize!=maxSize) {T*newarray=newT[newarray]; if(newarray=NULL) {cerr<<"存储分配错误"<<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)returni; elsereturn0; } //插入函数 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]=data[j-1]; 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<<"开始建立顺序表，请输入表中元素的最后位置："; while(1){ cin>>Last;Last--; if(Last<=maxSize-1)break; cout<<"表元素个数有误，个数不能超过"<<maxSize-1<<":"; } for(inti=0;i<=Last;i++) {cin>>data[i];} } //输出函数 template<classT> voidSeqList<T>::output(){ cout<<"顺序表中当前元素的最后位置为："<<Last<<endl; for(inti=0;i<=Last;i++) cout<<data[i]<<endl; } //重载操作，顺序表整体赋值 template<classT> SeqList<T>SeqList<T>::operator=(SeqList<T>&L){ maxSize=L.Size(); Last=L.Length()-1; data=newT[maxSize]; if(data==NULL) {cerr<<"存储分配错误"<<endl;exit(1);} for(inti=1;i<=Last+1;i++) data[i-1]=L.getData(i); } //合并函数，用于合并顺序表LA,LB。结果存于LA。重复元素只留一个。 voidhebing(SeqList<int>&LA,SeqList<int>&LB){ intn=LA.Length(),m=LB.Length(),k,x; for(inti=1;i<=m;i++) { x=LB.getData(i); k=LA.Search(x); if(k==0) {LA.Insert(n,x);n++;} } } //对合并后的顺序表进行排序 voidrank(SeqList<int>&L) { inti,j,temp; for(i=1;i<L.Length();i++) for(j=0;j<L.Length()-i;j++) { if(L.data[j]>L.data[j+1]) { temp=L.data[j]; L.data[j]=L.data[j+1]; L.data[j+1]=temp; } } } voidmain() { SeqList<int>LA;//定义顺序表类对象LA SeqList<int>LB;//定义顺序表类对象LB LA.input(); LB.input(); hebing(LA,LB); SeqList<int>LC(LA); rank(LC); LC.output(); }运行结果：【实验体会】通过本次试验，我熟练掌握顺序表的定义与应用。此次实验通过对顺序表的类定义，进行两顺序表的合并，并在合并后删除相同的元素，然后对新数组进行从小到大的排序。因为顺序表是基于一维数组的储存，所以可以选择冒泡法进行排序。类代码中包含三个数据成员，多个作为外部接口的成员函数，完成顺序表的搜索，定位，插入和删除等操作。运用类模板，Seqlist的数据成员不使用固定的类型定义，而是用class说明的虚拟类型名T作为变量的类型，在定义Seqlist类的对象时，再用C++的基本类型将对象的数据成员的类型实例化。这样做的好处是可以使用同一个类来定义不同数据类型的对象，提高代码的利用率。本次试验，受益匪浅。2.单链表的使用（书P86习题）【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。能够使用链表类的定义和部分函数的使用。掌握其数据结构的构建方式并实现相关成员函数。【实验内容】设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针h指向原链表的最后一个结点。【主要代码】#include<iostream>usingnamespacestd;template<classT>structLinkNode{//链表结点类的定义 Tdata;//数据域 LinkNode<T>*link;//链指针域 LinkNode(LinkNode<T>*ptr=NULL){link=ptr;}//仅初始化指针成员的构造函数LinkNode(constT&item,LinkNode<T>*ptr=NULL)//初始化数据与指针成员的构造函数，为item分配一个结点的空间 {data=item;link=ptr;}//将数据成员初始化};template<classT>classList{//链表类的定义，直接使用链表结点类的操作 protected: LinkNode<T>*first;//链表头指针 public: List(){first=newLinkNode<T>;}//链表类不带参数的构造函数List(constT&x){first=newLinkNode<T>(x);}//链表类带参数的构造函数 voidInputRear(intendTag);//后插法建立单链表函数，以endTag为结束标识符 voidoutput();//用于转置前和转置后链表的输出 voidreverse();//转置函数};template<classT>voidList<T>::InputRear(intendTag){//后插法建立单链表，保证插入的数的顺序与链表一致 LinkNode<T>*newnode,*last;Tval;//定义两个指针，一个指向头，一个指向结尾 cin>>val;last=first; while(val!=endTag){ newnode=newLinkNode<T>(val);//为插入的数分配内存空间 if(newnode==NULL){cerr<<"分配内存出错"<<endl;exit(1);} last->link=newnode;last=newnode;//插入到表末端 cin>>val;//再输入下一个数 } last->link=NULL;//表收尾，将最后一个数的link域为NULL};//下面输出函数是用于输出链表template<classT>voidList<T>::output(){ LinkNode<T>*current=first->link;//初始化，current指向first的link域 while(current!=NULL){ cout<<current->data<<endl; current=current->link; } }//下面为对链表实现转置的函数template<classT>voidList<T>::reverse(){ //转置函数的实现 LinkNode<T>*h=first,*p,*q;p=h->link;h->link=NULL; while(p!=NULL) { q=p; p=p->link; q->link=h->link; h->link=q; } }voidmain(){ List<int>L;//定义类的对象L cout<<"请输入若干数，以0作为结尾"<<endl; L.InputRear(0);//调用后插法建立单链表函数 cout<<"链表转置前为"<<endl; L.output();//输出未转置的链表 L.reverse();//调用转置函数，实现转置 cout<<"链表转置后为"<<endl;L.output();//输出转置后的链表}【实验过程】=1\*GB3①首先通过结构体和类建立接点和链表。=2\*GB3②然后，分别对实现功能所需要的函数进行定义=3\*GB3③然后，对定义的各部分函数，进行具体分布实施。运行如图：【实验体会】通过本次试验，我熟悉并掌握了链表的使用。链表适用于插入和删除频繁，存储空间需求不定的情形，有效的克服了顺序表的效率低和时间开销大缺点。带附加头结点的单链表，能够方便的进行链表的插入和删除等各类操作的实现。建立链表时使用后插法建立，使得链表的物理顺序和逻辑顺序一致，符合人们的使用习惯。在函数的实现的过程中，采用自顶向下分解的方法。受益匪浅。3.队列和栈的相关应用（书P134习题）【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。能够对栈和队列的理解和相关函数的应用。【实验内容】设用链表表示一个双端队列，要求可以从表的两端插入，但限制只能在表的一端删，试编写基于此的队列的插入和删除算法，并给出队空的的条件。【主要代码】#include<iostream>usingnamespacestd;template<classT>structLinkNode{//链表结点类的定义 Tdata;//数据域 LinkNode<T>*link;//链指针域 LinkNode(LinkNode<T>*ptr=NULL){link=ptr;}//仅初始化指针成员的构造函数LinkNode(constT&item,LinkNode<T>*ptr=NULL)//初始化数据与指针成员的构造函数，为item分配一个结点的空间 {data=item;link=ptr;}//将数据成员初始化};template<classT>classDeque{//Deque类protected: LinkNode<T>*front,*rear;//定义两个指针，分别指向链表的两端public: Deque()//Deque的构造函数 {front=rear=newLinkNode<T>;} voidEnqueue(T&x,intDir);//插入函数，x为插入的数，tag为插入的方向 voidDequeue();//删除函数 boolIsempty(){return(rear==front)?true:false;}//判断是否为空 voidoutput();//输出函数};template<classT>voidDeque<T>::Enqueue(T&x,intDir){//插入函数的实现 if(Dir==0){//规定tag=0为从前端插入LinkNode<T>*newnode; newnode=newLinkNode<T>(x);//建立一个新结点 if(newnode==NULL){cerr<<"分配内存出错"<<endl;exit(1);}//容错处理 newnode->link=front->link;//插入的实现 front->link=newnode; if(rear->link!=NULL)//保证rear指针是指向最后的接点 {rear=rear->link;} } else{//从后端插入LinkNode<T>*newnode; newnode=newLinkNode<T>(x); if(newnode==NULL){cerr<<"分配内存出错"<<endl;exit(1);} newnode->link=rear->link;rear->link=newnode; rear=rear->link;//在后端插入 }}template<classT>voidDeque<T>::Dequeue(){//删除函数的实现，从后端删除 LinkNode<T>*p;//声明一个p指针 p=front;//从front开始历遍到rear前一个 if(Isempty()==true)//判断链表是否为空 {cout<<"队列为空，无法删除"<<endl;exit(1);}//若空则直接退出else while(p->link!=rear){p=p->link;}//p指针历遍到rear前一个接点 rear=p; p=p->link; deletep;//删除最后一个接点