Chinaunix

标题: 有什么简单的办法检查单链表里是否有环？ [打印本页]

作者: mhello 时间: 2007-05-21 10:10
标题: 有什么简单的办法检查单链表里是否有环？
如给定:
typedef struct node {
char ch;
struct node *next;
}node_t;

int isCircle( node_t *head);

以这两个条件如何确定单链表里有环存在？

作者: chinaljj 时间: 2007-05-21 10:26
int isCircle( node_t *head)
{
node_t *pTmpNode;

pTmpNode = head;

while (pTmpNode != head)
{
pTmpNode = pTmpNode->next;
if (pTmpNode == NULL)
{
return false;
}
}
return true;
}

这样应该可以

作者: anhongkui 时间: 2007-05-21 10:42
楼上的不对，楼主请查找以前的帖子

作者: mhello 时间: 2007-05-21 10:43
问题是这个环可能是由结尾指针指向前边的任意元素，不一定指回头节点？
如：
head-->##-->##-->##-->##-->##--
                     ^                               |
                     |                               |
                        ---------------------------
（画得难看，见笑！）
可能我没说清楚，
正常的单链表一般应该是head->##->........->##->NULL，
假如出现异常操作，使得尾指针不是指向NULL，而是指向前面某个元素（不一定指回头节点），
这时假如需要一个接口去判断这个单链表是否是正常链表，这个接口用什么办法（或算法）实现！

作者: 福瑞哈哥 时间: 2007-05-21 10:48

int isCircle( node_t *head)
{
node_t *q,* p = head;
while (p) {
q = p->next;
while (q) {
if (p == q) return 1;
q = q->next;
}
p = p->next;
}
return 0;
}

复制代码

怎麼也得兩個循環吧？

作者: chinaljj 时间: 2007-05-21 10:59
So sorry！ I'm wrong

作者: mhello 时间: 2007-05-21 11:06
标题: 回复 5楼福瑞哈哥的帖子
如果有回环，第二个循环是否有死循环的可能？
如：
head->#->#->#->#->#->#->#->
                           ^                   |
                           |                   |
                           -----------------
这种情况可否正常工作？

作者: 福瑞哈哥 时间: 2007-05-21 11:08

原帖由 mhello 于 2007-5-21 11:06 发表
如果有回环，第二个循环是否有死循环的可能？
如：
head->#->#->#->#->#->#->#->
^ |
| ...

shit，入了陷阱！

作者: mhello 时间: 2007-05-21 11:29
标题: 回复 4楼 mhello 的帖子
各位大侠，有什么方法可以解决这个问题（先不考虑解决方法的效率问题）？

作者: billzhou 时间: 2007-05-21 11:37
这样可以吗

int isCircle(node_t *head)
{
   node_t *  p=&head;
   node_t *  q=&head;
   while(p->next != NULL && q->next->next!= NULL)
   {
      p=p->next;
      q=q->next->next;

         if(p->ch ==  q->ch)
      return 1;

   }

   return 0;
}

}

作者: emacsnw 时间: 2007-05-21 11:41

原帖由 mhello 于 2007-5-20 18:10 发表
如给定:
typedef struct node {
char ch;
struct node *next;
}node_t;

int isCircle( node_t *head);

以这两个条件如何确定单链表里有环存在？

搜一下前面的帖子吧。提供一个实现：

int isCircle(node_t *head)
{
if (!head)
return 0;
node_t *p = head, *q = head->next;
while (q) {
if (p == q) return 1;
p = p->next;
q = q->next;
if (!q) return 0;
q = q->next;
}
return 0;
}

复制代码

作者: 福瑞哈哥 时间: 2007-05-21 12:21

原帖由 emacsnw 于 2007-5-21 11:41 发表

