【线性表】（List）
程序员文章站
2024-01-19 09:58:10
...
本文围绕以下三个部分展开：
一、线性表（List）
二、顺序存储结构
三、链式存储结构
一、线性表（List）
1. 概念
线性表：0个或多个数据元素的有限序列。（像线一样性质的表）
线性表的每个数据元素的类型都是相同的。
A. 是一个序列。（元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。）
B. 元素个数是有限的。
类比：幼儿园小朋友按次序排队。
2. 线性表的抽象数据类型
（1）基本操作：
抽象数据类型定义如下：
（2）复杂的个性化操作
例题：union操作（实现两个线性表集合A和B的并集操作）
思想：把存在在集合B中但不存在在A中的数据元素插入到A中即可。即：循环集合B中的每个元素，判断当前元素是否存在A中。若不存在，则插入到A中即可。
二、顺序存储结构
1. 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。
2. 顺序存储方式
在内存中找了块地儿，通过占位符的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。
使用一维数组来实现顺序存储结构。即：把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
3. 顺序存储结构代码和三个属性
4. 地址计算方法
存储器中每个存储单元都有自己的编号，称为地址。
（1）数据元素的序号和存放它的数组下标之间的对应关系：
（2）假设一个数据元素占c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系：
第i个数据元素的存储位置和第1个数据元素的存储位置的关系：
（3）随机存取结构：可以随时算出线性表中任意位置的地址，存取时间复杂度均为O(1)，具有这样特点的存取结构称为随机存取结构。
5. 获得元素的操作（GetElem）：将线性表L中第i个位置元素值返回。
6. 插入某个数据元素
7. 删除某个数据元素
8. 优缺点
三、链式存储结构
1. 特点：
用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续，也可以不连续。意味着，这些数据元素可以存放在内存中未被占用的任意位置。
2. 数据域、指针域、指针/链、结点
3. 头结点、头指针
（1）头指针：链表中第一个结点的存储位置。
链表最后一个结点的指针为空（NULL/"^"）
（2）头结点：为了更方便地对链表进行操作，在单链表的第一个结点前附设的一个结点。
数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。
指针域存储指向第一个结点的指针。
（3）二者的异同
4. 分类
链式存储结构又有不同形式，分为：单链表、静态链表、循环链表和双向链表。
整理时重点参考：《大话数据结构》程杰著
一、线性表（List）
二、顺序存储结构
三、链式存储结构
一、线性表（List）
1. 概念
线性表：0个或多个数据元素的有限序列。（像线一样性质的表）
线性表的每个数据元素的类型都是相同的。
A. 是一个序列。（元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。）
B. 元素个数是有限的。
类比：幼儿园小朋友按次序排队。
2. 线性表的抽象数据类型
（1）基本操作：
抽象数据类型定义如下：
（2）复杂的个性化操作
例题：union操作（实现两个线性表集合A和B的并集操作）
思想：把存在在集合B中但不存在在A中的数据元素插入到A中即可。即：循环集合B中的每个元素，判断当前元素是否存在A中。若不存在，则插入到A中即可。
二、顺序存储结构
1. 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。
2. 顺序存储方式
在内存中找了块地儿，通过占位符的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。
使用一维数组来实现顺序存储结构。即：把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
3. 顺序存储结构代码和三个属性
4. 地址计算方法
存储器中每个存储单元都有自己的编号，称为地址。
（1）数据元素的序号和存放它的数组下标之间的对应关系：
（2）假设一个数据元素占c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系：
第i个数据元素的存储位置和第1个数据元素的存储位置的关系：
（3）随机存取结构：可以随时算出线性表中任意位置的地址，存取时间复杂度均为O(1)，具有这样特点的存取结构称为随机存取结构。
5. 获得元素的操作（GetElem）：将线性表L中第i个位置元素值返回。
6. 插入某个数据元素
7. 删除某个数据元素
8. 优缺点
三、链式存储结构
1. 特点：
用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续，也可以不连续。意味着，这些数据元素可以存放在内存中未被占用的任意位置。
2. 数据域、指针域、指针/链、结点
3. 头结点、头指针
（1）头指针：链表中第一个结点的存储位置。
链表最后一个结点的指针为空（NULL/"^"）
（2）头结点：为了更方便地对链表进行操作，在单链表的第一个结点前附设的一个结点。
数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。
指针域存储指向第一个结点的指针。
（3）二者的异同
4. 分类
链式存储结构又有不同形式，分为：单链表、静态链表、循环链表和双向链表。
整理时重点参考：《大话数据结构》程杰著