c语言循环链表约瑟夫问题的时间复杂度,用单向循环链表解决约瑟夫问题算法优劣性分析.doc...

用单向循环链表解决约瑟夫问题算法优劣性分析

用单向循环链表解决约瑟夫问题算法优劣性分析

摘要： 首先由简单问题引入约瑟夫问题，然后用单向循环链表解决约瑟夫问题，最后对模拟方法及数学方法的优劣性进行分析，从而为研究人员和开发人员基于性能选择使用算法解决约瑟夫问题的实例提供依据。

关键词： 约瑟夫问题；单向循环链表；结点；时间复杂度

中图分类号：TP3文献标识码：A文章编号：1671－7597(2011)0110012－02

1 链表相关知识

1.1 链表

链表是一种物理存储单元上非连续、非顺序的存储结构[1]，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表有单向链表、双向链表、循环链表三种。

1.2 循环链表

当链表的尾节点的后继节点指向头结点时，这种首尾相接的链表就是循环链表，它是单链表的另一种形式[1]。在循环链表中，从任意一个单元出发可以找到表中其他单元。循环链表分为单向和双向两种。在单向循环链表中，表中所有结点被链在一个环上，多重循环链表则是将表中的结点链在多个环上。

由于本文讨论的单向循环链表，所以我们看一下单向循环链表的数据结构，如图1所示。

图1单向循环链表

带头结点的单向循环链表的各种操作的实现算法与带头结点的单链表的实现算法类似，差别仅在于算法中的循环条件不是p!=NULL或p->next!=NULL，而是p!=L或p->next!=L。

1.3 单向循环链表的注意事项

1)在遍历单向循环链表时，要注意记住单向循环链表的开始，避免产生死循环。如果没有记住从哪里开始，就会在链表中无限循环下去。

2)在使用单向循环链表时，需要注意及时更新头指针head和尾指针tail。因为head丢失会导致链表在内存中丢失。这意味着在对链表中的元素进行插入、删除操作时，如果有必要，必须及时维护链表的head和tail指针。

3)在单向循环链表中，可以用头指针表示单向循环链表，也可以用尾指针表示单向循环链表，但是用尾指针表示单向循环链表常常会使操作变得更简单。如在用头指针表示的单向循环链表中，找开始结点a1的时间复杂度是O(1)，然而要找到终端结点an，则需要从头指针开始遍历整个链表，其时间复杂度是O(n)。如果用尾指针rear来表示单向循环链表，则查找开始结点和终端结点都很方便，它们的存储位置分别是rear-〉next-〉next和rear，显然，查找时间复杂度都是O(1)。另外，当两个链表L1和L2合并成一个链表时，此时用尾指针rear来表示单向循环链表，只要修改两个指针值即可，时间复杂度仍为O(1)。因此，实用中多采用尾指针表示单向循环链表。

2 由简单问题引发的约瑟夫问题

2.1 约瑟夫问题的描述

在解决约瑟夫问题之前，我们先看一个类似的简单问题：

假如一个旅行社要从n名旅客中选出一名幸运之星，为他提供免费环球旅行服务。方法是，大家站成圈，然后选定一个m，从第1个人开始报数，报到m时，这个人出列，然后从下一个人开始重新从1报数，重复这个过程，直到最后剩下一个人就是幸运之星。问题就是谁是幸运者呢？或者说是怎样才能赢大奖。实际上这个问题就是约瑟夫问题的实例[2]。

下面看一看最原始的约瑟夫问题，它表现为如下的四种描述：

1)约瑟夫(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)

提出的，约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名宁死不降的将士在附近的一个洞穴中避难。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。

2)17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

3)有ｎ只猴子，按顺时针方向围成一圈选大王(编号从１到ｎ)，从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

4)编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正