题目：约瑟夫环问题
班级：姓名：学号：完成日期：2011.12.28
一、需求分析
1.问题描述：设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。
2.测试时n=8，s=1，m=4，若初始的顺序为1,2,3,4,5,6,7,8,则问题的解为4,8,5,2,1,3,7,6。
二、概要设计
为实现上述程序功能，应以循环队列表示。循环队列可用数组实现，但由于n是变量，我选择以单向链表实现循环队列。通过移动头结点的指针来实现“重新开始报数”，以循环实现计数。
1. 循环队列的抽象数据类型定义为：
ADT LinkQueue{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定其中a1端为队列头，an端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
GetHead(Q,&e)
初始条件：Q为非空队列。
操作结果：用e返回Q的队头元素。
EnQueue（&Q,e）
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue（&Q,&e）
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。
}ADT LinkQueue
2．本程序包含3个模块：
1）结点定义模块——对表结点进行定义
2)子函数定义模块——对链表的各操作的定义
3)主程序模块
模块之间的关系为主函数调用子函数模块，子函数调用结点结构。
三、详细设计
1． 头函数、元素类型、结点类型和指针类型
typedef int LElemType;
typedef int Status;
typedef struct LNode
{
LElemType data;
struct LNode *next;
}LNode,*LinkList;
2． 根据循环队列的特点，链表的头指针和尾结点的指针都指向第一个结点。
对链表的基本操作如下：
LNode *CreateLinkList(int n)
//构造一个空的循环队列，长为输入值n
Status ListDelete_L(LNode *L,LElemType *e)
//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
其中部分操作的伪代码如下：
LNode *CreateLinkList(int n)//顺序建立链表,L为头结点
{
L=(LNode*)malloc(sizeof(LNode));
p=(LNode*)malloc(sizeof(LNode));
L->next=p;
p->next=L->next;
p->data=1;
x=1;
for(i=0;i<=n-2;i++)
{
x++;
s=(LNode*)malloc(sizeof(LNode));
s->data=x;//插入表尾
p->next=s;
p=s;
}
p->next=L->next;
return L;
}
Status ListDelete_L(LNode *L,LElemType *e)
{//删除队列当前位置的元素q，并用e返回其值
LNode *p;
LNode *q;
p=L;
if(!(p->next))
return ERROR;
if (p->next==p)
{
L->next=NULL;
}
else
{q=p->next;
p->next=q->next;
*e=q->data;
free(q);
}
return OK;
}//ListDelete_L
3.主函数的伪码算法
int main(void)
{
LNode *L;
cc=1; //CC用于判断是否刚开始报数，1:刚开始 2:已经有人离开队列
scanf("%d",&n);
scanf("%d",&s);
scanf("%d",&m);
L=CreateLinkList(n);
if(L->next->next= =L->next)
return OK;//空表
else
{
for(j=1;j<s-1;j++)
{L=L->next; //从第s个人开始报数
}
while(L->next!=NULL)
{
if (cc= =1)
{
for(j=1;j<m;j++)
{
L=L->next;
}
ListDelete_L(L,&e);//删除第m个
printf(e); //出队列的数打印
++cc;
}
else
{
for(j=2;j<=m;j++)
/*有人离开队列后，报数为1的数向前移动了一位，因此，循环从2开始*/
{ L=L->next;}
ListDelete_L(L,&e);//删数第m个
printf(e); //出队列的数打印
}
}
return OK;
}
}
四、调试分析
1.由于对算法在C语言的实现不是很熟练，在编写程序的过程中犯了些语法错误，改正错误浪费了时间。
2.由于开始时对循环链表为空时的状态不大清楚，修改程序花费了较长时间。链表为空时应该为L->next=NULL。
3.本程序的模块划分比较合理，基本按照初步设计的算法进行实现。
4.在调试中遇到了一些新问题，改进了算法。
5.调试中遇到的问题
问题一：每次第m个出队之后从后一个开始重新计数。
解决：及时加入L=L->next; 调整指针。
问题二：有些操作的算法实现不能使用。
解决：把Status换为int或者*。
问题三： 第一次报数会多数一人。
解决：引入了cc，cc=1则为第一次报数。
6.算法的时间复杂度分析
函数ListDelete_L的时间复杂度均为O(1)，函数CreateLinkList的时间复杂度为O(n)，主函数的时间复杂度为O(n2)，综合来看此算法的时间复杂度为O(n+ n2)=O(n2)。
五、用户使用说明
1.本系统的运行环境为Windows系统Visual C++ 6.0，执行文件为j.c。
2.运行程序后即显示
输入总人数n的值，按Enter确认。即显示下图：
输入开始计数的人的序号s的值，Enter确认后显示如下：
输入每次数多少个人，即m的值。按Enter后显示所求顺序。
六、测试结果
n、s、m的值分别为8、1、4时所得结果如下：
n、s、m的值分别为10、3、5时所得结果如下：
n、s、m的值分别为100、3、5时所得结果如下：
经过手算比较，程序运行正确。
六、附录
带注释的源程序为：
#include<stdio.h>
#include<stdlib.h>
#define ERROR -1
#define OK 0
typedef int LElemType;
typedef int Status;
typedef struct LNode
{
LElemType data;
struct LNode *next;
}LNode,*LinkList;
LNode *CreateLinkList(int n)//顺序建立链表,L为头结点
{
int i,x;
LNode *p;
LNode *s;
LNode *L;
L=(LNode*)malloc(sizeof(LNode));
p=(LNode*)malloc(sizeof(LNode));
L->next=p;//循环链表空表
p->next=L->next;//p为尾结点
p->data=1;
x=1;
for(i=0;i<=n-2;i++)
{
x++;
s=(LNode*)malloc(sizeof(LNode));
s->data=x;//插入表尾
p->next=s;
p=s;
// printf("%d\n",x);
}
p->next=L->next;
return L;
}
Status ListDelete_L(LNode *L,LElemType *e)
{//删除队列当前位置的元素q，并用e返回其值，
LNode *p;
LNode *q;
p=L;
if(!(p->next))
return ERROR;
if (p->next==p)
{
// printf("Only one node left!\n");
//printf("%5d\n",p->data);
L->next=NULL;
}
else
{q=p->next;
p->next=q->next;
*e=q->data;
free(q);
}
return OK;
}//ListDelete_L
int main(void)
{
int s,m,n;
int j,e,cc;
LNode *L;
cc=1;
printf("total number of people is:\n");
scanf("%d",&n);
printf("start from: \n");
scanf("%d",&s);
printf("select: \n");
scanf("%d",&m);
L=CreateLinkList(n);
if(L->next->next= =L->next)
return OK;//空表
else
{
for(j=1;j<s-1;j++)
{L=L->next;
//从第s个人开始报数
}
while(L->next!=NULL)
{
if (cc==1) //CC用于判断是否刚开始报数，1为刚开始 2为已经有人离开队列，
{
for(j=1;j<m;j++)
{
L=L->next;
//printf("s%5d\n",L->data); //用于调试，观察开始报数的顺序，正式运行时可以注释掉
}
ListDelete_L(L,&e);//删数第m个
printf("%5d",e); //出队列的数打印
++cc;
}
else
{
for(j=2;j<=m;j++) //有人离开队列后，报数为1的数向前移动了一位，因此，循环从2开始
{
L=L->next;
//printf("ss%5d\n",L->data); //用于调试，看开始报数的顺序，正式运行时可以注释掉
}
ListDelete_L(L,&e);//删数第m个
printf("%5d",e); //出队列的数打印
}
}
return OK;
}
getchar();//循环不自动结束
}
第二篇：北理工数据结构实验一
《数据结构与算法设计》
实验报告
——实验一
学院：
班级：
学号：姓名：
一、实验目的
1.
2.
3.
4. 通过实验实践、巩固线性表的相关操作； 熟悉VC环境，加强编程、调试的练习； 用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。
二、实验内容
1、采用单向环表实现约瑟夫环。
请按以下要求编程实现：
① 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，??，m。
② 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。
三、程序设计
1、概要设计
为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。
（1）、单向环表的抽象数据类型定义为：
ADT Joseph{
数据对象：D={ai|ai∈ElemSet,i=1,2,3??,n,n≥0}
数据关系：R1={ <ai-1,ai>|ai∈D,i=1,2,??,n}
基本操作：
create(&L,n)
操作结果：构造一个有n个结点的单向环表L。
show(L)
初始条件：单向环表L已存在。
操作结果：按顺序在屏幕上输出L的数据元素。
Josephf( L,m,s,n)
初始条件：单向环表L已存在， s>0,n>0，s<m。
操作结果：返回约瑟夫环的计算结果。
}ADT Joseph
（2）、主程序流程
主程序首先调用create(&L,n)函数，创建含有m个节点的单向环表L，然后调用show(L)函数，顺序输出链表中的数据，最后调用Josephf( L,m,s,n)函数，依次输出报的数。
（3）、函数调用关系图
2、详细设计
(1)、数据类型设计
typedef int ElemType; //定义元素类型
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*Linklist; //定义节点类型，指针类型
（2）、操作算法程序实现：
void create(Linklist &L,int m)
{
//生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，??，m Linklist h,p;
L=(Linklist)malloc(sizeof(Lnode));
L->data = 1;
h=L;
for(int i=2;i<=m;i++)
{
p = (Linklist)malloc(sizeof(Lnode));
p->data = i; //生成新节点，数据为节点编号
h->next = p;
h = p; //插入链表
}
h->next = L; //形成循环链表
}
void show(Linklist L,int m)
{
//从第一个节点开始依次输出节点编号
printf("The numbers of the list are: \n"); //提示用户
Linklist h;
h=L;
for(int i=1;i<=m;i++) {
printf("%d ",h->data);
h = h->next;
}
printf("\n");
}
void Josephf(Linklist &L,int m,int s,int n) {
//实现约瑟夫环
Linklist h,q;
h = L;
q = L;
while(h->data != s) // h = h->next;
while(q->next!=h) // q = q->next;
for(int j=1;j<=m;j++)
{
int i=1;
while(i<n)
{
q=q->next;
i++;
}
printf("%d ",q->next->data); // q->next = q->next->next; // }
printf("\n");
}
（3）、主程序的代码实现：
int main()
{
int s,m,n;
Linklist L;
printf("请输入节点数m：\n");
scanf("%d",&m);
create(L,m); // show(L,m); // printf("请输入起始位置s：\n");
scanf("%d",&s);
printf("请输入报的数n：\n");
scanf("%d",&n);
Josephf(L,m,s,n); //定位开始的节点 定位在开始位置的上一个节点依次输出报号为n的节点 删除已输出节点 建立循环链表 输出链表数据 输出所报数字
return 0;
}
四、程序调试分析
1.
2.
3.
4. 引用标识符&不符合C语言语法，应使用C++; 为了实现循环链表，建立时应该不设头结点且第一个节点就存储编号数据； 删除节点时要定位到前一个指针，所以在定位开始位置后还要再定位到前一个指针； 输出时要注意增加“ ”（空格）和“\n”（换行），使输出易于辨识。
五、 用户使用说明
1. 本程序的运行环境为DOS操作系统，执行文件为：实验一.exe，双击打开文件。
2. 进入程序后，出现提示语句“请输入节点数m：”，用户根据提示输入节点数m,按Enter
键，显示生成的链表，同时出现提示语句：“请输入起始位置s：”，用户输入起始位置s，按Enter键，出现提示语句“请输入报的数n：”，用户输入报的数，按Enter键，即可得到依次报号的结果。
六、程序运行结果
测试一：
测试二：
七、程序清单
#include "stdio.h"
#include "stdlib.h"
typedef int Status;
typedef int ElemType;
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*Linklist; //定义链表结点
void create(Linklist &L,int m)
{
//生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，??，m Linklist h,p;
L=(Linklist)malloc(sizeof(Lnode));
L->data = 1;
h=L;
for(int i=2;i<=m;i++)
{
p = (Linklist)malloc(sizeof(Lnode));
p->data = i; //生成新节点，数据为节点编号
h->next = p;
h = p; //插入链表
}
h->next = L; //形成循环链表
}
void show(Linklist L,int m)
{
//从第一个节点开始依次输出节点编号
printf("The numbers of the list are: \n"); //提示用户
Linklist h;
h=L;
for(int i=1;i<=m;i++)
{
printf("%d ",h->data);
h = h->next;
}
printf("\n");
}
void Josephf(Linklist &L,int m,int s,int n)
{
//实现约瑟夫环
Linklist h,q;
h = L;
q = L;
while(h->data != s) //定位开始的节点
h = h->next;
while(q->next!=h) //定位在开始位置的上一个节点
q = q->next;
for(int j=1;j<=m;j++)
{
int i=1;
while(i<n)
{
q=q->next;
i++;
}
printf("%d ",q->next->data); //依次输出报号为n的节点
q->next = q->next->next; //删除已输出节点
}
printf("\n");
}
int main()
{
int s,m,n;
Linklist L;
printf("请输入节点数m：\n");
scanf("%d",&m);
create(L,m);
show(L,m);
printf("请输入起始位置s：\n");
scanf("%d",&s);
printf("请输入报的数n：\n");
scanf("%d",&n);
Josephf(L,m,s,n);
return 0;
}
选做实验
2、归并顺序表（选作）。
请按以下要求编程实现：
① 从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标
记。
② 将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka
和linkb为空表。输出linkc。
③ 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一
个，输出删除重复整数后的链表。
例如：linka输入为：10 20 30 40 50 0
linkb输入为：15 20 25 30 35 40 45 50 0
归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50
程序清单
#include "stdio.h"
#include "stdlib.h"
typedef int ElemType;
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*Linklist; //定义链表结点,指针类型
void create(Linklist &L)
{
//生成从键盘输入的升序排列的整数序列链表
Linklist h,p;
int x = 1;
L=(Linklist)malloc(sizeof(Lnode)); //生成头指针
h=L;
while(x!=0)
{
scanf("%d",&x);
p = (Linklist)malloc(sizeof(Lnode));
p->data = x; //生成新节点，数据输入数字
h->next = p;
h = p; //插入链表
}
h->next = NULL;
}
void show(Linklist L)
{
//依次输出链表中的元素
Linklist h;
h=L->next;
while(h->next) //指针指向空指针时结束循环 {
printf("%d ",h->data);
h = h->next;
}
printf("\n");
}
void merge(Linklist &La,Linklist &Lb,Linklist &Lc)
{
//将链表La和Lb归并为Lc，Lc仍然为升序排列
Linklist ha,hb,hc,p;
Lc=(Linklist)malloc(sizeof(Lnode));//生成头指针
hc=Lc;
ha=La->next;
hb=Lb->next;
while(ha->next && hb->next) //插入La和Lb中较小的数,直到La或者Lb为空
{
p = (Linklist)malloc(sizeof(Lnode));
if(ha->data<=hb->data)
{
p->data = ha->data;
hc->next = p;
hc = p;
ha = ha->next;
}
else
{
p->data = hb->data;
hc->next = p;
hc = p;
hb = hb->next;
}
}
if(ha->next)
hc->next = ha;
if(hb->next)
hc->next = hb;
//将没有插入完的链表直接接在Lc后面
}
void listdelete(Linklist &L)
{
//删除Lc中重复的数字
Linklist h;
h=L;
while(h->next->next)
{
if(h->next->data == h->next->next->data)
h->next = h->next->next; //如果相邻两数字相同，删除相同数字中前一个对应的节点
else h=h->next; //如果相邻两数字不同，指针指向下一个节点 }
}
void clear(Linklist &La,Linklist &Lb)
{
//将La，Lb置空
La->next->next=NULL;
Lb->next->next=NULL;
printf("置空后La中的元素为：\n");
show(La);
printf("置空后Lb中的元素为：\n");
show(Lb);
}
int main()
{
int s,m,n;
Linklist La,Lb,Lc;
printf("请输入升序整数序列La：\n");
create(La);
printf("La中的元素依次为：\n");
show(La);
printf("请输入升序整数序列Lb：\n");
create(Lb);
printf("Lb中的元素依次为：\n");
show(Lb);
if(La->next->next || Lb->next->next) //判断输入是否正确 {
merge(La,Lb,Lc);
printf("合并后Lc中的元素为：\n");
show(Lc);
listdelete(Lc);
printf("删除重复整数后Lc的元素为：\n");
show(Lc);
clear(La,Lb);
}
else
printf("La 和 Lb 都是空表，输入有误\n");
return 0;
}
程序运行结果 测试一：
测试二：
测试三：
