约瑟夫问题.pdf

《约瑟夫问题.pdf》由会员分享，可在线阅读，更多相关《约瑟夫问题.pdf（2页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、约瑟夫问题 利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：有 n 个人(n=1)围坐在一个圆桌周围，把这 n 个人依次编号为1，n。从编号是 1 的人开始报数，顺时针数到 m 的那个人出列，他的下一个然后从出列的下一个人重新开始报数，数到第 m 个人又出列，如此反复直到所有的人全部出列。请问最后一个出列的人的编号。2.程序分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到 m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。在这个程序中解决了存储问题后，之后最大的难点就是关于出列节点的逻辑判断。由于

2、我插入元素时是将 rear 指针中也存入了元素值，又增加了一个 front 指针，实际上是front 指针始终存在而 rear 指针有可能消除。这样遇到的问题就是，假设 p 本身就是rear 指针，那当移到下一位时就应该移动两位来跳过 front 这一个空节点。这个是程序实现中容易发生逻辑错误的地方。2.1 存储结构 本实验中所用的存储结构为单链表。以下即为单链表的存储结构示意图：front （1）空单循环链表 a1 a2 an front rear （2）非空单循环链表 2.2 关键算法分析 1、关键算法：（1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front

3、头结点。在每加入一个节点时，都会直接连接在 front 后面，从而保证一开始就赋值的 rear 尾节点不用修改。伪代码阐释如下：1)、在堆中建立新节点：Node*s=new Node;2)、将 ai写入到新节点的数据域：s-data=ai;3)、修改新节点的指针域：s-next=front-next;4)、修改头结点的指针域，将新节点加入到链表中：front-next=s;时间复杂度为：1；(2)、删除：首先通过 p 指针查找到所要删除的节点的前一个节点，继而通过 q=p-next 简单地删除掉。假设所要查找的为第 i 个元素。伪代码阐释如下：1）、在堆中建立新节点 p,通过循环查找到 i-1

4、，将此节点的地址赋给 p。2）、设 q 指向第 i 个节点：若 p=rear，则 q=front-next;否则，q=p-next;3)、摘链，即将 q 从链表中摘除：若 q=rear，则 p-next=front-next；否则，则 p-next=q-next.4)、保存 q 元素的数据：x=q-data；5）、释放 q 元素：delete q；时间复杂度为：1；（3）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个 for 循环来计数所查找过的节点。其中查找的时间复杂度也为 1；感谢您的阅读，祝您生活愉快。