数据结构专业课程设计方案报告约瑟夫环.doc

*******************
实践教学
*******************

兰州理工大学

软件职业技术学院

春季学期

算法和数据结构课程设计

题 目： 约瑟夫环
专业班级：
姓 名：
学 号：
指导老师：
成 绩：

摘要
约瑟夫环问题是经典线性表应用实例，其开发关键包含后台数据库建立和维护和前端应用程序开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好库。而对于后者则要求应用程序功效完备，易使用等特点。
经过分析，我们使用 MICROSOFT企业Microsoft Visual C++6.0开发工具，利用其提供多种面向对象开发工具，尤其是数据窗口这一能方便而简练操纵数据库智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不停修正和改善，直到形成用户满意可行系统。
关键词：单循环链表；c语言；约瑟夫环；
序言
数据结构是研究数据元素之间逻辑关系一门课程，和数据元素及其关系在计算机中存放表示和对这些数据所施加运算。该课程设计目标是经过课程设计综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程关键内容。
此次课程设计内容是用单循环链表模拟约瑟夫环问题，循环链表是一个首尾相接链表，其特点是无须增加存放容量，仅对表链接方法稍作改变，使表处理愈加灵活，约瑟夫环问题就是用单循环链表处理一个实际应用。经过这个设计实例，了解单链表和单循环链表相同和不一样之处，深入加深对链表结构类型及链表操作了解。
经过该课程设计，能利用所学知识，能上机处理部分实际问题，了解并初步掌握设计、实现较大程序完整过程，包含系统分析、编码设计、系统集成、和调试分析，熟练掌握数据结构选择、设计、实现和操作方法，为深入应用开发打好基础。
目录
摘要 1
序言 2
目录 3
正文 4
一、问题描述 4
二、逻辑设计 5
三、具体设计 7
四、程序代码 13
五、程序调试和测试 13
设计总结 18
参考文件 19
致谢 20
附录 21

正文
一、问题描述
约瑟夫环问题描述是：设编号为1，2，…，nn（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起次序报数，报到m时停止报数，报m人出圈，将她密码作为新m值，从她在顺时针方向上下一个人起重新从1报数。如此下去，直到全部些人全部出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈编号序列。以下图分析：
1
2
3
4
5
6
7
8
9
0
这是第一个人，她密码是“1”，个她输一个m值，假如m=3,则从她开始向下走3个
这就是第二步位置，这时她密码作为新m值，即m=4,同时得到第一个密码为4；4号出去向下走4，到9这儿；（这这一步完了剩下为：1,2,3,5,6，，7,8,9,0，）
这就是第三步位置，这时她密码作为新m值，即m=9，同时得到第二个密码为9；9号出去向下走9，到0这儿；继续走就行了（这儿剩下就是：1，2，3，5，6,7,8,0）

图1约瑟夫环问图解

3
2
7
1
4
8
4
约瑟夫环原理演示图
1
2
3
4
5
6
7
第二部：第一次停下位置，此时6号出列，并将她值作为新m值，即：新m=8；从7好开始继续向下走8次，到1号位置
最终排序后密码序列：
（本图只演示前两步）
8
第三步：
第二次，1号出列
第四步：第三次，4号出列
3
第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置
2
4
1
7
4
6
1
4
7
2
3
5
图2 约瑟夫环原理演示图

二、逻辑设计
1、循环链表抽象数据类型定义
typedef struct LNode//定义单循环链表中节点结构
{
int num;//编号
int pwd;//password
struct LNode *next;//指向下一结点指针
}LNode;
2、本程序包含一下多个模块
（1）结构结点模块
LNode *createNode(int m_num,int m_pwd)
{
LNode *p;
p=(LNode *)malloc(sizeof(LNode));//生成一个结点

p->num=m_num;//把实参赋给对应数据域
p->pwd=m_pwd;
p->next=NULL;//指针域为空
return p;
}
（2）创建链表模块
void createList(LNode *ppHead,int n)
（3）出队处理模块
void jose(LNode *ppHead,int m_pwd)
（4）约瑟夫环说明输出模块
void instruction()
（5）菜单模块
void menu()
（6）主函数模块
int main（）
函数调用关系图以下：
Case 2:建立约瑟夫环,并输出已建立约瑟夫环：
createList(LNode **ppHead,int n)
输出该约瑟夫环每个人出列次序:
jose(LNode *ppHead,int m_pwd)
图3 约瑟夫环函数调用关系图
菜单函数；
void menu()
主函数调用函数；
main()

Case 1：一个简单输出函数，用于说明约瑟夫环；
void instruction()
Case 0:default : 输入0，退出
exit(0)；

三、具体设计
1. 主函数
Main()开始

Menu()功效菜单

