中国矿业大学数据结构实验一.doc

中国矿业大学计算机科学与技术系试验报告课程名称 _数据结构_ 试验名称_线性表操作_班级 X班 姓名 XXX 学号XXXX 仪器组号_ 实验日期 实验报告要求：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 退出程序。 四、五 程序清单和运行结果1-1基本题:#include #include #define TRUE 1 #define FALSE 0 typedef struct LNode ElemType dataMAXSIZE;int length; /length为线性表的长度SqList; /线性表定义/1.初始化操作，将线性表L置空void InitList(SqList &L)L.length=0;/2.建立一个顺序存储的线性表void CreatSqlist(SqList &L,int n)int i;for(i=0;in;i+)scanf(%d,&L.datai);L.length=n;/3.输出顺序表Lvoid output(SqList L) int i;for(i=0;iL.length;i+)printf(%5d,L.datai);printf(n);/4.判空int IsEmpty(SqList L)if(L.length=0)printf(此列表为空);elseprintf(此列表非空);return 0;/5.定位函数int LocateElem(SqList L,ElemType x)int k=0;while(kL.length&L.datak!=x)k+;if(kL.length)return k;elsereturn -1;/6.插入元素int Insert(SqList &L,ElemType x,int i)int k;if(iL.length|L.length=MAXSIZE)return 0;elsefor(k=L.length;k=i;k-) L.datak=L.datak-1;L.datai=x;L.length=L.length+1;return 1;/7.删除元素int Delete(SqList &L,int i)int k;if(iL.length)return 0;else for(k=i;kL.length;k+) L.datak=L.datak+1; L.length-;return 1; void main()SqList List; /构造线性表InitList(List); /置空printf(please input 10 numbers:n);CreatSqlist(List,10); /建立一个顺序线性表output(List); /输出线性表IsEmpty(List); /表的判空 printf(n); int x,k,i; /搜索元素printf(please intput a number you want to search:);scanf(%d,&x);k=LocateElem(List,x);printf(n); printf(output the position the number:%dn,k+1); /k+1;因为数组和阅读的关系，所以加1，下面也是如此printf(n);printf(input a nuebers position and a number you want to insert:);/插入元素scanf(%d,&i);scanf(%d,&x);Insert(List,x,i-1);output(List);printf(n); printf(please input a position of a number you want to delete:);/删除元素 scanf(%d,&i);Delete(List,i-1);output(List);printf(n);1-2加强：用数组解决#include #include #include #include int a100;int josephus(int n,int s,int m)if(!(n*s*m)printf(输入错误！n);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;printf(%d,i+1);printf(出局n);x=1;y-;for(j=0;jn;j+)if(aj+1)aj=x+;if(aj=m)aj=-1;x=1;y-;if(!y)break;elseprintf(%d,j+1);printf(出局n);return (j+1);void main()int n,s,m,y=0;int x;dofor(int i=0;i100;i+)ai=0;printf(请输入人游戏总人数：n);scanf(%d,&n);printf(请输入开始人位置与报数长度：n);scanf(%d,&s);scanf(%d,&m);x=josephus(n,s,m);printf(%d,x);printf(胜出n);printf(请选择：n);printf(1,重新游戏; 2,退出程序：n);scanf(%d,&y);while(y=1);getch();1-3提高题：循环链表#include#include#define NULL 0#includetypedef struct Lnodeint data;struct Lnode *next;Josephus;void CreateList(Josephus*&L,int n)/建立循环链表int i;Josephus *p,*s;s=(Josephus*)malloc(sizeof(Josephus);s-data=1;L=p=s;for(i=2;idata=i;p-next=s;p=s;p-next=L;void DeleteList(Josephus*&L,Josephus*p,Josephus*q)q-next=p-next;free(p);void Josephus1(Josephus*&L,int s,int m)Josephus *p,*q;int i;p=L;for(i=1;inext;q=p-next;while(q-next!=p)q=q-next;while(p-next!=p)for(int j=1;jnext;printf(%d,p-data);DeleteList(L,p,q);p=q-next;printf(%d,p-data);printf(n);void main()Josephus *L=NULL;int m,n,s;printf(请输入人数，报数的开始位置，报数的上限:n);scanf(%d%