数据结构基础实验6

浙大城院 数据结构基础实验6

浙江大学城市学院实验报告

课程名称 数据结构基础

实验项目名称 实验六 约瑟夫环的实现

学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。

2、掌握利用线性表的各种操作来进行具体的实际应用。

3、加强程序设计的能力。

二. 实验内容

1、编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。

基本要求:

（1） 人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由

键盘输入。

（2） 参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。

（3） 根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本

操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件

test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。

（4） 设计测试数据，并调试程序，直到正确运行。

2、填写实验报告，实验报告文件取名为report6.doc。

3、上传实验报告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、

test6_Link.h、test6_Link.cpp到Ftp服务器（ ）

自己的文件夹下。同时上交一份书面的实验报告。

三. 抽象数据类型定义

（需说明你设计的每个基本操作的功能）

浙大城院 数据结构基础实验6

Test6_seq

1、//清除单链表

void ClearList(LNode *&H)

2、//求单链表长度

int LengthList (LNode*H)

3、//判断单链表是否为空表

bool EmptyList (LNode *H)

4、//取单链表第 pos 位置上的元素

ElemType GetList (LNode*H, int pos)

5、//从单链表中查找是否存在给定值的元素

int FindList (LNode*H, ElemType item)

6、//向单链表插入一个元素

bool InsertList ( LNode*&H, ElemType item, int pos)

7、 //从单链表中删除一个元素

bool DeleteList ( LNode*&H, ElemType &item, int pos)

test6_Link

1、//初始化线性表

void InitList(SeqList &L)

2、//判断是否为空

bool EmptyList(SeqList L)

3、//查找给定值元素的位置

int FindList (SeqList L, ElemType item)

4、//在线性表L中求序号为pos的元素，该元素作为函数值返回

ElemType GetList(SeqList L, int pos)

5、//求线性表长度

int LengthList(SeqList L)

6、//按给定条件pos向线性表删除一个元素

bool DeleteList (SeqList &L, ElemType &item , int pos )

7、//按给定条件pos向线性表插入一个元素

bool InsertList(SeqList &L, ElemType item, int pos)

四. 两种类型（顺序和链式）的存储结构定义及算法思路

（包括两种存储结构定义及一些重要函数的算法实现思路） 顺序存储结构：

typedef int ElemType;

typedef struct List{

ElemType *list;

int size;

int MaxSize;

}SeqList;

重要函数的算法实现思路：

浙大城院 数据结构基础实验6

void InitList(SeqList &L) //初始化线性表

int LengthList(SeqList L)//求线性表长度

bool EmptyList(SeqList L)//判断是否为空

int FindList (SeqList L, ElemType item) //查找给定值元素的位置

ElemType GetList(SeqList L, int pos)//返回线性表L中序号为pos元素的值

bool DeleteList (SeqList &L, ElemType &item , int pos )

//按给定条件pos向线性表删除一个元素 主函数思路：

1.先求出线性表长度l

2.再利用j=(i+m-1)%l查出要出列的位置

3.如果j=0，则位置在线性表的末尾即j=l;

4.利用m=GetList(josephus1,j)得出密码作为新的m值

5.接着删除出列的人，长度减少1

6.使i=j，意思为从出列人的下一个人开始报数

7.最后利用函数FindList (josephus2,m)输出出列人的编号 链式存储结构：

typedef int ElemType;

struct LNode { // 定义单链表节点类型

ElemType data; // 存放结点中的数据信息

LNode *next; // 指示下一个结点地址的指针

}; 重要函数的算法实现思路：

void InitList (LNode*&H)//初始化单链表

int LengthList (LNode*H)//求单链表长度

bool EmptyList(LNode*H)//判断是否为空

int FindList (LNode*H, ElemType item)//查找给定值元素的位置

ElemType GetList (LNode*H, int pos)//取单链表第 pos 位置上的元素

bool InsertList ( LNode*&H, ElemType item, int pos)//向单链表插入一个元素

bool DeleteList ( LNode*&H, ElemType &item, int pos)

//从单链表中删除一个元素

主函数思路：

1.建立一个具有n个链结点

2.找出第1个报数人的位置

3.利用函数FindList (josephus2,m)输出出列人的编号

4.得出密码作为新的m值

5.接着删除出列的人，长度减少1

6.使i=j，意思为从出列人的下一个人开始报数

五. 实验结果与分析

浙大城院 数据结构基础实验6

（包括运行结果截图、结果分析等）

六. 心得体会

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建

议等。）

通过实验，我发现我对循坏链表不是很清楚，所以用链表作约瑟夫环的时候我没

有用循环链表的方法做

【附录----源程序】

Test6_seq.h

void InitList(SeqList &L)

{ //初始化线性表

L.MaxSize =10;

L.list = (ElemType *) malloc(L.MaxSize*sizeof(ElemType)) ;

if (L.list==NULL) {

cout<<"动态存储空间用完，退出运行"<<endl;

exit(1);

浙大城院 数据结构基础实验6

}

L.size = 0;

}

//判断是否为空

bool EmptyList(SeqList L)

{

return L.size==0;

}

//查找给定值元素的位置

int FindList (SeqList L, ElemType item)

{

for (int i=0; i<L.size; i++)

if (L.list[i]==item)

return i+1;

}