作为抽象数据类型数组的类声明

《作为抽象数据类型数组的类声明》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章数组第2章数组作为抽象数据类型数组的类声明。#include//在头文件“array.h”中#includeconstintDefaultSize=30;templateclassArray{//数组是数据类型相同的n（size）个元素的一个集合,下标范围从0到n-1。对数组中元素//可按下标所指示位置直接访问。private:Type*elements;//数组intArraySize;//元素个数public:Array(intSize=DefaultSize);//

2、构造函数Array(constArray&x);//复制构造函数~Array(){delete[]elements;}//析构函数Array&operator=(constArray&A);//数组整体赋值(复制)Type&operator[](inti);//按下标访问数组元素intLength()const{returnArraySize;}//取数组长度voidReSize(intsz);//修改数组长度}顺序表的类定义#include//定义在头文件“seqlist.h”中#

3、includetemplateclassSeqList{private:Type*data;//顺序表的存放数组intMaxSize;//顺序表的最大可容纳项数intlast;//顺序表当前已存表项的最后位置intcurrent;//顺序表的当前指针（最近处理的表项）public:SeqList(intMaxSize);//构造函数~SeqList(){delete[]data;}//析构函数intLength()const{returnlast+1;}//计算表长度intFind(Type&x)co

4、nst;//定位函数:找x在表中位置，置为当前表项intIsIn(Type&x);//判断x是否在表中，不置为当前表项Type*GetData(){returncurrent==-1？NULL:data[current];}//取当前表项的值intInsert(Type&x);//插入x在表中当前表项之后，置为当前表项intAppend(Type&x);//追加x到表尾，置为当前表项Type*Remove(Type&x);//删除x，置下一表项为当前表项Type*First();//取表中第一个表项的值，置为当前表项20第2章数组Type*N

5、ext(){returncurrent0?&data[--current]:NULL;}//取当前表项的前驱表项的值，置为当前表项intIsEmpty(){returnlast==-1;}//判断顺序表空否,空则返回1;否则返回0intIsFull(){returnlast==MaxSize-1;}//判断顺序表满否,满则返回1;否则返回0}2-1设n个人围坐在一个圆桌周围，现在从第s个人开

6、始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。2-2试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5，以及n=

7、9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下：voidJosephus(intA[],intn,s,m){inti,j,k,tmp;if(m==0){cout<<"m=0是无效的参数！"<1;i--){/*逐个出局，执行n-1次*/if(i==k)i=0;i=(i+m-1)%k;/*寻找

8、出局位置*/if(i!=k-1){tmp=A[i];/*出局者交换到第k-1位置*/for(j=i;j