题目：Joseph 环（线性表应用）
【问题描述】
编号是 1，2，……,n 的 n 个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始选一个正整数作为报数上限值 m,从第一个人开始顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
测试数据：m 的初值为 4，n=7 ,7 个人的密码依次为 3，1，7，2，4，7，4.
输出结果为: 4 6 1
5 7 3 2
要求：
输入数据：输入 n（人数），输入 m（初始报数值）以及 n 个人的密码。
输出形式：建立一个函数，输出正确的出列序列。
1）采用顺序存储结构实现上述 joseph 问题。
2）采用链式存储结构实现上述 joseph 问题。
设计思路
自顶向下设计：拆解该问题为一个个模块，然后分模块完成
本题即为：存储输入数据 → 创建Joseph环 → 得到输出序列
设计细节：
我的Joseph 环算法是模拟的，所以时间复杂度较高，循环链表的版本是O(n)；顺序表版本由于删除操作带来的时间开销很大，故时间复杂度为O(n ^ 2)，同时由此可见在删除操作多的场合下，链表是非常高效的。
设计步骤是先画好流程图，验证下基本没问题才上手写代码，流程图如下：
1）在顺序表中，我对数组下标 i 进行取余操作，以达到循环访问数组的目的，如不理解，可以参照样例手动做一遍，这或许对理解有所帮助。
2）在循环链表（一般都带头结点）中，当我们访问到表尾后，要直接改变pre指针指向，否则将会访问头结点，但是访问头结点是无意义的。
杂谈
题目不难，只是既然学习了数据结构，不妨亲自写一下线性表的基本操作：创销+增删改查 + 判空 + 求表长。
顺带一提，优秀算法的四个指标：正确性 + 健壮性 + 可读性 + 高效率与低存储，其中我相当注重 “可读性”。正如《计算机程序的结构与解释》一书的卷首语所言：
“程序写出来是给人看的，附带能在机器上运行。”
不过我认为可读性不是堆砌注释（大段的注释狗都不看），参考《代码简洁之道》中推荐的做法：使用表意的函数名与变量名，而不是简单的 Init()、Delete() 或m、n ，这有助于代码阅读者直击原作者的想法，进而帮助他们理解代码意图。基于同样的原因，我的代码会逐渐避免堆注释的现象，只在关键地方写一些注释以帮助理解。
代码实现
三部分：顺序表基本操作 + 循环链表基本操作 + Joseph环算法 * 2
（如果对基本操作 * 2 不感兴趣，可直接跳到文章最后看）
1 /******************************顺序表基本操作******************************/ 2 3 #define MaxSize 100 // 定义SqList最大容量 4 #define ElemType Person 5 6 // 定义顺序表结构体 7 typedef struct { 8 ElemType data[MaxSize]; 9 int length; // 顺序表有效长度 10 } SqList; 11 12 // 创 13 void InitList(SqList &L) { 14 L.length = 0; //有效长度初始化为0 15 } 16 17 // 销 18 void DestroyList(SqList &L) { 19 // 本顺序表只建立在系统栈上，可自动回收内存 20 } 21 22 // 增：在指定位序插入元素e 23 bool ListInsert(SqList &L, int index, ElemType e) { 24 if ((index < 1) || (index > (L.length + 1))) { return false; } 25 if (L.length >= MaxSize) { return false; } 26 27 for (int i = (L.length - 1); i >= (index - 1); i--) { 28 L.data[i + 1] = L.data[i]; 29 } 30 L.data[index - 1] = e; // 挪出位置后再插入elem 31 L.length++; 32 33 return true; 34 } 35 36 // 删：删除指定位序的元素e，并返回之 37 bool ListDelete(SqList &L, int index, ElemType &e) { 38 if ((index < 1) || (index > L.length)) { return false; } 39 40 e = L.data[index-1]; 41 for (int i = (index - 1); i < (L.length - 1); i++) { 42 L.data[i] = L.data[i + 1]; 43 } 44 L.length--; 45 46 return true; 47 } 48 49 //判空：空则返回true 50 bool Empty(SqList L) { 51 if (L.length == 0) { return true; } 52 return false; 53 } 54 55 //求表长 56 int Length(SqList L) { 57 if (Empty(L)) { 58 printf("\nError in Length()! no SqList.\n"); 59 return -1; 60 } 61 return L.length; 62 }
1 /*************************LinkedCirList基本操作************************/ 2 3 #define ElemType Person 4 5 typedef struct LNode { 6 ElemType data; 7 LNode *next; 8 } LNode, *LinkedCirList; 9 10 // 创：InitializeCircularList(), 初始化循环链表 11 bool InitCirList(LinkedCirList &L) { 12 L = new LNode; 13 if (L == nullptr) { 14 printf("Fail to Allocate Memory.\n"); 15 return false; // 内存分配失败 16 } 17 L->next = L; // 头结点next指针指向自己 18 return true; 19 } 20 21 // 销：程序结束前释放链表所占的内存空间 22 void DestroyList(LinkedCirList &L) { 23 if (L == nullptr) { 24 return; // 空链表，无需删除 25 } 26 27 LNode *currNode = L->next; // 从第一个节点的下一个节点开始删除 28 LNode *nextNode = nullptr; // 删除currNode前备份nextNode地址 29 30 while (currNode != L) { 31 nextNode = currNode->next; 32 delete currNode; 33 currNode = nextNode; 34 } 35 36 // 删除头节点 37 delete L; 38 L = nullptr; 39 } 40 41 // 判空：若循环链表为空，则返回true 42 bool Empty(LinkedCirList L) { 43 if(L == nullptr || L->next == L) { 44 return true; 45 } else { 46 return false; 47 } 48 } 49 50 // 求表长 51 int Length(LinkedCirList L) { 52 53 if(L == nullptr) { 54 printf("there is no List.\n"); 55 return -1; 56 } 57 58 int length = 0; 59 // 将 curr 初始化为链表的第一个结点，跳过头结点 然后for遍历链表求表长 // while当然也可以 只是for更紧凑易读，也更有挑战性 60 for(LNode* curr=L->next; curr!=L; curr=curr->next) { 61 length++; 62 } 63 64 return length; 65 } 66 67 68 // 增：插入操作 （头插法） 69 bool List_HeadInsert(LinkedCirList L, ElemType e) { 70 // 判断头结点L是否为空 71 if(L == nullptr) { 72 printf("\nthere is no List.\n"); 73 return false; 74 } 75 76 // 初始化一个临时结点存放e 77 LNode *temp = new LNode; 78 if(temp == nullptr) { 79 printf("\nFail to Allocate Memory.\n"); 80 delete temp; 81 return false; // 内存分配失败 82 } 83 temp->data = e; 84 temp->next = nullptr; 85 86 // 头插法插入循环链表 87 temp->next = L->next; 88 L->next = temp; 89 90 return true; 91 } // List_HeadInsert() 92 93 // 删：删除指定结点后一结点 94 bool ListDelete(LinkedCirList L, LNode *pre, ElemType &elem) { 95 if (pre == nullptr || 96 pre->next == nullptr || 97 pre->next->next == nullptr || 98 pre->next == L) { 99 return false; 100 } 101 102 LNode *tmp = pre->next; 103 elem = tmp->data; 104 pre->next = pre->next->next; 105 106 if (tmp != nullptr) { 107 delete tmp; 108 tmp = nullptr; // 防止野指针 109 } 110 111 return true; 112 }
1 /******************************朴实约瑟夫环算法（基于SqList）******************************/ 2 3 bool JosephSqList(int &CountCeil, const int &len) { 4 SqList L; 5 InitList(L); 6 7 // 健壮性保障 8 if ((CountCeil <= 0) || (len <= 0) || (len > MaxSize)) { 9 printf("ERROR! Invalid Input.\n"); 10 return false; 11 } 12 13 // 将参与Joseph环的所有人的信息存储于sqList L 中 14 int code = -1; 15 printf("Plz enter everyone's code:"); 16 for (int i = 1; i <= len; i++) { 17 scanf("%d", &code); 18 Person person(i, code); 19 ListInsert(L, i, person); 20 } 21 // 存储完毕 22 23 int count = 0; 24 ElemType e; 25 printf("The OUT order is:"); 26 for (int i = 0; !Empty(L); i = ((i + 1) % Length(L))) { 27 count++; 28 if (count == CountCeil) { 29 ListDelete(L, (i + 1), e); 30 printf("%d ", e.index); 31 i -= 1; // 由于有节点弹出，索引后退一位 32 count = 0; // 重置count 与 CountCeil 33 CountCeil = e.code; 34 if (Empty(L)) { // 由于弹出结点可能导致L为空，进而导致 i 的递推式出现对 0 取余的bug，所以此处先判断退出与否 35 break; 36 } 37 } 38 } 39 return true; 40 } 41 42 43 /******************************朴实约瑟夫环算法（基于循环链表）******************************/ 44 45 bool JosephCirLList(int CountCeil, int len) { 46 LinkedCirList L; 47 InitCirList(L); 48 49 // 健壮性保障 50 if ((CountCeil <= 0) || (len <= 0)) { 51 printf("ERROR! Invalid Input.\n"); 52 return false; 53 } 54 55 // 先把不带密码的众人“逆序”存入链表 56 for(int i = len; i > 0; i--) { 57 Person person(i); 58 List_HeadInsert(L, person); 59 } 60 61 // 再“顺序”赋予众人密码 62 int code_tmp = 0; 63 LNode *curr = L->next; // curr初始指向第一个数据结点 64 printf("Plz enter everyone's code:"); 65 while(curr != L) { 66 scanf("%d", &code_tmp); 67 curr->data.code = code_tmp; 68 curr = curr->next; 69 } 70 // 存储完毕 71 72 int count = 0; 73 ElemType e; 74 LNode *pre = L; 75 printf("The OUT order is:"); 76 while(!Empty(L)) { 77 count++; 78 if(count == CountCeil) { 79 ListDelete(L, pre, e); 80 printf("%d ", e.index); 81 count = 0; // 重置count 与 CountCeil 82 CountCeil = e.code; 83 } else { // 如果报数没报到m，则pre继续后移 84 pre = pre->next; 85 } 86 // 循环链表尾结点处理 87 if(pre->next == L) { pre = L; } 88 } 89 90 DestroyList(L); // 函数退出前，销毁链表 91 return true; 92 }
1 class Person { 2 public: 3 int index; // 原位序 4 int code; // 密码 5 6 Person() : index(-1), code(-1) {} 7 Person(int _index) : index(_index), code(-1) {} 8 Person(int _index, int _code) : index(_index), code(_code) {} 9 ~Person() { 10 // Person类中没有在堆上申请内存，空析构函数即可 11 } 12 };
运行结果
结束语
本人也是菜鸟一枚，还有很多需要学习，所以我希望我的博客能先满足不误人子弟的前提，在此基础上如果能对你有一些帮助就更好了。
如果你发现了任何问题或是存在别的什么需求，欢迎留言！