约瑟夫环问题(Josephus)　——循环单链表

问题描述

　　N个人围成一圈，从第一个开始报数，第ｋ个将被杀掉，直到最后剩下一个。

解决思路

　　用循环单链表解决。

代码示例

/* function：约瑟夫环问题 - 循环单链表 created by ： xilong date: 2017.2.５ */ #include "iostream" using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef double Elemtype; typedef int Status; typedef struct Node { Elemtype data; struct Node* next; }Node; typedef struct Node* CLinkList; /* 功能：初始化一个空的单向循环链表头，并创建链表 */ CLinkList CLinkList_CreateJosephus() { CLinkList head; head = (CLinkList)malloc(sizeof(CLinkList)); CLinkList p, s; p = head; int flag = 1; Elemtype c; while (flag) { cin >> c; if (c != -99999) { s = (CLinkList)malloc(sizeof(CLinkList)); s->data = c; p->next = s; p = s; s->next = head->next; } else { flag = 0; p->next = head->next; } } return head->next; } Status Josephus(CLinkList *head,int k) { CLinkList p, temp; int i,j; p = *head; if (p == NULL) { cout << "空链表" << endl; return ERROR; } while (p != p->next) { for (i = 1; i <= k-2; i++) { p = p->next; } cout << p->next->data << " "; temp = p->next; p->next = temp->next; //free(temp); p = p->next; } cout << p->data << endl; return OK; } void main() { CLinkList head; int k; cout << "开始输入(这里是尾插法建表，输入-99999结束建表)..........." << endl; head = CLinkList_CreateJosephus(); cout << "输入步长："; cin >> k; cout << "输出的顺序为：" << endl; Josephus(&head, k); system("pause"); }

程序截图