文档介绍：精品设计
设计1 约瑟夫环问题
需求分析
一、具体目标包括:
1、实现单循环链表的初始化以及节点的创建和赋值
2、理解约瑟夫环的定义,通过循环找到每次要出列的人的位置
3、从单循环链表中删除结点,对头节点和一般结点分情况讨论
二、单循环链表的抽象数据类型定义为:
ADT CLink {
数据对象:D{ai | ai∈Elemset,i=1,2,…,n,n≥0}
数据关系:R={<ai-1,ai>,<an,a1> | ai-1,ai∈D,i=2,…n}
基本操作:
Status CreateList(CLink &head,int length)
操作结果:构造一个含有n个元素的单向循环链表。
void Selectqueue(CLink head,int n,int m)
操作结果:输出符合上限应该出列的结点。}
三、问题描述
设编号为1,2…,n(n>0)个人按顺时针方向围坐一圈,每人持有一个正整数密码。开始时任意给出一个报数上限值m,从第一人开始顺时针方向自1 起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺指针方向上的下一个人起重新自1起顺序报数;下去,直到所有人全部出列为止。要求设计一个程序模拟此过程。
四、基本要求
利用单向循环链表存储结构模拟此过程,按照出列的顺序输出个人的编号以及持有的密码。
二、概要设计
一、本程序主要分为三个模块
1、主模块
void main(){
单循环链表的初始化;
输入总人数和第一个上限值;
调用另外两个模块,实现出列人的顺序;}
单向循环链表抽象数据类型模块:CreateList(CLink &head,int length)实现单向循环链表的抽象数据类型功能;
3、出列节点的顺序模块:Selectqueue(CLink head,int n,int m),实现出列结点的顺序功能;
三、详细设计
1、主模块的实现算法
基本思想:对单链表进行初始化,并设置总人数和第一个报数的上限值。若总人数或者上限不符合要求时则重新输入。
2、构建一个单循环链表算法
基本思想:先创建单链表的一个结点,再依次循环创建直至达到总结点数,并且让最后一个创建的结点的指针域为头结点的地址。
Status CreateList(CLink &head,int length)
{
CLink before;
CLink new_node;
int i;
printf("Please Input Password 1 : ");
scanf("%d",&head->password);
head->number=1;
head->next=NULL;
before=head;
for(i=1;i<length;i++)
{
if(!(new_node=(CLink)malloc(ode))))
return OVERFLOW;
new_node->number = i+1;
printf("Please Input Password %d : ", new_node->number);
scanf("%d",&new_node->password);
new_node->next = NULL;
before->next=new_node;
before=new_node;
}
new_node->next =head;
return TRUE;
}
流程图1
3、构建一个实现出列顺序的算法
基本思想:用ptr只向当前出列的结点,若为头结点时则找到指向头结点的指针,并做结点的删除,若不是头结点,则用
back指针作为指向ptr的指针,进行结点的删除。
void selectqueue(CLink head,int n,int m)
{
CLink ptr,back,last;
int i,j;
ptr=head;
for(i=0;i<n;i++)
{
for(j=0;j<m-1;j++)
{
back=ptr;//定位最后一个数的接点赋值给back
ptr=back->next;
}
m=ptr->password;
printf("第%d个出列的编号以及密码为:%d,%d\n",i+1,ptr->number,m);
if(ptr==head)
{
last=head;
while(last->next!=head)
last=last->next;
last->next=head->next;
free(ptr);