实验名称：约瑟夫环问题
实验类型：综合性实验
班级：
学号：
姓名：
实验日期：2014.5.19
1.问题描述
设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
2.数据结构设计
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
typedef struct LNode
{
int M;
LNode *next;
} Lnode;
3.算法设计
（1）建立一个循环链表
LNode *create_l(int n){
LNode *L,*p;
int i;
L=(LNode*)malloc(sizeof(LNode));
L->M=1;
L->next=L;
for(i=n;i>1;i--)
{
p=(LNode*)malloc(sizeof(LNode));
p->M=i;
p->next=L->next;
L->next=p;
}
return L;
}
（2）依次删除第m个结点，并输出该节点的序号
int Dele(LNode *L,int m)
{
LNode *p,*pre;
int j;
p=L;
pre=L;
while(pre->next!=L)
pre=pre->next;
while(p!=p->next)
{
for(j=1;j pre=p; p=p->next; } printf("%d ",p->M); pre->next=p->next; free(p); p=pre->next; } printf("%d ",pre->M); free(pre); } （3）主函数 int main( ) { LNode *first; int m,n; printf("Please input n: "); scanf("%d",&n); printf("Please input m: "); scanf("%d",&m); create_l(n); first=create_l(n); printf("the delete number is:"); Dele(first,m); } 4．程序代码 #include #include typedef struct LNode { int M; LNode *next; }LNode; LNode *create_l(int n){ LNode *L,*p; int i; L=(LNode*)malloc(sizeof(LNode)); L->M=1; L->next=L; for(i=n;i>1;i--) { p=(LNode*)malloc(sizeof(LNode)); p->M=i; p->next=L->next; L->next=p; } return L; } int Dele(LNode *L,int m) { LNode *p,*pre; int j; p=L; pre=L; while(pre->next!=L) pre=pre->next; while(p!=p->next) { for(j=1;j pre=p; p=p->next; } printf("%d ",p->M); pre->next=p->next; free(p); p=pre->next; } printf("%d ",pre->M); free(pre); } int main( ) { LNode *first; int m,n; printf("Please input n: "); scanf("%d",&n); printf("Please input m: "); scanf("%d",&m); create_l(n); first=create_l(n); printf("the delete number is:"); Dele(first,m); } 5.运行、测试与分析 （1）、运行,例如n=5,m=3 （2）得出结果 5.实验收获及思考 考虑不太周全，刚开始没有考虑到只有一个人或者密码是1的情况，以后写程序要考虑周到。 而且之前学习的都是算法，这是第一次写数据结构的实验。真正第一次将自己的算法用C语言表达并运行出来。所以，纸上学来终觉浅，只有真正实践过才会了解。 ● 思考：采用顺序存储结构如何实现约瑟夫环问题？ 建立一个长度为n的顺序表，依次删除第n个元素，并将后面的元素都向前移。 ●如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 建立含有两个数据域的结构体，一个存放顺序号，一个存放密码。在做删除循环时，每次先访问删除节点的下一个节点的数据域，获得密码值作为循环移动的上限值。下载本文
