数据结构之单向环形链表

in 网站建设
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

介绍

和单向链表的唯一区别就是,在链表最后的节点指向了链表的头节点.

微信图片_20191219150059.png

案例:

单向环形链表经典的案例就是约瑟夫环的问题,引申出来类似猴子选大王,丢手帕等都是约瑟夫的实际场景.
假设有编号为1,2,3...n的人围成一圈,约定编号为k(1 <= k <= n)的人开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人在出列,以此类推,直到所有人出列完毕,由此产生出一个出队的编号序列.
class Node
{
    public $no;
    public $next;

    public function __construct($no)
    {
        $this->no = $no;
    }
}
class CircleLinkedList
{
    public $first;
}
public function addNode($total)
{
    $cur = null;
    //循环插入$total个节点
    for ($i = 1; $i <= $total; $i++) {
        $boy = new Node($i);
        if ($i == 1) {
        //如果是第一个节点,则将$first指向它.
            $this->first = $boy;
            $cur = $boy;
        } else {
        //新的人的next域指向第一人,形成一个环状.
            $boy->next = $this->first;
            //将$cur后移之下新的人
            $cur->next = $boy;
            $cur = $boy;
        }
    }
}
  1. 新建两个变量$temp和$helper,现将$temp指向$first,$helper指向链表的最后一个人.
  2. 将$temp和$helper都移动k-1位,找到开始报数的那个人.
  3. 当$temp开始报数时,$temp和$helper同时移动$num位.
  4. 最后将$helper的next域指向$temp的next,$temp向后移动一位,即完成出列.
  5. 循环第二步,直到$temp == $helper说明链表只剩下一个人,出列完毕.
public function leaveCircle($k, $num)
{
    //现将$temp指向$first
    $temp = $this->first;
    //然后通过遍历将$temp指向链表的最后一个人.
    while (true) {
        if ($temp->next == $this->first) {
            break;
        }
        $temp = $temp->next;
    }
    //$temp和$helper移动k-1位找到开始报数的那个人
    for ($i = 0; $i < $k - 1; $i++) {
        $this->first = $this->first->next;
        $temp = $temp->next;
    }
    //循环遍历出列
    while (true) {
        //如果$first == $temp说明链表只剩下一个节点,退出循环
        if ($this->first == $temp) {
            break;
        }
        //开始报数,$temp和$helper开始移动
        for ($i = 0; $i < $num - 1; $i++) {
            $this->first = $this->first->next;
            $temp = $temp->next;
        }
        //$this->frist指向报数结束后的那个人
        echo "\n" . "编号为" . $this->first->no . "的人出圈";
        //将当前指针$frist移动到下一个,然后让$temp的next指向$first,完成出圈
        $this->first = $this->first->next;
        $temp->next = $this->first;

    }
    echo "\n" . "最后一个人的编号为:" . $this->first->no;
}
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看