线性表

摘要:线性表(Linear list)是最基本、最简单、也是最常用的一种数据结构,使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线儿串起来,再存储到物理空间中”。

线性表

线性表(linear list)是数据结构的一种,一个线性表是 n 个具有相同特性的数据元素的有限序列。

  • 数据结构中,一组数据中的每个个体被称为 "数据元素",简称 "元素";
  • 线性表中元素之间的关系是 "一对一" 逻辑关系,即除了第一个和最后一个元素之外,其它元素都是首尾相接的;
  • 使用线性表存储数据的方式可以这样理解,即 "把所有数据用一根线儿串起来,再存储到物理空间中"。

如下图所示,这是一组具有 "一对一" 逻辑关系的数据,接下来我们采用线性表将其储存到物理空间中。

"一对一"逻辑关系的数据

首先,用 "一根线儿" 把它们按照顺序 "串" 起来,左侧是 "串" 起来的数据,右侧是空闲的物理空间。

数据的线性结构

把这 "一串儿" 数据放置到物理空间,我们可以选择以下两种方式,如下图所示。

两种线性存储结构

图 3a) 是多数人想到的存储方式,而图 3b) 却少有人想到。

我们知道,数据存储的成功与否,取决于是否能将数据完整地复原成它本来的样子。如果把图 3a) 和图 3b) 线的一头扯起,你会发现数据的位置依旧没有发生改变。因此可以认定,这两种存储方式都是正确的。

将具有 "一对一" 关系的数据 "线性" 地存储到物理空间中,这种存储结构就称为线性存储结构(简称线性表)。

虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

也就是说,线性表存储的数据,要么全部都是整形,要么全部都是字符串。一半是整形,另一半是字符串的一组数据无法使用线性表存储。

存储结构

从上图中我们可以看出,线性表存储数据可细分为以下 2 种:

  • 如图 3a) 所示,将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表);
  • 如图 3b) 所示,数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表)。

也就是说,线性表存储结构可细分为顺序存储结构和链式存储结构。在实际应用中,常以栈、队列、字符串等特殊形式使用。

前驱和后继

对于具有 "一对一" 逻辑关系的数据,我们一直在用 "某一元素的左侧(前边)或右侧(后边)" 这样不专业的词,其实线性表中有更准确的术语:

  • 某一元素的左侧相邻元素称为 "直接前驱" ,位于此元素左侧的所有元素都统称为 "前驱元素" ;
  • 某一元素的右侧相邻元素称为 "直接后继" ,位于此元素右侧的所有元素都统称为 "后继元素" 。

如下图中的元素 3,它的直接前驱是 2 ,此元素的前驱元素有 2 个,分别是 1 和 2;同理,此元素的直接后继是 4 ,后继元素也有 2 个,分别是 4 和 5。

织梦tag标签添加自定义seo标题、关键词、描述、缩略图

链表

链表,又称链式存储结构,用于存储逻辑关系为 "一对一" 的数据。

与顺序表不同,链表不限制数据的物理存储状态,换句话说,使用链表存储的数据元素,其物理存储位置是随机的。

例如,使用链表存储 {1,2,3},数据的物理存储状态如下图所示。

链表随机存储数据

我们看到,上图根本无法体现出各数据之间的逻辑关系。

对此,链表的解决方案是,每个数据元素在存储时都配备一个指针,用于指向自己的直接后继元素。

各数据元素配备指针

因此,链表是一种物理存储单元上非连续、非顺序的存储结构,由一系列结点(链表中每一个数据元素称为结点)组成,结点可以在运行时动态生成。

织梦tag标签添加自定义seo标题、关键词、描述、缩略图

结点的逻辑顺序是通过链表中的指针链接次序实现的,每个结点包括两个部分:

  • 存储数据元素(data)的数据域;
  • 存储下一个结点地址(next)的指针域。
  • 织梦tag标签添加自定义seo标题、关键词、描述、缩略图

相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而线性表和顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
  • 链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。
  • 注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点)。
    版权声明:本文为博主原创文章,未经博主允许不得转载。http://www.dedenotes.com/html/linear-list.html
    (1)
    打赏 微信扫一扫 微信 支付宝 QQ 扫码打赏

    HTTP消息结构 HTTP请求报文和响应报文的格式

    Dedenotes 赞(3)

    HTTP 协议(HyperText Transfer Protocol,超文本传输协议)是因特网上应用最为广泛的一种网络传输协议,基于 TCP/IP 通信协议来传递数据(HTML 文件, 图片文件, 查询结果等),所有的 WWW(World Wide Web)文件都必须遵守这个标准。

    防止表单重复提交的 4 种方法

    Dedenotes 赞(3)

    平时开发的项目中可能会出现下面这些情况:由于用户误操作,多次点击表单提交按钮;由于网速等原因造成页面卡顿,用户重复刷新提交页面;黑客或恶意用户使用 Postman 等工具重复恶意提交表单(攻击网站)。

    meta

    Dedenotes 赞(3)

    meta 是 html 语言 head 区的一个辅助性标签,位于文档的头部,不包含任何内容,标签的属性定义了与文档相关联的名称/值对。meta 标签可提供相关页面的元信息(meta-information),比如针对搜索引擎和更新频度的描述和关键词。