第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
约瑟夫环问题（数据结构课程设计报告+源代码）.doc
《数据结构》课程设计报告
实验二 链表的设计
班
学
姓
级：
号：
名：
同 组 者：
时
间：
计升 091
090814101
王芙麟
无
一、设计目的与内容
1．设计目的
（1）．熟悉线性表的链式储结构，单链表、双链表、循环链表。
（2）．熟悉对链表的一些基本操作和具体的函数定义。
（3）．熟悉在链表上的常用操作方法。
（4）．利用链表的基本操作完成一定设计任务。
2．设计内容：
约瑟夫环问题
编号是 1，2，……,n 的 n 个人，按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。
一开始任选一个正整数作为报数上限值 m,从第一个人开始顺时针方向自 1 开始顺序报数，
报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一
个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺
序。
要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号
二、 算法的基本思想
用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大
主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队
的函数、主函数等函数。
（1）主程序模块
Void main（）{
初始化；
do
{
接受命令；
处理命令；
}while（“命令”=“退出”）；
}
（2）创建链表模块
Static void creatlist（行参）{
初始化；
For{
接受命令；
处理命令 }
}
（3）输出链表信息模块
static void PrntList(参数){
定义变量并初始化；
输出命令；
}
（4）删除结点也就是出队模块
static void StatGame(参数){
定义变量并初始化；
While{
开始报数；
输出结果；}}
三、测试数据
m 的初值为 20，n=7 ,7 个人的密码依次为 3，1，7，2，4，7，4
四、源程序及系统文件使用说明
（1） 主函数模块代码
circularlist pHead=NULL;
int main(void)
{ int n, m， iflag=1
while(iflag=1){
printf("请输入总人数 n=");
scanf("%d",&n);
printf("\n 再请输入初始报数上限 m="); scanf("%d",&m)；
CreatList(&pHead,n);
printf("\n 输出所有人的信息如下:\n");
PrntList(pHead);
printf("\n 按照出列顺序输出每个人的编号:\n");
StatGame(&pHead, m);
printf("\n 约瑟夫环的游戏完成!\n");
printf("输入 1 开始建环做游戏，输入 0 退出该游戏，请选择!");scanf("%d",&i);
return 0;
}
}
程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入总人数和初始的
报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再调用 StatGame（）函数，
报到上限的那个结点从表中删除既出队，然后再选择输入一个数确定是否继续游戏，输入 1 继
续，输入 0 退出。
（2） 创建单循环链表函数模块代码
static void CreatList(circularlist * ppHead, const int n)
{
int i,ikey;
Node *pNew, *pCur;
for(i=1;i<=n;i++)
{
printf("请输入第%d个人所持有的密码:",i);
scanf("%d", &ikey);
pNew=GetNode(i,ikey);
if(*ppHead==NULL)
{
*ppHead=pCur=pNew; pCur->next=*ppHead;
}
else
{
pNew->next=pCur->next; pCur->next=pNew; pCur=pNew; }
}
程序解释：用一个for循环来给链表的每个结点分配空间，并从键盘输入每人所
持有的密码，如果头结点的值为空，使其指向新生成的一个结点，新结点的next
指针指向头结点，如果不是，则当前结点的next的值赋给新结点的next，然后
当前结点的next值指向新结点，再当前结点的指针指向新结点，实现链表的建
立。
（3）删除结点函数代码
static void StatGame(circularlist * ppHead, int ikey)
{
int iCounter, iFlag=1;
Node *pPrv, *pCur, *pDel;
pPrv=pCur=*ppHead;
while(iFlag) ! */
{
for(iCounter=1;iCounter<=ikey;iCounter++)
{
pPrv=pCur; pCur=pCur->next;
}
if(pPrv==pCur) iFlag=0;
pDel=pCur; Prv->next=pCur->next;
pCur=pCur->next;
ikey=pDel->key;
printf("第 %d个人出列, 所持有密码是: %d\n", pDel->id,pDel->key); free(pDel);
}
ppHead=NULL;
}
程序解释：设立一个标签，值为 1 执行循环语句，值为 0 跳出循环。循环语句里的 for 循环
实现报数功能，也就是结点移动的功能，移动 ikey 个结点，再删除第 ikey 个结点，并把该
结点的密码值赋给 ikey，再从该结点的下一个结点移动，重复上面的过程，结点全都删除后
使标签的值为 0，结束 while 循环，游戏结束。
源程序：
#include
#include
#define TRUE 1
#define FALSE 0
typedef struct Node
{ int id; /* 编号 */
int key; /* 密码 */
struct Node *next;
} Node,* circularlist; /* 创建单向循环链表 */
static void CreatList(circularlist * pphead, const int n); /* 运行"约瑟夫环"问题 */
static void StatGame(circularlist * pphead, int ikey); /* 打印循环链表 */
static void PrntList(const Node *); /* 得到一个结点 */
static Node *GetNode(const int, const int); /* 测试链表是否为空, 空为 TRUE 空为 FALSE */
static unsigned EmptyList(const Node *);
int main(void)
{
int n, m;
while(iflag==1){
int iflag=1;
circularlist pHead=NULL;
printf("请输入总人数 n="); scanf("%d",&n);
printf("\n 再请输入初始报数上限 m="); scanf("%d",&m);
CreatList(&pHead,n);
printf("\n------------输出所有的人信息如下:-------------\n");
PrntList(pHead);
printf("\n--------------按照出列顺序输出每个人的编号:---------------\n");
StatGame(&pHead, m);
printf("\n 约瑟夫环的游戏完成!\n");
printf("\n\n 是否继续游戏?输入 1 继续，输入 0 退出，请选择!\n");
scanf("%d",&iflag);
}
return 0;
pCur->next=*ppHead;
pNew=GetNode(i,ikey);
}
static void CreatList(circularlist * ppHead, const int n)
{
int i,ikey; Node *pNew, *pCur;
for(i=1;i<=n;i++)
{
printf("请输入第%d 个人所持有的密码:",i);
scanf("%d", &ikey);
if(*ppHead==NULL)
{
*ppHead=pCur=pNew;
}
else
{
pNew->next=pCur->next;
}
}
printf("约瑟夫环已建成,可以开始报数游戏!\n");
}
static void StatGame(circularlist * ppHead, int ikey)
{
int iCounter, iFlag=1;
pPrv=pCur=*ppHead;
while(pPrv->next!=*ppHead)
while(iFlag)
{
for(iCounter=1;iCounter<=ikey;iCounter++) /*移动 iCipher-1 趟指针! */
pCur->next=pNew;
pCur=pNew;
Node *pPrv, *pCur, *pDel;
/* 将 pPrv 初始为指向尾结点，为删除作好准备 */
pPrv=pPrv->next;
{
pPrv=pCur;
}
if(pPrv==pCur) /* 是否为最后一个结点了 */
pCur=pCur->next;
iFlag=0;
pDel=pCur; /* 删除 pCur 指向的结点，即有人出列 */
pPrv->next=pCur->next;
pCur=pCur->next;
ikey=pDel->key;
printf("第 %d 个人出列, 所持有密码是: %d\n", pDel->id,pDel->key); /* 这个编号标识出列的
顺序 */
free(pDel);
}
ppHead=NULL; /* 为了安全就给个空值 */
}
static void PrntList(const Node *pHead)
{
const Node *pCur=pHead;
if (EmptyList(pHead))
return;
do
{
printf("第 %d 个人所持有的密码是: %d\n",pCur->id,pCur->key);
pCur=pCur->next;
} while (pCur!=pHead);
}
static Node *GetNode(const int iId,const int ikey)
{
Node *pNew;
pNew=(Node *)malloc(sizeof(Node));
if(!pNew)
{
printf("存储分配不成功!\n");
exit(-1);
}
pNew->id=iId;
}
pNew->key=ikey;
pNew->next=NULL;
return pNew;
static unsigned EmptyList(const Node *pHead)
{
if(!pHead)
{
printf("表是空的!\n");
return TRUE;
}
return FALSE;
}
五、心得体会
通过课程设计，培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深
入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基
本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线形表、链表、
循环链表、树、图等存储结构，特别是对单循环链表理解的更深。也使我认识到《数据结构》
这门课程是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重
要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强
的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理
解与掌握书本上的东西。
本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏，由于刚开始对循环链表的理
解不够，也没理请约瑟夫环的基本思路，做起来有点难，但通过反复的修改，最终还是能够
理解的。
六、参考文献
1．《数据结构（C 语言版）》 严蔚敏，吴伟民 清华大学出版社
2．《数据结构题集（C 语言版）》严蔚敏，吴伟民 米宁 清华大学出版社
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
