摘要:本文主要向大家介绍了C++语言之链表初解的约瑟夫环之循环链表实现,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
本文主要向大家介绍了C++语言之链表初解的约瑟夫环之循环链表实现,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开
始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。现编写循环链表程序来实现约瑟夫环问题并输出每次出列的结果~
用循环链表模拟此过程即可:1、建表;2、模拟出列规则。
下面还是老套路,直接贴上源码+注释~
Code:
[cpp] view plain copy 1. #include<iostream> 2. using namespace std; 3. 4. typedef struct List 5. { 6. int data; 7. struct List *next; 8. }List, *Lnode; 9. 10. void Josephus(int n, int k, int m)//n:有n个人,编号1-n;k:从编号为k的人开始报数;m:数到m的人出列。 11. { 12. Lnode first, now, pre, temp;//first:头节点;now:始终代表当前指针位置;pre:now的前驱节点;temp:新创建的节点。 13. //创建一个节点的循环链表 14. first = (Lnode)malloc(sizeof(List)); 15. first->data = 1; 16. first->next = first; 17. now = first; 18. //创建循环链表,编号为1-n 19. for(int iFirst = 2; iFirst <= n; iFirst++) 20. { 21. temp = (Lnode)malloc(sizeof(List)); 22. temp->data = iFirst; //给每个节点编号为1-n。 23. //将当前指针的后继赋给新创建的节点的后继(即新节点的后继为默认的“头节点”first)。 24. temp->next = now->next; 25. now->next = temp; //将断开的连接修复好。 26. now = temp; //移动当前指针,继续建表过程。 27. } 28. //将当前指针位置初始化,指向编号为1处。 29. now = now->next; 30. //当前指针指向编号为k处。 31. while(--k) 32. { 33. pre = now; 34. now = now->next; 35. } 36. //模拟出列过程。 37. printf("The Line is : "); 38. while(n--) 39. { 40. for(int j = 1; j < m; j++) 41. {//当前指针指向第m个报数的人。 42. pre = now; 43. now = now->next; 44. } 45. //删除并输出出列的编号。 46. pre->next = now->next; 47. if(now->next == now) printf("%d\n\n", now->data);//当剩余一个节点时,换行。 48. else printf("%d->", now->data); 49. first = now->next; //出列后,第一个报数的人。 50. free(now); //释放删除的节点。 51. now = first; //当前指针转移到第一个报数的人,继续出列的过程。 52. } 53. } 54. 55. int main() 56. { 57. Josephus(9, 1, 5); 58. return 0; 59. }
Ps:仅供参考哈~~
本文由职坐标整理并发布,了解更多内容,请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号