欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 数据结构——约瑟夫环C语言链表实现

数据结构——约瑟夫环C语言链表实现

2025/2/13 9:44:14 来源:https://blog.csdn.net/m0_64089565/article/details/140335246  浏览:    关键词:数据结构——约瑟夫环C语言链表实现

        约瑟夫环问题由古罗马史学家约瑟夫(Josephus)提出,他参加并记录了公元66—70年犹太人反抗罗马的起义。在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。起义者表示“宁为玉碎不为瓦全”,约瑟夫则想“留得青山在不愁没柴烧”。于是,约瑟夫建议41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。问:约瑟夫及其朋友应该站在哪个位置?、

        n个人围成一个圆圈,然后从第一个人开始,按:1,2,3,…,m报数,数到m的人出圈,并有出圈者的下一个人重新开始报数,数到m又要出圈,如此类推,直到所有人都出圈,打印出圈的次序,其中n和m为输入数据

        这个问题可以通过数学推理和递归算法来解决。通过不断地计算,可以发现每次移除一个人后,剩下的人重新排列成一个新的圆圈,规模减小并且从下一个人开始。通过不断地递归计算,可以找到最后一个人的位置。

        本篇博客用C语言,利用循环单链表求解约瑟夫环问题。

        引用的头文件

#include<stdio.h>
#include<malloc.h>
#include<time.h>//计算执行时间 

        在main函数中,首先输入总人数count和报数规律num,然后调用Solve_lijie函数求解约瑟夫环问题。为了计算程序执行时间,使用了clock函数来记录开始和结束时刻,然后计算差值得到执行时间。

int main()
{int count, num;double duration; Loop* L;printf("输入总人数count和报数规律num:");scanf("%d%*c%d", &count, &num);//循环单链表求解clock_t start, finish;//长整型数 start = clock();Solve(L, count, num);finish = clock();//记录前后时刻 duration = (double)(finish - start) / CLOCKS_PER_SEC;//这个是有定义的宏 printf("\n使用循环单链表存储所用执行时间:%lf", duration);return 0; } 

结构体定义

typedef int ElemType;
typedef struct Josephus
{ElemType MEN;	struct Josephus* next;
}Loop;
// 循环单链表初始化
void Init(Loop* &L)
{L = (Loop *)malloc(sizeof(Loop));L -> next = L;	// 头尾相连 
}void Create(Loop* &L, int count)
{if(count < 1){printf("介个是个空环\n");return;}Loop *s, *r;Init(L); //初始化头节点 L->MEN = 1; r = L;	//指向头节点 for(int i = 2; i <= count; i++){	//对头节点后面的节点进行初始化并录入数据 Init(s);s->MEN = i;s->next = L;//循环,尾部也是L r->next = s;//r指向头节点 r = s;}
}void Display(Loop* &L)//用于检测是否正常录入数据 
{Loop *p = L;if(L == NULL)return;	printf("报数:\n");do{printf("%d\t", p->MEN);p = p->next;}while(p != L);//兜兜转转回到原点 printf("\n");return; 
}
void Solve(Loop* &L, int count, int num)
{Create(L, count);Display(L);int j;//循环,根据报数规律num让成员出列,受总人数count影响//每杀一个,count--; 每到第num个,就打印后free一个 Loop *p, *r;r=p = L;while(r->next != L)r = r->next;for(int i = count; i > 1; i--){j = 1;do{		r = p;	//形成一前一后两指针 p = p->next;j++;}while(j < num);// 不符合出列条件。此时两指针各下移一个单位r->next = p->next;printf("这个人死了: %d\n", p->MEN);free(p);p = r->next;//符合条件。此时后指针后续链接前指针的后续,释放前指针p,然后恢复前后位置顺序。}printf("获胜者是%d\n", p->MEN);
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com