约瑟夫环问题——数据结构p76页（耿国华主编）

约瑟夫环问题

题目： 约瑟夫问题的一种描述是：编号为1，2，……，n的n个人按顺序顺时针方向围坐一圈，每人持有一个密码（正整数）。开始时任选一个整数作为报数上限m，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有的人全部出列为止。

例如，m的初值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5

题目比较简单，这里就不做解释啦，代码中有部分注释，直接上代码

c代码如下：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>typedef struct Node {int data;int index;struct Node* next;
}NODE,*PNODE;//初始化链表
PNODE init_list(int);
//遍历链表
void tarveral_list(PNODE,int);
//解决约瑟夫问题
void yuesefu_list(PNODE,int);int main(void) {//len链表长度，即人员个数，用户输入；int len;printf_s("请输入人的个数 n = ");scanf_s("%d", &len);PNODE pHead = NULL;pHead = init_list(len);tarveral_list(pHead,len);yuesefu_list(pHead,len);return 0;
}PNODE init_list(int len) {// val每个人持有的密码，用户输入；int i,val;PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义一个头节点PNODE pTail;//定义一个尾结点pTail = pHead;pTail->next = NULL;if (pHead == NULL) {printf_s("内存分配失败，程序退出");exit(-1);}for (i = 0; i < len; i++) {PNODE pNew = (PNODE)malloc(sizeof(NODE));if (pNew == NULL) {printf_s("内存分配失败，程序退出");exit(-1);}printf("请输入第%d个人的密码:", i + 1);scanf_s("%d",&val);//尾插法pNew->index = i + 1;pNew->data = val;pTail->next = pNew;pNew->next = NULL;pTail = pNew;}pTail->next = pHead->next;printf_s("\n");return pHead;
}void tarveral_list(PNODE pHead,int len) {int i;PNODE p = pHead->next;printf_s("您输入的每个人的密码依次是：\n");for (i = 0; i < len; i++) {printf_s("%d\t", p->data);p = p->next;}printf_s("\n");return;
}void yuesefu_list(PNODE pHead,int len) {int m,n;int i;PNODE p = pHead;//r用来指向p指向的上一个结点PNODE r = NULL;printf_s("请输入初始m值，m = ");scanf_s("%d",&m);//当p指向自己的时候证明循环单链表只剩一个结点，退出循环，然后再最后把这一个结点的序号输出while (p->next != p) {for (i = 0; i < m; i++) {//让r指向要出列结点的上一个结点r = p;p = p->next;}//输出p指向结点的序号，然后把p的data赋给m；删除p指向结点，p指向p指向的上一个结点；printf_s("%d   ", p->index);m = p->data;r->next = p->next;p = r;};printf("%d",p->index);
}