约瑟夫环（Joseph）问题数据结构的实验。c++编程~

#include

using

namespace

std//每个做晌人的号码和密码。struct

people{

int

NO

int

pass}nodetemplate

class

Link{private:

static

Link*

freelist//静态数据成员的头接点。public:

struct

people

element

Link*

next

Link(people

elemval,Link*

nextval=NULL)

{

element.NO=elemval.NO

element.pass=elemval.pass

next=nextval

}

Link(Link*

nextval=NULL)

{

next=nextval

}

void*

operator

new(size_t)//

重载new

函数。

void

operator

delete(void*)//重载delete函数。}template

class

LList{private:

Link

*head

Link

*tail

Link

*fence

void

init()

{

head=tail=fence=new

Link

tail->next=head->next

//生成链表是要把它的头接点和尾接点连接起来构成循环链表。

//因为有一个空的头接点配袭。所以要把他的尾接点纯卖锋接到头接点的下一个指针。

}

void

removeall()

{

while(head!=NULL)

{

fence=head

fence=fence->next

delete

fence

}

}public:

LList()

{

init()

}

~LList()

{

removeall()

}

bool

insert(const

people&

T)

bool

remove(Elem&)

void

getOut(int&,int&)

void

prev()

bool

append(const

people&

T)}太长了。。。。去这里看

http://blog.programfan.com/article.asp?id=23037

//这个是带密码的约瑟夫环问题，并且的确是用链表做的0.0

//有不懂的请在问题补充里说明

//个人理解，如有不当还请见谅

#include<iostream>

#include"LinkList.h"

using namespace std

void Creat(LinkList &y,int &n) //构造约瑟夫环y,人数为n

{ //每个人包含两个信息:一个是他的密码,一个是他的序号,即他是第几个人

int a1,a2,i //a1为密码,a2表示这是第几个人i是临时变量,用于下面的for循环

cout<<"请输入"<<n<<"个密码:"<<endl

for(i = 1i<=ni++) //循环n次,每次读取下一个人的信息

{

cin>>a1 //读入密码

a2 = i//读入序号

y.Append(a1,a2) //将这个人加入到约瑟夫弯缓环中,其中a1是他的密码,a2是他的序号

}

}

int main()

{

LinkList y //y为约瑟夫环

int j,n,m //n为人数,m为第一个上限

cout<<"请输入参与人数n:"<<endl //这句你看的懂吧?输出提示信息

cin>>n //读入人数n

cout<<"汪樱请输入第一个困闹丛上限m:"<<endl//输出提示信息

cin>>m //读入m

Creat(y,n) //调用Creat构造约瑟夫环y,人数为n

y.Delete(m)//第一个上限为m,以此调用Delete对约瑟夫环y逐个删除

system("pause")//暂停一下好让你看清结果

return 0

}

//头文件LinkList.h的文件如下

#ifndef _LinkLIST_

#define _LINKLIST_

//#include<iostream>

using namespace std

struct LinkNode //设置约瑟夫环中的基本单元LinkNode,或者说,每个LinkNode代表一个人

{

int data, num //每个人包括密码,序号

LinkNode *next //以及指向下一个人的指针

}

class LinkList //LinkList类:约瑟夫环

{

public: //公共变量声明

LinkList()//构造函数(用于初始化)

bool Append(int,int) //函数Append用于加人

bool Delete(int) //Delete用于删人

private://private变量声明

LinkNode *tail//tail为尾指针,指向约瑟夫环中的最后一个人

}

/*构造函数*/

LinkList::LinkList()

{

tail = NULL //初始化:将尾指针tail指针置为空

}

/*尾部插入模板,用于输入数据的保存*/

bool LinkList::Append(int e1,int e2)//函数Append用于加人

{

LinkNode *p = new LinkNode//新建一个人p

p->data = e1 //将这个人的密码设为e1

p->num = e2 //序号设为e2

if (tail== NULL)//如果尾指针tail为空,说明p是第一个人

{

tail = p //将尾指针指向p

tail->next = tail //tail是尾指针,tail->next表示头指针,即约瑟夫环的起始点,即约瑟夫环中的第一个人

//指向自己,即p的下一个人还是p。因为目前只有一个人所以这么设置,方便后续 *** 作

}

else//尾指针tail不为空时

{ //tail表示最后一个人

p->next = tail->next //p-指向起始点,即p的下一个人是第一个人

tail->next = p//tail指向p,即tail的下一个人是p

tail = p //tail变为p,即p变成最后一个人

}

return true

}

/*删除函数模板，用于保存编号、密码和删除*/

bool LinkList::Delete(int m) //删除函数用于删人

{

LinkNode *p = tail,*q//新建p,p初始化为最后一个人,q为临时变量

while(p != p->next)//当p的下一个人不是他自己时,即当约瑟夫环中的人数大等2时

{ //{

for(int k=1k<mk++) //从k=1开始往后数,数到第m-1个人

p = p->next //p一直往后移,相当于一直往后数

q = p->next //q为p的下一个人,即要删的人

p->next = q->next//p指向q的下一个人,相当于p指向p的下两个人

cout<<q->num<<" "//输出q的序号

m = q->data //m设为q的密码

delete q //把q删了

} //}删到只剩一个人

cout<<p->num<<" "//输出此人序号

delete p //删之

}

#endif

/*

【基本要求】

基本的约瑟夫的描述：

古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，

从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决，

直到剩下的最后一个可赦免。

发展的约瑟夫的描述：

古代某法官要判决N个犯人的死刑，

但这N个人每人持有一个密码，他有一条荒唐的法律，将含雹码犯人站成一个圆圈，

法官先给出一个密码M，从第S个人开始数起，每数到第M个犯人，就拉出来处决，

再根据这个人所持有的密码F，然后再数F个，数到的人再处决，

以此类推直到剩下的最后一个可赦免。

【测试数据】

数据请自己添加。

*/

#include <iostream>

using namespace std

// 表示一个犯人的结构体

struct Prisoner

{

// 编号

int id

// 密码

int pass

// 用于链表的指针

struct Prisoner * pre

struct Prisoner * next

}

class JosephCircle

{

public:

// 基本的约瑟夫构造函数

JosephCircle(int N,int S,int D)

// 发展的约瑟夫构造函数

JosephCircle(int N,int S,int M,int password[])

// 输出约瑟夫环

void print()

// 开始处决犯人

void start()

private:

// 约瑟夫环的头指针

struct Prisoner * head

// 第一个被处决的犯人的节点指针

struct Prisoner * firstPunishedPrision

}

JosephCircle::JosephCircle(int N,int S,int D)

{

struct Prisoner * p , *pr

// 约瑟夫环的头指针初始化为空

this->head = NULL

// 构造一个由 N 个犯人组成的约瑟夫环

for(int i=1i<=Ni++)

{

// 当前添加的犯人是第一肆局个犯人，要特殊处理一下

if(this->head == NULL)

{

// 新增一个犯人

p = new struct Prisoner()

// 犯人编号

p ->id = i

// 犯人密码

p ->pass = D

// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）

p ->pre = p

p ->next = p

// 约瑟夫环的头指针

this->head = pr = p

}

else

{

p = new struct Prisoner()

p ->id = i

p ->pass = D

p ->pre = pr

p ->next = pr->next

pr ->next ->pre = p

pr ->next = p

pr = p

}

}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】

firstPunishedPrision = head

for(int i=2i<=(S+D-1)i++)

{

this->firstPunishedPrision = this->firstPunishedPrision ->next

}

}

JosephCircle::JosephCircle(int N,int S,int M,int password[])

{

struct Prisoner * p , *pr

// 约瑟夫环的头指针初始化为空

this->head = NULL

// 构造一个由 N 个犯人组成的约瑟夫环

for(int i=1i<=Ni++)

{

// 当前添加的犯人是第一个犯人，要特殊处理一下

if(this->head == NULL)

{

// 新增一个犯人

p = new struct Prisoner()

// 犯人编号

p ->id = i

// 犯人密码

p ->pass = password[i-1]

// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他谈哪犯人）

p ->pre = p

p ->next = p

// 约瑟夫环的头指针

this->head = pr = p

}

else

{

p = new struct Prisoner()

p ->id = i

p ->pass = password[i-1]

p ->pre = pr

p ->next = pr->next

pr ->next ->pre = p

pr ->next = p

pr = p

}

}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】

firstPunishedPrision = head

for(int i=2i<=(S+M-1)i++)

{

this->firstPunishedPrision = this->firstPunishedPrision ->next

}

}

// 输出约瑟夫环

void JosephCircle::print()

{

struct Prisoner * p = this->head

if(p != NULL)

{

do

{

cout <<"[编号：" <<p->id <<"，密码：" <<p->pass <<"]"

if(p->next != this->head)

{

cout<<" ->"

}

p = p->next

}while(p != this->head)

}

cout <<endl <<endl

}

// 开始处决犯人

void JosephCircle::start()

{

struct Prisoner * p = this->firstPunishedPrision,*pr,*q

int counter = 1

/*

因为约瑟夫环是一个循环链表（也就是一个圈），

当 p->next != p 的时候，说明圈里面还有多余一个的节点（犯人），

继续数数并处决犯人

*/

while(p->next != p)

{

// q 向当前被处决的犯人

q = p

// 从约瑟夫环里面删除被处决掉的犯人

q ->pre ->next = q ->next

q ->next ->pre = q ->pre

p = p ->next

// 输出被处决的犯人的信息

cout <<"第 "<<(counter++) <<" 个被处决的犯人编号：" <<q->id <<endl

// 寻找下一个将要处决的犯人

for(int i=1i<=(q->pass-1)i++)

{

p = p->next

}

// 释放内存（被处决掉的犯人）。

free(q)

}

// 输出被赦免的犯人的信息

cout <<"被赦免的犯人的编号：" <<p->id <<endl <<endl

}

int main(int argc, char *argv[])

{

// 基本的约瑟夫环： JosephCircle(int N,int S,int D)

JosephCircle j1 = JosephCircle(3,1,2)

j1.print()

j1.start()

// 发展的约瑟夫环： JosephCircle(int N,int S,int M,int password[])

int pass[]={1,5,3}

JosephCircle j2 = JosephCircle(3,1,2,pass)

j2.print()

j2.start()

return 0

}

---