关于php:PHP数据结构线性表顺序表链表别再傻傻分不清楚

听从所有教材以及各类数据结构相干的书书籍，咱们先从线性表开始入门。明天这篇文章更偏概念，是对于有线性表的一个知识点的汇总。

上文说过，物理构造是用于确定数据以何种形式存储的。其余的数据结构（树、图）、算法等根本都是建设在这样一个物理构造之上的，也能够说，物理构造就是数据结构的基本。在这里，咱们先介绍两个物理构造，也是咱们未来学习数据结构的基石，它们就是程序表和链表。

不扯简单的定义，不扯什么数学表达式，咱们最直观的了解，程序表就是数组。

是不是非常简单，没错，在 PHP 或者 C 的世界中，咱们就把程序表定义为数组，而雷同的名词还包含：顺序存储、程序构造等。只有看到这种名词，马上想到数组就能够了。当然，在 Java 中，咱们也能够将 List 这类的汇合当成是顺序存储构造。不过须要留神的是，Java 的 HashMap，在 PHP 中是以键值对模式定义的数组，它们是哈希表（Hash），从模式上来说，他们并不是程序的。在这里咱们肯定要记住，像数组下标递增这样程序构造的才是顺序存储构造。

程序表个别占用间断的内存空间。不仅逻辑上，连物理空间上都是相邻间断的。

链表个别在 C 中会定义为一个构造体，其中包含数据和指向下一个链表的指针，它不是程序的，尽管逻辑是有程序的（按指针指向），但在物理是能够离开的。也就是说，链表不必占用间断的内存空间，不须要在初始化的时候像数组一样给定长度。

在 PHP 中，咱们没有构造体这种语法模式，所以咱们间接应用类来示意链表构造。


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

这就是一个简略的链表构造，咱们能够把它叫做一个“结点”。data 中寄存咱们要保留的数据，能够是任意类型。而 next 则是咱们下一个链表结点。如果咱们须要简略的遍历链表，间接不停的调用 next 直到它为空即可。


while($n->next){
    $n = $n->next;
    echo $n->data, PHP_EOL;
}

上图就是对于链表的逻辑状态以及它的遍历方向。具体的链表操作相干函数咱们将在前面的文章中进行解说。

链表有很多种形式，下面咱们定义的是一个简略的单向链表。咱们还能够定义双向链表（加一个 prev 指向上一个结点），循环链表（最初一个 next 指回第一个结点）以及双向循环链表（最初一个 next 指回第一个结点，第一个的 prev 指向最初一个结点）。对于这些内容，咱们也会放到前面的文章中一一解说。

理解了程序表和链表之后，咱们最初就来说说线性表。

其实，程序表和链表这两种物理构造在默认状态下所实现的就是“程序表”这个逻辑数据结构。

程序表：由 n(n>0) 个数据个性雷同的元素形成的无限序列 （严蔚敏版）

留神几个关键点：

无限：数组长度、链表内存大小
序列：逻辑有序（数组是逻辑和物理都有序，链表是逻辑有序而物理无序）
数据个性雷同：PHP 中不显著，C 或 Java 中数组是固定类型的，而且也要给一个初始长度

为什么说线性表这么重要呢？咱们想想 MySQL 这样一行一行存储数据的关系型数据库，一张数据表不就是一个线性表吗？特地是咱们做 PHP 的程序员，天天都是在和数组（数据库读出来的数据个别都放到数据中）打交道（当然，咱们用哈希可能更多些），也就是说，咱们在做开发的时候，天天都在接触这个货色，你说它重要不重要。

而树和图这些数据结构却并不是线性表，在事实的归类中，它们是属于非线性表的领域的。线性表在个很大的特点是只有前后关系，不论是链表还是数组，它们都是遵循着这种前后关系的，然而在树和图中，除了前后之外，还有上下左右等更简单的关系。虽说它们的根本表现形式仍然是应用数组和链表，然而从严格的角度来说，或者从考试面试的角度来说，它们真的不属于线性构造，而应该划分到非线性构造中。

明天这篇文章是学习数据结构中根底的根底。当然，有条件的最好还是看看 C 用构造体是如何定义数组、链表的，PHP 在底层曾经帮咱们解决了太多问题，所以这些原始的语法结构咱们曾经用不到了。可能用 C 来学习数据结构是更加举荐的模式。

下一篇文章咱们将介绍的是程序表（数组）的线性表相干逻辑操作。

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

===========

各自媒体平台均可搜寻【硬核项目经理】

程序表

链表

线性表

总结