约瑟夫环问题
问题描述:设编号为 1,2,…,n(n>0)个人按顺时针方向围坐一圈,每人持有一
个正整数密码。开始时任意给出一个报数上限值 m,从第一个人开始顺时针方
向自 1 起顺序报数,报到 m 时停止报数,抱 m 的人出列,将他的密码作为新
的 m 值,从他在顺时针方向上的下一个人起重新自 1 起顺序报数;如此下去,
直到所有人全部出列为止。要求设计一个程序模拟此过程,并给出出列人的编
号序列。
基本要求:
(1)初始报数上限值 m 和测试数据在程序中确定;
(2)用带头结点的单循环链表作数据元素的存储结构;
(3)把带头结点的单循环链表作为抽象数据类型设计。
测试数据:
n = 7,七个人的密码依次为 3,1,7,2,4,8,4
初始报数上限值 m = 20
算法思想:
JesephRing()函数是实现问题要求的主要函数,其算法思想是:从 1 至 m 对
带头结点的单循环链表循环计数,到 m 时,输出该结点的编号值,将该结点的
密码作为新的 m 值,再从该结点的下一个结点起重新自 1 起循环计数;如此下
去,直到单循环链表空时循环过程结束。
模块划分:
(1)带头结点的单循环链表抽象数据类型 SCLinList,其中包括基本操作的函
数有:初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取
一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为
SCLinList.h。
(2)void SCLLDeleteAfter(SCLNode *p),其功能是删除带头结点的单循
环链表中指针 p 所指结点的下一个结点。这是对带头结点的单循环链表抽象数
据类型 SCLinList,补充本问题需要的一个操作函数。
(3)void JesephRing(SCLNode *head, int m),其功能是对带头结点的单
循环链表 head,以 m 为初始报数上限值实现问题要求。
(4)void main(void),主函数,功能是给出测试数据值,建立测试数据值的
带头结点单循环链表,调用 JesephRing()函数实现问题要求。
数据结构:
(1)数据类型 DataType 定义如下:
typedef struct
{
int number;
int cipher;
} DataType;
(2)带头结点单循环链表抽象数据类型 SCLinList。
(3)带头结点单循环链表抽象数据类型的结点结构定义如下:
typedef struct node
{
评论3