C++ 中循环链表和约瑟夫环
更新时间:2020年4月25日 17:31 点击:1707
循环链表和约瑟夫环
循环链表的实现
单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head。
代码实现分为四部分:
- 初始化
- 插入
- 删除
- 定位寻找
代码实现:
void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"<<endl; while(1){ cin>>item; if(!item) return ; if(!(pNode)){ //当空表的时候,head==NULL pNode = new Node ; if(!(pNode)) exit(0);//未成功申请 pNode->data = item; pNode->next = pNode; } else{ // for(target = pNode;target->next!=pNode;target = target->next) ; temp = new Node; if(!(temp)) exit(0); temp->data = item; temp->next = pNode; target->next = temp; } } } void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置 Node *temp; Node *target; int item; cout<<"输入您要插入的值:"<<endl; cin>>item; if(i==1){ temp = new Node; if(!temp) exit(0); temp->data = item; for(target=pNode;target->next != pNode;target = target->next) ; temp->next = pNode; target->next = temp; pNode = temp; } else{ target = pNode; for (int j=1;j<i-1;++j) target = target->next; temp = new Node; if(!temp) exit(0); temp->data = item; temp->next = target->next; target->next = temp; } } void ListDelete(Node *pNode,int i){ Node *target,*temp; if(i==1){ for(target=pNode;target->next!=pNode;target=target->next) ; temp = pNode;//保存一下要删除的首节点 ,一会便于释放 pNode = pNode->next; target->next = pNode; delete temp; } else{ target = pNode; for(int j=1;j<i-1;++j) target = target->next; temp = target->next;//要释放的node target->next = target->next->next; delete temp; } } int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置 Node *target; int i=1; for(target = pNode;target->data!=elem && target->next!= pNode;++i) target = target->next; if(target->next == pNode && target->data!=elem) return 0; else return i; }
约瑟夫问题
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。
注意:编写代码的时候,注意报数为m = 1的时候特殊情况
#include<iostream> #include<cstdio> using namespace std; typedef struct Node{ int data; Node *next; }; Node *Create(int n){ Node *p = NULL, *head; head = new Node; if (!head) exit(0); p = head; // p是当前指针 int item=1; if(n){ int i=1; Node *temp; while(i<=n){ temp = new Node; if(!temp) exit(0); temp->data = i++; p->next = temp; p = temp; } p->next = head->next; } delete head; return p->next; } void Joseph(int n,int m){ //n为总人数,m为数到第m个的退出 m = n%m; Node *start = Create(n); if(m){//如果取余数后的m!=0,说明 m!=1 while(start->next!=start){ Node *temp = new Node; if(!temp) exit(0); for(int i=0;i<m-1;i++) // m = 3%2 = 1 start = start->next; temp = start->next; start->next = start->next->next; start = start->next; cout<<temp->data<<" "; delete temp; } } else{ for(int i=0;i<n-1;i++){ Node *temp = new Node; if(!temp) exit(0); cout<<start->data<<" "; temp = start; start = start->next; delete temp; } } cout<<endl; cout<<"The last person is:"<<start->data<<endl; } int main(){ Joseph(3,1); Joseph(3,2); return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
下一篇: C语言数据输入与输出实例详解
相关文章
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++ 约瑟夫环的实例代码的相关资料,希望通过本文能帮助到大家,实现这样的功能,需要的朋友可以参考下...2020-04-25
- 本篇文章是对约瑟夫环的数学优化方法进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了详解约瑟夫环问题及其相关的C语言算法实现,也是ACM当中经常会引用到的基础题目,文中共介绍了三种C语言解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言约瑟夫环的实现的相关资料,这里主要是利用数据数据结果中循环链表来实现,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++循环链表之约瑟夫环的实现方法,对于学习数据结构与算法有一定的借鉴价值,需要的朋友可以参考下...2020-04-25
- 本篇文章是对HDOJ 1443 约瑟夫环的最新应用进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了python实现数据结构中双向循环链表操作的示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-09
- 这篇文章主要介绍了C++ 中约瑟夫环替换计数器m(数组解决)的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言基于循环链表解决约瑟夫环问题的方法,简单描述了约瑟夫环问题并结合实例形式分析了C语言使用循环链表解决约瑟夫环问题的具体操作技巧,需要的朋友可以参考下...2020-04-25
- 本篇文章是对用C++实现双向循环链表的方法进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C数据结构循环链表实现约瑟夫环的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ 中循环链表和约瑟夫环的相关资料,需要的朋友可以参考下...2020-04-25
- C#数据结构之循环链表的实例代码,需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了C语言数据结构之双向循环链表的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了数据结构 C语言实现循环单链表的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之循环链表的简单实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之判断循环链表空与满的相关资料,希望通过本文能帮助到大家,让大家掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了约瑟夫环问题(数组法)c语言实现,有需要的朋友可以参考一下...2020-04-25
- 本篇文章是对用C++实现单向循环链表的解决方法进行了详细的分析介绍,需要的朋友参考下...2020-04-25