篇一:约瑟夫环实验报告
《数据结构与算法设计》
实验报告
——实验一
学院:自动化学院
班级: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页
《约瑟夫环实验分析》
由:免费论文网互联网用户整理提供,链接地址:
http://m.csmayi.cn/show/118674.html
转载请保留,谢谢!
- 上一篇:记大过的正规表述
- 下一篇:交通部16号令