空间数据结构基础实验指导书

1《空间数据结构基础》课程实习指导书实习周数：2周学分数：2一、实习目的数据结构是一门重要的专业基础课，其特点是理论与实践都占据着极其重要的位置。这门课对学生的主要要求包括要掌握各种基本数据结构的定义、抽象数据类型描述、相关的算法描述与算法的性能分析与评价，以及数据结构与算法的综合应用能力。为了达到教学要求，以上机实验为主要形式的实践教学环节是不可缺少的。上机实验的主要内容可分为两种，一是验证经典算法和教材中的算法例程，二是设计并检验自己设计的算法，课程中的16课时的上机实验主要是以前者为目的，而为期2周的课程实习则以后者为目的。通过课程实习可以帮助学生正确理解所学概念，了解不同的算法特点，掌握算法性能，积累算法设计经验。教学经验表明，学生只有通过一定时间量的算法设计和程序调试等实践活动，才能较全面和较深入地掌握数据结构的知识，在此基础上，发挥学生的想象力和创造力，设计出新颖多样的有应用价值的算法。二、实习要求1.通过实习，学生能够对所学的每一种数据结构正确理解，能够针对不同的问题选择合适的数据结构，在程序中将抽象数据类型实例化。2.深刻理解典型算法的设计思想，掌握不同算法在解题策略和流程控制逻辑等方面的不同特点和实现方法。再进一步总结并掌握计算机处理数据和解决问题的一般规律，从而能够自行设计应用算法。3.学会对算法进行性能评价和分析，比较同一个问题的多种解法，针对具体问题能够设计出高效的算法。4.提高学生进行程序设计的综合能力，使其从初学者进阶到较有经验和专业素质的程序设计者。5．要求学生严格遵守实习纪律，认真开发，按时提交实习报告。三、实习内容参见“六、实习内容简介”中每章的“二、程序设计练习”和第4章的练习。根据个人情况任选3~5题予以完成。四、实习内容的时间分配先集中1天左右时间对实习的安排，实习分组，实习要求等作出部署，并分项讲解不同实习项目的要求；针对不同的实习项目，学生用2天左右的时间进行资料查询和开发方案设计；方案和数据结构设计完成后，利用5天左右时间进行程序编码、调试和优化，最后利用2天左右时间进行汇报讨论和提交实习报告。五、成绩评定本实习采取考核方式，以实习教学所占总成绩的比例为100，其中上机操作占20％，实习纪律占20％，实习报告占60％。实验成绩折算成优、良、中、及格、不及格五个等级进行评分。2六、实习内容简介第1章C++面向对象程序设计基础本章实验目的：学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。熟练掌握C++程序的编制、调试和运行方法，为本课程的实验做好准备。学习重点：理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。一、C++面向对象程序设计范例1.二维坐标点point的C++描述【实验目的】用面向对象的方法定义一个简单的抽象数据结构，本例实验内容为坐标点的数据结构。学会如何用C++语言描述数据结构和算法，理解将数据集和在此数据集上的操作分开描述的方法。【数据结构】将坐标点数据结构定义为一个C++类Point，在其内部分别定义数据成员和成员函数。(1)数据成员：一个平面直角坐标系中的点有两个属性，它们是x轴上的水平坐标值和y轴上的垂直坐标值。在Point类中，这两个属性分别由数据成员x和y来表示，定义为double类型的私有数据成员。(2)操作方法：定义成员函数，为类的使用者提供服务接口。先设计允许对点对象进行的操作，再用C++描述实现操作的算法，并定义为类Point的成员函数。在本例中提供了两个操作：move()函数将一个Point对象移至另一位置，Show()函数输出Point对象的数据成员值。两个构造函数，分别用于建立缺省参数的对象和带参数的对象。【算法提示】缺省构造函数Point()将新建立的坐标点对象初始化为原点位置(０,０)。带参数的构造函数Point(doublepx,doublepy)允许用户建立对象时指定初始坐标位置。点对象的移动操作move()函数需要在调用时给出新位置参数。输出坐标值为无参函数。以下是平面直角坐标系中的点的类定义，main()函数对类Point的属性和操作进行测试。【程序1.1】#includeiostream.hclassPoint{//平面直角坐标系中的点private:doublex;//水平坐标值doubley;//垂直坐标值public:Point(){x=0;y=0;}//缺省构造函数3Point(doublepx,doublepy){x=px;y=py;}//带参数的构造函数voidmove(doublemx,doublemy){x=mx;y=my;}//移动位置(修改坐标值)voidShow(){coutx=x''y=yendl;}//输出坐标值};voidmain(){Pointa,b(12.5,34.8);//建立两个Point对象cout点a的位置：;a.Show();//输出点a的坐标值cout点b的位置：;b.Show();//输出点b的坐标值a.move(45.6,57.8);cout点a移动后的位置：;a.Show();//输出点a的坐标值}2.使用模板建立坐标点point的数据结构，直接表示抽象数据类型【实验目的】将程序1.1数据结构的类型参数化（模板），实现更高层次的数据抽象。【算法提示】Point的数据成员不使用固定的类型定义，而是用typename说明的虚拟类型名ptType作为变量的类型，在定义Point类的对象时，再用C++的基本类型将对象的数据成员的类型实例化。这样做的好处是可以使用同一个类来定义不同数据类型的对象，提高代码的利用率。【程序1.2】templatetypenameptTypeclassPoint{//平面直角坐标系中的点private:ptTypex;//虚拟类型的水平坐标值ptTypey;//虚拟类型的垂直坐标值public:Point(){x=0;y=0;}//缺省构造函数Point(ptTypepx,ptTypepy){x=px;y=py;}//带参数的构造函数voidmove(ptTypemx,ptTypemy){x=mx;y=my;}//移动位置(修改坐标值)voidShow(){coutx=x''y=yendl;}//输出坐标值};voidmain(){Pointinta(24,36);//建立整型的Point对象Pointfloatb(12.5,34.8);//建立浮点型的Point对象cout点a的位置：;a.Show();//输出点a的坐标值cout点b的位置：;b.Show();//输出点b的坐标值a.move(25,18);cout点a移动后的位置：;4a.Show();//输出点a的坐标值b.move(45.6,57.8);cout点b移动后的位置：;b.Show();//输出点b的坐标值}注：定义模板的关键字typename可以用class代替。如：templateclassptTypeclassPoint与例中的templatetypenameptTypeclassPoint具有相同功能。3.利用Point类定义矩形类Rectangle【实验目的】了解复合数据结构的描述方法。矩形是一个包含坐标点的复合数据结构，在C++程序中将坐标点和矩形分别定义为具有继承关系的两个类，即定义矩形类Rectangle为Point的派生类。使用派生类的形式定义一个数据结构，其主要目的是提高基类的代码利用率，并使派生类的结构得到简化。基类和派生类的定义体现了C++继承机制的运用，最大程度地提高了数据结构的利用率。【数据结构】派生的矩形类Rectangle有四个数据成员，其中左下角坐标点x和y由基类Point定义，派生类Rectangle能够继承下来作为自己的数据成员。为了在派生类的成员函数中自由访问基类定义的数据成员，需要将这些数据成员定义为被保护的（protected）访问权限。矩形的宽度width和高度height在派生类中定义。在矩形类中这四个数据成员的访问权限是相同的。【算法提示】(1)基类Point定义的成员函数都可以由派生类Rectangle继承，在矩形对象中可以直接使用。(2)若用一个点对象为新的矩形对象初始化，注意构造函数的写法。对基类成员的赋值由基类的拷贝构造函数完成，例如利用点对象p3定义的矩形对象rt4，实际上使用了Point类的缺省拷贝构造函数。如果基类成员初始化比较复杂，如含有内存分配等要求，就需要重新定义基类的拷贝构造函数。【程序1.3】#includeiostream.hclassPoint{//二维坐标点类protected:doublex,y;public:Point(){x=0;y=0;}//缺省构造函数Point(doublepx,doublepy){x=px;y=py;}//带参数的构造函数doubleGetx(){returnx;}//返回坐标点的x值doubleGety(){returny;}//返回坐标点的y值voidMove(doublemx,doublemy){x=mx;y=my;}//移动坐标点的位置voidShow(){coutx=x''y=yendl;}//输出坐标点的属性值};classRectangle:publicPoint{//矩形类（Point的派生类，Point对象为矩形左下角的坐标点）doublewidth,height;//矩形的宽度和高度5public:Rectangle(){width=0;height=0;x=0;y=0;}//缺省构造函数Rectangle(doublea,doubleb,doublec,doubled):Point(a,b){//带参数的构造函数width=c;height=d;}Rectangle(Point&pn):Point(pn){//带参数的构造函数，由点pn定义矩形左下角的位置width=1;height=1;}doubleArea(){returnwidth*height;}//求矩形的面积voidSet(doublea,doubleb){x=a;y=b;}//重置矩形的左下角坐标intPosition(Point&pt);//求点pt相对于矩形的位置，返回-1(在矩形内),//0(在矩形边上)和1(在矩形外)voidJudge(Point&pt);//判断点pt相对于矩形的位置，给出提示voidShow();//输出矩形的各属性值和面积};intRectangle::Position(Point&pt){//求点pt相对于矩形的位置if(pt.Getx()x||pt.Getx()x+width||pt.Gety()y||pt.Gety()y+height)return1;//在矩形外elseif(pt.Getx()x&&pt.Getx()x+width&&pt.Gety()y&&pt.Gety()y+height)return-1;//在矩形内elsereturn0;//在矩形边上}voidRectangle::Judge(Point&pt){pt.Show();Show();switch(Position(pt)){case0:cout点在矩形边上endlendl;break;case-1:cout点在矩形内endlendl;break;case1:cout点在矩形外endlendl;break;}}voidRectangle::Show(){//输出矩形的各属性值和面积coutrx=x'\t'ry=