数据结构学习笔记——线性表（上）

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

线性表的定义

线性表，从名字上可以感觉到，是具有像线一样的性质的表。

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

注意;

• 首先它是一个序列。也就是说，元素之间是有序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素有且只有一个前驱和后继。
• 线性表强调有限，元素个数是有限的。

其结构如下图：

线性表元素的个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。在非空表中的每个元素都有一个确定的位置，如a1是第一个元素，an是最后一个元素，ai是第i各元素，i称为数据元素ai在线性表中的位序。

在较复杂的线性表中，一个元素可以由若干个数据项组成。

线性表的顺序存储结构

1、顺序存储定义

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

这里强调两点：

1. 地址连续
2. 与线性表顺序一致

如图：

2、顺序存储方式

通俗地讲，线性表的顺序存储结构，就是在内存中找块地儿，通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地。

可以用一个一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置，接着把线性表相邻的元素存储在数组中相邻的位置。

我们发现描述存储结构三个重要的属性：

• 存储空间的起始位置；
• 线性表的最大存储容量；
• 线性表的当前长度。

3、数组长度与线性表长度区别

• 数组长度：定义数组时，已经开辟了固定大小的空间，一般不变；
• 线性表长度：线性表中数据元素的个数，随着插入和删除的操作，这个量是变化的。

所以：线性表长度≤数组长度

4、地址计算方法

线性表的第i各元素存储在数组下标为i-1的位置，如下图：

这个图也体现了数组长度和线性表长度的关系。用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组长度空间应该大于等于当前线性表的长度。

存储器中的每个存储单元都有自己的编号，这个编号叫做地址。

顺序结构的插入删除

1、获得元素操作

对于线性表的顺序存储结构来说，我们要实现getElem操作，即将线性表L中的第i个元素值返回，直接将数组第i-1下标的的值返回即可。

如果已知第一个元素的地址，和每个元素所占内存大小，即可算出第i个元素的内存地址，时间复杂度为O(1)。

2、插入操作

插入算法思路：

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

3、删除操作

删除算法思路：

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

4、操作整理

• 读取、存入数据： O(1)
• 插入、删除数据： O(n)

总的来说，线性表的顺序存储结构：读取快，增删慢。

5、优缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
• 可以快速地存取表中任意一个位置的元素；

缺点：

• 插入和删除操作需要移动大量的元素；（最大缺点）
• 当线性表长度变化较大时，难以确定存储空间的容量；
• 容易造成存储空间的“碎片”。