数据结构约瑟夫环代码(约瑟夫环数据结构c++编程)

http://www.itjxue.com  2023-04-13 22:39  来源:未知  点击次数: 

用数据结构编写约瑟夫环算法思想

这个算法是利用单链表编写的,主函数里的算法理解起来可能有点难,但是时间复杂度低。这是完整的核宽cpp 代码,你可以直接复制过去再测试!

#include iostream.h

#include stdlib.h

struct Member//定义结构体闷轮

{

int number;

int password;

Member *next;

};

class Joseph

{

public:

Member *frist;//头指针

int size;

Joseph(void);

~Joseph(void);

int Size(void) const;//返回长度

Member *Index(int i);//定位

void Create(int i);//构造循环单链表

int Delete(int i);//删除结点并返回number的值

};

Joseph::Joseph()

{

//frist=new Member;

Member *p=new Member;

frist=p;

size=0;

}

Member *Joseph::Index(int i)

{

if(i==0)return frist;

Member *p=frist-next;

int j=1;

while(ji)

{

p=p-next;

j++;

}

return p;

}

int Joseph::Size(void)const

{

return size;

}

void Joseph::Create(int i)

{

for(int j=1;j=i;j++)

{

Member *p=Index(j-1);

Member *q=new Member;

q-number=j;

p-next=q;

size++;

};

//Member *p=Index(i);

//p-next=frist;

}

Joseph::~Joseph(void)

{

Member *p,*q;

p=frist;

while(size!=0)

{

q=p;

p=p-next;

delete q;

size--;

}

size=0;

frist=NULL;

}

int Joseph::Delete(int i)

{

Member *s,*p=Index(i-1);

s=p-next;

p-next=p-next-next;

int x=s-number;

cout蚂氏信x" ";

int y=s-password;

delete s;

size--;

return y;

}

void main(void)

{

Joseph jos;

int i;

cout"Please input number of people :"endl;

cini;

jos.Create(i);

int frist;//设初始值

cout"Please input the frist number :"endl;

cinfrist;

for(int k=1;k=i;k++)//用循环输入每个人的密码

{

cout"please input No."k"`s password:"endl;

Member *b=jos.Index(k);

cinb-password;

}

cout"The final is :"endl;

int l=frist%i;

if (l==0) l=i;

for(int b=i-1;b0;b--)

{

frist=jos.Delete(l);

l=(frist+l-1)%b;

int e=jos.Size();

if(l==0)

l=e;

}

jos.Delete(l);

coutendl;

}

数据结构C语言的约瑟夫环怎么做?

参考代码:\x0d\x0a#include\x0d\x0a#include\x0d\x0a#include\x0d\x0atypedef struct LNode{\x0d\x0aint number;\x0d\x0astruct LNode *next;\x0d\x0a} LNode,*Linklist;\x0d\x0aint main()\x0d\x0a{\x0d\x0aint M,N;\x0d\x0aint i;\x0d\x0aLinklist L,r;\x0d\x0aprintf("Please input two M , N:");\x0d\x0ascanf("%d%d",M,N);\x0d\x0aL = (Linklist)malloc(N * sizeof(struct LNode));\x0d\x0aif(L == NULL) printf("Error!\n"),exit(0);\x0d\x0ar = L;\x0d\x0afor(i = 1;i next = L + i;\x0d\x0a老指橘r-number = i;\x0d\x0a 侍团 r = r-next;\x0d\x0a}\x0d\x0ar-next = L;\x0d\x0ar-number = N;\x0d\x0a逗配while(r != r-next)\x0d\x0a{\x0d\x0afor(i = 0;i next;\x0d\x0aprintf("%4d",r-next-number);\x0d\x0ar-next = r-next-next;\x0d\x0a}\x0d\x0aprintf("\n When N = %d and M = %d,Josephus,hiding in position %d survive.\n",N,M,r-number);\x0d\x0afree(L);\x0d\x0a}

数据结构中的约瑟夫环问题用C语言怎么编写出来啊?

题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出

 弊凳灶圈子,问最后留下的是原来第几号的那位。

1.

程序分析:这是一粗盯个比较经典的算法--约瑟夫环问题.

2.个人分析:

算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法

则体现了使用数组来完成链表该完成租扮的功能,虽然形式上完全不相同,但却求出了

相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本

人写的代码不会叫大家啐骂!

3.程序源代码:

#include

stdio.h

#define

N

50

#define

S

3

void

main()

{

int

a[N];

int

i,k;

int

sum=N;

k=0;

for(i=0;iN;i++)

a[i]=i+1;

for(i=0;iN;i++)

printf("%-4d",a[i]);

printf("\n");

for(i=0;;i++)

{

if(sum==1)

break;

if(a[i%N]!=0)

{

k++;

}

if(k==S)

{

k=0;

//printf("%4d",a[i%N]);

a[i%N]=0;

sum--;

}

}

for(i=0;iN;i++)

if(a[i]!=0)

printf("\n最后一个数为:%d\n",a[i]);

}

两年前念书的时候写的,献丑了!

用c语言实现约瑟夫环

正好之前写过基础的察雀约瑟夫环,稍作修改就可以满足你的题目

#include?stdio.h

#include?stdlib.h

typedef?struct?_node?{

????int?id;

????int?key;

????struct?_node?*next;

}?Linklist;

int?main()?{

int?n,?m;

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

int?i,?count?=?0;

Linklist?*head?=?(Linklist*)malloc(sizeof(Linklist)),?*tail?=?head;

head-id?=?1;

scanf("%d",?head-key);

head-next?=?head;

for(i?=?2;?i?=?n;?i++)?{

Linklist?*p?=?(Linklist*)malloc(sizeof(Linklist));

p-id?=?i;

scanf("%d",?p-key);

p-next?=?head;

tail-next?=?世没败p;

tail?=?p;

}

while(head?!=?tail)?{

if(++count?%?m)?{

tail?=?head;

}?else?{

????m?=?head-key;

????count?=?0;

printf("%d?"搜颤,?head-id);

tail-next?=?head-next;

free(head);

}

head?=?tail-next;

}

printf("%d\n",?head-id);

free(head);

return?0;

}

约瑟夫环问题的代码

首先,这个代码输出的是,约瑟夫环到达的让腊最后位置。输出结果是15。

//把iostream这个文件中的内容复制到这个地方。

#includeiostream

using namespace std;

int main()

{

//定义一个常量的整形100,表示人的个数。纳键

const int n=100;

//定义约瑟夫环的参数。

int m=30;

//定义一个数组,用于计算约瑟夫环的位置。

int a[n];

//给数组赋值,让数组的每个值就是这个元素的编号。

for(int j=0;jn;j++)

a[j]=j+1;

//定义一个标志k,当K等于N的时候,表示到达约瑟夫环的最后位置。

int k=1;

int i=-1;

while(1)

{

for(int j=0;jm;)

{

//不停的取数组的下一个元素。

i=(i+1)%n;

//如果这个元素没有被标记为0,说明这个位置还没有被排除,j加1,进入下一个循环

if(a[i]!=0)

j++;

}

//如果标志K等于n,说明约瑟夫环的循环到达最后一个位置,跳出While死循环。

if(k==n)

break;

//否则,把这个位置的元素设为零,标志它被排除。

a[i]=0;

//标志+1。

k++;

}

//输出约瑟夫环到达洞滑巧的最后一个位置。

couta[i]endl;

return 0;

}

(责任编辑:IT教学网)

更多
上一篇:没有了

推荐网站策划文章