搜一下前面的帖子吧。提供一个实现：
[

太強了，利用步長來循環。

作者: 清汤挂面 时间: 2007-05-21 16:21

原帖由 福瑞哈哥 于 2007-5-21 12:21 发表

太強了，利用步長來循環。

呵呵，是很强的，如果有循环，是一定可以追上来的

只是效率上。。。

我有一个想法，如果把遍历过程中所有的节点的地址都hash存起来，那么只要一旦有环，立刻就能发现，岂不是很好

作者: 福瑞哈哥 时间: 2007-05-21 16:28

原帖由 清汤挂面 于 2007-5-21 16:21 发表

呵呵，是很强的，如果有循环，是一定可以追上来的

只是效率上。。。

我有一个想法，如果把遍历过程中所有的节点的地址都hash存起来，那么只要一旦有环，立刻就能发现，岂不是很好

如果是在實際工程中遇到這樣的問題，我一定用hash，馬上就可以想到。
我在c中都是經常挂著glib或apr的庫的。

不過這些人都是搞算法的，又不實際干活。

作者: emacsnw 时间: 2007-05-21 16:45

原帖由 福瑞哈哥 于 2007-5-21 00:28 发表

如果是在實際工程中遇到這樣的問題，我一定用hash，馬上就可以想到。
我在c中都是經常挂著glib或apr的庫的。

不過這些人都是搞算法的，又不實際干活。

效率应该不是问题，慢的那个最多绕两圈 -_- ，因此时间复杂度还是O(N)的。
用hash的话需要O(N)的额外空间，时间上还是O(N)。

作者: win_hate 时间: 2007-05-21 18:58
很多朋友（这个帖子里以及以前相关的帖子里）倾向于这样的观点： Floyd 的双步长方法是多余的，纯粹是搞算法的人在自娱自乐，用 hash 或其它技术手段会得到更好的结果。

在这里我举一个非平凡的例子，说明在某些情形下，其它手段似乎都是无效的，只有 Floyd 方法可行。

例子：整数分解的 Pollard ``rho'' 方法。

思路：目的是找到大整数 N 的一个因子。先找一个函数 f，通常就是 f(x)= x^2 + a (mod N) , a 不为 0 和 -2. 从某个随意的值 x_0 开始迭代，得到一串整数

x_0, x_1, x_2, .......

这个序列是终归周期的，周期通常非常长，而且这个序列可以认为是近似随机的。若 N 存在某个小因子 d（相对），则模 d 的同余类比模 N 的同余类要少得多，所以对上面的序列中每个数取模，有可能找到某对 i,j 使得

x_i = x_j (mod d)
x_i != x_j (mod N)

则 gcd(x_i-x_j, N) 是 N 的非平凡因子。

x_i = x_j (mod d) 可以认为是在 mod d 的意义下，原来的序列出现了··环''，那么怎么找出这个环呢？我们并不知道 d 是多少，要是知道就不用算了。所以判断环的标准是 gcd(x_i-x_j, N) 得到一个 (1, N) 内的整数。

Floyd 方法能避免对每对 i,j 检查是否构成``环''，此时只需要比较 x_i 和 x_{2i}.

[ 本帖最后由 win_hate 于 2007-5-22 13:47 编辑 ]

作者: softsongs 时间: 2007-05-21 19:49
查找以前的帖子，至少有N中方法。

原帖由 mhello 于 2007-5-21 11:29 发表
各位大侠，有什么方法可以解决这个问题（先不考虑解决方法的效率问题）？

作者: 福瑞哈哥 时间: 2007-05-22 09:42

原帖由 emacsnw 于 2007-5-21 16:45 发表

效率应该不是问题，慢的那个最多绕两圈 -_- ，因此时间复杂度还是O(N)的。
用hash的话需要O(N)的额外空间，时间上还是O(N)。

沒錯啦，從算法上講是這樣的。
不過如果最先想到hash，那就先寫出來再說，不用過早考慮優化問題。
如果知識淵博，最先想到這個算法，那也很好。

作者: Edengundam 时间: 2007-05-22 10:01
崇拜下, win_hate的数学...^^

例子：整数分解的 Pollard ``rho'' 方法。 /* 没有读明白 */

=.=

作者: ArXoR 时间: 2007-05-22 10:21

原帖由 福瑞哈哥 于 5/21/07 16:28 发表

如果是在實際工程中遇到這樣的問題，我一定用hash，馬上就可以想到。
我在c中都是經常挂著glib或apr的庫的。

不過這些人都是搞算法的，又不實際干活。

hash每次操作不保证是O(1)的，即使是平均也不是O(1)，可以参考TAOCP

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)