社区
C语言 帖子详情 如何判断链表是否存在循环 reinhardai 2005-10-11 10:25:41 我写了一个程序,思想是两个指针,一个指向第一个,一个指向第三个,判断它们是否相
等,如果等,就是循环,如果不等,第一前进一个,第二个前进两个,继续判断,直至相
等或者一个遇到null为止,感觉上好像有点问题
int is_circle(struct list *head)
{
if(head==null&&head->next==null) return 0;
list *p=head;
list *q=head->next;
if(q->next==null) return 0;
q=q->next;
while(p!=null&&q!=null)
{
if(p==q)
return 1;
else
{
p=p->next;
q=q->next;
if(q->next==null) return 0;
q=q->next;
}
}
return 0;
}
...全文
348 11 打赏 收藏 如何判断链表是否存在循环 我写了一个程序,思想是两个指针,一个指向第一个,一个指向第三个,判断它们是否相 等,如果等,就是循环,如果不等,第一前进一个,第二个前进两个,继续判断,直至相 等或者一个遇到null为止,感觉上好像有点问题 int is_circle(struct list *head) { if(head==null&&head->next==null) return 0; list *p=head; list *q=head->next; if(q->next==null) return 0; q=q->n 复制链接
扫一扫 分享 转发到动态 举报 AI 作业
写回复 配置赞助广告取 消
确 定
用AI写文章 11 条回复 切换为时间正序 请发表友善的回复… 发表回复 打赏红包 需支付: 0.00 元 取 消 确 定 iwdc 2005-10-18 打赏举报 回复 建议 Cnwanglin(林) 的程序里面开头部分
//判断节点的个数为0或者1个的时候,不可能存在循环
if(head==null&&head->next==null) return 0;
“&&”改成“||” skg55 2005-10-14 打赏举报 回复 给还不明白的兄弟点提示,如果有环,那就相当于一个操场,这时p在起点,而q在p前面2个单位,因为操场是圆的,所以也可以说q在p后面n个单位(n=操场周长-2),然后pq一起往前走,p每次走1个单位,q每次走2个单位,好了,这就变成了高中时候物理的追赶问题了,他们的距离差为n个单位,他们的速度差为2-1=1个单位,那么只要有足够的时间,哪怕操场(即这个环)再大也一定能追上,也就是说总有一个时刻p=q!
希望对兄弟们有帮助^_^ reinhardai 2005-10-11 打赏举报 回复 这个考虑了亚,p=head了,然后q=head->next,由于head->!=null,q=head->next->next,最后q=head了,判断了 pomelowu 2005-10-11 打赏举报 回复 你这样会漏掉很多可能的循环方式。
比如
head == 0x00000001;
head->next == head;
你的程序就无法检测到。
可以沿head往后,把所有next保存到一个数组中,然后没拿到一个next,就与这个数组的元素相比较 reinhardai 2005-10-11 打赏举报 回复 在k()的程序里面
else
{
p=p->next;
q=q->next;
}
q每次前进一个,这样不一定可以检测循环
我说话有的时候太简洁了
谢谢Cnwanglin(林) 的注释,呵呵 Cnwanglin 2005-10-11 打赏举报 回复 我加下注释,请问问题:“后面的前进一个不行”是什么意思
==================================================
/*
*功能:判断链表中是否存在节点
*名称:is_circle(struct list *)
*传入参数:struct list* 链表的首地址
*返回值:int (1)为0,链表中无循环
(2) 为1,链表中有循环
*/
int is_circle(struct list *head)
{
//判断节点的个数为0或者1个的时候,不可能存在循环
if(head==null&&head->next==null) return 0;
//定义指针p,q,分别指向head; head->next;
list *p=head;
list *q=head->next;
//判断节点的个数为2个的时候,如果不是循环,退出;
if(q->next==null) return 0;
q=q->next;
//循环判断
while(p!=null&&q!=null)
{
if(p==q)
//存在循环,退出
return 1;
else
{
p=p->next;
q=q->next;
//指针q的STEP为2,要加上这句判断;(q + 1)是否为链表的终点
if(q->next==null) return 0;
//(q + 2)
q=q->next;
}
}
return 0;
}
reinhardai 2005-10-11 打赏举报 回复 这个有问题,后面的前进一个不行 K 2005-10-11 打赏举报 回复 int is_circle(struct list *head)
{
if(head==null&&head->next==null) return 0;
list *p=head;
list *q=head->next;
if(q->next==null) return 0;
q=q->next;
while(p!=null&&q!=null)
{
if(p==q)
return 1;
else
{
p=p->next;
q=q->next;
}
}
return 0;
}
reinhardai 2005-10-11 打赏举报 回复 最前面的判断是防止出现q=null后还继续前进,即没有循环,而且就一个或者两个节点的情况,
使用时没有出现什么问题,就是感觉上有点不是太对,说不上来的感觉,呵呵
就是请大家看看有没有问题,如果有,讨论一下 pomelowu 2005-10-11 打赏举报 回复 我弄错了。那还有什么问题 Cnwanglin 2005-10-11 打赏举报 回复 判断的方法应该没错的, 如果STEP 不同,那么两个指针指向同一地址的时候,表明该链表内有循环。
具体出了什么问题了么?
==============================================
回复人: pomelowu(羽战士) ( ) 信誉:99 2005-10-11 11:20:00 得分: 0
提到的方法中:说的是当链表的节点个数小于3个的时候,这种情况: A <-> B 两个节点的循环,
但是在您的程序中:
list *p=head;
list *q=head->next;
if(q->next==null) return 0;
这里已经作了判断
所以,如果使用起来出现什么问题
麻烦您贴上来,关注;
==================================================
不对的地方还请多指点! 判断单链表中是否存在环 笔试时,常见的题型。判断单链表中是否存在环 用C++实现的循环链表 这是一个单循环链表,具备基本的操作,在普通链表的基础上,实现了定长循环链表的循环输入,判断链表是否有环等较为特殊的操作。增删改查自然也有。 带头结点和不带头结点的循环链表 这学期学数据结构,写了带头结点和不带头结点的循环链表,供其他在校学生参考学习,体会在链表中带头结点和不带头结点的差别 python单向循环链表原理与实现方法示例 本文实例讲述了python单向循环链表原理与实现方法。分享给大家供大家参考,具体如下:
单向循环链表
单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
操作
is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在
实现
# -*- cod
C语言
70,020
社区成员
243,267
社区内容
发帖 与我相关 我的任务 C语言 C语言相关问题讨论 复制链接
扫一扫 分享 确定 社区描述 C语言相关问题讨论 社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告 试试用AI创作助手写篇文章吧
+ 用AI写文章