大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 循环链表基础
在单链表中，有了头结点，我们可以在O(1)时间访问到第一个节点，但如果要访问最后一个节点却需要O(n)的时间，因为我们需要对整个链表进行一次遍历。在循环链表中，我们可以借助尾节点来实现，即不用头指针，而是用指向终端结点的尾指针来表示循环链表，这时候无论是查找第一个节点还是最后一个节点都很方便，可以控制在O(1)的时间内，如下图所示。
二 代码实现
（1）循环链表初始化
template <typename T> struct Node { T data; Node<T>* pNext; }; void InitList() { // 删除所有节点 Clear(); m_pHead = new Node<T>; memset(m_pHead,0, sizeof(Node<T>)); m_pHead->pNext = m_pHead; }
（2）循环链表新结点插入
// 从尾部添加节点 void AddNode(T data) { Node<T> *pNode = new Node<T>; pNode->data = data; Node<T>* pTemp = m_pHead; while (pTemp->pNext!= m_pHead) { pTemp = pTemp->pNext; } pNode->pNext = pTemp->pNext; pTemp->pNext = pNode; }
（3）循环链接结点删除
void DeleteNode(T data) { Node<T> *pNode = m_pHead; Node<T> *pTemp = NULL; while (pNode->pNext != m_pHead) { if (pNode->pNext->data == data) { pTemp = pNode->pNext; pNode->pNext = pTemp->pNext; delete pTemp; } else { pNode = pNode->pNext; } } }
（4）删除循环链表
void Clear() { if (NULL == m_pHead) { return; } Node<T>* pTemp = NULL; Node<T>* pNode = m_pHead->pNext; while (pNode != m_pHead) { pTemp = pNode; pNode = pNode->pNext; delete pTemp; } delete pNode;
（5）打印循环链表
void PrintList() { Node<T>* pNode = m_pHead->pNext; while (pNode != m_pHead) { cout << pNode->data << " "; pNode = pNode->pNext; } cout << endl; }
（6）代码
#include "stdio.h" #include <iostream> using namespace std; template <typename T> struct Node { T data; Node<T>* pNext; }; // 主要实现循环链表的添加、删除和打印 template <typename T> class CircList { public: CircList() { m_pHead = NULL; nLen = 0; } ~CircList() { Clear(); m_pHead = NULL; } void InitList() { // 删除所有节点 Clear(); m_pHead = new Node<T>; memset(m_pHead,0, sizeof(Node<T>)); m_pHead->pNext = m_pHead; } // 从尾部添加节点 void AddNode(T data) { Node<T> *pNode = new Node<T>; pNode->data = data; Node<T>* pTemp = m_pHead; while (pTemp->pNext!= m_pHead) { pTemp = pTemp->pNext; } pNode->pNext = pTemp->pNext; pTemp->pNext = pNode; nLen ++; } void DeleteNode(T data) { Node<T> *pNode = m_pHead; Node<T> *pTemp = NULL; while (pNode->pNext != m_pHead) { if (pNode->pNext->data == data) { pTemp = pNode->pNext; pNode->pNext = pTemp->pNext; delete pTemp; } else { pNode = pNode->pNext; } } nLen --; } void PrintList() { Node<T>* pNode = m_pHead->pNext; while (pNode != m_pHead) { cout << pNode->data << " "; pNode = pNode->pNext; } } void Clear() { if (NULL == m_pHead) { return; } Node<T>* pTemp = NULL; Node<T>* pNode = m_pHead->pNext; while (pNode != m_pHead) { pTemp = pNode; pNode = pNode->pNext; delete pTemp; nLen --; } delete pNode; nLen --; } Node<T>* ListHead() { return m_pHead; } int ListLength() { return nLen; } private: Node<T>* m_pHead; int nLen; };
View Code
三 约瑟夫问题
（1）何为约瑟夫问题
据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
以上就是著名的约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下Q个。从围成一圈这里就启发了我们可以使用循环链表来解决该问题。
（2）代码实现
void JosephusTest() { int n,m; cout << "约瑟夫问题:" << "N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下Q个" << endl; cout << "请输入数字N:"; cin >> n; cout << "请输入数字M:"; cin >> m; CircList<int> cirllist; cirllist.InitList(); for (int i = 0; i < n; i ++) { cirllist.AddNode(i + 1); } cout << "所有参与人员："; cirllist.PrintList(); cout << endl; cout << "-------------------" << endl; Node<int>* pListHead = cirllist.ListHead(); Node<int>* pStartNode = pListHead; Node<int>* pTemp = NULL; int nListLen = cirllist.ListLength(); while(nListLen >= m) { for (int j = 1; j < m; j ++) { if (pStartNode == pListHead) { pStartNode = pStartNode->pNext; } pStartNode = pStartNode->pNext; } if (pStartNode == pListHead) { pStartNode = pStartNode->pNext; } pTemp = pStartNode; pStartNode = pStartNode->pNext; cirllist.DeleteNode(pTemp->data); nListLen --; cout << "剩余报数人员："; cirllist.PrintList(); cout << endl; } } void main() { JosephusTest(); return; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120157.html原文链接：https://javaforall.net
