2. 线性结构-线性表

2.1 线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

• 它是一个序列。即元素之间是由顺序的，若元素有多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
• 线性表强调是有限的，元素个数当然是有限的。

数学语言定义：

• 所以线性表元素的个数n(n >= 0)定义为线性表的长度，当n=0时，称为空表。
• 在非空表中的每个数据元素都有一个确定的位置，如a_i是第i个数据元素，称i为数据元素a_i在线性表中的位序。

2.2 线性表的抽象数据类型

2.2 线性表的顺序存储结构

2.2.1顺序存储定义

线性表的物理结构之顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储示意

2.2.2 顺序存储方式

说白了，就是在内存找了块地儿，通过占位的形式，把一定内存空间给占了，然后把形同数据类型的数据元素依次存放在这块空地中。

顺序存储结构三个属性：（1）存储空间起始位置；（2）线性表的最大存储容量；（3）线性表的当前长度。

2.2.3 数据长度和线性表长度区别

数组长度一般是固定的，动态分配数组就不说了，而线性表长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

3. 顺序存储结构的插入与删除

1. 获得元素操作
   对于线性表的顺序存储结构来说，如果要实现GetElem操作。即将线性表中的第 i 个位置元素值返回，代码：
   
   
2. 插入操作
   如果要实现ListInsert（*L, i, e），即在线性表L中的第 i 个位置插入新元素e，如何操作？
   

插入算法的思路：

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

实现代码：

3. 删除操作
   
   删除算法的思路：

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

实现代码：

插入和删除的时间复杂度：
——最好的情况：如果元素要插入到最后一个位置，或者要删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素，不会影响到前面的任何人。

——最坏的情况：如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度为O(n)，因为要移动所有的元素向后或向前，

——平均情况，由于元素插入到第 i 个位置，或删除第 i 个元素，需要移动 n-i 个元素， 根据概率原理，每个位置插入或删除元素的可能性是相同的，位置靠前移动元素多，位置靠后移动元素少。 最终平均移动次数和最中间的那个元素移动次数相等，为 n-1/2 。所以平均时间复杂度为 O(n)。

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

2.3 线性表的链式存储结构

2.3.1 顺序存储结构不足的解决办法

顺序存储结构最大的缺点就是插入和删除需要**移动大量元素**，这显然很耗费时间。怎么解决呢？

分析原因：因为相邻的两个元素之间在内存中的位置也是挨着的，中间没有空隙，当然也就没办法快速介入。删除后，当中就会留出空隙，自然需要弥补。

问题： 如何增加空位有效解决插入和删除需要移动元素、并且对空间复杂度不会有太大影响？

2.3.2 线性表链式存储结构定义

线性表的另一种物理结构——链式存储结构的特点就是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不是连续的。

以前在顺序结构中，每个数据元素只需要存储数据元素信息就可以了。
现在链式结构中，每个数据元素要存储元素信息和它的后继元素的存储地址。

元素的结点（存储映像） = 数据域 + 指针域
数据域：存储数据元素信息；
指针域 ：存储指针或链。
n 个结点结成一个链表， 因为上图链表的每个结点中只包含一个指针域，所以叫单链表。

线性表必须有头有尾，我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行。之后每一个结点，其实就是上一个的后继指针指向的位置。线性链表的最后一个结点指针为“空”（通常用NULL或“ ^ ”符号表示）。

为了方便：我们会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息。也可以存储如线性表的长度等附加信息。

2.3.3 头指针和头结点的异同

2.3.4 线性表链式存储结构代码描述

若 线性表为空表，则头结点的指针域为“ 空 ”，如图所示。
改用更方便的存储示意图来表示单链表：
带有头结点的单链表：

空链表：