实验一线性表操作实验报告

1、中国矿业大学计算机学院实验报告课程名称数据结构实验名称_线性表操作实验报告要求:1.实验目的2.实验内容3.实验步骤4.运行结果5.流程图6.实验体会、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。精品文档，你值得期待2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。3熟悉VC+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关 系及各自的作用。4熟悉VC+操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。优质文档放心阅读二、实验要求1实验之前认真准备，编写好源程序。2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。 3不断积累程序的调

2、试方法。三、实验内容基本题：1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。源程序：#in clude#in clude#in cludeconst LIST_INIT_SIZE=10;const LISTINCREMENT=1;typedef structint *elem;int len gth;int listsize;SqList;void InitList Sq(SqList&L)/ 构造一个空的线性表LL.elem=(i nt*)malloc(LIST_INIT_SIZE*sizeof(i nt);/在顺序线性表L中第i个位置之前插入新的元素j,/i 的合法值为 1=

3、i=ListInsert_Sq(L)+1if(!L.elem)exit(0);L.le ngth=O;L.listsize=LIST_INIT_SIZE; coutOK!e ndl; void ListI nsert_Sq(SqList&L,i nt i,i nt j)if(iL.le ngth+1) coutERROR!=L .li stsize)/存储分配失败/空表长度为0/初始存储容量/i值不合法/当前存储空间已满，增加分配in t *n ewbase=(i nt*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(i nt); if(!n

4、 ewbase)exit(0);/存储分配失败L.elem=newbase;/ 新基址L.listsize+=LISTINCREMENT;/ 增加存储容量int *q=&(L.elemi-1);for(i nt*p=&(L.elemL.le ngth-1);p=q;-p)*(p+1)=*p;*q=j;+L .len gth; coutOK!e ndl;/Listl nsert_Sqvoid ListDelete_Sq(SqList&L,int i,int&j)if(iL.le ngth) coutERROR!e ndl;int *p=&(L.elemi-1);j=*p;int *q=L.ele

5、m+L .len gth-1;for(+p;p=q;+p) *(p-1)=*p;-L.listsize;coutOK!e ndl;/ListDelete_Sq/在顺序线性表L中删除第i个元素，并用j返回其值/i 的合法值为 1=i=ListInsert_Sq(L)/i值不合法/p为被删除元素的位置/被删除元素的值赋给j/表尾元素的位置/被删除元素之后的元素左移/表长减1bool compare。nt m,i nt n) if(m=n)return true;elsereturn false;/在顺序线性表L中查找第1个值与j满足compare()/若找到，则返回其在 L中的位序，否则返/i的初

