约瑟夫环问题的实验报告讲解

1、第一次试验报告一. 实验题目线性表及其应用约瑟夫环二. 实验目的帮助学生熟练掌握线性表的根本操作在顺序和链式两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。三. 实验内容：1. 问题描述：约瑟夫问题的一种描述为，编号为1,2,3,n的n个人按 顺时针方向围坐一圈，每人持有一个密码正整数。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停 止报数。报m的人出 列，将他的密码作为新的m的值，从他在顺时针方向上的下一个人开始重新从1报数, 如此下去，直至所有的人全部出列为止。试设计一个程序求出出列顺序。2. 根本操作：利用单向循环链表存储结构模

2、拟此过程，按照出列的顺序印出各人的编号。3. 测试数据：m的初值为20; n=7,7个人的密码依次为：3,1,7,2,4,8,4首先m值 为6 正确的出列顺序应为6,1,4,7,235。4. 实现提示：程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设nW 30此题所用的循环链表中不需要头结点请注意空表 和非空表的界限。四. 实验程序源代码#in elude <iostream> using n amespace std; typedef struct LNode int num; /表示该元素的编号 int key; /表示该元素的密码 struct LNode

3、 *n ext;int/*构建约瑟夫环*LNode,*LinkList; /结点类型，指针类型 In sert(L in kList &L,i nt key, i nt num) Lin kList p;if(L=NULL) / 第一个结点p=(LinkList)malloc(sizeof(LNode); 分配空间 if(!p)cout?"分配空间失败！"<<e ndl;return -1;p->num=num;p->key=key;L=p； else p=(Li n kList)malloc(sizeof(LNode); if(!p)cou

4、t?"分配空间失败！"<<e ndl; return -1; p->num=num; p->key=key; L->n ext=p; p->n ext=NULL; L=p; return 0;ff * 出人数出列的顺序 * voidJoseph(L in kList & L,i nt k,i nt m) int i;Lin kList p,q;p=q=L;while(q->n ext!=L)q=q->n ex t;while(k>0)for(i=1;i<m;i+) q=q->n ext; p=p-&g

5、t;n ext;q->n ext=p->n ext; cout? p->num <<"" m=p->key; / 更新 m 的值 free(p);k-; /人数减1 p=q->n ex t; cout? e ndl;int m,n ,i, t;Lin kList head,p=NULL;cout << "请输入人的数量(<=30)"v<endl ; coutvv"请输入人数："/输入人数n cin>>n; coutvv"请输入初始密码："/输入初始密码m cin>>m;coutvv"请输入每个人手中的密码："<<e n dl; for(i=1;i<=n ;i+) cin> >t;if(ln sert(p,t,i)=-1) return 0;if(i=1)head=p;p->n ext=head; cout?"出列的顺序如下："<<e ndl; Joseph(head, n, m); system("paus