功效1：约瑟夫环说明
功效2：按要求求解约瑟夫环

功效3：退出系统

输入总人数n

输入开始上线数：m

输入每个玩家密码

调用：createList(&ppHead,n);
jose(ppHead,m);函数求解所需密码序列
选择要实施操作
程序运行完，自动返回到功效菜单

图4 主函数数据步骤图

依据步骤图，主函数程序以下：
int main()
{
int n,m,x;
LNode *ppHead=NULL;
menu();
for(;;){
printf("\n请选择要实施操作：");
scanf("%d",&x);
system("cls");
switch(x){
case 1:
printf("****************************************************************\n");
printf("约瑟夫环:\n");
printf(" 编号为1,2,3,4…,nn个人按顺时针方向围坐一圈,每人持有一个密\n");
printf("码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始\n");
printf("按顺时针方向自1开始次序报数,报到m时停止.报m人出列，将她密码\n");
printf("m作为新m值,从她在顺时针方向上下一人开始重新从1报数,如此下去,\n");
printf("直到全部些人全部出列为止.编程打印出列次序.\n");
printf("****************************************************************\n");
main();
break;
case 2:
printf("\n请输入总人数n：");
scanf("%d",&n);
printf("请输入开始上限数m：");
scanf("%d",&m);
createList(&ppHead,n);
printf("\n");
printf("出队次序：\n");
jose(ppHead,m);
printf("\n约瑟夫周游戏结束!\n");
main();
break;
case 0:
exit(0);
default:
system("cls");
printf("\n您选择操作有误，请重新选择...\n\n\n");
main();
}
}
return 0;
}
2. 链表创建
否
是
createList（）;

从主函数中获取玩家信息n

假如n>0
创建循环单链表，储存各个玩家密码
退出
创建链表完成返回主函数main()
创建储存玩家密码循环单链表方法
Main()函数
图5 创建链表函数数据步骤图

/*创建单向循环链表ppHead，人数个数为n，并输入每个人密码值，若建立失败则生成头结点，让cur指向她，若建立成功则插入结点P，cur指向数据元素为p,后续为"空"节点，再把P插入循环链表ppHead中*/
依据步骤图，创建链表函数程序以下：
void createList(LNode **ppHead,int n)
{
int i,m_pwd;
LNode *p,*cur;//cur:浮标指针
for(i=1;i<=n;i++)
{
printf("输入第%d个人密码：",i);
scanf("%d",&m_pwd);//输入持有密码
p=createNode(i,m_pwd);//调用结构结点函数
if(*ppHead==NULL)//假如头结点为空
{
*ppHead=cur=p;//生成头结点，让cur指向她
cur->next=*ppHead;//cur指针域指向本身
}
else//假如不为空，则插入结点
{
p->next = cur->next;
cur->next = p;
cur= p;//cur指向新插入结点
}
}
printf("完成创建！\n"); //提醒链表创建完成
}
3. 出队处理
Main()函数
从循环链表中按初始密码依次扫描，找出对应玩家序列
输出其持有密码i=ppHead->pwd; j=ppHead->num;
移动浮标指针
m_pwd=ppHead->pwd;
输出密码后，删除对应结点，并释放所占储存空间free(ppHead); ppHead=p->next;
实施完后返回主函数
jose()；出队函数
出队处理方法
图6 出队函数数据步骤图

/*p指向要删除节点前一个节点，ppHead指向要删除节点，使p=ppHead，ppHead再指向要删除节点下一个节点，使p和ppHead链接，输出p指向节点编号和密码值，释放ppHead，如此循环，直至把全部节点全部打印和删除为止！*/
依据步骤图，出队函数程序以下：
void jose(LNode *ppHead,int m_pwd)
{
int i,j;
LNode *p,*p_del;//定义指针变量
for(i=1;p!=ppHead;i++){
for(j=1;j<m_pwd;++j){
p=ppHead;//p赋值为ppHead，p指向要删除结点前一个结点
ppHead=ppHead->next;//ppHead指向下一个元素
}
p->next = ppHead->next;//p结点和头结点链接
i=ppHead->pwd;//i赋值为ppHead->pwd
j=ppHead->num;//j赋值为ppHead->num，j为要删除密码值
printf("第%d个人出列，密码：%d\n",j,i);
m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd
free(ppHead);//释放头结点
ppHead=p->next;//ppHead重新赋值给p->next,即释放前ppHead->pwd指针//删除报数结点
}
i=ppHead->pwd;//i赋值为ppHead->pwd
j=ppHead->num;//j赋值为ppHead->num
printf("最终一个出列是%d号，密码是:%d\n",j,i);
free(ppHead);//释放头结点
}
4. 约瑟夫环说明模块
void instruction()
{
printf("****************************************************************\n");
printf("约瑟夫环:\n");
printf(" 编号为1,2,3,4…,nn个人按顺时针方向围坐一圈,每人持有一个密\n");
printf("码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始\n");
printf("按顺时针方向自1开始次序报数,报到时停止.报m人出列，将她密码\n");
printf("m作为新m值,从她在顺时针方向上下一人开始重新从1报数,如此下去,\n");
printf("直到全部些人全部出列为止.编程打印出列次序.\n");
printf("******************************************************\n");

return 0;
}

