数据结构详解——线性表

线性表

  线性表是最常用且是最简单的一种数据结构。形如：A1、A2、A3….An这样含有有限的数据序列，我们就称之为线性表。

一、线性表的定义

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

线性表、包括顺序表和链表

顺序表（其实就是数组）里面元素的地址是连续的，

链表里面节点的地址不是连续的，是通过指针连起来的。

二、线性表的抽象数据类型

  线性表的抽象数据类型定义如下：

三、线性表的顺序存储

1. 顺序存储定义

  顺序表，一般使用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中，数组大小有两种方式指定，一是静态分配，二是动态扩展。

  顺序表相关的操作跟数组有关，一般都是移动数组元素。

2. 顺序存储的实现方式

结构

  我们直接来看顺序表的模板类的代码：

顺序表的封装需要三个属性：

存储空间的起始位置。数组data的存储位置就是线性表存储空间的存储位置

线性表的最大存储容量。数组长度MAXSIZE

线性表的当前长度。length

注意：数组的长度与线性表的当前长度是不一样的。数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会改变的。

  下面我们将实现顺序表的各个功能：

有参数构造：

  创建一个长度为n的顺序表，需要将给定的数组元素作为线性表的数据元素传入顺序表中，并将传入的元素个数作为顺序表的长度

按位查找

  按位查找的时间复杂度为

O(1)

。

按值查找

  按值查找，需要对顺序表中的元素依次进行比较。

插入

  插入的过程中需要注意元素移动的方向，必须从最后一个元素开始移动，如果表满了，则引发上溢；如果插入位置不合理，则引发位置异常。

删除

  注意算法中元素移动方向，移动元素之前必须取出被删的元素，如果表为空则发生下溢，如果删除位置不合理，则引发删除位置异常。

遍历

  按下标依次输出各元素

  完整代码示例(更多数据结构完整示例可见GitHub)：

3. 顺序存储的优缺点

优点：

随机访问特性，查找O(1)时间，存储密度高；

逻辑上相邻的元素，物理上也相邻；

无须为表中元素之间的逻辑关系而增加额外的存储空间；

缺点：

插入和删除需移动大量元素；

当线性表长度变化较大时，难以确定存储空间的容量；

造成存储空间的“碎片”

四、线性表的链式存储

1. 链式存储定义

  线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些元素可以存在内存未被占用的任意位置。

  链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用，线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。

2. 链式存储的实现方式

存储方法

  结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

结构

  单链表的模板类的代码：

特点：

用一组任意的存储单元存储线性表的数据元素， 这组存储单元可以存在内存中未被占用的任意位置

顺序存储结构每个数据元素只需要存储一个位置就可以了，而链式存储结构中，除了要存储数据信息外，还要存储它的后继元素的存储地址

无参数构造

  生成只有头结点的空链表

头插法构造单链表

  头插法是每次将新申请的结点插在头结点后面

尾插法构造单链表

  尾插法就是每次将新申请的结点插在终端节点的后面

析构函数

  单链表类中的结点是用new申请的，在释放的时候无法自动释放，所以，析构函数要将单链表中的结点空间释放

计算长度

  单链表中不能直接求出长度，所以我们只能将单链表扫描一遍，所以时间复杂度为

O(n)

按位查找

  单链表中即使知道节点位置也不能直接访问，需要从头指针开始逐个节点向下搜索，平均时间性能为

O(n)

，单链表是顺序存取结构

按值查找

  单链表中按值查找与顺序表中的实现方法类似，对链表中的元素依次进行比较，平均时间性能为

O(n)

.

插入

  单链表在插入过程中需要注意分析在表头、表中间、表尾的三种情况，由于单链表带头结点，这三种情况的操作语句一致，不用特殊处理，时间复杂度为

O(n)

删除

  删除操作时需要注意表尾的特殊情况，此时虽然被删结点不存在，但其前驱结点却存在。因此仅当被删结点的前驱结点存在且不是终端节点时，才能确定被删节点存在，时间复杂度为

O(n)

.

遍历

  遍历单链表时间复杂度为

O(n)

.

  完整代码示例(更多数据结构完整示例可见GitHub)：

链式存储的优缺点

优点：

插入、删除不需移动其他元素，只需改变指针.

链表各个节点在内存中空间不要求连续，空间利用率高

缺点：

查找需要遍历操作，比较麻烦

五、其他线性表

循环链表

  循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。（通常为了使空表和非空表的处理一致，通常也附加一个头结点）

  在很多实际问题中，一般都使用尾指针来指示循环链表，因为使用尾指针查找开始结点和终端结点都很方便。

  循环链表没有增加任何存储量，仅对链接方式稍作改变，循环链表仅在循环条件与单链表不同。从循环链表的任一结点出发可扫描到其他结点，增加了灵活性。但是，由于循环链表没有明显的尾端，所以链表操作有进入死循环的危险。通常以判断指针是否等于某一指定指针来判定是否扫描了整个循环链表。

双链表

  循环链表虽然可以从任意结点出发扫描其他结点，但是如果要查找其前驱结点，则需遍历整个循环链表。为了快速确定任意结点的前驱结点，可以再每个节点中再设置一个指向前驱结点的指针域，这样就形成了双链表。

存储方法

  结点p的地址既存储在其前驱结点的后继指针域内，又存储在它后继结点的前驱指针域中

需要注意：

循环双链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同。

插入操作需要修改4个指针，并且要注意修改的相对顺序。

静态链表

  静态链表是用数组来表示单链表，用数组元素的下标来模拟单链表的指针。

静态链表的存储结构：

静态链表存储示意图：

静态链表插入操作示意图：

静态链表删除操作示意图：

  静态链表虽然是用数组来存储线性表的元素，但在插入和删除操作时，只需要修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点，但是它并没有解决连续存储分配带来的表长难以确定的问题。

间接寻址

  间接寻址是将数组和指针结合起来的一种方法，它将数组中存储的单元改为存储指向该元素的指针。

  该算法的时间复杂度仍为

O(n)

，但当每个元素占用较大空间时，比顺序表的插入快的多。线性表的间接寻址保持了顺序表随机存取的优点，同时改进了插入和删除操作的时间性能，但是它也没有解决连续存储分配带来的表长难以确定的问题。

  具体代码实现均可在GitHub中找到。如有错误，请在评论区指正。

参考

数据结构（C++版）王红梅等编著