本文主要是介绍链表初解(三)——约瑟夫环之循环链表实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开
始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。现编写循环链表程序来实现约瑟夫环问题并输出每次出列的结果~
用循环链表模拟此过程即可:1、建表;2、模拟出列规则。
下面还是老套路,直接贴上源码+注释~
Code:
#include<iostream>
using namespace std;typedef struct List
{int data;struct List *next;
}List, *Lnode;void Josephus(int n, int k, int m)//n:有n个人,编号1-n;k:从编号为k的人开始报数;m:数到m的人出列。
{Lnode first, now, pre, temp;//first:头节点;now:始终代表当前指针位置;pre:now的前驱节点;temp:新创建的节点。//创建一个节点的循环链表first = (Lnode)malloc(sizeof(List));first->data = 1;first->next = first;now = first;//创建循环链表,编号为1-n for(int iFirst = 2; iFirst <= n; iFirst++){temp = (Lnode)malloc(sizeof(List));temp->data = iFirst; //给每个节点编号为1-n。//将当前指针的后继赋给新创建的节点的后继(即新节点的后继为默认的“头节点”first)。temp->next = now->next; now->next = temp; //将断开的连接修复好。now = temp; //移动当前指针,继续建表过程。}//将当前指针位置初始化,指向编号为1处。now = now->next;//当前指针指向编号为k处。while(--k) {pre = now;now = now->next;}//模拟出列过程。printf("The Line is : ");while(n--){for(int j = 1; j < m; j++){//当前指针指向第m个报数的人。pre = now;now = now->next;}//删除并输出出列的编号。pre->next = now->next;if(now->next == now) printf("%d\n\n", now->data);//当剩余一个节点时,换行。else printf("%d->", now->data);first = now->next; //出列后,第一个报数的人。free(now); //释放删除的节点。now = first; //当前指针转移到第一个报数的人,继续出列的过程。}
}int main()
{Josephus(9, 1, 5);return 0;
}
Ps:仅供参考哈~~
这篇关于链表初解(三)——约瑟夫环之循环链表实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!