实验6--约瑟夫环的实现(大作业)

1、精选优质文档-倾情为你奉上浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验六 约瑟夫环的实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用线性表的各种操作来进行具体的实际应用。3、加强程序设计的能力。二. 实验内容1、编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，n (n0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0i=n)，另一个为起始报数上限值m。接着从编号为

2、i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求:（1） 人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。（2） 参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。（3） 根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的

3、程序存放在文件test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。（4） 设计测试数据，并调试程序，直到正确运行。2、填写实验报告，实验报告文件取名为report6.doc。3、上传实验报告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、test6_Link.h、test6_Link.cpp到Ftp服务器（ 22:2007 ）自己的文件夹下。同时上交一份书面的实验报告。三. 抽象数据类型定义（需说明你设计的每个基本操作的功能）1. 初始化线性表2. 清除线性表3. 在线性表中插入某个元素4.

4、 删除线性表中的某个元素5约瑟夫函数四. 两种类型（顺序和链式）的存储结构定义及算法思路1.顺序typedef struct List ElemType *list; int size; int MaxSize; SeqList;void InitList(SeqList &L)；void ClearList(SeqList &L)；bool InsertList(SeqList &L, ElemType item, int pos)；bool DeleteList(List &L,ElemType &item,int pos)2.链式typedef struct LNode int code

5、; int num; struct LNode *next; LNode;void josephus(int n,int m,int s)。五. 实验结果与分析1.顺序输出结果2.链式输出结果六. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现2、掌握利用线性表的各种操作来进行具体的实际应用3、加强程序设计的能力，同时对前面所学习的只是进行了回顾，掌握了链表的基本技巧【附录-源程序】1. 顺序test6_Seq.cpp专心-专注-专业#include #include #include

6、 typedef int ElemType;#include test6_Seq.htypedef struct List ElemType *list; int size; int MaxSize; SeqList;void main()SeqList L;int n,m,i,j;printf(输入人数 n, 首次报数人编号i, 初始报数上限值m :);scanf(%d%d%d,&n,&i,&m);InitList (L);for(j=0;jn;j+)InsertList(L,j+1,0);for(j=0;jn;j+)cout L.listj endl;/Josephusint count=

7、0,k=0,no=1,item;j=i-1;while(count=n)j=0;while(jn)if(L.listj!=0)k+;if(k=m)printf(No%d: %dn, no, L.listj);k=0;count+;no+;m=L.listj;L.listj=0;DeleteList(L,item,L.listj);j+;ClearList(L);test6_Seq.hvoid InitList(SeqList &L) /初始化线性表 L.MaxSize=100; L.list=new ElemTypeL.MaxSize; if(L.list=NULL) cout动态可分配的存储

8、空间用完，退出运行！endl; exit(1); L.size=0;void ClearList(SeqList &L) /清除线性表 if(L.list!=NULL) delete L.list; L.list=NULL; L.MaxSize=0; L.size=0;bool InsertList(SeqList &L, ElemType item, int pos) /按给定条件pos向线性表插入一个元素if(posL.size+1)coutpos值无效!endl; return false;int i;if(pos=0)for(i=0;iL.size;i+)if(itemL.listi)

9、 break;pos=i+1;else if(pos=-1) pos=L.size+1;if(L.size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout动态可分配的存储空间用完，退出运行！=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.size+;return true;bool DeleteList(List &L,ElemType &item,int pos) if(L.size=0) co

10、ut线性表为空，删除无效endl; return false; if(posL.size )coutpos值无效endl;return false;int i; /根据pos值，确定需删除元素的位置，使下标保存到pos中if(pos=0) /查找删除for(i=0;iL.size ;i+) if(item=L.listi) break;if(i=L.size) return false;pos=i+1;else if(pos=-1) pos=L.size ; /表尾元素删除item=L.listpos-1; /被删元素保存返回/从被删元素后开始依次前移，即从下标pos开始移动for(i=pos

11、;iL.size ;i+)L.list i-1=L.list i;L.size -; /长度减1/调整线性表空间，空余太多，小于40%时调整if(float(L.size )/L.MaxSize 10)int k=sizeof(ElemType);L.list =(ElemType *)realloc(L.list ,L.MaxSize *k/2); L.MaxSize =L.MaxSize /2; /新长度空间return true; /成功2. 链式test6_Link.cpp#include #include typedef struct LNode int code; int num;

12、 struct LNode *next; LNode;#include test6_Link.hvoid main() int m,n,s; printf(输入人数 n, 首次报数人编号i, 初始报数上限值m :);scanf(%d%d%d,&n,&s,&m);josephus(n,m,s);test6_Link.hvoid josephus(int n,int m,int s)struct LNode *head;struct LNode *p1,*p2; int i,j; p1=(struct LNode*)malloc(sizeof(LNode); head = p1;for(i=1;inext =(struct LNode*)malloc(sizeof(LNode); printf(输入第 %d 个人的密码:,i);scanf(%d,&p1-next-code);p1-next-num = i;p1 = p1-next; p1-next = head-next; p2 = head-next; delete head; for(i=1;inex