线性表的顺序存储及解决约瑟夫问题.docVIP

线性表的顺序存储一、 实验目的1. 掌握线性表的顺序存储结构。2. 能熟练地利用顺序存储结构实现线性表的基本操作。3. 能熟练地掌握顺序存储结构中算法的实现。二、 实验内容1. 建立含有若干个元素的顺序表，并将结果在屏幕上输出。2. 对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。3. 解决约瑟夫问题：假设有n个人按1、2、3、n的顺序围成一圈，现在，从第s个人开始按1、2、3、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用顺序表解决这个问题。三、 算法描述1. 第1题、第2题的算法提示对第1题，先定义顺序表的数据类型，然后以1n的序号建立顺序表，将输出结果单独定义成一个函数，以便后面反复使用它。对第2题，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。2. 第3题的算法提示对于第3题，可以将n个人的编号存入一个一维数组中，表的长度就是人数n，因此，就可以用一维数组来代替顺序表。算法的思想是：先求出出圈人的编号，用一个临时单元保存它，然后从出圈人的后一个开始，直到最后一个，都按顺序向前移动一个位置，再将临时单元中的出圈人编号存入最后。当这个重复步骤完成后，数组中存放的是出圈人的逆序列。本题中，围圈的人数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(int i, int x); /插入操作void Delete(int i); /删除操作void PrintList(); /输出结果private:int dataMaxSize;int length;List:List(int a,int n)if(nMaxSize)cout参数非法endl;for(int i=0;in;i+) datai=ai;length=n;int List:Get(int i)if(ilength)cout查找位置非法endl;else cout该位置元素值为：datai-1endl; return 0;int List:Locate(int x)for(int i=0;ilength;i+)if(datai=x)cout该值元素的位置为：i+1=MaxSize)cout上溢endl;if(ilength+1)cout位置非法=i;j-)dataj=dataj-1;datai-1=x;length+;void List:Delete(int i)if(length=0)cout下溢endl;if(ilength)cout位置 非法endl;int x=datai-1;for(int j=i;jlength;j+)dataj-1=dataj;length-;coutxendl;void List:PrintList()for(int i=0;ilength;i+)coutdataiendl;int main()int b10=0,1,2,3,4,5,6,7,8,9;List c(b,10);int d,e,f,g,h;cout原顺序表为：endl;c.PrintList();coutd;c.Get(d);coute;c.Locate(e);coutfg;c.Insert(f,g);cout插入数据后的顺序表为：endl;c.PrintList();couth;c.Delete(h);cout删除数据后的顺序表为：endl;c.PrintList();return 0;程序运行结果：原顺序表为：0 1 2 3 4 5 6 7 8 9请输入要查找的位置：3该位置的元素值为 ：2请输入要查找的元素值：6该元素的位置为：7请输入要插入的位置f和元素值g：5 7插入数据后的顺序表为： 0 1 2 3 7 4 5 6 7 8 9请输入待删元素的位置h：6删除数据后的顺序表为：0 1 2 3 7 5 6 7 8 9第三题的源程序及程序清单#include using 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) cout参数非法endl;for(int i=0;in;i+)datai=ai;length=n;/查找待出圈的编码int List:get(int i)int x=datai-1;for(int j=i;jlength;j+)dataj-1=dataj;length-;return x;int main()int a10=1,2,3,4,5,6,7,8,9,10; int b10;List L(a,10);int s, m, n;couts;coutm;/实现约瑟夫循环for(int i=0;i=n) bi=L.get(n); else n=n%L.Length(); bi=L.get(