空间数据结构基础.docx

空间数据结构基础.docx

《空间数据结构基础.docx》由会员分享，可在线阅读，更多相关《空间数据结构基础.docx（19页珍藏版）》请在冰点文库上搜索。

空间数据结构基础

《空间数据结构基础》

上机实验报告（2010级）

姓名李坚

班级测绘10-3班

学号07103108

环境与测绘学院

11             C++面向对象程序设计基础

【实验简介】

学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。

理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。

从面向对象的观点看，这两部分代表了对象的属性和方法。

掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。

类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。

【实验内容】

1.定义三维空间的坐标点Tpoint。

2.用面向对象的方法定义一个简单的抽象数据结构，本例实验内容为坐标点的数据结构。

学会如何用C++语言描述数据结构和算法，理解将数据集和在此数据集上的操作分开描述的方法。

3.使用模板建立坐标点point的数据结构，直接表示抽象数据类型。

将程序1.1数据结构的类型参数化（模板），实现更高层次的数据抽象。

【主要代码】

程序1.1：

#include

#include"point.h"

classPoint

{

private:

doublex;

doubley;

public:

Point（）{x=0;y=0;}

Point（doublepx,doublepy）{x=px;y=py;}

voidmove（doublemx,doublemy）{x=mx;y=my;}

voidShow（）{cout<<"x="<

};

voidmain（）

{

Pointa,b（12.5,34.8）;

cout<<"点a的位置：

";

a.Show（）;

cout<<"点b的位置：

";

b.Show（）;

a.move（45.6,57.8）;

cout<<"点a移动后的位置：

";

a.Show（）;

}

程序1.2：

#include

#include"point1.h"

template

classPoint

{

private:

ptTypex;

ptTypey;

public:

Point（）{x=0;y=0;}

Point（ptTypepx,ptTypepy）{x=px;y=py;}

voidmove（ptTypemx,ptTypemy）{x=mx;y=my;}

voidShow（）{cout<<"x="<

};

voidmain（）

{

Pointa（24,36）;

Pointb（12.5,34.8）;

cout<<"点a的位置：

";

a.Show（）;

cout<<"点b的位置：

";

b.Show（）;

a.move（25,18）;

cout<<"点a移动后的位置：

";

a.Show（）;

b.move（45.6,57.8）;

cout<<"点b移动后的位置：

";

b.Show（）;

}

【实验过程】

1.将坐标点数据结构定义为一个C++类Point，在其内部分别定义数据成员和成员函数。

1．数据成员：

一个平面直角坐标系中的点有两个属性，它们是x轴上的水平坐标值和y轴上的垂直坐标值。

在Point类中，这两个属性分别由数据成员x和y来表示，定义为double类型的私有数据成员。

2．操作方法：

定义成员函数，为类的使用者提供服务接口。

先设计允许对点对象进行的操作，再用C++描述实现操作的算法，并定义为类Point的成员函数。

在本例中提供了两个操作：

move（）函数将一个Point对象移至另一位置，Show（）函数输出Point对象的数据成员值。

两个构造函数，分别用于建立缺省参数的对象和带参数的对象。

（算法提示）缺省构造函数Point（）将新建立的坐标点对象初始化为原点位置（０,０）。

带参数的构造函数Point（doublepx,doublepy）允许用户建立对象时指定初始坐标位置。

点对象的移动操作move（）函数需要在调用时给出新位置参数。

输出坐标值为无参函数。

3.point的数据成员不使用固定的类型定义，而是用typename说明的虚拟类型名ptType作为变量的类型，在定义Point类的对象时，再用C++的基本类型将对象的数据成员的类型实例化。

这样做的好处是可以使用同一个类来定义不同数据类型的对象，提高代码的利用率。

【实验体会】

通过这次上机实践，基本了解了用算法语言描述抽象数据类型和如何使用模板建立数据结构。

最重要的是如何去调试和正常使用一个程序。

22n阶二项式系数（用队列实现）

【实验简介】

队列是另外一种限定存取位置的线性表。

将n阶二项式展开，其系数构成杨辉三角形。

设定一个数组，将n行的数据全部处理并打印完，第n+1行的数据也全都计算出来并已存入数组中。

一旦第n+1行的数据形成，第n行的数据就已经不在数组中了。

这个数组实际就是一个队列。

利用它可以实现需要逐排扫描处理的问题。

【实验内容】

1.理解队列操作的算法和程序实现，学会使用队列解决问题。

2.计算并输出n阶二项式系数。

【主要代码】

#include

#include"queue.h"

#include

template

classQueue

{

public:

Queue（intsz=20）;

~Queue（）{delete[]elements;};

voidEnQueue（constType&item）;

TypeDeQueue（）;

TypeGetFront（）;

voidMakeEmpty（）{front=rear=0;}

intIsEmpty（）const

{returnfront==rear;}

intIsFull（）const

{return（rear+1）%maxsize==front;}

intLength（）const

{return（rear-front+maxsize）%maxsize;}

private:

intrear,front;

Type*elements;

intmaxsize;

};

template

Queue:

:

Queue（intsz）:

front（0）,rear（0）,maxsize（sz）

{

elements=newType[maxsize];

assert（elements!

=0）;

}

template

voidQueue:

:

EnQueue（constType&item）

{

assert（!

IsFull（））;

rear=（rear+1）%maxsize;

elements[rear]=item;

}

template

TypeQueue:

:

DeQueue（）

{

assert（!

IsEmpty（））;

front=（front+1）%maxsize;

returnelements[front];

}

template

TypeQueue:

:

GetFront（）

{

assert（!

IsEmpty（））;

returnelements[front];

}

voidYangHui（intn）

{

Queueq;

q.MakeEmpty（）;

q.EnQueue

（1）;q.EnQueue

（1）;

ints=0;

for（inti=1;i<=n;i++）

{

cout<

q.EnQueue（0）;

for（intj=1;j<=i+2;j++）

{

intt=q.DeQueue（）;

q.EnQueue（s+t）;

s=t;

if（j!

=i+2）cout<

}

}

}

voidmain（）

{

intn;

n=6;

YangHui（n）;

cout<

}

【实验过程】

1.用顺序存储的队列classQueue对象暂存求得的二项式系数。

本题特点是递推式计算。

计算求得的二项式系数可以摆成一个三角形，称为“杨辉三角形”。

2.应用程序为YangHui（intn）函数。

（1）初始的两个系数1由常量赋值，以后每一个新系数由语句q.EnQueue（s+t）产生并插入队列。

s和t分别表示新系数左肩上和右肩上的系数。

新系数插入队列后，t值赋给s，出队一个数据赋给t，再进行下一个系数的计算，如此循环。

在上下行的换行处插入一个0，以产生边上的1。

（2）计算工作由二重循环实现，外循环for（inti=1;i<=n;i++）控制产生n行系数。

内循环for（intj=1;j<=i+2;j++）控制按行输出系数。

每行系数的个数与行序号存在对应关系，如i表示行号，则第i行系数个数为i+2。

【实验体会】

在这次试验中，我学会了队列操作的算法和程序实现，基本掌握了怎样使用队列解决问题。

通过这次上机实践，我加深了对上机调试程序的理解，能够更加迅速地找出程序中的错误。

33合并顺序表（用顺序表实现）

【实验简介】

设有两个整数类型的顺序表A（有m个元素）和B（有n个元素）,其元素均以从小到大的升序排列。

试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以从小到大的升序排列。

【实验内容】

以顺序表为数据结构，应用其的相关函数，写出一个总的函数将有两个整数类型的顺序表A（有m个元素）和B（有n个元素）合并成一个顺序表C，并且保证A、B、C三个顺序表中的元素都以从小到大的升序排列。

【主要代码】

#ifndefSEQLIST_H

#defineSEQLIST_H

#include

#include

constintdefaultSize=100;

template

classSeqList

{

protected:

T*data;

intmaxSize;

intlast;

voidreSize（intnewSize）;

public:

SeqList（intsz=defaultSize）;

SeqList（SeqList&L）;

~SeqList（）{delete[]data;}

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;

}

boolsetData（inti,T&x）

{

if（i>0&&i<=last+1）

{

data[i-1]=x;

returntrue;

}

else

returnfalse;

}

boolInsert（inti,T&x）;

boolRemove（inti,T&x）;

voidSort（）;

boolIsEmpty（）{return（last==-1）?

true:

false;}

boolIsFull（）{return（last==maxSize-1）?

true:

false;}

voidinput（）;

voidoutput（）;

SeqListUnion（constSeqList&La,constSeqList&Lb）;

};

template

SeqList:

:

SeqList（intsz/*=100）*/）

{

if（sz>0）

{

maxSize=sz;

last=-1;

data=newT[maxSize];

if（data==NULL）

{

cerr<<"存储分配错误！

"<

exit

（1）;

}

}

}

template

SeqList:

:

SeqList（SeqList&L）

{

maxSize=L.Size（）;

last=L.Length（）-1;

Tvalue;

data=newT[maxSize];

if（data==NULL）

{

cerr<<"存储分配错误！

"<

exit

（1）;

}

for（inti=1;i<=last+1;i++）

{

L.getData（i,value）;

data[i-1]=value;

}

}

template

voidSeqList:

:

reSize（intnewSize）

{

if（newSize<=0）

{

cerr<<"无效的数组大小"<

return;

}

if（newSize!

=maxSize）

{

T*newarray=newT[newSize];

if（newarray==NULL）

{

cerr<<"存储分配错误！

"<

exit

（1）;

}

intn=last+1;

T*srcptr=data;

T*destptr=newarray;

while（n--）

*destptr++=*srcptr++;

delete[]data;

data=newarray;

maxSize=newSize;

}

}

template

intSeqList:

:

Search（T&x）const

{

for（inti=0;i<=last;i++）

if（data[i]=x）

returni+1;

else

return0;

}

template

intSeqList:

:

Locate（inti）const

{

if（i>=1&&i<=last+1）

returni;

else

return0;

}

template

boolSeqList:

:

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

boolSeqList:

:

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

voidSeqList:

:

Sort（）

{

intt,n=last;

for（inti=0;i

{

for（intj=0;j

if（data[j]>data[j+1]）

{

t=data[j];

data[j]=data[j+1];

data[j+1]=t;

}

}

}

template

voidSeqList:

:

input（）

{

intnum;

cout<<"开始建立顺序表，请输入表中元素个数：

";

while

（1）

{

cin>>num;

last=num-1;

if（last<=maxSize-1）

break;

cout<<"表元素个数输入有误，范围不能超过"<

";

}

cout<<"请输入表各元素的值：

"<

for（inti=0;i<=last;i++）

{

cout<

";

cin>>data[i];

}

cout<

}

template

voidSeqList:

:

output（）

{

cout<<"顺序表当前元素最后位置为：

"<

for（inti=0;i<=last;i++）

cout<<"#"<

"<

}

template

SeqListSeqList:

:

Union（constSeqList&La,constSeqList&Lb）

{

intn=0;

last=La.Length（）+Lb.Length（）-1;

if（maxSize

reSize（La.Size（）+Lb.Size（））;

Tvalue;

for（inti=1;i<=La.Length（）;i++）

{

La.getData（i,value）;

data[n]=value;

n++;

}

for（intj=1;j<=Lb.Length（）;j++）

{

Lb.getData（j,value）;

data[n]=value;

n++;

}

Sort（）;

return*this;

}

#endif

#include

#include"SeqList.h"

voidmain（）

{

SeqListList1（50）,List2（30）;

inta[]={1,23,234,322,12,34,54,3123,3,23,213,32};

intb[]={123,234,123,23,243,54,67,6,56,86,5,23};

for（inti=0;i

List1.Insert（i,a[i]）;

for（intj=0;j

List2.Insert（j,b[j]）;

List1.Sort（）;

List2.Sort（）;

SeqListList3;

List3.Union（List1,List2）;

cout<<"合并List1与List2后经过从小到大排序的顺序表为:

"<

List3.output（）;

}

【实验过程】

1、程序编写过程不断思考，总结和请教同学，最终确定出来了最后的结果。

2、调试时遇到的主要问题及解决遇到的主要问题：

没有把找到的位置用一个变量记下，解决方法：

通过请教老师和同学。

3、运行结果（输入及输出，可以截取运行窗体的界面）

【实验体会】

通过这次试验我基本掌握了顺序表的建立和使用，初步理解了顺序表的构建原理，并且可以将两个顺序表进行合并，以及掌握了顺序表的排序工作。