5. 菜单模块
void menu(){
printf("**************************约瑟夫环 *****************************\n");
printf(" \n");
printf(" [1]约瑟夫环问题叙述 \n");
printf(" [2]按要求求解约瑟夫环 \n");
printf(" [0]退出 \n");
printf("************************** 欢迎使用！ ****************************\n");
}
四、程序代码
见附录源程序。
五、程序调试和测试
1. 调用模块时，结点结构调用和其它模块产生冲突，造成每一行全部出现两次错误，加入子函数申明后错误消失。
2 . 刚开始时曾忽略了部分变量参数标识"&"和“*”，使调试程序时费时不少。以后应重视确定参数变量和赋值属性区分和标识。
3. 此次课程设计采取数据抽象程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思绪较为清楚，实现调用顺利。 经过此次试验，使我对数据结构这门课程有了深入了解，每一个程序经过需求分析、概要设计、具体设计以后，思绪即清楚展现，程序也很快就出来了，最终经过调试、运行又有新体验。
<测试用例>
这是一个使用循环链表经典问题。本程序开始运行界面以下：
图7 约瑟夫环开始运行界面

选择1进入约瑟夫环问题叙述。

图8 约瑟夫环问题叙述

①选择2，输入下列数据测试：
请输入总人数n：7
请输入开始上限数m：20；
请依次输入每个人密码：3 1 7 2 4 8 4
出队次序：6 1 4 7 2 3 5

图9 约瑟夫环测试1

②继续选择2，输入下列数据测试：
请输入总人数n：5
请输入开始上限数m：30
请依次输入每个人密码：3 4 5 6 7
出队次序：5 3 1 2 4

图10 约瑟夫环测试2

③继续选择2，输入下列数据测试：
请输入总人数n：8
请输入开始上限数m：14
请依次输入每个人密码：3 4 5 6 7 8 9 10
出队次序：6 7 2 8 3 5 1 4

图11 约瑟夫环测试3

测试完成，选择0退出。

