- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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
您可能关注的文档
最近下载
- 废旧塑料购销合同6篇.docx VIP
- 山东省烟台市芝罘区2022-2023学年七年级(五四学制)上学期期中地理试题(含答案).docx VIP
- 建筑工程施工技术交底大全.docx
- 柔性光伏钢构及组件安装施工方案.docx VIP
- 中成药学讲稿祛暑中成药.docx VIP
- 石油化工企业设计防火规范(GB50160-2018-).doc
- 山东省烟台市芝罘区(五四制)2023-2024学年六年级上学期期中考试生物试题(解析版).docx VIP
- 医疗机构医院感染管理专职人员管理办法(2020年版).pdf
- 南宁师范大学信息技术课程与教学考研真题试题2019年.pdf
- 加强风电设备管理提升风机可利用率(电力系统及自动化范文).doc
文档评论(0)