数据结构——约瑟夫环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);
}