1.问题描述

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

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

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

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

2.模板库项目搭建

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

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

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

点击“下一步”：

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

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

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

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

[ASP.NET Core 3框架揭秘] Options[6]: 扩展与定制

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

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

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

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

CMakeLists.txt相关代码如下：

# CMakeList.txt: DataStructure 的 CMake 项目，在此处包括源代码并定义
# 项目特定的逻辑。
#
cmake_minimum_required (VERSION 3.8)

# 将源代码添加到此项目的可执行文件。
add_executable (circList "main.cpp" "circList.h" )

# TODO: 如有需要，请添加测试并安装目标。

main.cpp相关代码如下：

#include<iostream>
#include "circList.h"

using namespace std;

template<class T>
void Josephus(CircList<T> &Js,int n,int m) {
    CircLinkNode<T>* p = Js.getHead();
    CircLinkNode<T>* pre = NULL;

    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < m-1; j++) {
            pre = p;
            p = p->link;
        }
        
        cout << "出列的是：" << p->data << endl;
        pre->link = p->link;

        Js.Remove(p->data,p,pre);
        
        p = pre->link;

        cout << "出列后的队列为：" << endl;
        Js.output();
        cout << "当前元素为：" << p->data << endl;
    }
}

int main() {
    CircList<int> clist;
    int i, n, m;
    cout << "输入游戏者人数和报数间隔："<<endl;
    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        clist.Insert(i,i);
    }

    Josephus(clist, n, m);
}

程序运行后效果如下：
通过例子进阶学习C++（七）CMake项目通过模板库实现约瑟夫环