《数据结构实验一线性表操作.docx》由会员分享，可在线阅读，更多相关《数据结构实验一线性表操作.docx（6页珍藏版）》请在三一办公上搜索。
1、数据结构实验一线性表操作中国矿业大学计算机科学与技术系试验报告 课程名称 _数据结构_ 试验名称_线性表操作_ 班级_信息安全08-1_ 姓名_ _ 学号_ 仪器组号_ 实验日期_09-11-18_ 实验报告要求：1.实验目的 2.实验内容 3.实验步骤 4.程序清单 5.运行结果 6.流程图 7.实验体会 一、实验目的： 1、并掌握线性表的逻辑结构、物理结构。 2、并掌握顺序表的存储结构、基本操作和具体的函数定义。 3、VC+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。 4、悉VC+操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。 二、实验要
2、求： 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作为输入数据，检查你的程序的正 确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusC
3、ircle类，其中含完成初始化、报数出圈成 员函数、输出显示等方法。 加强题： 采用数组作为求解过程中使用的数据结构。 提高题： 采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入 n = 0 退出程序。 四、程序清单 基本题: #include #include #include const LIST_INIT_SIZE=10; const LISTINCREMENT=1; typedef struct int *elem; int length; int listsize; SqList; void InitList_sq(SqList&L) /构造一个空
4、的线性表L L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int); if(!L.elem) exit(0); /存储分配失败 L.length=0; /空表长度为0 L.listsize=LIST_INIT_SIZE; /初始存储容量 coutOK!endl; void ListInsert_Sq(SqList&L,int i,int e) /在顺序线性表L中第i个位置之前插入新的元素e， /i的合法值为1=i=ListInsert_Sq(L)+1 if(iL.length+1) /i值不合法 coutERROR!=L.listsize) /当前存储空间
5、已满，增加分配 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_Sq void ListDelete_S
6、q(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; /表长减1 coutOK!endl; /ListDelete_Sq bool compare(in
7、t m,int n) if(m=n) return true; else return false; int LocateElem_Sq(SqList L,int e) /在顺序线性表L中查找第1个值与e满足compare的元素的位序 /若找到，则返回其在L中的位序，否则返回0 int 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_Sq void disp(Sq
8、List&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输入错误！
9、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; else coutj+1出局endl; return (j+1); void main int n,s,m,y=0; int x; do for(int i=0;i100;i+) ai=0; cout请输入人游戏总
10、人数：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 JosephusCircle int n; int s; int m; public: JosephusCirclen=1;s=1;m=1; JosephusCircle(int n1,int s1,int m1):n(n1),s(s1),m(m1)cout初始化结束！endl;
11、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; else int 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=-
12、1; x=1; y-; if(!y) break; else coutj+1出局endl; return (j+1); /else return 0; void main int n,s,m,y=0; int x; do for(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; 五、运行结果 六、实验体会 线性链表和顺序表都属于线性表，但是线性链表比顺序表灵活，方便；但是，线性表在做元素寻找的操作的时候，必须从头结点开始寻找。 在编程序的时候，我们肯定会遇到许多问题：就像我就遇到一个问题，那就是：当我在运行程序的时候，输入一个元素后就不继续做下面的操作也不停止运行，我自己做了好久都没发现问题，后来实在没办法，我就问同学，最后终于发现有一条语句错误，所以写的时候我们要仔细点。 教师评价 优 良 中 及格 不及格 教师签名 日期
