约瑟夫环实验报告.doc

《数据结构》
实验报告
实验题目:
约瑟夫环
班级:
学号:
姓名:
完成日期:

1、利用单向循环链表存储结构模拟Josephus问题,按照出列的顺序输出出列序号。建立一个不带头结点的循环单链表,结点数据域值分别为1-n;根据输入的第一个报数位置,找到单向循环链表中相应结点;根据输入的要报数值,反复进行以下操作:计数到m,输出对应结点的数据元素值并删除该结点,直到所有结点全部删除。
2、输出形式
从屏幕显示出列顺序
3、程序功能
演示程序以用户与计算机的对话方式执行,用户输入相应的数据,输出结果显示在其后。
测试数据:
(1) n=8, s=1, m=4
出列顺序为:4,8,5,2,1,3,7,6
(2) n=9, s=4, m=5
出列顺序为:7,3,9,6,5,8,2,4,1
(3) n=7, s=6, m=2
出列顺序为:6,1,3,5,2,7,4
(4) n=10, s=3, m=2
出列顺序为:3,5,7,9,1,4,8,2,10,6
(5) n=6, s=3, m=5
出列顺序为:6,5,1,3,4,2

为实现上述程序功能,应利用单向循环链表存储结构模拟此过程。
单向循环链表的抽象数据类型定义为:
ADT CircularList{
数据对象:D={ai|ai∈LNode,i=1,2,…,n,n≥0}
数据关系:R1={<ai-1,ai>|ai-1∈D,i=2,…,n}
基本操作:
LinkList InitList(ElemType n);
操作结果:构造一个空的循环表L,为线性表分配存储空间用于存放数据元素。
void Josephus(LinkList p,ElemType number,ElemType n);
操作结果:根据输入的要报数值,反复进行以下操作:计数到n,输出对应结点的数据元素值并删除该结点,直到所有结点(number)全部删除。
}
本程序中包括的两个基本模块:
主程序模块:
Int main(){
初始化;
接受命令;
处理命令;
Return 0;
}
2)、单向循环列表模块——实现循环列表抽象数据类型;
3、各模块之间的调用关系如下:
主程序模块单向循环列表模块

1、1)结点类型
typedef struct Lnode
{
int value;//编号
struct Lnode *next; //指向直接后继结点
}LNode,*LinkList;
2) 用循环链表存储约瑟夫环,没有头结点,基本操作函数如下:
LinkList InitList(ElemType n)
{//构造一个空的循环列表结构的约瑟夫环,结点个数为n
LinkList head=NULL,p=NULL,q=NULL;
int i=1;
head=(LinkList )malloc(sizeof(LNode)); //头指针
head->value=i;
p=head;
for(i=2;i<=n;i++)
{
q=(LinkList )malloc(sizeof(LNode));
if(q==0) return ER