约瑟夫环的课程设计实验报告

数据结构课程设计报告

学 院 专 业 2005-- 7 班 课程设计(论文)题目 约瑟夫

二、课程设计(论文)工作自 2007 年1月 8 日起至 2007 年 1月 12 日止。 三、课程设计(论文) 地点: 软件学院机房 四、课程设计(论文)内容要求： 1．本课程设计的目的

1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操

作实现算法，以及它们在程序中的使用方法。

2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2．课程设计的任务及要求 1）基本要求：

1. 分析题目，查阅相关资料； 2. 算法设计、数据结构设计； 3. 编写代码并调试； 4. 完成课程设计报告。

年 月 日

- 1 -

目录

一、 问题描述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．5 二、 基本要求．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．5 三、 测试数据．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．6 四、 算法思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．7 五、 模块划分．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．8 六、 数据结构．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11 七、 源程序．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．12 八、 测试情况．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．26

正文

一、问题描述

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，„，n

的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序，以及密码顺序。

- 2 -

二、基本要求

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

- 3 -

三、测试数据

数 项 值 目 次 数 1 测试结果1 测试结果2 出队 密码 顺序 顺序 测试结果3 出队 密码 顺序 顺序 测试结果4 出队 密码 顺序 顺序 2 35 12 8 6 7 3 4 出队 密码 顺序 顺序 参与人数 上限值 第一人的密码 第二人的密码 第三人的密码 第四人的密码 第五人的密码 第六人的密码 第七人的密码 第八人的密码 第九人的密码 第十人的密码 第十一人的密码 第十二人的密码 4 5 3 4 6 1 1 5 9 1 5 9 6 1 3 4 1 2 4 3 6 8 15 12 13 3 12 6 5 1 6 10 5 7 9 4 8 2 7 5 3 9 20 11 11 1 1 2 5 3 6 6 1 4 12 5 8 6 12 6 1 8 3 5 9 24 15 54 20 5 11 13 12 5 8 1 4 2 8 2 3 ★注（由于表格有限，特在此注明）：当输入的人数大于30时，系统提示“输

入数字无效”重新输入；当输入的上限值大于10时，系统提示“输入数字无效”重新输入；；当输入的密码大于10时，系统提示“输入数字无效”重新输入。（有两组数字的方格中，下面的数字为有效数值）

- 4 -

四、算法思想

为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。

用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。

- 5 -

五、模块划分

（1）创建单循环链表模块；

void CreatLinkList(LinkList *L)//构建单循环链表

