计算机科学与技术专业
《数据结构与算法》课程设计报告
班 级： 206721
学 号： 20672113
姓 名：吴凤娇
指导老师：张一
摘 要
1． 本演示程序中，人数 n 应为任意的，首先应输入一个值
赋给初始报数上限 m，程序应能自动保存出列人的序号和将
出列的人所持的密码赋给 m，再次作为报数上限，如此循环，
直至所有人都出列为止。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终
端上显示“提示信息”之后，由用户在键盘上输入相应数据
（即每个人所持的密码），每个人的序号由程序自动分配。
3． 程序执行的命令包括：
（1）构造链表；（2）输入数据；（3）执行报数，储存出列
人的序号，删除出列人的信息以及把出列人的密码赋给 m；
（4）结束。
目 录
一、 问题描述和分析 …………………………………………… 1
二、 数据结构设计 …………………………………………… 3
三、 算法设计 ………………………………………………… 6
四、 源代码说明 ………………………………………………… 9
五、 结果与分析 ………………………………………………… 12
一、问题描述和分析
1. 问题描述
约瑟夫环是一个数学的应用问题：
已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆
桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的
下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重
复下去，直到圆桌周围的人全部出列。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入
n,m,k 三个正整数，来求出列的序列。这个问题采用的是典型的
循环链表的数据结构，就是将一个链表的尾元素指针指向队首元
素。 p->link=head
解决问题的核心步骤：
1.建立一个具有 n 个链结点，无头结点的循环链表
2.确定第 1 个报数人的位置
3.不断地从链表中删除链结点，直到链表为空
2. 分析
确定问题的类型。
（1）带头结点的单循环链表抽象数据类型 sclinlist，其中包括的基
本操作函数有：初始化操作函数，插入一个结点操作函数，删除一
个几结点操作函数，取一个结点数据操作函数和判表是否为非空操
作函数。
（2） void sclldeleteafter（sclnode *p），其功能是删除带头结点的
单循环链表中指针 p 所指结点的下一个结点。
（3） void jesephring（sclnode *head，int m），其功能是对带头结
点的单循环链表 head，
以 m 为初始报数上限值实现问题要求。
（4） void main（），主函数，其功能是给出测试数据值，建立测
试数据值的带头结点单循环链表，调用 jesering（）函数实现问题要
求。
二、数据结构设计
1. 数据结构设计考虑
为了实现上述操作，应以单向循环链表为存储结构。
基本操作：
new_code( )
操作结果：构造空链表，若成功就初始化每个人的相关信息
delete_code( )
初始条件：线性链表存在
操作结果：释放指向出列的人的结点，并重新报数
本程序包含三个模块：
（1）主程序模块；
（2）构造链表并输入每个人信息模块；
（3）释放结点模块；
2. 逻辑结构与存储结构（用伪码描述）
1、 元素类型，结点类型和指针类型：
typedef int ElemType;
typedef struct LNode
{
int num;
ElemType data;
struct LNode *next;
}LNode;
LNode *head; *this; *new;
2、 每个模块的分析：
i. 主程序模块：
main()
{
int m,n,i;
printf("Enter the first code (m):");
scanf("%d",&m);
printf("\nEnter the people number (n):");
scanf("%d",&n);
