一维数组实现约瑟夫环_约瑟夫环问题_约瑟夫环隔两人杀一个

数据结构实验报告

班级： 计科0901班

学号： 0908030106

姓名：王玲

西安科技大学

计算机科学与技术学院

题 目： 约瑟夫环问题

一、设计内容

约瑟夫环问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部出列为止。试设计程序实现之。

二、设计目的

1. 达到熟练掌握C++语言的基本知识和技能；

2. 能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。约瑟夫环问题

三、系统分析与设计（确定程序功能模块）

JesephRing()函数是实现问题要求的主要函数，其算法思想是：从1至m对带头结点的单循环链表计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，并删除该结点，然后从该结点的下一个结点起重新从1开始循环计数；如此下去，直到单循环链表为空时，循环过程结束。

模块划分：

（1）头文件SCLinLish.h。头文件SCLinLish.h中包括结点结构体定义.初始化操作.插入一个结点操作.删除一个结点操作.取一个数据元素操作及判单循环链表是否为空操作等！

（2）Main.c文件。Main.c文件包括以下3个函数。

void SCLLDeleteAfter(SCLNode *p)函数：其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。这是根据本问题中需要设计的一个函数。 Void JesephRing(SCLNode *head,int m)函数：其功能是对带头结点的单循环链表head，以m为初始报数上限值，完成约瑟夫环问题程序模拟过程。

Void main(void )函数：主函数，其功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。

数据结构：

（1）数据类型DataType定义如下：

Typedef struct

{

Int number;

Int cipher;

}DataType;

(2) 带头结点单循环链表结点的结构体定义如下：

typedef struct node

{

DataType data;

struct node *next;

}SCLNode;

四、源程序代码

#include <stdio.h>

#include<stdlib.h>

#include<malloc.h>

#include<iostream.h>

#include"SCLinList.h"// 包含头文件SCLinList

typedef struct node

{

DataType data;

struct node *next;

}SCLNode;

void SCLLInitiate (SCLNode **head)

{

if(*head = (SCLNode *)mallloc(sizeof(SCLNode)))==NULL exit(1); (*head)->next=*head;

}

int SCLLInsert (SCLNode *head,int i,DataType x)

{

SCLNode *p,*q;

int j;

p=head ->next;j=1;

while(p!=head && j<j-1)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-32307-1.html