衡阳师范学院
《 数 据 结 构 》 课 程 设 计
题 目: 约瑟夫环
班 级: 07 计算机 1 班
学 号:
作者姓名:
指导教师:
08 年 12 月 10 日
2
目 录
1、需求分析………………………………………………………………………………
(3)
1.1 问题描述…………………………………………………………………(3)
1.2 基本要求…………………………………………………………………(3)
2、概要设计………………………………………………………………………………
(4)
2.1 数据结构…………………………………………………………………(4)
2.2 程序模块…………………………………………………………………(4)
2.3 各模块之间的调用关系及算法设计……………………………………(6)
3、详细设计………………………………………………………………………………
(9)
4、调试与分析…………………………………………………………………………(12)
4.1 程序调试…………………………………………………………………(12)
5、用户手册……………………………………………………………………………
(16)
5.1 运行环境…………………………………………………………………(16)
5.2 执行文件…………………………………………………………………(16)
6、参考文献……………………………………………………………………………
(16)
7、心得体会……………………………………………………………………………
3
(16)
8、小组成员任务分配及工作进度安排…………………………………………(17)
1、 需求分析
1.1 问题描述
本演示程序中,人数 n 应为任意的,首先应输入一个值赋给初始报
数上限 m,程序应能自动保存出列人的序号和将出列的人所持的密
码赋给 m,再次作为报数上限,如此循环,直至所有人都出列为止。
演示程序以用户和计算机的对话方式执行,即在计算机终端上显示
“提示信息”之后,由用户在键盘上输入相应数据(即每个人所持
的密码),每个人的序号由程序自动分配。
程序执行的命令包括:
(1)构造链表;(2)输入数据;(3)执行报数,储存出列人的序号,
删除出列人的信息以及把出列人的密码赋给 m;(4)结束。
测试数据
(1)n=5,5 个人的密码依次为:2,5,4,6,7,首先 m 值为 6,
则这正确的出列顺序为 1,3,4,2,5。
1.2 基本要求
演示程序以用户和计算机对话方式进行,根据提示信息由用户从键
盘输入数据,以“回车符“为结束标志,运行后输出的结果是约瑟
夫环的相关信息和经过报数后出队的人的序列号及相关信息。结果
出来后再选择输入一数字,输入 1 继续新一轮的游戏,输入 0 结束,
退出此游戏。
4
2、 概要设计
2.1 数据结构
本程序包含三个模块:
(1) 主程序模块;
(2) 构造链表并输入每个人信息模块;
(3) 释放结点模块;
2.2 程序模块
1. 元素类型,结点类型和指针类型:
typedef int ElemType;
typedef struct LNode
{
int num;
ElemType data;
struct LNode *next;
}LNode;
LNode *head; *this; *new;
2. 每个模块的分析:
(1) 主程序模块:
int main(void)//主函数
{
LinkList L;
int personNumber, reportValue;
int array[MAXPERSONNUMBER];
personNumber = GetPersonNumber();
reportValue = GetFirstCountValue();
CreatLinkList(&L);
InitLinkList(&L, personNumber);
5
GetOutputOrder(&L, personNumber, reportValue, array);
printResult(array, personNumber);
system("pause");
return 0;
(2) 构造链表并输入每个人信息模块;
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->data = 1;
p->password = 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);
}
(3) 构造结点模块
void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int
array[MAXPERSONNUMBER])
{