用循环链表解决约瑟夫环问题

#include<stdioh>

#include<stdlibh>

#define N 9

#define OVERFLOW 0

#define OK 1

int KeyW[N]={4,7,5,9,3,2,6,1,8};

typedef struct LNode{

int keyword;

struct LNode next;

}LNode,LinkList;

void Joseph(LinkList p,int m,int x)

{

LinkList q;

int i;

if(x==0)return;

q=p;

m%=x;/获取头结点/

if(m==0)m=x;/取余/

for(i=1;i<=m;i++)/找到下一个结点/

{

p=q;

q=p->next;

}

p->next=q->next;/移动结点/

i=q->keyword;/获取编号/

printf("%d ",q->keyword);

free(q);/释放结点/

Joseph(p,i,x-1);/递归调用/

}

int main()

{

int i,m;

LinkList Lhead,p,q;

Lhead=(LinkList)malloc(sizeof(LNode));/申请结点空间/

if(!Lhead)return OVERFLOW;

Lhead->keyword=KeyW[0];/数据域赋值/

Lhead->next=NULL;

p=Lhead;/指向头结点/

for(i=1;i<9;i++)

{

if(!(q=(LinkList)malloc(sizeof(LNode))))return OVERFLOW;

q->keyword=KeyW[i];/数据域赋值/

p->next=q;

p=q;/移动到下一结点/

}

p->next=Lhead;/尾结点指向头结点，形成循环链表/

printf("Please input the first recode m:\n");

scanf("%d",&m);/输入起始位置/

printf("The output alignment is:\n");

Joseph(p,m,N);/调用函数/

return OK;

}

约瑟夫环，已加注释

正好我以前写的这个还留着，如下：

n为人数，m是初始随机数

#include<stdioh>

int main(void)

{

int m,n,i,j,k,times,num,a[2][100],b[100];

scanf("%d %d",&n,&m);

k=0;

if(n>0&&n<100)

{

for(num=1;num<n+1;num++)

{

scanf("%d",&a[0][num]);

a[1][num]=1;

}

for(j=0,i=1,times=1;times<=n;i++)

{

if(a[1][i]==1)

j++;

else

;

if(j==m)

{

a[1][i]=0;

j=0;

m=a[0][i];

b[k]=i;

k++;

times++;

}

if(i>=n)

i=0;

}

for(num=0;num<n;num++)

printf("%d ",b[num]);

}

return 0;

}

/

基本要求

基本的约瑟夫的描述：

古代某法官要判决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=1;i<=N;i++)

{

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

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=2;i<=(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=1;i<=N;i++)

{

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

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=2;i<=(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=1;i<=(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);

j1print();

j1start();

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

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

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

j2print();

j2start();

return 0;

}

以上就是关于用循环链表解决约瑟夫环问题全部的内容，包括:用循环链表解决约瑟夫环问题、求一个，循环队列解决约瑟夫环问题的C语言程序，谢谢、C++编程：约瑟夫环问题。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！