6、值为第1个元素的位序/p的初值为第1个元素的存储位置int LocateElem_Sq(SqList L,i nt j) 的元素的位序回0int i=1;int *p=L.elem;while(i=L .len gth&!compare(*p,j) +i;p+;if(i=L .len gth)return i;elsereturn 0;/LocateElem_Sq void disp(SqList&L)int *p=L.elem;for(i nt i=0;iL .li stsize;i+) cout*p;p+; void mai n()SqList List;In itList_Sq(List

7、);int *p=List.elem;int m, n,j,k,x,y;for(i nt i=0;i x;*p=x;P+；List.le ngth+;cout插入请按1 ;删除请按2;寻找请按3endl; for(k=0;k=10;k+)ciny;if(y=1)cout请输入插入位置和元素的值:e ndl;cinmn;List In sert_Sq(List,m ,n); disp(List);else if(y=2)cout请输入要删除第几个元素:e ndl; cinm;ListDelete_Sq(List,m,j);coutje ndl; disp(List);elsecout请输入所要查

8、找的元素:e ndl;cinm;coutLocateElem_Sq(List,m)e ndl;coute ndl;运行结果:E -E八学习文flA赣据结枸l究蛙一、实蛙i-IU矗隅、案艘l lee慣输入所要査找的元素；加强、提高题: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 类，其中

9、含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）加强题：1采用数组作为求解过程中使用的数据结构。提高题:2、采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。源程序：(1)加强：#in clude #in elude #in elude nt a100;nt josephus(i nt n ,i nt s,i nt m) if(!( n*s*m)cout输入错误!endl; exit(0);int x=1,y=n;int i=s-1;int j;while(y)for(i=0;i n ;i+)if(ai+1)ai=x+;

10、if(ai=m)ai=-1;couti+1出局!endl;x=1;y-;for(j=0;j n;j+)if(aj+1)aj=x+;if(aj=m)aj=-1;x=1;y-;if(!y)break;elsecoutj+1出局!endl;return (j+1);void mai n()int n,s,m,y=0;int兀dofor(i nt i=0;i100;i+)ai=0;cout请输入参加游戏的总人数:e ndl;cinn;cout请输入开始人的位置与报数长度: s; cinm;x=josephus (n, s,m);coutx胜出!endl; cout请选择:endl;cout1.重新游戏

11、。2.退出程序。:e ndl;ciny;while(y=1);getch();运行结果：回八学习文fK数据结构实鲨一实鑿17 （加强）DebugSfe 1-2 OWSO - exe-(2)提高：#in clude using n amespace std;typedef struct LNodestruct LNode *n ext;int a;LNode,*Li nkList;class JosephouCircle /定义一个类包括三个元素 public:void SetValue();void PickOut();private:int n;int s;int m;void Joseph

12、ouCircle:SetValue()/ 设置初值的大小cout请输入参加游戏的总人数:e ndl;cinn;cout请输入开始人的位置 : s;cout请输入报数长度: next=NULL;LNode*r;r=L;for (int i=1;ia=i;p- next=NULL;r-n ext=p;r=p;p-n ext=L-n ext;p=L-n ext;j=1;while(p&jn ext;+j;for(i=1;i=n ;i+)for(j=1;jn ext;q=p-n ext;p-n ext=q _n ext;p=q _n ext;k=q_a;cout输出的结果为:kendl; free(q

13、);int main (i nt argc,char* argv)JosephouCircle Jo1;Jo1.SetValue();Jo1.PickOut();return 0;运行结果：S3 取、学习文件*数据结构实鲨一实验1-2儂高八DMugh实验1-2 提高）-eze0 2 1 t 163112598417 畳 M * * W ! W * W _ n”- mN 日7 n”- ml? mf-r n”- 11= m; R1L- 11= ml? _T-三UTT孚-匕了身克身身芽戶琴y 士口士口-HET士口士口士口士口士口虫口士口士口士口 n 一舟一-+!- 一建一绘w-f 一 空一绘w-土应

14、一 a 肉阳肉肉阳 肉肉 阳肉自阳 afanj- T s 出出出出出出出出出出岀出continue入参加游戏的总入数 主输入开始人的位置： I输入按数长度：四、实验体会与总结1、对于线性链表和顺序表都属于线性表问题，但是线性链表比顺序表要灵活，方便;2、线性表在做元素寻找的操作的时候，必须从头结点开始寻找。体会：在编程序的时候，我们每个人肯定会遇到许多问题，我遇到的问题是：当我在运行程序的时候，在输入一个元素后，程序就不继续做下面的操作也不停止运行，自己寻找并修改了 好久都没发现问题的所在， 最后实在没办法，就去问同学，结果终于发现是一条语句在编写 时出现了错误。所以，以后再写程序的时候我一定

15、要再认真仔细一点仔细点。教师评价优良中及格不及格教师签名日期想来生活，从来就不是阳春白雪的神话。光阴的陌上，总有风自八方来，或许是忧凄，也许是欢喜，无论怎样，都是岁月最真的馈赠。待到老去的那一日，偶尔有回忆念及了过往，依旧还会有初初的心动，流转了眉眼。而那一路迤逦而来的美好，一步一步写就两个梅花小楷一一日常。暖阳小窗，无事此静坐。杯盏光阴，又在指间如风轻过，回首，依稀还是那年秋，低低一低眉，却已是春光葳蕤。光阴荏苒，而流年从来也不曾缺少错乱和犹疑。是否在这样一个万物复苏的季节里，一切的纷扰是非，终究会给出一个水落石出的答案。轻倚初春的门楣，且把盏清风，问心明月，让来者可来，去者可去，宿命里的拥有，一一欣喜悦纳。而我也只需以花香绕肩的美，步履从容的，走过生命里的山山水水。若说，那一程走旧的时光，已然温暖了我的眉眼。那么，在明日那个花满枝桠的清晨，我依旧愿意轻踮了脚尖，重行