数据结构与算法实验报告-约瑟夫环

题目：约瑟夫环问题

班级：姓名：学号：完成日期：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∈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(\scanf(\scanf(\

L=CreateLinkList(n);

if(L->next->next= =L->next) return OK;//空表 else {

for(j=1;j

{L=L->next; //从第s个人开始报数 }

while(L->next!=NULL) {

if (cc= =1) {

for(j=1;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时所得结果如下：