数据结构上机指导书第次上机实验指导书.doc

数据结构上机指导书第次上机实验指导书 第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(double px,double py)允许用户建立对象时指定初始坐标位置。 点对象的移动操作move()函数需要在调用时给出新位置参数。 输出坐标值为无参函数。 以下是平面直角坐标系中的点的类定义，main()函数对类Point的属性和操作进行测试。 【程序1.1】#includeclass Point/平面直角坐标系中的点private:double x;/水平坐标值double y;/垂直坐标值public:Point()x=0;y=0;/缺省构造函数Point(double px,double py)x=px;y=py;/带参数的构造函数void move(double mx,double my)x=mx;y=my;/移动位置(修改坐标值)void Show()coutx= 【算法提示】Point的数据成员不使用固定的类型定义，而是用typename说明的虚拟类型名ptType作为变量的类型，在定义Point类的对象时，再用C+的基本类型将对象的数据成员的类型实例化。 这样做的好处是可以使用同一个类来定义不同数据类型的对象，提高代码的利用率。 【程序1.2】templateclass Point/平面直角坐标系中的点private:ptType x;/虚拟类型的水平坐标值ptType y;/虚拟类型的垂直坐标值public:Point()x=0;y=0;/缺省构造函数Point(ptType px,ptType py)x=px;y=py;/带参数的构造函数void move(ptType mx,ptType my)x=mx;y=my;/移动位置(修改坐标值)void Show()coutx= 如templateclass Point与例中的templateclass Point具有相同功能。 第2章线性表本章实验目的认识容器类数据结构。 了解线性数据结构，掌握顺序存储和链式存储的两种线性表的建立和使用方法。 一、经典算法和例题1.顺序表的模板类【实验目的】本例给出了较完整的顺序表的抽象数据类型定义，通过C+模板的应用体现了数据抽象原理。 【问题描述】定义一个顺序存储的线性表数据结构，在应用程序（main函数）中建立一个整型的线性表对象，在该表中进行插入、删除、查找和输出等操作。 【数据结构】定义一个顺序存储的线性表类SeqList，数据成员包括表的存储数组，表的最大允许长度，表中最后元素下标和元素游标等。 定义常用的基本操作。 【算法提示】 (1)在表示顺序表的SeqList类定义中，表元素的存储空间是数组element，采用动态内存分配方式。 表的初始化工作由构造函数实现。 (2)顺序表的基本操作以公用接口形式（类的成员函数）提供。 一般顺序表最常用的操作是输出、插入、删除、查找和求表长度等，其中数据量较大的输出操作采用运算符重载的方式来实现，以便用户能以习惯的cout (2)在该数据结构中定义了一个整型数据成员current作为游标（也称为迭代子），它的作用是始终指示表中当前元素(最近处理的元素)的位置。 表初始化时current值为-1，以后每次遇对表元素的操作就将current值修改为被操作元素的下标。 游标的运用是C+标准模板库的重要组成部分，通过本实验可以深入理解这一概念。 【算法实现_程序2.1】#include#define DefaultSize20templateclass SeqListType*element;/顺序表的存储数组int MaxSize;/表的最大允许长度int last;/表中最后元素下标int current;/游标(迭代子)，指示表中当前元素(最近处理的元素)的位置，初始化为-1public:SeqList(int MaxSize=DefaultSize);/构造函数SeqList()deleteelement;/析构函数int Length()constreturn last+1;/计算顺序表的长度（元素个数）int Find(Type&x);/查找，返回表中第一个与x相等的元素的位置int IsIn(Type&x);/判断x是否在表中Type GetElem(int i)current=i;return ilast?NULL:elementi;/取第i个元素的值Type LocaElem()return current=-1?NULL:elementcurrent;/取当前元素的值int Insert(Type&x,int i);/插入x在表的第i个位置处，并置为当前位置int Append(Type&x);/在表尾添加元素x，并置为当前位置int Delete(Type&x);/删除表中第一个值为x的元素，返回该元素的位置Type First();/如果表不空返回表的第一个元素值Type Next()return current=0?element-current:NULL;/得到当前元素的前趋int IsEmpty()return last=-1;/判断顺序表是否为空，空则返回1，否则返回0int IsFull()return last=MaxSize-1;/判断顺序表是否满，满则返回1，否则返回0friend ostream&operator0)MaxSize=sz;last=-1;element=new TypeMaxSize;if(element=NULL)MaxSize=0;last=-1;current=-1;return;templateint SeqList:Find(Type&x)/查找函数在表中从前向后顺序查找x，若查找成功，/返回x在表中的位置，否则返回-1，当前指针置于表尾之后current=0;/int i=0;while(currentlast)return-1;else returncurrent;templateint SeqList:Insert(Type&x,int i)/插入x在表的第i个位置处，并置为当前位置。 函数返回否成功信息，成功为1，否则为0。 if(ilast+1|last=MaxSize-1)return0;elselast+;for(current=last;currenti;current-)elementcurrent=elementcurrent-1;elementi=x;return1;templateint SeqList:Append(Type&x)if(last=MaxSize-1)return0;current=+last;elementcurrent=x;return1;templateint SeqList:Delete(Type&x)/删除表中第一个值为x的元素，返回该元素的位置，未找到x时，返回-1。 int i=Find(x);if(i=0)last-;for(int j=i;j=last;j+)elementj=elementj+1;return i;return-1;templateType SeqList:First()/返回表的第一个元素值if(last=-1)return NULL;/如果表空返回NULL current=0;return element0;template/输出顺序表中的全部元素ostream&operator(ostream