《数据结构与算法》课程设计：32-约瑟夫环

《数据结构与算法》课程设计

32、约瑟夫环

问题描述：
编号为1，2，……n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
基本要求：
（1）利用单循环链表作为存储结构模拟此过程；
（2）键盘输入总人数、初始报数上限值m及各人密码；
（3）按照出列顺序输出各人的编号。

#include <iostream>using namespace std;typedef struct JosephRing {
    int number;                     //约瑟夫环中某个人的序号int password;                   //约瑟夫环中某个人的密码struct JosephRing *next;        //约瑟夫环的下一个节点
} Node;/*** 初始化约瑟夫环* @param n 成员数目* @param array 每个人的密码* @return 头结点*/
Node *init(int n, int array[]) {
    int i = 1;Node *head;         //链表首结点Node *current;      //链表当前节点Node *next;         //链表下一个节点current = (Node *) malloc(sizeof(Node));            //为当前结点分配内存空间current->number = i;                                //为当前结点的序号赋值current->password = array[i - 1];                   //为当前结点的密码赋值head = current;                                     //首结点为当前结点for (i = 2; i <= n; ++i) {
                              //循环生成结点next = (Node *) malloc(sizeof(Node));           //为下一结点分配内存空间next->number = i;                               //为下一结点的序号赋值next->password = array[i - 1];                  //为下一结点的密码赋值current->next = next;                           //连接链表与新创建的节点current = next;                                 //指针移向下一结点}current->next = head;                               //尾节点连接到首结点，形成循环链表return head;                                        //返回首结点
}/*** 遍历约瑟夫环，报数出列* @param head 头结点* @param length 约瑟夫环长度* @param password 初始密码*/
void function(Node *head, int length, int password) {
    Node *pre;          //前一个节点Node *next;         //后一个节点Node *temp;         //要删除的节点next = head;        //初始化for (int i = 1; i < length; ++i) {
          //pre 指向首结点的前一个结点即尾结点pre = next->next;next = next->next;}for (int i = 1; i <= length; ++i) {
                 //遍历所有人for (int j = 1; j < password; ++j) {
            //先将指针移动到出列的前一个pre = pre->next;}temp = pre->next;                   //保存要删除的节点next = temp->next;                  //下一个节点password = temp->password;          //修改密码cout << temp->number << endl;       //输出出列序号pre->next = next;                   //连接链表，去除中间节点free(temp);                         //释放中间节点}
}int main() {
    int length;         //环的长度cout << "输入约瑟夫环的长度：";cin >> length;int array[length];      //每个人的密码cout << "请输入m的初始值 m:";int m;cin >> m;cout << "请输入每个人的密码: " << endl;for (int i = 0; i < length; ++i) {
    cin >> array[i];}Node *head = init(length, array);function(head, length, m);return 0;
}