2344049封其业joseph环.docx
《2344049封其业joseph环.docx》由会员分享，可在线阅读，更多相关《2344049封其业joseph环.docx（12页珍藏版）》请在冰点文库上搜索。
2344049封其业joseph环
滨江学院
《数据结构》课程设计
题目joseph环
学号20102344049
姓名封其业
专业软件工程
指导教师
组号
一、问题描述
任务：
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
设计一个程序来求出出列顺序。
要求：
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：
m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
要求：
输入数据：
建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。
输出形式：
建立一个输出函数，将正确的输出序列
二、需求分析
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。
1.输入的形式和输入值的范围
本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。
2.输出的形式
从屏幕显示出列顺序。
3.程序功能
提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。
三、概要设计
以单向循环链表实现该结构。
1.抽象数据类型的定义为：
ADTLNode
{
数据对象Daiai∈CharSeti12…nn≥0
数据关系R1ltai-1aigtai∈DI2…n
基本操作
InitListLinkListL
操作结果构造一个空的线性链表L。
DestroyListLinkListL
初始条件线性链表L已存在。
操作结果销毁线性链表L。
ListLengthLinkListL
初始条件线性链表L已存在。
操作结果返回线性链表L的长度。
ListEmptyLinkListL
初始条件线性链表L已存在。
操作结果若线性链表L为空表则返回True否则返回False。
GetElemLinkListLpos
初始条件线性链表L已存在。
操作结果若1posLengthL则返回表中第pos个数据元素。
LocateElemLinkListLeq初始条件线性链表L已存在。
操作结果若线性链表L中存在元素e则q指示L中第一个值为e的元素的位置并返回函数值True否则q指示第一个大于e的元素的前驱的位置并返回函数值False
AppendLinkListLe初始条件线性链表L已存在。
操作结果在线性链表L的末尾插入元素e。
InsertAfterLinkListLqe初始条件线性链表L已存在q指示L中一个元素。
操作结果在线性链表L中q指示的元素之后插入元素e。
ListTraverseqvisit初始条件线性链表L已存在q指示L中一个元素。
操作结果依次对L中q指示的元素开始的每个元素调用函数visit。
}
ADTLNode
由于上面已经确定用单向循环链表来存储JOSEPH环，所以现在定义一下的数据结构来存储JOSEPH环。
定义linklisthead为头指针，用来调用链表中的数据。
本程序共包含3个函数
1）主函数main
2）创建JOSEPH环函数creat3输出JOSEPH环函数shuchu各函数关系：
图
3）各函数关系：
主程序模块→有序表单元模块→输出函数模块
4、详细设计
（1）抽象数据类型
Adtlist{
数据对象：
D={ai|ai∈ElemSet，2，…，n,n>=0}
数据关系：
R1=|ai-1，a∈D,i=2,…,n}
基本操作：
statusCreateList_Circle（member**q_head,intn）
操作结果为构造一个空循环链表*L
statusOutNode（member**qq）
初始条件为线性循环链表存在，操作结果为输出出对队列并删除选择对象
}ADTList
（2）定义结构体类型
其中password为密码，No为序号，将两者均定义为整型，LNode*next为下一成员指针，具体算法如下：
typedefstructLNode
{
intpassword;
intNo;
structLNode*next;
}member;
typedefintstatus;
（3）主函数模块算法
程序main中调用了CreateList_Circle函数，创建了循环链表，还调用了OutNode函数实现了输出。
首先定义人数n，头指针即首员地址和遍历指针均为空，当输入人数小于等于0时，输出“重新输入”字样，如果输入数大于0则创建循环链表，返回头指针。
当m小于等于0时也提示重新输入，把head附给q，寻找出列成员，化简m值，k从1到m-1指向出列成员，然后修改m,删除链表的出列成员，成员数自减。
具体算法如下：
statusmain（）
{
intn,m;
member*head=NULL,*q=NULL;
while（n<=0）
printf（"nmustbepositive,pleaseenteragain:
\n"）;
if（!
CreateList_Circle（&head,n））
returnOVERFLOW;
while（m<=0）
printf（"mmustbepositive,pleaseenteragain:
\n"）;
p=head;，
while（n>=2）
{
intk;
m=（m%n==0）?
n:
m%n;
for（k=1;ip=p->next;
m=p->password;
OutNode（&q）;
n--;
}
returnOK;
}
（4）创建链表模块算法
创建一个无头结点的循环链表，结点数n,*q_head返回链表头指针即首结点地址
statusCreateList_Circle（member**p_head,intn）
{
inti;
member*tail,*p;
*p_head=（member*）malloc（sizeof（member））;
if（!
（*p_head））returnOVERFLOW;
（*p_head）->No=1;
printf（"PleaseenterpasswordofNo.1:
\n"）;
scanf（"%d",&（*p_head）->password）;
tail=*p_head;
tail->next=NULL;
for（i=2;i{
p=（member*）malloc（sizeof（member））;
if（!
p）returnOVERFLOW;
p->No=i;
printf（"PleaseenterpasswordofNo.%d:
\n",i）;
scanf（"%d",&（p->password））;
tail=p;
}
tail->next=*p_head;
returnOK;
}
（5）输出模块算法
此算法删除链表中的结点*qq，操作实质是将*qq下一结点复制到*qq后将其释放。
具体算法如下：
statusOutNode（member**qq）
{
member*p;
（*qq）->password=（（*qq）->next）->password;
（*qq）->No=（（*qq）->next）->No;
p=（*qq）->next;
（*qq）->next=（*qq）->next->next;
free（p）;
returnOK;
}
流程图：
创建链表：
五、源代码
#include
#include
typedefstructNode
{
intkey;//每个人持有的密码
intnum;//这个人的编号
structNode*next;//指向下一个节点
}Node,*Link;
voidInitList（Link&L）//创建一个空的链表
{
L=（Node*）malloc（sizeof（Node））;
if（!
L）exit
（1）;
L->key=0;
L->num=0;
L->next=L;
}
voidCreater（intn,Link&L）//初始化链表
{
Linkp,q;
q=L;
for（inti=1;i<=n;i++）
{
p=（Node*）malloc（sizeof（Node））;
if（!
p）exit
（1）;
printf（"thekey_%dis:
",i）;
scanf（"%d",&p->key）;
p->num=i;
L->next=p;
L=p;
}
L->next=q->next;
free（q）;
}
voidmain（）
{
LinkL,p,q;
intn,x;
L=NULL;
InitList（L）;//构造出一个只有头结点的空链表
printf（"pleaseinputthetotlenumberofpeople:
"）;
scanf（"%d",&n）;//总共的人数n
printf（"thestartkeyis:
"）;
scanf（"%d",&x）;//初始密码为x
Creater（n,L）;//建立好一个约瑟夫环
p=L;
for（inti=1;i<=n;i++）
{
for（intj=1;jp=p->next;
q=p->next;
x=q->key;
printf（"%d",q->num）;
p->next=q->next;
free（q）;
}
}
五、测试数据
m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,
（正确的出列顺序应为6,1,4,7,2,3,5）
1.运行界面：
2.输入测试数据：
3.运行结果：
6、设计总结
我的这次数据结构课程设计的题目是:
《joseph环》通过对题目的设计，我加深了了对数据结构及储存结构的理解，进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单链表、单循环链表上基本运算的实现，学会了如何把学到的东西用于解决实际问题，锻炼了自己的动手能力。
通过这次数据结构课程设计，我感受最深的就是对于单链表，单循环链表，结构体等的使用，可以说对单链表，单循环链表有了比以前更进一步地认识，以前只是一知半解，如果只给个题目自己根本不知道怎么把程序完整的编出来，所以这次课程设计最大的收获就在于对循环表有一定的理解，包括其中的一系列操作，如建立一个单链表，循环列表，建一个结构体，删除链表中的结点，增加结点等。
在其中我学习到了很多平时书本上没有的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识知识融会，组织起来进行学习。
总之我学到的很多，受益匪浅。
升级会员 