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

2019-11-14 09:17:53

字体：大中小

来源：转载

供稿：网友

问题描述

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

解决思路

　　用循环单链表解决。

代码示例

/* function：约瑟夫环问题 - 循环单链表 created by ： xilong date: 2017.2.５*/#include "iostream"using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef 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");}