1 /** 2  * 循环链表求解约瑟夫环问题 3  **/ 4 #include 
     
       5 #include 
      
        6 using namespace std; 7  8 /** 9  * 数据结构10  **/11 typedef struct DanamicList {12     int id;13     struct DanamicList* next;14 } List;15 16 /**17  * 创建循环链表18  **/19 List* InitList(int numCount) {20     if(numCount <= 0) {21         cout << "Value is invalid!!!\n";22         exit(-1);23     }24     List *head = head = new List;25     if(!head) {26         cout << "Alloc memory failed!!!\n";27         exit(-1);28     }29 30     head->id = 1;31     List *pre = head;32     for(int index = 1; index < numCount; ++index) {33         List *temp = new List;34         if(!temp) {35             cout << "Alloc memory failed!!!\n";36             exit(-1);37         }38         temp->id = index + 1;39         temp->next = NULL;40         pre->next = temp;41         pre = temp;42     }43     pre->next = head;44 45     return head;46 }47 48 /**49  * 求解约瑟夫环问题50  **/51 void josephus(List* head, int number) {52     int count = 0, flag = 0;53     List *pre = head, *del = NULL;54 55     while(pre->next != head)56         pre = pre->next;57     do {58         ++count;59         if(number != count)60             pre = pre->next;61         else {62             count = 0;63             del = pre->next;64             cout << del->id << "\t";65             pre->next = pre->next->next;66             if (pre != pre->next)67                 delete del;68         }69         if(pre == pre->next)70             ++flag;71     } while(flag - (number + 1));             // 数学关系72     delete pre;73 }74 75 /**76  * 主函数77  **/78 int main(void) {79     List *head = NULL;80     int totalPeople = 0, outNumber = 0;81     cout << "请输入总数和出队密码：";82     cin >> totalPeople;83     cin >> outNumber;84 85     head = InitList(totalPeople);             // 创建循环链表86     josephus(head, outNumber);                // 求解约瑟夫环87 88     return 0;89 }