本文是通过例子学习 C++ 的第七篇, 通过这个例子可以快速入门 c++ 相关的语法.
1. 问题描述
回顾一下约瑟夫环问题: n 个人围坐在一个圆桌周围, 现在从第 s 个人开始报数, 数到第 m 个人, 让他出局; 然后从出局的下一个人重新开始报数, 数到第 m 个人, 再让他出局......, 如此反复直到所有人全部出局为止.
上一篇我们通过数组, 静态链表实现了约瑟夫环, 具体参考:
通过例子进阶学习 C++(六) 你真的能写出约瑟夫环么 https://www.cnblogs.com/siweihz/p/12198744.html
本文, 我们进一步深入分析约瑟夫环问题, 并通过 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 ¤t->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);
- }
程序运行后效果如下:
4. 总结
本着 Talk is cheap. Show me the code 原则, 代码实现不做过多解释.
通过该例子, 可以学习:
在 Visual Studio 中搭建 CMake 项目;
在 CMake 项目中增加 "可执行文件";
掌握 struct 定义; class 定义; template class ,function 定义; 构造函数; 析构函数;
通过模板库实现约瑟夫环问题
本文从构思到完成, 可谓是耗费了大量的心血.
如果您阅读本文后哪怕有一丢丢收获, 请不要吝啬你手中关注和点赞的权力, 谢谢!
另外, 如果需要相关代码, 请留言, 可以提供完整源代码!
来源: http://www.bubuko.com/infodetail-3387489.html