約瑟夫環問題(Josephus)　—— 循環單鏈表

2019-11-11 07:25:05

字體：大中小

來源：轉載

供稿：網友

問題描述

　　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");}