线性表

RenShiWei 2021/5/1

线性表是一个具有相同特性的数据元素的有限序列

# 特性

相同特性：所有元素属于同一数据类型。

有限：数据元素个数是有限的。

序列：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。

# 线性表的长度

线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。 n=0时，表示线性表是一个空表，即表中不包含任何元素。

# 线性表的逻辑表示

![image-20210602180407310](https://gitee.com/koala010/typora/raw/master/img/ 线性表的逻辑表示.png)

线性表的知识结构

# 重点

线性表两类存储结构的差异

每种存储结构中基本运算的实现算法

利用线性表求解实际问题

利用有序表特性设计高效算法

# 顺序存储结构

# 定义

把线性表中的所有元素按照顺序存储方法进行存储。

按逻辑顺序依次存储到存储器中一篇连续的存储空间中。

# 相关算法

已知长度为n的线性表A采用顺序存储结构。设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素

# 以下两种方法都不满足要求

如果每删除一个值为x的元素都进行移动，其时间复杂度为O(n2)，空间复杂度为O(1)。

如果借助一个新的顺序表，存放将A中所有不为x的元素，其时间复杂度为O(n)，空间复杂度为O(n)。

# 解法一

设删除A中所有值等于x元素后的顺序表为A1，显然A1包含在A中，为此A1重用A的空间

思路：扫描顺序表A，重建A只包含不等于x的元素。

# 解法二

用k记录顺序表A中等于x的元素个数，一边扫描A一边统计k值。

思路：将不为x的元素前移k个位置，最后修改A的长度

# 链式存储结构

# 特点

线性表中每个节点有唯一的前趋节点和前趋节点
设计链式存储结构时，每个逻辑节点存储单独存储，为了表示逻辑关系，增加指针域
- 每个物理节点增加一个指向后继节点的指针域  单链表
- 每个物理节点增加一个指向后继节点的指针域和一个指向前趋节点的指针域 双链表
单链表增加一个头节点的优点
- 第一个节点的操作和表中其他节点的操作相一致，无需进行特殊处理
- 无论链表是否为空，都有一个头节点，因此空表和非空表的处理也就统一了

# 存储密度

# 单链表

# 特点

当访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前趋节点

# 插入节点

插入操作：将值为x的新节点*s插入到*p节点之后

特点：只需修改相关节点的指针域，不需要移动节点

![image-20210602181130816](https://gitee.com/koala010/typora/raw/master/img/ 单链表插入节点.png)

# 删除节点

删除操作：删除*p节点之后的一个节点

特点：只需修改相关节点的指针域，不需要移动节点

# 头插法

从一个空表开始，创建一个头节点。依次读取字符数组a中的元素，生成新节点将新节点插入到当前链表的表头上，直到结束为止

# 尾插法

从一个空表开始，创建一个头节点。依次读取字符数组a中的元素，生成新节点将新节点插入到当前链表的表尾上，直到结束为止

# 双链表

在线性表的链式存储结构中，每个物理节点增加一个指向后继节点的指针域和一个指向前趋节点的指针域 双链表

# 优点

从任一节点出发可以快速找到其前趋节点和后继节点
从任一节点出发可以访问其他节点

# 插入节点

# 删除节点

# 循环链表

# 循环单链表

将表中尾节点的指针域改为指向表头节点，整个链表形成一个环。由此从表中任一节点出发均可找到链表中其他节点

Duktig

Choose mode

线性表

线性表

# 特性

# 线性表的长度

# 线性表的逻辑表示

# 重点

# 顺序存储结构

# 定义

# 相关算法

# 以下两种方法都不满足要求

# 解法一

# 解法二

# 链式存储结构

# 特点

# 存储密度

# 单链表

# 特点

# 插入节点

# 删除节点

# 头插法

# 尾插法

# 双链表

# 优点

# 插入节点

# 删除节点

# 循环链表

# 循环单链表

# 示意图

# 对比非循环单链表

# 循环双链表

# 定义

# 示意图

# 对比非循环双链表

# 有序表

# 结构