2023年数据结构约瑟夫环实验报告

⑥北京廿大母世化埠茂

CenturyCo*”，MpUnArm»y.F»mpodT»l»c^m<nMrfc<q*on>

《数据结构与算法设计》

约瑟夫环实验报告

——实验一

专业:物联网工程

班级:物联网1班

学号：15180118

姓名:刘沛航

一、实验目的

1、熟悉VC环境，学习使用C语言运用链表的存储结构解决实际

的问题。

2、在编程、上机调试的过程中，加深对线性链表这种数据结构

的

基本概念理解。

3、锻炼较强的思维和动手能力和更加了解编程思想和编程技

巧。

二、实验内容

1、采用单向环表实现约瑟夫环。

请按以下规定编程实现：

①从键盘输入整数m,通过create函数生成一个具有m个结点

的单向环表。环表中的结点编号依次为1,2,……,m。

②从键盘输入整数s(l<=s<=m)和n,从环表的第s个结点开始

计数为1,当计数到第n个结点时，输出该第n结点相应的编

号，将该结点从环表中消除，从输出结点的下一个结点开始重

新计数到n,这样,不断进行计数，不断进行输出，直到输出了

这个环表的所有结点为止。

例如，m=l0,s=3,n=4o则输出序列为：6,10,4,9,5,

2,1,3,8,7o

三、程序设计

1、概要设计

为了解决约瑟夫环的问题，我们可以建立单向环表来存储每

个人的信息(该人的编号以及其下一个人的编号)，及结点，人

后通过查找每个结点，完毕相应的操作来解决约瑟夫问题。

(1)抽象数据类型定义

ADTJoh{

数据对象：D=[at|ateElemSet,i=l,2,...,n,n>0}

。数据关系：R1={<4T，《>l%，4eD,i=l,2,...,n}

基本操作：

»create(&J,n)

。。。操作结果:构造一个有n个结点的单向环表Jo

show(J)

。初始条件：单向环表J已存在。

。。操作结果：按顺序在屏幕上输出J的数据元素。

。。ca1culate(J,s,n)

初始条件:单向环表J已存在,s>0,n>0,s<环表结点

数。

操作结果:返回约瑟夫环的计算结果。

}ADTJoh

(2)宏定义

#defineNULL0

#defineOK1

#defineERROR-1

(3)主程序流程

(4)

程序分为下述模块:

1)主函数模块一一执行输入调用其他的功能函数

2)创建环表模块----创建单向环表

3)计算解决模块一一计算出要出列的标号并输出

4)显示模块一一输出建立好的环表

调用关系如下:

主函数模块

创%环表模块

,示模块

计算解决模块

2、具体设计

(1)数据类型设计

typedefintElemType;//元素类型

typedefstruct{

正1emTypedata;

structJoh*next;

}Joh,*LinkList,*p;//结点类型，指针类型

(2)操作算法

Statuscreate(LinkList&J,intn){

〃创建一个有n个结点的单向环表

if(n<-0)

sreturnERROR;。//n<0错误

J=(LinkList)malloc(sizeof(J));

oJ->data=1;

0J->next=J;//建立第一个结点

for(inti=n；i>1-i){

。p=(LinkList)ma1loc(sizeof(J));

p->data=i;

sp->next=J->next；J->next=p;//插入至ll表头

。}

returnOK;

}//create

voidshow(LinkListJ){〃重要的操作函数

。〃顺序输出环表J的结点

ep=J;

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

p=p->next；

«whi1e(p!=J){〃循环终止条件

sprintf("%d",p—>data);

。P=P〉next;

。}

}//show

voidca1culate(LinkListJ,ints,intn){

。P=J;

Joh*head=p；//声明结点

*while(p->data!=s){

p=p->next;

«head=p;

}〃寻找起始结点

°whi1e(p->next!=p)(〃终止条件

for(inti=0;i<n-l;i++){

。head=p;//保存前置节点

。叩=p->next;

。}

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

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

p=head—>next;

。}

if(n!=l)

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

else

printf("\n");

}//calculate

(3)主函数代码

intmain(){〃主函数

Joh*J;intm,s,n;

printf("Thenumofnodeis:");

»scanf("%d",&m);

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

show(J)；〃输出J的数据

oprintf("\n");

printf("Thefirstnodewhichyouwantis

<>scanf("%d",&s);

printf("Theinterna1whichyouwantis

oscanf("%d",&n);

ocalculate(J,s,n);〃计算并输出结果

return0;

}//main

四、程序调试分析

1、细节决定成败，编程最需要的是严谨，如何的严谨都但是分,

往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类

型上。在写重要操作函数caculate。时、在终止条件的书写处不

是很清楚,导致我浪费了很多时间。

2、尚有一点很大的感触就是，在自己绞尽脑汁都解决不

了碰到的问题时，一个很好的手段就是询问同学，寻求其帮助，

就比如我在想函数终止条件时，同学一句简朴的话语就让我如梦

初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时,

还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛

吧。

五、用户使用说明

1、本程序的运营环境为Windows操作系统下的Microso

ftVisualC++6.Oo

2、在VC环境下打开程序后，按规定键入规定的数字，以等号或

空格断开，敲击“回车符”，即可以显示规定的结果。

3、按下任意键以继续。

六、程序运营结果

程序测试1：

程序测试2：

七、程序清单

#include<stdio.h>

#include<stdlib.h>〃引用函数库

structLNode

(

intnum；

structLNode*next；

);〃定义链表

typedefstructLNodeNODE;

NODE*create1inklist(intn)

(

。//初始化循环链表，并返回头指针

NODE*head

inti=1;

head=p=(structLNode*)mal1oc(sizeof(structLNode));

p->num=i；

for(i=2;i<=n;i++)

(

q=(structLNode*)malloc(sizeof(structLNode))；

if(q==0)return(0);

p->next=q;

p=q；

p->num=i;

)

P—>next=head;〃使链表尾指向链表头,形成循环链表

6retumhead;

)

voidjoseph(NODE*p,intn,intm)

(

〃约瑟夫函数，用于输出约瑟夫环

inti,j;

NODE*q;

for(i=l;i<=n；i++)

for(j=l;j<m；j++)

。p=p->next;〃计算出列者序号

°q=P->next;

。p->next=q->next;

gprintf(M%d”，q->num);

。free(q)；

}

p—>next=NULL；

)

voidmain()

(

NODE*head;

intn,s,m;

。inti；

//拟定计算系