数据结构_实验一_线表操作.doc

中国矿业大学计算机科学与技术系试验报告课程名称 _数据结构_ 试验名称_线性表操作_班级_信息安全08-1_ 姓名_ _ 学号_ 仪器组号_ 实验日期_09-11-18_实验报告要求：1.实验目的 2.实验内容 3.实验步骤 4.程序清单5.运行结果 6.流程图 7.实验体会一、实验目的：1、并掌握线性表的逻辑结构、物理结构。2、并掌握顺序表的存储结构、基本操作和具体的函数定义。3、VC+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。4、悉VC+操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。二、实验要求：1 实验之前认真准备，编写好源程序。2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3 不断积累程序的调试方法。三、实验内容基本题:1 对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。加强、提高题：2、编写一个求解Josephus问题的函数。用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正 确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusCircle类，其中含完成初始化、报数出圈成 员函数、输出显示等方法。（可以选做其中之一）加强题：（1）采用数组作为求解过程中使用的数据结构。提高题：（2）采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入 n = 0 退出程序。 四、程序清单基本题:#include#include#includeconst LIST_INIT_SIZE=10;const LISTINCREMENT=1;typedef structint *elem;int length;int listsize;SqList;void InitList_sq(SqList&L)/构造一个空的线性表LL.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem)exit(0);/存储分配失败L.length=0;/空表长度为0L.listsize=LIST_INIT_SIZE;/初始存储容量coutOK!endl;void ListInsert_Sq(SqList&L,int i,int e)/在顺序线性表L中第i个位置之前插入新的元素e，/i的合法值为1=i=ListInsert_Sq(L)+1if(iL.length+1)/i值不合法coutERROR!=L.listsize)/当前存储空间已满，增加分配int *newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);/存储分配失败L.elem=newbase;/新基址L.listsize+=LISTINCREMENT;/增加存储容量int *q=&(L.elemi-1);for(int*p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;coutOK!endl;/ListInsert_Sqvoid ListDelete_Sq(SqList&L,int i,int&e)/在顺序线性表L中删除第i个元素，并用e返回其值/i的合法值为1=i=ListInsert_Sq(L)if(iL.length)coutERROR!endl;/i值不合法int *p=&(L.elemi-1);/p为被删除元素的位置e=*p;/被删除元素的值赋给e int *q=L.elem+L.length-1;/表尾元素的位置for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1coutOK!endl;/ListDelete_Sqbool compare(int m,int n)if(m=n)return true;elsereturn false;int LocateElem_Sq(SqList L,int e)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序/若找到，则返回其在L中的位序，否则返回0int i=1;/i的初值为第1个元素的位序int *p=L.elem;/p的初值为第1个元素的存储位置while(i=L.length&!compare(*p+,e)+i;if(i=L.length)return i;else return 0;/LocateElem_Sqvoid disp(SqList&L)int *p=L.elem;for(int i=0;iL.listsize;i+)cout*pt;p+;void main()SqList List;InitList_sq(List);int *p=List.elem;for(int i=0;iList.listsize;i+)*p=i+1;p+;coutendl;disp(List);coutendl;getch();加强：#include #include #include int a100;int josephus(int n,int s,int m)if(!(n*s*m)cout输入错误！endl;exit(0);int x=1,y=n;int i=s-1;int j;while(y)for(;in;i+)if(ai+1)ai=x+;if(ai=m)ai=-1;couti+1出局endl;x=1;y-;for(j=0;jn;j+)if(aj+1)aj=x+;if(aj=m)aj=-1;x=1;y-;if(!y)break;elsecoutj+1出局endl;return (j+1);void main()int n,s,m,y=0;int x;dofor(int i=0;i100;i+)ai=0;cout请输入人游戏总人数：n;cout请输入开始人位置与报数长度：s;cinm;x=josephus(n,s,m);coutx胜出endl;cout请选择：endl;cout1,重新游戏; 2,退出程序：y;while(y=1);getch();提高题：#include #include int c100;class JosephusCircleint n;int s;int m;public:JosephusCircle()n=1;s=1;m=1;JosephusCircle(int n1,int s1,int m1):n(n1),s(s1),m(m1)cout初始化结束！endl;friend int josephus(JosephusCircle& a);int josephus(JosephusCircle& a)if(!(a.m*a.n*a.s)|(a.m=a.s&a.m=a.n&a.n=1)cout输入错误！endl;elseint x=1,y=a.n;int i=a.s-1;int j;while(y)for(;ia.n;i+)if(ci+1)ci=x+;if(ci=a.m)ci=-1;couti+1出局endl;x=1;y-;for(j=0;ja.n;j+)if(cj+1)cj=x+;if(cj=a.m)cj=-1;x=1;y-;if(!y)break;elsecoutj+1出局endl;return (j+1);/elsereturn 0;void main()int n,s,m,y=0;int x;dofor(int i=0;i100;i+)ci=0;cout请输入游戏总人数：n;cout请输入开始人位置与报数长度：s;cinm;JosephusCircle b(n,s,m);x=josephus(b);if(x)coutx胜出endlendl;cout请选择：endl;cout1,重新游戏; 2,退出程序：y;while(y=1);getch();五、运行结果六、实验体会 线性链表和顺序表都属于线性表，但是线性链表比顺序表