设计总结
我这次数据结构课程设计题目是:《约瑟夫环》,经过对该题目标设计,我加深了对数据结构及存放结构了解,深入地了解和掌握了书本中所学多种数据结构，尤其是对单循环链表上基础运算实现,学会了怎样把学到知识用于处理实际问题,锻炼了自己动手能力。
经过这次数据结构课程设计，我感受最深就是对于循环链表使用，能够说对循环链表有了比以前更深入认识，以前只是一知半解，假如只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大收获就在于对循环链表有了一定了解，包含其中一系列操作，如建立一个循环链表，删除链表中一个结点，增加一个结点等。
在调试程序时候我也有所体会，即使约瑟夫环问题不是极难，但调试时候还是会出现很多错误，所以我们不能认为轻易就不认真对待。在以后学习中，要能不停发觉问题，提出问题，处理问题，从不足之处出发，在不停学习中提升自己。
两周课程设计很短暂，但其间内容是很充实，在其中我学习到了很多平时书本中无法学到东西，积累了经验，锻炼了自己分析问题，处理问题能力，并学会了怎样将所学各课知识融会，组织起来进行学习，总而言之这两周中我学到很多，受益匪浅。
参考文件
1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4．谭浩强.《c语言程序设计》. 清华大学出版社.
致谢
这次课程设计，我们两人一个小组去完成我们自己课程，不过还是得到了来自很多方面帮助。在此首先要感谢学院提供给我这次实践机会，让我们有机会贴近现实，感受成功喜悦；其次要感谢试验机房老师提供优良试验设备供我们做课设，正是这种良好课设环境让我们整个课设过程心情全部很愉快。再次要感谢指导老师们辛勤指导，每当我们碰到疑难问题时，是她们一次次不厌其烦解释和悉心指导，我们才能闯过一个个难关，抵达胜利彼岸，是她们给我们提供了一次宝贵检验自己机会。最终也要感谢同学们帮助，有了她们支持使我碰到任何困难全部不是一个人在战斗。感谢全部在我课程设计过程中帮助过我人！
附录
源代码：
#include <stdio.h>//输入输出函数头文件
#include <stdlib.h>//字符串转短整形函数头文件10140219
//
typedef struct LNode//定义单循环链表中节点结构
{
int num;//编号
int pwd;//password
struct LNode *next;//指向下一结点指针
}LNode;
/*结构结点*/
LNode *createNode(int m_num,int m_pwd)
{
LNode *p;
p=(LNode *)malloc(sizeof(LNode));//生成一个结点

p->num=m_num;//把实参赋给对应数据域
p->pwd=m_pwd;
p->next=NULL;//指针域为空
return p;
}
/**创建循环链表**/
void createList(LNode **ppHead,int n)
{/*创建单向循环链表ppHead，人数个数为n，并输入每个人密码值，若
建立失败则生成头结点，让cur指向她，若建立成功则插入结点P，cur指
向数据元素为p,后续为"空"节点，再把P插入循环链表ppHead中*/
int i,m_pwd;
LNode *p,*cur;//cur:浮标指针
for(i=1;i<=n;i++)
{
printf("输入第%d个人密码：",i);
scanf("%d",&m_pwd);//输入持有密码
p=createNode(i,m_pwd);//调用结构结点函数
if(*ppHead==NULL)//假如头结点为空
{
*ppHead=cur=p;//生成头结点，让cur指向她
cur->next=*ppHead;//cur指针域指向本身
}
else//假如不为空，则插入结点
{
p->next = cur->next;
cur->next = p;
cur= p;//cur指向新插入结点
}
}
printf("完成创建！\n"); //提醒链表创建完成
}
/*出队处理*/
void jose(LNode *ppHead,int m_pwd)
{/*p指向要删除节点前一个节点，ppHead指向要删除节点，使p=ppHead，ppHead再指向要删除节点下一个节点，使p和ppHead链接，输出p指向节点编号和密码值，释
放ppHead，如此循环，直至把全部节点全部打印和删除为止！*/
int i,j;
LNode *p,*p_del;//定义指针变量
for(i=1;p!=ppHead;i++){
for(j=1;j<m_pwd;++j){
p=ppHead;//p赋值为ppHead，p指向要删除结点前一个结点
ppHead=ppHead->next;//ppHead指向下一个元素
}
p->next = ppHead->next;//p结点和头结点链接
i=ppHead->pwd;//i赋值为ppHead->pwd
j=ppHead->num;//j赋值为ppHead->num，j为要删除密码值
printf("第%d个人出列，密码：%d\n",j,i);
m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd
free(ppHead);//释放头结点
ppHead=p->next;//ppHead重新赋值给p->next,即释放前ppHead->pwd指针//删除报数结点
}
i=ppHead->pwd;//i赋值为ppHead->pwd
j=ppHead->num;//j赋值为ppHead->num
printf("最终一个出列是%d号，密码是:%d\n",j,i);
free(ppHead);//释放头结点
}
void instruction()
{
printf("****************************************************************\n");
printf("约瑟夫环:\n");
printf(" 编号为1,2,3,4…,nn个人按顺时针方向围坐一圈,每人持有一个密\n");
printf("码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始\n");
printf("按顺时针方向自1开始次序报数,报到时停止.报m人出列，将她密码\n");
printf("m作为新m值,从她在顺时针方向上下一人开始重新从1报数,如此下去,\n");
printf("直到全部些人全部出列为止.编程打印出列次序.\n");
printf("******************************************************\n");
return 0;
}
void menu(){
printf("**************************约瑟夫环 *****************************\n");
printf(" \n");
printf(" [1]约瑟夫环问题叙述 \n");
printf(" [2]按要求求解约瑟夫环 \n");
printf(" [0]退出 \n");
printf("************************** 欢迎使用！ ****************************\n");
}
/*主函数模块*/
int main(){
int n,m,x;
LNode *ppHead=NULL;
menu();
for(;;){
printf("\n请选择要实施操作：");
scanf("%d",&x);
system("cls");
switch(x){
case 1:
printf("****************************************************************\n");
printf("约瑟夫环:\n");
printf(" 编号为1,2,3,4…,nn个人按顺时针方向围坐一圈,每人持有一个密\n");
printf("码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始\n");
printf("按顺时针方向自1开始次序报数,报到m时停止.报m人出列，将她密码\n");
printf("m作为新m值,从她在顺时针方向上下一人开始重新从1报数,如此下去,\n");
printf("直到全部些人全部出列为止.编程打印出列次序.\n");
printf("****************************************************************\n");
main();
break;
case 2:
printf("\n请输入总人数n：");
scanf("%d",&n);
printf("请输入开始上限数m：");
scanf("%d",&m);
createList(&ppHead,n);
printf("\n");
printf("出队次序：\n");
jose(ppHead,m);
printf("\n约瑟夫周游戏结束!\n");
main();
break;

case 0:
exit(0);
default:
system("cls");
printf("\n您选择操作有误，请重新选择...\n\n\n");
main();
}
}
return 0;
}