《线性表的顺序存储及解决约瑟夫问题》由会员分享，可在线阅读，更多相关《线性表的顺序存储及解决约瑟夫问题（7页珍藏版）》请在金锄头文库上搜索。
1、线性表的顺序存储一、实验目的1. 掌握线性表的顺序存储结构。2. 能熟练地利用顺序存储结构实现线性表的基本操作。3. 能熟练地掌握顺序存储结构中算法的实现。二、实验内容1. 建立含有若干个元素的顺序表，并将结果在屏幕上输出。2. 对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。3. 解决约瑟夫问题：假设有 n 个人按 1、2、3 、n 的顺序围成一圈，现在，从第s个人开始按 1、2、3 、m 的顺序报数，数到 m 的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用顺序表解决这个问题。三、算法描述1. 第 1 题、第 2 题的算法提示对第 1 题，先定义顺序
2、表的数据类型，然后以 1n 的序号建立顺序表，将输出结果单独定义成一个函数，以便后面反复使用它。对第 2 题，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。2. 第 3 题的算法提示对于第 3 题，可以将 n 个人的编号存入一个一维数组中，表的长度就是人数 n，因此，就可以用一维数组来代替顺序表。算法的思想是：先求出出圈人的编号，用一个临时单元保存它，然后从出圈人的后一个开始，直到最后一个，都按顺序向前移动一个位置，再将临时单元中的出圈人编号存入最后。当这个重复步骤完成后，数组中存放的是出圈人的逆序列。本题中，围圈的人
3、数 n、出圈的报数号 m、开始报数的位置 s 在程序中预先给定为10、 3、2。当然，也可以从键盘临时输入。四、源程序第 1、2 题的源程序及程序清单#includeusing namespace std;const int MaxSize=100;class Listpublic:List()length=0; / 建立一个空表List(int a, int n); /建立一个长度为n的顺序表List()int Length()return length; /求线性表的长度int Get(int i); /按位查找int Locate(int x); /按值查找 void Insert(in
4、t i, int x); /插入操作void Delete(int i); /删除操作void PrintList(); /输出结果private:int dataMaxSize;int length;List:List(int a,int n)if(nMaxSize)coutlength)cout=MaxSize)coutlength+1)cout=i;j-)dataj=dataj-1;datai-1=x;length+;void List:Delete(int i)if(length=0)coutlength)coutd;c.Get(d);coute;c.Locate(e);coutfg;
5、c.Insert(f,g);couth;c.Delete(h);coutusing namespace std;const int MaxSize=100;class Listpublic:List()length=0;List(int a, int n);List()int get(int i); int Length()return length;public:int dataMaxSize;int length;/构造函数List:List(int a, int n)if(nMaxSize)couts;coutm;/实现约瑟夫循环for(int i=0;i=n)bi=L.get(n);else n=n%L.Length();bi=L.get(n);s=n;/输出出圈顺序cout出圈的顺序为：endl;for(int k=0;k10;k+)coutbkendl;return 0;程序运行结果：请输入开始报数的编码：2请输入待出圈报数的编码：7出圈的顺序为：8 5 3 2 4 7 1 6 9 10
