判断一个单链表是否有环及环的链接点.doc

判断一个单链表是否有环及环的链接点.doc

  1. 1、本文档共22页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
给定一个单链表,只给出头指针h: 1、如何判断是否存在环? 2、如何知道环的长度? 3、如何找出环的连接点在哪里? 4、带环链表的长度是多少? 解法: 1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。 2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。 3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。(证明在后面附注) 4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度 void Isloop(Llink head) { if(!head||!head-next) return; Llink p,q; bool loop=false; p=q=head-next; while(qq-next)//判断是否有环 { p=p-next; q=q-next-next; if(p==q) { loop=true; break; } } if(!loop) coutThis link has not loop\n; else { coutThis link has a loop\n; Llink r=p; q=head-next; int nonloop=1,loopcount=1; //nonloop计算非环结点数,loopcount计算环上结点数 do//计算环上的结点数 { p=p-next; ++loopcount; }while(p!=r); --loopcount; while(p!=q)//得到环的入口结点,同时计算得到非环的结点数 { p=p-next; q=q-next; ++nonloop; } --nonloop; cout\nStart of loop: p-dataendl; cout\nCount of nonloop: nonloop \nCount of loop: loopcount \nCount of Linknode: nonloop+loopcountendl; } } 判断是否存在环的程序: bool IsExitsLoop(slist *head) { slist *slow = head, *fast = head; while ( fast fast-next ) { slow = slow-next; fast = fast-next-next; if ( slow == fast ) break; } return !(fast == NULL || fast-next == NULL); } 寻找环连接点(入口点)的程序: slist* FindLoopPort(slist *head) { slist *slow = head, *fast = head; while ( fast fast-next ) { slow = slow-next; fast = fast-next-next; if ( slow == fast ) break; } if (fast == NULL || fast-next == NULL) return NULL; slow = head; while (slow != fast) { slow = slow-next; fast = fast-next; } return slow; } 亦可以用类似与hash表的方法,即设立一个数组,将链表结点中的值做数组下标,当赋值冲突时就是环的接入点 bool isloop(Llink p) { if(!p||!p-next) return true; int a[MAXSIZE],n=0; memset(a,0,sizeof(int)*MAXSIZE); p=p-next; while(p) { if

文档评论(0)

dsdmlwz1v9 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档