约瑟夫环实验报告.doc

数据结构集中上机
试验报告
学院: 计算机科学与技术专业:计算机科学与技术
学号:1********** 班级:(6) 姓名: 莫莫莫

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,则正确的输出是什么?
实验过程:
:
本程序主要是以建立单循环链表的形式,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,如下
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报数,如此下去,直到所有人全部出列为止。
:
约瑟夫环
#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;
p