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

伏倒咛洗石n

《数据结构》课程实验报告书

RMAL

姓名:徐鑫

学号：________

专业:物联网工程

班级:1604

2023年10月15日

一、实验目的

1.掌握线性表特性

2.纯熟掌握线性表的基本操作

3.运用线性表设计算法并实现

二、实验内容

1.解决约瑟夫环问题：已知n个人（以编号1,2,3...n分别表达）围坐在一

张圆桌周边。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又

从1开始报数，数到m的那个人又出列；依此规律反复下去，直到圆桌周边的人

所有出列。

2.基本规定：1）根据题目规定设计解决约瑟夫环应用问题的数据结构。

2）规定采用C++编程语言实现设计的算法。

三、设计思绪

1.数据逻辑关系的分析

。。令将人的顺序简朴编号，从1至Un;

。。土构造一个循环链表，可以解决首位相连的问题；

4s将人的编号插入到结构体的Data域中；

布应历人的编号，输出参与的人的编号；

<}>开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点。

直到人数只有一个人时，退出循环，输出获胜的人。

2.存储结构设计

（建立约瑟夫环）

（循环结束条件）

3.算法的核心思想说明

口拟定需要删除的位置；

口。设立并删除该位置。

已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，假如

获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际

长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设立

为该位置，继而删掉该位置。

反复进行上述拟定位置和删除位置的操作，直到顺序表为空。

四、数据结构设计

1.类的声明和定义（规定给出完整的类声明和核心成员函数的定义）

ob#ifndefJoseph_H

#defineJoseph_H

#include<iostream>

usingnamespacestd;

structNode//结点

（

®intdata;//存储数据

woNode*next；〃下一个节点的地址

）；

classCircularLinkList//单向循环链表类

public:

CircularLinkList()〃构造函数

。ofirst=newNode;

3first->data=NULL;

市rst->next=first;

8}

g〜Circu1arLinkList(){deletefirs}〃析构函数

8VoidCreateLinkList(inta[],intn)；〃创建单I句循环链表

3®voidPrintLinkList();〃遍历链表

gvoidJoseph(intk,intn);〃约瑟夫环实现

private:

®ode*first;

)；

#endif

2.算法实现

#include"Joseph.h"

#include<windows,h>

#inc1ude<iomanip>

voidCircularLinkList:：CreateLinkList(inta[],intn)

(

gNode*s,*r=first;//尾指针初始化

gfor(inti=0；i<n;i++)//尾插法

00{

s=newNode；

。s->data=a[i]；

oMr—>next=s;

3sr=s;

oe}

gr—>next=first—>next;〃循环

}

voidCircu1arLinkList::PrintLinkList()

(

gintcount=0;//计数器

Node*r=first->next；

8do{

ocout«setw(3)«r—>data;

ocount++；

Qr=r—>next;

。if(count%10==0)

®®cout«endl<<H"；

g。}while(r!=first->next);//当链表循环到第一节点时跳出循环

gocout«end1；

)

voidCircularLinkList::Joseph(intk,intn)

(

intm;

eCOUt«”-->>请输入约瑟夫密码：”；

Min»m;〃输入约瑟夫密码

©Node*pre,*p;

spre=first;//工作指针初始化

。p=pre->next;

®for(inti=0;i<k-l;i++)

8pre=pre->next;

。叩=pre->next;

000}

»intcount=1;//计数器初始化，约瑟夫问题至少有两个成员

acout«n************************************************

***\n'、

°while(pre!=p)

d6(

6®®if(count==m)//假如计数器等于密码

。。Sleep(l*1000);〃执行挂起一段时间(1秒)

6cout<<setw(26)«p->data<v”号死亡!”vvendl;//显示结果

。Node*q=P；

g叩re->next=p->next;

g。de1eteq;//删除死亡结点

Qgp=pre—>next;

oocount=1;//计数器重新计数

00|

®else

0{

gopre=pre->next;〃工作指针后移

goop=p->next;

8。。count++;〃计数器加一

00|

60|

6cout«**********************************************

*****\n”；

。cout«setw(26)<<p—>data<<”号存活！"<<endl；//显示最后存活

的

^deletep;//删除结点p

ssystem。'pause")；

)

五、程序测试与实现

1.程序在调试过程中出现的问题及解决办法

2.程序运营过程及结果界面

HBC:\Windows\system32\cmd.exe—□X

》》约瑟夫环游戏《《

—>〉请输入参与人数：6

C:\Windows\system32\cmd.exe—□X

》》约瑟夫环游戏《《

一>>请输入参与人数：6

对所有人进行编号！！

编号如下：

123456

一>>请输入从第几人开始：2

六、实验调试

HBC:\Windows\system32\cmd.exe□X

》》约瑟夫环游戏《《

—>>请输入参与人数：6

对所有人进行编号！！

编号如下：

123456

一》请输入从第几人开始：2

一》请输入约瑟夫密码：4

5号死亡！

3号死亡！

2号死亡！

4号死亡！

1号死亡！

6号存活！

请按任意键继续...

搜狗拼音输入法全：

七、问题及解决方法

问题：无法从第k个人开始报数。

解决方法：用while循环，找寻开始报数的编号k,找到后把他报的数标记为1.

问题：将LinkList.h文献的LinkList类中的行为函数放进LinkList.cpp文

献中出现错误“重定义”。

解决办法:将行为函数的定义与声明均放进LinkList.