资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
线性表的顺序存储一、实验目的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)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;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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号