Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4495601
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-04-26 14:18:52

一、结点结构
        单链表的数据结构定义如下:
        typedef struct node
        {
            ElemType data;
            struct node *next;
        }list;
        其中,ElemType可以是任意数据类型如int、float或者char等,在算法中,规定其默认为int类型。

二、判断是否有环
        判断是否有环的原理是:利用两个指针,一个速度是另外一个的两倍,即慢指针每次移动一个节点,快指针每次移动两个节点,如果有环,则两指针会在某一个点相遇;如果无环,则快指针会先到达链表结尾。具体代码如下:
        bool hascircle(list *head)
        {
            if (NULL == head)
            {
                return false;
            }
            bool hascircle = false;
            list *slow=head, *fast=head;
            while (fast && fast->next)     // fast的下一个和下下一个结点不能为NULL,否则fast->next->next会异常
            {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast)         // 相遇了即fast追上slow了
                {
                    hascircle = true;
                    break;
                }
            }
            return hascircle;
        }

三、求环的起点

        求环的起点原理与求是否有环类似,但需要额外步骤:用两个步长分别为1和2的指针遍历链表,直到两者相遇,此时慢指针走过的长度就是环的长度,相遇后把其中一个指针(比如:步长为2的指针)重新设定为起始点,让两个指针都以步长1再走一遍链表,相遇点就是环的起始点。推理证明步骤如下:
        第一次相遇时:
                慢指针走过的路程:S1 = 非环部分长度 + 弧A长
                快指针走过的路程:S2 = 非环部分长度 + n*环长 + 弧A长
                由S1*2 = S2可以得出:非环部分长度 = n*环长 - 弧A长
        让指针A回到起始点后,走过一个非环部分长度,指针B走过了相等的长度,也就是n*环长,正好回到环的开头。
        如果不能理解这些的话,可以从纯数学的角度来看此问题,即非环部分长度 = n*环长 - 弧A长,那就行了,具体算法如下:
        
list *beginofcircle(list *head)
        {
            if (NULL == head)
            {
                return NULL;
            }
            list *slow=head, *fast=head;
            while (fast && fast->next)                    // 找相遇点,但fast的下一个和下下一个结点不能为NULL,否则fast->next->next会异常
            {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast)                         // 相遇了即fast追上slow了
                {
                    break;
                }
            }
            if ((NULL == fast) || (NULL == fast->next))    // 此时链表无环
            {
                return NULL;
            }
            fast = head;                                   // fast指针移到链表起始点,slow保持在相遇点
            while (slow != fast)                           // fast和slow都以步长1开始移动
            {
                slow = slow->next;
                fast = fast->next;
            }

            return fast;                                   // 再次相遇点即为环的起点
        }


阅读(2292) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

scq2099yt2013-04-26 14:19:10

文明上网,理性发言...