<返回更多

「PHP数据结构」线性表?顺序表?链表?别再傻傻分不清楚

2021-07-19    硬核项目经理
加入收藏

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

上文说过,物理结构是用于确定数据以何种方式存储的。其他的数据结构(树、图)、算法等基本都是建立在这样一个物理结构之上的,也可以说,物理结构就是数据结构的根本。在这里,我们先介绍两个物理结构,也是我们将来学习数据结构的基石,它们就是顺序表和链表。

顺序表

不扯复杂的定义,不扯什么数学表达式,我们最直观的理解,顺序表就是数组。

是不是非常简单,没错,在 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;
}

「PHP数据结构」线性表?顺序表?链表?别再傻傻分不清楚

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

链表有很多种形式,上面我们定义的是一个简单的单向链表。我们还可以定义双向链表(加一个 prev 指向上一个结点),循环链表(最后一个next指回第一个结点)以及双向循环链表(最后一个next指回第一个结点,第一个的 prev 指向最后一个结点)。关于这些内容,我们也会放到后面的文章中一一讲解。

线性表

了解了顺序表和链表之后,我们最后就来说说线性表。

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

顺序表:由n(n>0)个数据特性相同的元素构成的有限序列(严蔚敏版)

注意几个关键点:

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

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

总结

今天这篇文章是学习数据结构中基础的基础。当然,有条件的最好还是看看 C 用结构体是如何定义数组、链表的,PHP 在底层已经帮我们解决了太多问题,所以这些原始的语法结构我们已经用不到了。能够用 C 来学习数据结构是更加推荐的形式。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>