一、实验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、实验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。
一、需求分析 1.输入的形式和输入值的范围 本程序中，需输入的系数n，m，a[i]都是正整数，由键盘按提示依次输入，以回车结束
2.输出的形式 从屏幕输出出列顺序
3.程序所能达到的功能 用户由键盘输入约瑟夫环的必要数据（人数，起始m值，各人手中密码），由屏幕输出出列顺序
4.测试数据 m 的初值为20；n=7,7个人的密码依次是：3,1,7,2，4，8，4。首先m值为6，正确的出列顺序应该为（6,1,4,7,2,3,5）。
三、概要设计 以单向循环链表实现该程序 1.抽象数据类型的定义 ADT ListNode { 数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0} 数据关系：R1={< ai-1 ，ai > | ai ∈D， I=2，…，n} 基本操作： InitList(&L) 操作结果：构造一个最大长度ms内容为空的有序表L。 ClearList(&L) 初始条件：线性表L已经存在。 操作结果：将L重置为空表。 EmptyList(L) 初始条件：线性表L已经存在。 操作结果：若L为空表返回TRUE，否则返回FALSE。 ListLength(L) 初始条件：线性表L已经存在。 操作结果：返回L中数据元素个数。 GetElem(L, pos, &e) 初始条件：线性表L已经存在，1≤i≤ListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 LocateElem(L, e) 初始条件：线性表L已经存在。 操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。 ListInsert (L, i, e) 初始条件：线性表L已经存在。 操作结果：在L中的第i个元素的位置之前插入新元素 e,L的长度加1。ListDelete(L, pos, e) 初始条件：线性表L已经存在，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L) 初始条件：线性表L已经存在。 操作结果：依次对L的每个数据元素进行访问。 }ADT CirLinkedList
四、源代码
typedef struct node{int data;int sercet;struct node *next;}ListNode;typedef ListNode *LinkList;//建立单循环链表函数LinkList InitRing (int n,LinkList R,int a[N]){ListNode *p,*q;int i;R=q=(ListNode *)malloc(sizeof(ListNode));for(i=0;i<n-1;i++){p=(ListNode *)malloc(sizeof(ListNode));q->data=i+1;q->sercet=a[i];q->next=p;q=p;}p->data=n;p->sercet=a[n-1];p->next=R;R=p;return R;}//删除被数到的人LinkList Delete(int n,LinkList R,int k){int i,j;ListNode *p,*q;p=R;for(i=1;i<n;i++){ for(j=1;j<k;j++)p=p->next;q=p->next;p->next=q->next;printf(“%d “,q->data);k=q->sercet;free(q);}R=p;printf(“胜利不出列的序号是：%d”,p->data);return R;}void main(){LinkList R;int n,i,m;printf(“请输入玩约瑟夫环的人数 : “);scanf(“%d”,&n);printf(“请输入初始m值： “);scanf(“%d”,&m);int a[N];printf(“请按顺序写出各个人手上的密码： \n”);for(i=0;i<n;i++)scanf(“%d”,&a[i]);printf(“出列的顺序为： “);R=InitRing (n,R,a);R=Delete(n,R,m);printf(“\n”);}
结果截图
都属于昨天。哪怕那山再青，那水再秀，