{

(*L) = (LinkList)malloc(sizeof(Node)); if ((*L) == NULL) {

printf(\"memory allocation failed, goodbye\"); exit(1); } }

void InitLinkList(LinkList *L, int personNumber)//初始化单循环链表 {

Node *p, *q;//定义结构体类型指针变量 int i ;

p = (*L);//初始化第一个结点,并赋值给p p->data = 1;

p->password = GetPassword();//调用GetPassword()输入密码 for (i = 2; i <= personNumber; i++) {

q = (LinkList)malloc(sizeof(Node)); if (q == NULL) {

printf(\"memory allocation failed, goodbye\"); exit(1); }

q->password = GetPassword(); q->data = i; p->next = q; p = q; }

p->next = (*L); }

- 6 -

（2）“约瑟夫环”的操作模块；

void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int array[MAXPERSONNUMBER],int key[MAXPERSONNUMBER]) {

Node *p, *q;

int count = 1, i = 0,j=0;

p = (*L);

if(reportValue==1) {

q=p;

while(q->next!=p)

q=q->next; //寻找p的头一个节点 array[i++] = p ->data;

reportValue=key[j++] = p->password; q->next = p->next; //删除结点p

free(p); //释放p中所有数值 p = q->next;

count = 1; //重新记当前位置为1 personNumber--; //人数减1 }

while (personNumber!=0) {

while (count != reportValue) {

q = p; p = p->next; count++;

}

array[i++] = p ->data;

reportValue=key[j++]= p->password; q->next = p->next; free(p);

p = q->next;

count = 1; //重新记当前位置为1 personNumber--;

- 7 -

} }

（3）输出出列顺序及密码顺序块；

void printResult(int array[],int personNumber) //输出出列顺序 {

int i;

printf(\"\\n出队的顺序为:\");

for(i = 0; i < personNumber; i++) {

printf(\"%-3d\} }

void printkey(int key[],int personNumber) //{

int i;

printf(\"\\n出队的密码为:\");

for(i = 0; i < personNumber; i++) {

printf(\"%-3d\}

printf(\"\\n\"); printf(\"\\n\"); }

（4）主程序模块；

int main(void){ 初始化； do{

接受命令； 处理命令；

}while(“命令”==“Y”)； return 0; }

- 8 -

输出密码顺序 六、数据结构

基本抽象数据类型：建立线性表的链式存储结构；利用链式存储结构建立一单向循环链表！ typedef struct Node {

int data; //整型（注：基本数据类型） int password; //整型（注：基本数据类型） struct Node *next; //结点类型，指针类型 }Node, *LinkList; //基本抽象数据类型

int array[] ;//整型数组（注：存放出对序列）

int keyp[] ; //整型数组（注：按出队的正确序列，存放密码）

int personNumber；//整型（注：输入参与的人的个数） int reportValue; //整型 （注：每次执行的上限值）

char I; //字符型（注：用于控制是否重新进入运行程序）

- 9 -

七、源程序及流程图

#include\"stdio.h\" #include\"stdlib.h\" #include

#define MAXPASSWORDVALUE 20

#define MAXPERSONNUMBER 30 //输入人数的最大值 #define MAXFIRSTCOUNTVALUE 10 //最大初始上限值 #define MAXPASSWORD 20 //输入密码最大值 void jiemian ( ) {

cout<<\"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\"<cout<<\"@ 设计者:毛敏 @\"<typedef struct Node {

int data; int password; struct Node *next; }Node, *LinkList;

//////////////////////////////////////////////// /////函数的声明

//////////////////////////////////////////////// void CreatLinkList(LinkList *); void InitLinkList(LinkList *,int ); int GetPassword();

int GetPersonNumber(); int GetPersonNumber(); int GetFirstCountValue();

void GetOutputOrder(LinkList* , int, int, int* ); void printResult(int * ,int );

void CreatLinkList(LinkList *L)//构建单链表 {

- 10 -

(*L) = (LinkList)malloc(sizeof(Node)); if ((*L) == NULL) {

printf(\"memory allocation failed, goodbye\"); exit(1);

} //系统出现错误 }

void InitLinkList(LinkList *L, int personNumber)//初始化单链表 {

Node *p, *q;//定义结构体类型指针变量 int i ;

p = (*L);//初始化第一个结点,并赋值给p p->data = 1;

p->password = GetPassword();//调用GetPassword()输入密码 for (i = 2; i <= personNumber; i++) {

q = (LinkList)malloc(sizeof(Node)); if (q == NULL) {

printf(\"memory allocation failed, goodbye\"); exit(1); }

q->password = GetPassword(); q->data = i; p->next = q; p = q; }

p->next = (*L); }

int GetPassword()//给每个人赋密码 {

int password;

static int count = 1;//定义静态局部整性变量

printf(\"\\n请输入第%d的密码:\

scanf(\"%d\

while (password > MAXPASSWORDVALUE || password < 0)

- 11 -

{

printf(\"您输入的数字无效，请输入在1到%d的整数:\scanf(\"%d\}

printf(\"第%d个人的密码为:%d\count++;

return password; //返回参数 }

int GetPersonNumber()//确定需要输入的人数 {

int personNumber;

printf(\"请输入需要输入人的数目:\"); scanf(\"%d\

while (personNumber > MAXPERSONNUMBER || personNumber <=0)

{

printf(\"\\n你输入的数字无效,请输入在1到%d的整数!\scanf(\"%d\

}

printf(\"最终确定的人数为%d\\n\

return personNumber; //返回参数 }

int GetFirstCountValue()//确定开始的上限值 {

int firstCountValue;

printf(\"请输入初始的上限值:\"); scanf(\"%d\

while (firstCountValue >MAXFIRSTCOUNTVALUE || firstCountValue <=0) {

printf(\"\\n

你输入的数字无效,请输入在

1

到%d

的整

数!\

scanf(\"%d\

}

printf(\"最终的上限值为:%d\

- 12 -

return firstCountValue; //返回参数 }

///////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////// void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int array[MAXPERSONNUMBER],int key[MAXPERSONNUMBER]) {

Node *p, *q;

int count = 1, i = 0,j=0;

p = (*L);

if(reportValue==1) { q=p;

while(q->next!=p)

q=q->next; //寻找p的头一个节点 array[i++] = p ->data;

reportValue=key[j++] = p->password; q->next = p->next; //删除结点p free(p); //释放p中所有数值 p = q->next;

count = 1; //重新记当前位置为1 personNumber--; //人数减1 }

while (personNumber!=0) {

while (count != reportValue) {

q = p;

p = p->next; count++; }

array[i++] = p ->data;

reportValue=key[j++]= p->password; q->next = p->next; free(p);

- 13 -

p = q->next;

count = 1; //重新记当前位置为1 personNumber--; } }

void printResult(int array[],int personNumber) //输出出列结果 { int i;

printf(\"\\n出队的顺序为:\"); for(i = 0; i < personNumber; i++) {

printf(\"%-3d\}

}

void printkey(int key[],int personNumber) //输出密码顺序 {

int i;

printf(\"\\n出队的密码为:\"); for(i = 0; i < personNumber; i++) {

printf(\"%-3d\}

printf(\"\\n\"); printf(\"\\n\");

}

int main(void) //主函数 {

char i; //定义变量

do //执行do－while语句

{ //建立并初始化链表,以及调用各个函数

LinkList L; jiemian ( );

int personNumber, reportValue; int array[MAXPERSONNUMBER]; int key[MAXPERSONNUMBER];

personNumber = GetPersonNumber();

- 14 -

reportValue = GetFirstCountValue(); CreatLinkList(&L);

InitLinkList(&L, personNumber);

GetOutputOrder(&L,personNumber, reportValue, array,key); printResult(array, personNumber); printkey(key, personNumber);

printf(\"请问您是否需要重新开始(Y/N):\"); scanf(\"%d\}while(i=='Y'); return 0; }

- 15 -

流程图 一、主程序流程图

开始 定义各种变量 调用jiemian(); 输出界面 调用GetPersonNumber() ;输入参与人数 调用GetFirstCoutValue();输入所要确定的上限值 调用CreatLinkList();构造单链表 调用InitLinkList();初始化单链表 调用GetOutputOrder();开始进行约瑟夫环的操作 调用printResult();输出出列顺序 调用printkey();输出密码 do－while语句 输入一数值i i=’Y’ 假 结束 - 16 -

真 二、子程序流程图 (1)

GetPersonNumber() 定义变量personNumber 输入一数值 personNumber>30|| personNumber<=0 假 真 重新输入一数值 返回参数 - 17 -

(2)

GetFirstCountValue() 定义变量firstCountValue 输入一数值 firstCountValue>30|| firstCountValue<=0 假 真 重新输入一数值 返回参数 - 18 -

(3)

InitLinkList() 定义结构体类型指针 *p,q*; 定义整型变量i 初始化第一个结点，并赋值给p,调用GetPassword(),输入密码 ２＜＝i&&i<=perNumber 假 真 生成结点，并赋值给q q==0 真 系统出错 假 初始化q的序列号和密码，并调用GetPassword(),输入密码 把q链接到单链表中，让p下移 i++ 实现单向循环链表 - 19 -

(4)

GetPassword 定义整型变量password； 定义静态局部整型变量 输入一数值 password>20|| password<0 真 重新输入一数值 假 输入下一个人的密码 cout++ 返回参数 - 20 -

(5) GetOutputOrder() 定义结构体类型指针*p,*q 定义整型变量cout, i, j 初始化第一个结点，并赋 值给p 假 reportValue = =1 真 q=p 假 q－>next!=p 真 把p.date赋值给array[i] i++ 把p－>password赋值给 reportValue和key[j] j++ 删除并释放结点p personNumber!=0 真 cout!= reportValue 真 q=p; p=p->next 假 调用结束 假 cout++ 把p.date赋值给array[i] 删除并释放结点p i++ p=q－>next cout=1;重新记当前位置为１ 人数减１ - 21 - 把p－>password赋值给reportValue和key[j] (6)

printResult() 接23页

j++ 删除并释放结点p p=q－>next cout=1;重新记当前位置为１ 人数减１ 定义整型变量 输入一数值 ０＜＝i&& i(7)

printkey() 定义整型变量 输入一数值 ０＜＝i&& i八、测试情况

1、进入“约瑟夫环”运行界面

2、第一次测试。输入所规定范围内的数值。 运行结果如下：

- 24 -

3、当输入的数值超过范围时，系统自动跳出提示框，输出“你输入的数字无效”，请重新输入在规定范围内的值。 运行如下：

- 25 -

4、当设定初始上限值为1时，程序运行的界面如下：

- 26 -

5、第四次测试的数据及界面如下：

- 27 -