约瑟夫环问题分析及源码

约瑟夫环问题

- 问题描述：
- 基本要求：
- 提示与分析：
- 算法思路：
- 数据类型定义：

问题描述：

设编号为1,2,3,……,n个人按顺时针方向围坐一圈，约定编号为k（1≤k≤n）的人按顺时针方向从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依此类推，直到所有人出列为止，由此产生一个出队编号的序列。试设计算法求出n个人的出列顺序。

基本要求：

程序运行时，首先要求用户指定人数n、第一个开始报数的人的编号k及报数上限值m，然后按照出列的顺序打印出相应的编号序列。

提示与分析：

由于报到m的人出列的动作对应着数据元素的删除操作，而且这种删除操作比较频繁，因此单向循环链表适于作为存储结构来模拟此过程。而且为了保证程序指针每一次都指向一个具体的数据元素结点，应使用不带头结点循环链表作为存储结构。相应地，需要注意空表与非空表的区别。

算法思路：

先创建一个含有n个结点的单循环链表，然后由第一个结点起从1开始计数（此时假设k=1），计到m时，对应结点从链表中删除，接下来从被删除结点的下一个结点重新开始从1开始计数，计到m时，从链表删除对应中，如此循环，直到最后一个结点从链表中删除，算法结束。

数据类型定义：

 问题描述：

 基本要求：

程序运行时，首先要求用户指定人数n、第一个开始报数的人的编号k及报数上限值m，然后按照出列的顺序打印出相应的编号序列。

 提示与分析：

 算法思路：

 数据类型定义：

设单向循环链表的头指针为L，对应的数据类型定义描述如下：

typedef struct LNode

{

int number; //每个人的编号

struct LNode next; //指向表示下一个结点的指针

}LNode,*LinkList;

LinkList L;
为了记录退出的人先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以了，所以定义一个整型一维数组就可以。

int quit[N]; //N为一个根据实际问题定义的一个足够大的整数。

源码展示:

#define N 50

#define OK 1

#define ERROR 0

#include <stdio.h>

#include <stdlib.h>

typedef int Status;

typedef struct LNode

{

int number; //每个人的编号

struct LNode *next; //指向表示下一个结点的指针

}LNode,*LinkList;

//创建单循环链表

Status CreateLinkList(LinkList *L,int n)

{

int i;

LNode *p,*q;

*L=(LinkList)malloc(sizeof(LNode));

(*L)->next = NULL;

(*L)->number=1;

p = (*L);

for(i=2;i<=n;i++) {

q = (LinkList)malloc(sizeof(LNode));

q->number = i;

q->next = *L;

p->next = q;

p = p->next;

}

return OK;

}

//输出单循环链表的元素

Status PrintLinkList(LinkList *L) {

LNode *p;

p = *L;

{

printf("%d\t",p->number);

p = p->next;

}while(p!=*L);

return OK;

}

//删除单循环链表的第m个元素。

Status ListDelete(LinkList *L, int m, int *e)

{ LinkList q;

LinkList p = (*L);

int j = 1;

//先找到第m-1个元素（完成相关代码……）

while(p -> next!=p&&j<m-1)

{

p = p->next;

j++;

}

//找到第m-1个元素后，将第m个元素的值存入e所指向的单元

//删除第m个元素，并使后面的那个元素成为单循环链表首元节点

if(j==m-1)

{ q = p->next;

*e = q->number;

p->next=q->next;

*L = p->next;

}

else if(j==1){

*e = p->number;

}

free (q);

return OK;

}

//主函数

int main()

{

LinkList L;

LNode *p;

int e,n,k,m,j=0,quit[N];

printf(“请输入总人数n：”);

scanf("%d",&n);

printf(“请输入m的值：”);

scanf("%d",&m);

//创建一个具有n个元素的链表

CreateLinkList(&L,n);

printf(“共有%d个人围成一个环，每数%d个数出列，初始编号为：”,n,m);

PrintLinkList(&L);

printf("\n");

while(L->next!=L)
{
    ListDelete(&L,m,&e);
    quit[j++]=e;
}
printf("\n出列的顺序为：");
for(k=0;k<j;k++)
    printf("%d、",quit[k]);
printf("%d。",L->number);

getchar();
getchar();
return 0;

}

约瑟夫环问题分析及源码