线性表（顺序存储结构）

在之前的 数据结构与算法 的章节当中，我们介绍了什么是数据结构和时间复杂度的相关概念，那么在这一章，我们就正式的开始深入的了解它们，我们就从最基本的线性表和线性表当中的顺序存储结构开始

什么是线性表

线性表由零个或多个数据元素组成的有序序列，它有以下特点

• 它是一个序列，也就是说元素之间是先来后到的
• 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继
• 另外，线性表强调是有限的，事实上无论计算机发展到多大，它所处理的元素都是有限的

若将线性表记为 a1, a2 ... ai - 1, ai, ai + 1, ... an，则 ai - 1 领先于 ai，ai 领先于 ai + 1，称 ai - 1 是 ai 的直接前驱元素，ai + 1 是 ai 的直接后继元素，所以当线性表元素的个数 n（n >= 0） 定义为线性表的长度，当 n = 0 的时候，称为空表（允许有空表）

抽象数据类型

是指一组性质相同的值的集合及定义在此集合上的一些操作的总称，简单来说就是比如一些编程语言当中的整型，浮点型，字符型这些指的就是数据类型，例如在 C 语言当中，按照取值的不同，数据类型可以分为两类

• 原子类型，不可以再分解的基本类型，例如整型，浮点型，字符串型
• 结构类型，由若干个类型组合而成，是可以再分解的，例如整型数组是由若干整型数据组成的

什么是抽象

是指抽取出事物具有的普遍性的本质，它要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括，抽象是一种思考问题的方法，它隐藏了繁杂的细节

什么是抽象数据类型

我们对已有的数据类型进行抽象，就有了抽象数据类型（Abstract Data Type，简称 ADT），是指一个数学模型及定义在该模型上的一组操作（有点类似于编程语言当中的类），抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关

比如 1 + 1 = 2 这样一个操作，在不同 CPU 的处理上可能会不一样，但是由于其定义的数学特性相同，所以在计算机编程者看来，它们都是相同的，为了便于后续对于抽象数据类型的描述，所以采用以下格式进行描述

1
2
3
4
5
6

ADT 抽象数据类型名
Data
  数据元素之间逻辑关系的定义
Operation
  操作
endADT

比如我们来将线性表进行抽象描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ADT 线性表（List）
Data
  线性表的数据对象集合为 { a1, a2, ... an }
  每个元素的类型均为 DataType
  其中除去第一个元素 a1 以外，每一个元素有且只有一个直接前驱元素
  除了最后一个元素 an 以外，每一个素都有且只有一个直接后继元素
  数据元素之间的关系是一对一的关系
Operation
  InitList(*L)           初始化操作，建立一个空的线性表 L
  ListEmpty(L)           判断线性表是否为空，若线性表为空，返回 True，否则返回 False
  ClearList(*L)          将线性表清空
  GetElem(L, i, *e)      将线性表 L 中的第 i 个位置元素值返回给 e
  LocateElem(L, e)       在线性表 L 中查找与给定值 e 相等的元素，如果成功则返回序号，否则返回 0
  ListInsert(*L, i, e)   在线性表 L 中的第 i 个位置插入新元素 e
  ListDelete(*L, i, *e)  删除线性表 L 中的第 i 个位置元素，并用 e 返回其值
endADT

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中设计的关于线性表的更为复杂的操作，可以用以上基本操作的组合来进行实现

线性表的顺序存储结构

线性表有两种物理存储结构，顺序存储结构和链式存储结构，物理上的存储方式事实上就是在内存中找一个初始地址，然后通过占位的形式，把一定的内存空间给占用，然后把相同数据类型的数据元素依次放在这块空地中

顺序存储结构

顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素，也就是上面介绍过的 a1, a2 ... ai - 1, ai, ai + 1, ... an，顺序存储的结构代码如下

1
2
3
4
5
6
7

#define MAXSIZE 20
typedef int ElemType;

typedef struct {
  ElemType data[MAXSIZE]
  int length;  // 线性表当前长度
} SqList;

事实上就是对数组进行了封装，增加了一个当前长度的变量，稍微总结下，顺序存储结构封装需要三个属性

• 存储空间的起始位置，数组 data，它的存储位置就是线性表存储空间的存储位置
• 线性表的最大存储容量，数组的长度（MAXSIZE）
• 线性表的当前长度，length

