约瑟夫环实验报告

来源:m.fanwen118.com时间:2022.9.21

《数据结构与算法设计》

实验报告

——实验一

学院:自动化学院

班级: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;

} p->next=J->next;J->next=p;//插入到表头

return OK;

}//create

void show(LinkList J){//主要的操作函数 //顺序输出环表J的结点

p=J;

printf("%d ",p->data);

p=p->next;

while(p!=J){ //循环终止条件

}

}//show

void calculate(LinkList J,int s,int n){ p=J;

Joh *head=p; //声明结点 while(p->data!=s){

p=p->next; head=p; printf("%d ",p->data); p=p->next;

}//寻找起始结点

while(p->next!=p){ //终止条件

for(int i=0;i<n-1;i++){

}

printf("%d ",p->data);

head->next=p->next; //删除已输出结点 p=head->next;

}

if(n!=1)

printf("%d\n",p->data); head=p; //保存前置节点 p=p->next;

else

printf("\n");

}//calculate

(3)主函数代码

int main(){//主函数

Joh *J;int m,s,n;

printf("The num of node is:"); scanf("%d",&m);

create(J,m); //创建单向环表J show(J); //输出J的数据 printf("\n");

printf("The first node which you want is:");

scanf("%d",&s);

printf("The internal which you want is:");

scanf("%d",&n);

calculate(J,s,n); //计算并输出结果

return 0;

}//main

四、程序调试分析

1、细节决定成败,编程最需要的是严谨,如何的严谨都不过分,往往检查了半天发现错误发生在某个括号,分号,引号,或者数据类型上。在写主要操作函数caculate()时,在终止条件的书写处不是很清楚,导致我浪费了很多时间。

2、还有一点很大的感触就是,在自己绞尽脑汁都解决不了遇到的问题时,一个很好的手段就是询问同学,寻求其帮助,就比如我在想函数终止条件时,同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情,相反的,在快速解决问题的同时,还会收获友谊,不是一举两得吗。我想,这也是合作学习的真谛吧。

五、用户使用说明

1、本程序的运行环境为Windows操作系统下的Microsoft Visual C++ 6.0。

2、在VC环境下打开程序后,按要求键入要求的数字,以等号或空格断开,敲击“回车符”,即可以显示要求的结果。

3、按下任意键以继续。

六、程序运行结果

测试用例1:

输入:m=10,s=3,n=4 输出:6,10,4,9,5,2,1,3,8,

约瑟夫环实验报告

7

测试用例2:

输入:m=13,s=4,n=3 输出:6,9,12,2 ,5,10 ,1, 7 ,13 ,8 ,4 ,11 ,

约瑟夫环实验报告

3

七、程序清单

#define NULL 0

#define OK 1

#define ERROR 0

typedef int Status;

typedef int ElemType;

typedef struct {//结点类型

ElemType data;

struct Joh *next;

}Joh,*LinkList;//定义约瑟夫结构

Joh *p;

#include"stdio.h"

#include"stdlib.h"

Status create(LinkList &J,int n){

if(n<=0)

return ERROR;

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;

p->next=J->next;J->next=p;//插入到表头 }

return OK;

}//构造函数

void show(LinkList J){

p=J;

printf("%d ",p->data);

p=p->next;

while(p!=J){ //循环结束条件

printf("%d ",p->data);

p=p->next;

}

}//显示函数

void calculate(LinkList J,int s,int n){ p=J;

Joh *head=p;

while(p->data!=s){

p=p->next;

head=p;

}//寻找起始结点

while(p->next!=p){

for(int i=0;i<n-1;i++){

head=p; //保存前置结点

p=p->next;

}

printf("%d ",p->data);

head->next=p->next; //删除已输出结点 p=head->next;

}

if(n!=1)

printf("%d\n",p->data);

else

printf("\n");

}//主体计算函数

int main()

{

Joh *J;int m,s,n;

printf("The num of node is(m=):");

scanf("%d",&m);

create(J,m); //创建单向环表J

show(J); //显示J的数据内容

printf("The first node which you want is(s=0):"); scanf("%d",&s);

printf("The internal which you want is(n=):"); scanf("%d",&n);

calculate(J,s,n); //计算并输出最后结果 return 0;

}


