约瑟夫环问题出列顺序c语言循环链表

约瑟夫环问题是经典的算法题之一，在实际应用中可以利用**循环链表**模拟该过程。以下是基于 C 语言的解决方案及原理说明： ### **约瑟夫环问题描述** 假设 `n` 个人围成一个圈，从第一个人开始报数，每次从 `1` 数到 `m`，凡数到 `m` 的人退出圈子，直到所有人都退出为止。 --- ### **解决思路：使用循环链表** #### 1. 创建节点结构体 首先定义一个包含数据域 (`data`) 和指针域 (`next`) 的节点结构体： ```c typedef struct Node { int data; // 节点编号 struct Node* next; // 指向下一个节点 } Node; ``` #### 2. 初始化循环链表 创建并连接所有节点形成闭环： - 第一步：构造单项链表； - 第二步：将最后一个节点指向第一个节点完成闭合。 例如初始化有 n=5 人的链表表示 [0 -> 1 -> 2 -> 3 -> 4] 并使其首尾相接。 #### 3. 遍历删除结点 按照规则逐一移除满足条件 (即数到 m) 的节点，并记录下被移除者的序号值直至整个链条为空。 示意图展示大致操作流程： 初始状态->(0)->(1)->...-(n-2)->(n-1) 第一次删去的位置取决于起始位置startAt与stepSize 完整代码片段如下所示: ```c #include <stdio.h> #include <stdlib.h> // 定义节点 typedef struct Node { int data; struct Node* next; } Node; Node* createCircle(int num); void josephusKill(Node *head,int step); int main(){ int peopleNum = 7;//总人数 int killStep = 3 ; //每隔killStep杀掉一个人 Node *circleHead=createCircle(peopleNum); printf("The out sequence is:\n"); josephusKill(circleHead , killStep ); } /* 创建大小为num的圆圈 */ Node* createCircle(int num){ if(num<=0)return NULL; Node *first=(Node*)malloc(sizeof(Node)); first->data=0; Node *pre,*pnow=first; for(int i=1;i<num;i++){ pre=pnow; pnow=(Node *)malloc(sizeof(Node)); pnow->data=i; pre->next=pnow; } pnow->next=first; /* 构造循环*/ return first ; } /* 执行约瑟夫环杀死行动 */ void josephusKill(Node *head,int step){ Node *tmp=head,*tail=NULL,*toDel; while(tmp!=tmp->next){ tail=tmp; for(int count=1;count<step;count++) tmp=tail=tmp->next; toDel=tmp->next; printf("%d ",toDel->data+1);// 输出的是人的顺序而非数组索引 tail->next=toDel->next; free(toDel); } printf("\nThe last survivor:%d\n",tmp->data +1); free(tmp); } ``` 上述程序通过不断迭代更新当前临时变量(`tmp`)所指向的内容最终实现了对指定间隔人员淘汰的过程同时保持了内存释放良好习惯避免泄漏发生. --- ### 总结 此解法借助于循环链表形象化地解决了Josephus Problem ，它清晰直观易懂易于理解并且效率相对较高尤其当数目较大时相比递归版本更优。 ---