这里有个需要注意的地方，即数组的长度与线性表的当前长度需要区分一下

• 数组的长度是存放线性表的存储空间的总长度，一般初始化后不变（虽然可以动态扩容，但是会影响性能）
• 而线性表的当前长度是线性中元素的个数，是会变化的

地址计算方法

假设 ElemType 占用的是 C 个存储单元（字节，比如 int 整型会占用四个字节），那么线性表中第 i + 1 个数据元素和第 i 个数据元素的存储位置关系为

1
2
3

// LOC 表示获得存储位置的函数
// 比如 ai 存放的是一个整型，地址在 0000 10 处，ai + 1 就存放在 0000 14 处（四个字节）
LOC(ai + 1) = LO(ai) + C

所以对于第 i 个数据元素 ai 的存储位置可以由 a1 推算得出

1

LOC(ai) = LOC(a1) + (i - 1) * c

可以配合下表进行理解

通过上面的公式，我们可以随时计算出线性表中任意位置的地址，不管它是第一个还是最后一个都是相同的时间，所以它的存储时间性能为 O(1)，我们通常将其称为随机存储结构，下面我们来看一下针对于线性表的顺序存储结构当中有哪些操作方法和与其相对应的时间复杂度

读取操作

获取线性表 List 中的第 i 个位置的元素值，只要 i 的数值在数组下标范围内，就把数组第 i - 1 下标的值返回即可，但是在 JavaScript 这种高级编程语言中，其实已经内置了很多对数组直接操作的函数，如 push、splice 等方法，但是在 C 语言这种底层语言中是没有的，所以在接下来的代码中，我们不会采用这些内置的操作函数，而是按照底层语言的实现思路和步骤，用高级语言来进行实现，下面就来看看如何使用 JavaScript 来进行实现

1
2
3
4
5
6
7
8
9
10
11
12

// 初始条件，线性表 list 已经存在并且 i <= index <= list.length
// 算法复杂度为 O(n)
function getItem(index) {
  if (index < 0 || index > list.length - 1) {
    throw new Error(`ERROR`)
  }
  for (let i = 0; i < list.length; i++) {
    if (k === index) {
      return list[k]
    }
  }
}

插入操作

线性表的顺序存储结构具有随机存储结构的特点，时间复杂度为 O(1)，在线性表 List 中的第 i 个位置插入新元素 e，实现思路如下

1. 如果插入位置不合理，抛出异常
2. 如果线性表长度大于等于数组长度 ，则抛出异常或动态增加容量
3. 从最后一个元素开始向前遍历到第 i 个位置，分别将他们都向后移动一个位置
4. 将要插入元素填入位置 i 处
5. 表长加 1

1
2
3
4
5
6
7
8
9
10
11
12

// 初始条件，链表 list 已经存在且 1 <= index <= list.length
// 功能，在 list 中第 index 个位置之前插入新的数据元素 data
function insertItem(data, index) {
  if (index < 0 || index >= list.length) {
    throw new Error(`ERROR`)
  } else {
    for (let i = list.length - 1; i > index - 1; i--) {
      list[i + 1] = list[i]
    }
    list[index] = data
  }
}

删除操作

删除算法的实现思路如下

1. 如果删除位置不合理，抛出异常
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置
4. 表长减 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 初始条件，链表 list 已经存在且 1 ≤ index ≤ list.length
function deleteItem(index) {
  if (list.length === 0) {
    throw new Error(`ERROR`)
  }
  if (index < 0 || index > list.length - 1) {
    throw new Error(`ERROR`)
  }
  if (index < list.length - 1) {
    for (let k = index; k < list.length - 1; k++) {
      list[k] = list[k + 1]
    }
  }
  list.length--
  // return list[index]
  return list
}

线性表顺序存储结构的优缺点

线性表的顺序存储结构，在存或者读取数据的时候，不管是在哪个位置，时间复杂度均为 O(1)，而在插入或者删除的时候，时间复杂度都是 O(n)，这就可以说明，它比较适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用，简单的总结如下

• 优点
  • 无需为表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任意位置的元素
• 缺点
  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大的时候，难以确定存储空间的容量
  • 容易造成存储空间的碎片（因为申请空间是一整块一整块来进行申请的）