通过例子进阶学习C++（七）CMake项目通过模板库实现约瑟夫环

回顾一下约瑟夫环问题：n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一个人重新开始报数，数到第 m 个人，再让他出局......,如此反复直到所有人全部出局为止。

上一篇我们通过数组、静态链表实现了约瑟夫环，具体参考：

通过例子进阶学习C++（六）你真的能写出约瑟夫环么

本文，我们进一步深入分析约瑟夫环问题，并通过c++模板库实现该问题求解，最后我们说明用模板库的优劣之处。

2.模板库项目搭建

本文我们用c++的模板库通过单向循环链表实现约瑟夫环问题，用c++模板库实现约瑟夫环。

首先我们在Visual Studio中“文件”--“新建”--”CMake项目“：

点击“下一步”：

点击“创建”，即可生成一个CMake的C++项目。

在解决方案上面，点击“右键”，“添加”--“新建文件夹”：

在文件夹中新建文件“circList.h”、“CMakeLists.txt”和“main.cpp”。

然后在整个项目的“CMakeLists.txt"中增加如下内容：

3.C++模板库通过循环链表实现约瑟夫环

用C++模板库实现约瑟夫环，主要包括这3个文件：“circList.h”、“CMakeLists.txt”和“main.cpp”。整个代码以《数据结构 用面向对象方法与c++语言描述》（第2版）上面的实现为基础。

用书本上面的例子，是无法直接运行的，耗费了一定的时间才修改好。

circList.h相关代码：

template<class T> struct CircLinkNode { T data; CircLinkNode<T>* link; CircLinkNode(CircLinkNode<T> *next = NULL):link(next){} CircLinkNode(T d, CircLinkNode<T> *next = NULL):data(d),link(next){} }; template<class T> class CircList { public: CircList() { first = last = NULL; } CircList(const T& x) { first = new CircLinkNode<T>(x); } CircList(CircList<T>& L) { T value; CircLinkNode<T>* srcptr = L.getHead(); CircLinkNode<T>* destptr = first = new CircLinkNode<T>; while (srcptr->link != NULL) { value = srcptr->link->data; destptr->link = new CircLinkNode<T>(value); destptr = destptr->link; srcptr = srcptr->link; } destptr->link = NULL; } ~CircList() { //makeEmpty(); } void makeEmpty() { CircLinkNode<T>* q; while (first!=NULL && first->link != first) { q = first->link; first->link = q->link; delete q; } } int length() const { CircLinkNode<T>* p = first->link; int count = 0; while (p != NULL) { count++; p = p->link; } return count; } CircLinkNode<T>* getHead()const { return first; } void setHead(CircLinkNode<T>* p) { first = p; } CircLinkNode<T>* Search(T x) { CircLinkNode<T>* current = first->link; while (current != first) { if (current->data == x) break; else current = current->link; } return current; } CircLinkNode<T>* Locate(int i) { if (i < 0) return NULL; CircLinkNode<T>* current = first; int k = 0; while (current->link != first && k < i) { current = current->link; k++; } return current; } T* getData(int i) { if (i < 0) return NULL; CircLinkNode<T>* current = Locate(i); if (current == NULL) return NULL; else return &current->data; } void setData(int i, T& x) { if (i < 0) return; CircLinkNode<T>* current = Locate(i); if (current == NULL) return; else current->data = x; } bool Insert(int i, T& x) { CircLinkNode<T>* newNode = new CircLinkNode<T>(x); if (newNode == NULL) { cerr << "存储分配失败！" << endl; exit(1); } if (i == 1) { first = last = newNode; first->link = newNode; } else { last->link = newNode; last = newNode; } newNode->link = first; return true; } bool Remove(int i, CircLinkNode<T> * p, CircLinkNode<T>* pre) { if (first == p) { first = p->link; } if (last == p) { last = pre; } delete p; return true; } void output() { CircLinkNode<T>* current = first->link; cout << first->data << " "; while (current != last->link) { cout << current->data <<" "; current = current->link; } cout << endl; } private: CircLinkNode<T>* first, * last; };