1、- 1 - 数学与计算机学院数学与计算机学院 数据结构课程设计数据结构课程设计 设计题目：设计题目：约瑟夫环 - 2 - 一选题背景：一选题背景： 题目：约瑟夫环题目：约瑟夫环 问题描述：问题描述： 编号为 1,2，n 的 n 个人按顺时针方向围坐圈，每个人持有 一个密码（正整数） 。一开始任选一个正整数作为报数上限值 m， 从第一个人开始按顺时针方向自 1 开始顺序报数， 报到 m时停止报 数。报 m的人出列，将他的密码作为新的 m值，从他在顺时针方向 上的下一个人开始重新重新从 1 报数，如此下去， 直至所有人全部 出列为止。 基本要求：基本要求： 建立模型，确定存储结构； 对任意 n 个
2、人，密码为 m ，实现约瑟夫环问题； 出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想：设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。 由于约瑟夫环问题本身 具有循环性质， 考虑采用循环链表，为了统一对表中任意结点的操 作，循环链表不带头结点。 其次，建立一个不带头结点的循环链 表并由头指针 first 指示。 最后，设计约瑟夫环问题的算法。下 面给出伪代码描述，操作示意图如图 2-1 所示。 - 3 - 二方案论证二方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构 体 node，然后给他开辟一个储存空间；利用头指针 head 标记链表， 利用尾指针
3、向后移将建立的结点连接成我们需要的单循环链表， 过程如下过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中 node-num 编号 n，node-data 为每个人的密码。建立单循环链表后，通过初始报数 上限找到出列的结点，输出该结点的 node-num 值，将该结点中的 data 中数作为新密码开始下一个步的开始，将该结点从链表中删除， 并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接 将该结点中的 num 值输出，删除该结点，并释放该结点的空间。输出 的 num 值即为约瑟夫中人的编号。 三过程论述：三过程论述： typedef struct nodetypedef st
4、ruct node int data;int data; int num;int num; struct node *next;struct node *next; listnode;listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;inext=(listnode*)malloc(sizeof(listnode);/ 建 立建 立 一个新一个新的空间，并将它的地址赋给的空间，并将它的地址赋给 p1p1- -nextnext p1=p1p1=p1- -next;next; p1p1- -data=j;data=j; p1p1- -num=i;/num=i;/对结点的对结点的 numnum 和和 datadata 成员赋值成员赋值 p1p1- -next=headnext=head- -next;/next;/构成单循环链表构成单循环链表 定义指针 p1，然后建立一个新结点并将 p1-next 指向它的地址，然 后将这个地址赋给 p1，最后将 head-n
