约瑟夫问题数据结构实验报告.doc

-
. z
中南民族大学管理学院
学生实验报告
实验工程: 约瑟夫问题
课程名称：　　数据构造　　
年 是
创立Clinklist类的对象，首先建立循环链表，之后调用Josef函数。
判断链表是否为空
跳出函数
否
循环查找到所要删除节点的前一个节点。
判断所要删除节点是否为最后一个
是
否
删除该节点，并从该节点的直接后继结点重新计数。此时要判断
P和q是否存在恰好为rear指针的情况
输出m的位置
完毕
〔三〕详细设计
#include<iostream>
using namespace std;
const int d=50000;
struct Node
{
-
. z
int data;
struct Node*ne*t; //声明ne*t指针
};
class Clinklist
{
public:
Clinklist(int a[],int n);
void Josef(int m,int n);
private:
Node *rear; //声明rear和front指针
Node *front;
int n;
};
Clinklist::Clinklist(int a[],int n)
{
rear=new Node;
front=new Node;
front->ne*t=rear;//构造空单链表
rear->ne*t=front;
rear->data=a[n-1];
for(int i=n-2;i>=0;i--)
{
Node*s=new Node; //循环插入元素来建立链表
s->data=a[i];
s->ne*t=front->ne*t;
front->ne*t=s;
}
}
void Clinklist::Josef(int m,int n)
{
Node* p=front;
int j=0;
while(front->ne*t!=front)
{
int i=0;
while(i!=m-1) //实现第m-1个节点的查找
{
if(p==rear)
-
. z
p=front->ne*t;
else p=p->ne*t;