篇一：约瑟夫环实验报告
《数据结构与算法设计》
实验报告
——实验一
学院：自动化学院
班级：06111001
学号：1120101525
姓名：王冬
一、 实验目的
1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际的问题。
2、在编程、上机调试的过程中，加深对线性链表这种数据结构的 基本概念理解。
3、锻炼较强的思维和动手能力和更加了解编程思想和编程技 巧。
二、实验内容
1、 采用单向环表实现约瑟夫环。
请按以下要求编程实现：
① 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，??，m。
② 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。
例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。
三、程序设计
1、概要设计
为了解决约瑟夫环的问题，我们可以建立单向环表来存储每个人的信息（该人的编号以及其下一个人的编号），及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。
（1） 抽象数据类型定义
ADT Joh{
数据对象：D={ai|ai?ElemSet,i?1,2,?,n,n?0} 数据关系：R1={?ai?1,ai?|ai?1,ai?D,i?1,2,?,n} 基本操作： create(&J, n) 操作结果：构造一个有n个结点的单向环表J。 show(J)初始条件：单向环表J已存在。 操作结果：按顺序在屏幕上输出J的数据元素。 calculate( J,s,n)
初始条件：单向环表J已存在，s>0，n>0，s<环表
结点数。
操作结果：返回约瑟夫环的计算结果。
}ADT Joh
（2）宏定义
#define NULL 0
#define OK 1
#define ERROR -1
（3）主程序流程
（4）
程序分为下述模块：
1）主函数模块——执行输入调用其他的功能函数
2）创建环表模块——创建单向环表
3）计算处理模块——计算出要出列的标号并输出
4）显示模块——输出建立好的环表
调用关系如下：
2、详细设计
(1)数据类型设计
typedef int ElemType; //元素类型 typedef struct {
ElemType data;
struct Joh *next;
}Joh, *LinkList,*p;//结点类型，指针类型
(2)操作算法
Status create(LinkList &J,int n){
//创建一个有n个结点的单向环表 if(n<=0)
return ERROR; //n<0错误
J=(LinkList)malloc(sizeof(J));
J->data=1;
J->next=J;//建立第一个结点
for(int i=n;i>1;--i){
p=(LinkList)malloc(sizeof(J));
p->data=i;
篇二：约瑟夫环实验报告
第二章实验报告
实验名称：约瑟夫环问题
实验类型：综合性实验
班级：
学号：
姓名：
实验日期：2014.5.17
1.问题描述
设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
2.数据结构设计
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
typedef struct node
{
int data;
struct node *next;
} LinkList;
3.算法设计
我没有分一个个函数来编写，而是用一个主函数把程序编写完成： Int main()
{
int n,m,i;
LinkList *head,*back,*front,*temp;/* 这里的back是一个伪指针 */ head = back = front =NULL;
printf("请参与者的个数：\n");
scanf("%d",&n);
printf("请输入喊到几的参与者跳出：\n");
scanf("%d",&m);
for(i = 1; i<n+1; i++)
{
temp = (LinkList *)malloc(sizeof(LinkList)); /* 分配内存 */temp->data = i;
if(i==1)
{
head = temp;
temp->next = head;
back = temp;
}
else
{
back->next = temp;
temp->next = head;
back = temp;
}
}
temp = head;
int total = n; /* 参与者的总数量 */
printf("参与者的总数量是：%d\n",n);
front = head; /*只剩一个节点时停止跳出 */
while(total!=1)
{
for( i = 1; i<m; i++) /*找到报数为m的参与者 */
{
temp = temp->next;
}
while(front->next != temp) /* 找到报数为m的参与者的前一个人*/{
front = front->next;
}
printf("%d\n",temp->data); /* 打印参与者报数为m的编号 */front->next = temp->next; /* 连接m前后两个参与者 */
free(temp); /* 删除报数为m的参与者 */
total--;
temp = front->next;
}
printf("%d\n",front->data);
printf("最后剩余的人的编号为:%d\n",front->data);
return 0;
}
4.界面设计
我们只需要按提示输入要参加的人数，第几个人跳出，就可以了。
5. 运行、测试与分析
（1）运行程序，显示菜单，如图1.1所示。
图1.1 输入参与者界面
（2）根据提示，输入参与者的个数，如图1.2所示。
图1.2 第几个参与者跳出界面
（4）根据提示，输入喊到几的参与者跳出，如图1.3所示。
图1.3 约瑟夫环实现界面
（5）如图所示，程序完美地运行了。
6.实验收获及思考
在本次上机实验中，我熟悉了单向循环列表的基本操作。特别对插入操作、查找操作和删除操作有了较深的理解。对于数组和指针的用法也更熟练，在程序的调试和异常处理方面有了一定的经验。相信在本次实验中积累的经验、提高的能力将在今后的实验中展现出来。
当然，这次实验我也存在一些问题，比如说程序的格式不是很工整，在检查的时候会比较麻烦，下次会把程序编写成一个个函数，通过不同的函数实现不同的功能。这样，不仅看起来会工整很多，而且也便于检查。
源代码：
#include<stdio.h>
#include<malloc.h>
#define MAX_NODE_NUM 100
#define TRUE 1U
#define FALSE 0U
typedef struct NodeType
{
int id;
int cipher;
struct NodeType *next;
} NodeType;
/* 创建单向循环链表 */
static void CreaList(NodeType **, const int);
/* 运行"约瑟夫环"问题 */
static void StatGame(NodeType **, int);
/* 打印循环链表 */
static void PrntList(const NodeType *);
/* 得到一个结点 */
static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE，非空为FALSE */ static unsigned EmptyList(const NodeType *);
static void CreaList(NodeType **ppHead, const int n) {
int i, iCipher;
NodeType *pNew, *pCur;
for (i = 1; i <= n; i++)
{
printf("输入第%d个人的密码: ", i);
scanf("%d", &iCipher);
pNew = GetNode(i, iCipher);
if (*ppHead == NULL)
{
*ppHead = pCur = pNew;
pCur->next = *ppHead;
}
else
{
pNew->next = pCur->next;
pCur->next = pNew;
pCur = pNew;
}
}
printf("循环链表创建完成\n");
}
static void StatGame(NodeType **ppHead, int iCipher) {
int iCounter, iFlag = 1;
NodeType *pPrv, *pCur, *pDel;
pPrv = pCur = *ppHead;
/* 将pPrv初始为指向尾结点，为删除作好准备 */
while (pPrv->next != *ppHead)
pPrv = pPrv->next;
while (iFlag)
{
for (iCounter = 1; iCounter < iCipher; iCounter++) {
pPrv = pCur;
篇三：约瑟夫环问题实验报告
天津理工大学实验报告
学院（系）名称：计算机与通信工程学院
第1页 共4页
第2页 共4页
第3页 共4页
第4页 共4页
免费论文网友情提示：本网站所有内容为共享上传提供，不涉及任何商业利益，本站对此不承担任何保证责任！
Copyright © www.csmayi.cn Corporation, All Rights Reserved 共享时代 共享你我他 版权所有