关于约瑟夫环问题的实验报告书中详细设计

Question

如题所述

Answer 1

约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
1．需求分析和说明
分析约瑟夫问题：n个人围成圈，每人各持一个密码，任选一个正整数作为报数上限值m，从第一个人开始，数到第m个人，删除并以出列者密码作为新的m值，从下一个人开始进行第二轮操作，直到所有人都出列。例如n=6, m=3, 处理过程下图。
2．设计
n个人围圈，形成线性关系；处理为逐个删除，故用链式结构合适；又人员围成圆圈，所以此链式结构采用循环方式较好；排号按照一个方向进行，故数据结构采用带头结点的单向循环链表。假设人员以首次的编号命名，对每个人员采用编号和密码加以描述。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

存储结构：

typedef struct Node
{
ElemType date; //编号
int mima; //密码
struct Node *next;
}Node,*LinkList;
单向循环链表：
LinkList H; //表头指针
Node *Q,*Pre;//*Q指新建结点，*pre指向当前工作结点
Q=(Node*)malloc(sizeof(Node));

构造函数：
void InitList(LinkList *H); //初始化循环链表
void InPut(LinkList H,int *A);//插入结点
void DelList(LinkList H,int *x, int*a); //删除结点