约瑟夫环 实习报告

题目：约瑟夫（Joseph）问题的一种描述是：编号为1，2，......，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。试设计一个程序求出出列顺序。

一、需求分析

1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的

编号和密码），模拟约瑟夫环的显示过程，按照出列的顺序印出各人的编号。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示\"提示信

息\"之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。 3． 程序执行的命令包括：

1)构造单向循环链表；2） 按照出列的顺序印出各人的编号。 4． 测试数据

m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，1，3，5）。

二、概要设计

1．单向循环链表的抽象数据类型定义为：

ADT List｛

数据对象：D=｛ai | ai∈正整数，I=1，2，......，n,n≥0｝

数据关系：R1=｛< ai-1，ai > |，ai-1，ai∈D,I=1，2，......，n｝ 基本操作： Init List(&L)

操作结果：构造一个空的线性表L。 List Insert(&L,i,e)

初始条件：线性表L已存在，1≤i≤List Length(L)+1.

操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。 List Delete(&L,i,&e)

初始条件：线性表L存在非空，1≤i≤List Length(L).

操作结果：删除L的第i个元素，并用e返回其值，L长度减1。

2． 程序包含三个模块：

1）主程序模块：

Void main（）{

初始化； do {

接受命令； 处理命令； }while（“命令”=“退出”）； }

2）有序表单元模块——实现有序表的抽象数据类型。 3）输出函数模块——有序表的输出

输出函数模有序表单元模块 主程序模块 三、详细设计

1、 元素类型，结点类型和指针类型。

typedef struct LNode //定义结构体 {

int data; //data用来存储人的序号， int data1； //data1用来存储人的密码

struct LNode *next; };

lnode,*linklist; //定义结点

2、 创建循环链表函数及创建输入密码函数

void initlist(linklist &l,int n) //参数n传递人数 {

int i;

l=(linklist)malloc(sizeof(lnode)); //创建一个带头结点的链表 cin>>l->data; l->data1=1; l->next=l; lnode *p,*q; q=l;

for(int i=0;i<(n-1);i++) {

p=(linklist)malloc(sizeof(lnode)); cin>>p->data; p->data1=(i+2); q->next=p; q=p; }

if(n>1)

p->next=l; }

3、 创建输出函数

void delet(lnode *p) //传递报数上限值和人数 {

lnode *q; q=p;

while(q->next!=p) //用一个while搜索循环链表 q=q->next;

q->next=q->next->next; //删除结点

free(p); //释放动态申请的结点空间 }

4、 main主函数 void main() {

linklist l; lnode *p,*q; int m,n;

cout<<\"请输入m的初值（即初始密码）：\"<>m;

cout<<\"请输入总人数（即n的值）：\"<>n;

cout<<\"请输入各人密码：\"<cout<<\"则正确的出列顺序为:\"<0) {

for(int i=0;i<(m-1);i++) {

p=p->next; }

cout<data1<<\" \"; m=p->data; q=p;

p=p->next; delet(q); n--; }

cout<四、调试分析

1、由于对循环链表的理解不够，在几次课上的讲解以及作业的练习之后，

开始慢慢了解，也慢慢可以理清约瑟夫环的基本思路 2、忽视字母大小写，以及变量名的定义

3、经常弄混链表中的指针，将其所指位置混淆，以致在头结点的问题上徘

徊多时，今后应注意这方面的问题。

4、本实习作业采用数据抽象的程序设计方法，将程序分为三个层次：主函

数，创建循环链表函数及输入密码函数，输出链表函数，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性。

5、在不同系统上的测试成功，表明程序具有一定的通用性，可避免因系统

的问题导致的调试问题的出现。

6、因为要求用单向链表实现，因而实现起来比较麻烦，很多人第一感觉是

可以应用数组，也比较简单，起初用过数组做法，可以从中体会问题的主要思想。

五、用户手册

1、 本程序运行环境为WindowsXP Professional以及Windows Vista。 2、 可以直接执行yoseph.exe文件，进入演示程序后即显示文本方式的用户界面，并带有提示信息。

3、 输入报数上m及人数n后，再输入各人的密码。 4、 执行相应运算和显示结果。

六、测试结果

1、运行程序后，初界面：

2、输入m的初值后：

3、输入总人数后

4、输入各人的密码后，最后的运行结果：

七、 附录

源程序文件名清单： yoseph.cpp //主程序