第二篇:C++约瑟夫环实验报告 2400字

数据结构集中上机

试验报告

学院: 计算机科学与技术 专业:计算机科学与技术学号:111111111111 班级:(6) 姓名: 莫莫莫

20010.10.7

joseph环上机实验报告

实验名称:joseph环

题目要求的约瑟夫环操作:编号是1,2,……,n的n个人

按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。

实验要求:1~)利用单向循环链表存储结构模拟此过程,按照出列的顺

序输出各个人的编号。

2~)建立输入处理输入数据,输入每个人的密码,建立单

循环链表。

3~)测试数据:m的初值为6,n=7 ,7个人的密码依次为3,

1,7,2,4,8,4,首先m=6,则正确的输出是什么?

实验过程:

1.基本算法以及分析:

本程序主要是以建立单循环链表的形式,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,如下

struct Joseph

{

long number;

Joseph* next;

float score;

};程序有主函数开始,首先,提示输入每个环上所带的密码。然后,开始调用Joseph*Create()函数,利用单循环链表建立起约瑟夫环, pEnd->next=head;就是将最后一个结点的后继指向头结点,函数结尾 return( head); 将约瑟夫环的头指针返回,并将它赋值head,依次录入各节点的密码值,然后主函数继续调用 Delete函数,实现如下功能:

编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。

2.程序源代码:

约瑟夫环

#include<iostream>

using namespace std;

struct Joseph

{

long number;

Joseph * next;

float score;

};

Joseph* head;

Joseph*Create()

{

int k=1;

Joseph*ps; //当前要插入的结点

Joseph*pEnd; //链尾指针

ps=new Joseph; //

cin>>ps->score;

ps->number=k++;

head=NULL; //初始化链表,开始时链表为空

pEnd=ps;

while(ps->score!=0) //以输入的学生号为0作为结束条件 {

if(head==NULL) //当前插入的结点为链表的第一个结点

head=ps;

else

pEnd->next=ps;

pEnd=ps;

ps=new Joseph;

cin>>ps->score;

ps->number=k++;

}

pEnd->next=head;

delete ps; //释放结点成员number为0的结点所占的内存 return (head);

}

void Delete(Joseph *q,int m)

{

Joseph *p;

Joseph *pGuard;

pGuard=q;

p=new Joseph;

p->next=pGuard;

while(pGuard->next!=pGuard) //循环判断,若只剩下最后一个节点,则循环结束

{

for(int i=1;i<m;i++) //开始顺序报数

{

p=pGuard;

pGuard=pGuard->next;

}

p->next=pGuard->next;

cout<<pGuard->number <<" have been deleted\n"<<endl; //输出循环删除的结点

m=pGuard->score; //将节点密码作为新的m值 delete(pGuard);

pGuard=p->next;

}

cout<<pGuard->number <<" have been deleted\n"<<endl; //输出最后删除的结点

}

void main()

{

}

cout<<"请依次输入每个人的密码:"; head=Create(); Delete(head,6);

3.运行结果

C约瑟夫环实验报告

初始密码6,输入七个人的密码,以0作为结束条件 输入密码:3 1 7 2 4 8 4

输出结果:6 1 4 7 2 3 5

4

此程序目前的缺点在于,结点密码数据类型定义的存储类型是int型,不能超过-2147483648~2147483648,一旦超过则程序输出结果有误,另一个缺点就是程序运行当中,一旦中途输入出现错误,则无法返回,必须将当前操作结束等到下个主函数的循环开始,或者直接退出重新运行此程序。优点则在于程序运行速度较快,不会出现输出结果有误的问题

更多类似范文
┣ 用顺序表解决约瑟夫环问题 200字
┣ C++数据结构之约瑟夫环 4000字
┣ 北理工数据结构第二章实验报告 4300字
┣ 数据结构实验指导书(20xx级) 17700字
┣ 更多约瑟夫环实验报告
┗ 搜索类似范文