文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

php中链表的示例分析

2023-06-20 17:14

关注

这篇文章将为大家详细讲解有关php中链表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

链表的操作相对顺序表来说就复杂了许多。因为PHP确实已经为我们解决了很多数组操作上的问题,所以我们可以很方便的操作数组,也就不用为数组定义很多的逻辑操作。比如在C中,数组是有长度限制的,而在PHP中我们就不会考虑这个问题。

链式结构的定义

首先,在之前的关于线性表的第一篇文章中我们就说过链表的定义,在这里,我们再复习一下之前的那个关于链表的图来更清晰的理解链表的概念。

php中链表的示例分析

我们将图中的节点 Node 用类来表示:

class LinkedList{    public $data;    public $next;}

一个链表类就看可以看做是链表中的一个节点,它包含两个内容,data 表示数据,next 表示下一个节点的指针。就像链条一样一环套一环,这就是传说中的链表结构。

生成链表及初始化操作

function createLinkedList(){    $list = new LinkedList();    $list->data = null;    $list->next = null;    return $list;}function Init(array $data){    // 初始化    $list = createLinkedList();    $r = $list;    foreach ($data as $key => $value) {        $link = new LinkedList();        $link->data = $value;        $link->next = null;        $r->next = $link;        $r = $link;    }    return $list;}$link = Init(range(1, 10));print_r($link);// LinkedList Object// (//     [data] =>//     [next] => LinkedList Object//         (//             [data] => 1//             [next] => LinkedList Object//                 (//                     [data] => 2//                     [next] => LinkedList Object//                         (//                             [data] => 3//                             [next] => LinkedList Object//                                 (//                                     [data] => 4//                                     [next] => LinkedList Object//                                         (//                                             [data] => 5//                                             [next] => LinkedList Object//                                                 (//                                                     [data] => 6//                                                     [next] => LinkedList Object//                                                         (//                                                             [data] => 7//                                                             [next] => LinkedList Object//                                                                 (//                                                                     [data] => 8//                                                                     [next] => LinkedList Object//                                                                         (//                                                                             [data] => 9//                                                                             [next] => LinkedList Object//                                                                                 (//                                                                                     [data] => 10//                                                                                     [next] =>//                                                                                 )//                                                                         )//                                                                 )//                                                         )//                                                 )//                                         )//                                 )//                         )//                 )//         )// )

在使用链表的时候,我们一般会让第一个结点不包含任何数据,仅仅是做为一个空的结点来指向第一个有数据的结点。这种结点我们可以称之为头结点,如果需要判断链表是否为空的话,只需要判断第一个结点的 next 是否为空就可以了。在上面的代码中,创建链表 createLinkedList() 函数其实就是生成了这样一个头结点。

然后,我们通过 Init() 初始化函数来构造这个链表。构造过程还是比较简单的,这里我们是固定的传递进来一个数组,按照这个数组结构来构造这个链表,当然,在实际应用中,我们可以使用任何数据来构造链表。构造过程也并不复杂,将当前结点赋值给 r 变量,然后创建一个新结点,让 r->next 等于这个新创建的节点就可以了。构造好的链表直接打印出来的结构就是注释中的形式。

遍历链表

function IteratorLinkedList(LinkedList $link){    while (($link = $link->next) != null) {        echo $link->data, ',';    }    echo PHP_EOL;}

链表的遍历是不是非常像某些数据库的游标操作,或者像迭代器模式的操作一样。没错,其实游标和迭代器的结构就是链表的一种表现形式。我们不停的寻找 $next 直到没有下一个结点为止,这样就完成了一次链表的遍历。可以看出,这个过程的时间复杂度是 O(n) 。

插入、删除

function Insert(LinkedList &$list, int $i, $data){    $j = 0;    $item = $list;    // 遍历链表,找指定位置的前一个位置    while ($j < $i - 1) {        $item = $item->next;        $j++;    }    // 如果 item 不存在或者 $i > n+1 或者 $i < 0    if ($item == null || $j > $i - 1) {        return false;    }    // 创建一个新节点    $s = new LinkedList();    $s->data = $data;    // 新创建节点的下一个节点指向原 i-1 节点的下一跳节点,也就是当前的 i 节点    $s->next = $item->next;    // 将 i-1 节点的下一跳节点指向 s ,完成将 s 插入指定的 i 位置,并让原来的 i 位置元素变成 i+1 位置    $item->next = $s;    return true;}function Delete(LinkedList &$list, int $i){    $j = 0;    $item = $list;    // 遍历链表,找指定位置的前一个位置    while ($j < $i - 1) {        $item = $item->next;        $j++;    }    // 如果 item 不存在或者 $i > n+1 或者 $i < 0    if ($item == null || $j > $i - 1) {        return false;    }    // 使用一个临时节点保存当前节点信息,$item 是第 i-1 个节点,所以 $item->next 就是我们要找到的当前这个 i 节点    $temp = $item->next;    // 让当前节点,也就是目标节点的上一个节点, i-1 的这个节点的下一跳(原来的 i 位置的节点)变成原来 i 位置节点的下一跳 next 节点,让i位置的节点脱离链条    $item->next = $temp->next;    return true;}// 插入Insert($link, 5, 55);// 遍历链表IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,// 删除Delete($link, 7);// 遍历链表IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,

链表的插入和删除其实很类似,都是需要寻找到插入或删除位置的前一个元素,也就是第 i-1 这个位置的元素。然后通过对这个元素的 next 指针的操作来实现链表元素的插入删除操作。

它们在遍历和位置判断这两个功能中的代码其实都是一样的,不同的是创建时要新创建一个结点,然后让这个结点的 next 指向之前 i-1 位置元素的 next ,再将 i-1 位置元素的 next 指向新创建的这个结点。而删除操作则是保存要删除这个位置 i 的结点到一个临时变量中,然后将 i-1 位置元素的 next 指向删除位置 i 的 next 。

上面的解释需要结合代码一步一步来看,当然,我们也可以结合下面的这个图来学习。插入和删除操作是链表操作的核心,也是最复杂的部分,需要多多理解掌握。

php中链表的示例分析

根据位置查找、根据数据查找

function GetElem(LinkedList &$list, int $i){    $item = $list;    $j = 1; // 从第一个开始查找,0是头结点     while ($item && $j <= $i) {        $item = $item->next;        $j++;    }    if (!$item || $j > $i + 1) {        return false;    }    return $item->data;}function LocateElem(LinkedList &$list, $data){    $item = $list;    $j = 1; // 从第一个开始查找,0是头结点     while (($item = $item->next)!=null) {        if($item->data == $data){            return $j;        }        $j++;    }    return false;}// 获取指定位置的元素内容var_dump(GetElem($link, 5)); // int(55)// 获取指定元素所在的位置var_dump(LocateElem($link, 55)); // int(5)

链表的查找有两种形式,一种是给一个位置,比如要我要第五个位置的元素内容,那么就是根据指定位置查找元素的值,就像数组的下标一样。不过需要注意的是,链表的下标是从 1 开始的,因为 0 的位置是我们的头结点了。当然,我们也可以变换代码忽略掉头结点让它和数组保持一致,但这样的话,链表的特点就不明显了,所以这里的测试代码我们还是以 1 为起始。

另一种查找就是给定一个数据内容,查找它在链表的什么位置。其实这两种算法都是在遍历整个链表,本质上没有什么区别。由于链表不像数组一样有下标的能力,所以它的这些查找操作的时间复杂度都是 O(n) 。

关于“php中链表的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