数据结构 线性表
本文主要内容：线性表的逻辑结构和存储结构以及相应算法；
1. 定义和特点
1. 定义：
由N（N>=0）个数据特性相同的元素构成的有限序列称为线性表。N为线性表长度，当N为0时就是空表。
| 编号 | 描述 |
|---|---|
| 1 | 存在唯一的被称为“第一个”的数据元素. |
| 2 | 存在唯一的被称为“最后一个”的数据元素. |
| 3 | 除第一个之外，结构中每一个元素都有一个前驱. |
| 4 | 除最后一个之外，结构中每一个元素都有一个后继. |
非空线性表或是线性结构，其的特点是：
| 编号 | 描述 |
|---|---|
| 1 | 存在唯一的被称为“第一个”的数据元素. |
| 2 | 存在唯一的被称为“最后一个”的数据元素. |
| 3 | 除第一个之外，结构中每一个元素都有一个前驱. |
| 4 | 除最后一个之外，结构中每一个元素都有一个后继. |
线性表的顺序表示和实现
线性表的顺序表：指的是用一组地址连续的存储单元依次存储线性表的数据元素。（这种表示又叫线性表的顺序存储结构或顺序映像）Sequential List
2. 特点**：
逻辑上相邻的元素，物理上也相邻 ；
公式：Loc（ai）=Loc(a0）+（i-1）x L
所以只要确定了一个元素的位置，表中任意元素都可以随机存取，因此线性表是一种随机存取的存储结构。
存取的时间复杂度为O(1).
缺点：插入和删除费时，需要移动大量的元素，长度固定。
3. 线性表的算法时间复杂度
| 名称 | 算法时间复杂度 |
|---|---|
| 查找算法 | 主要时间是在比较操作上，算法的时间复杂度为O（n）。 |
| 插入算法 | 主要时间是在移动元素上，算法的时间复杂度为O（n）。 |
| 删除算法 | 主要时间是在移动元素上，算法的时间复杂度为O（n）。 |
4. 线性表的链式表示和实现
线性表的链式存储结构的特点：
用一组任意的存储单元（可连续可不连续）存储线性表的数据元素，存储时需要额外的存储单元存储后继元素的信息。
每个存储的元素称为节点（Node），它由两部分组成：
- 数据域：存储数据元素信息的区域；
- 指针域：存储直接后继元素的位置；（称为：指针或链）
由n个节点链结成一个链表，即为链式的线性表。
根据链表所含的指针个数，指针指向，指针连接方式，将链表分为：
| 编号 | 链表名称 | 通常实现的数据结构 |
|---|---|---|
| 1 | 单链表 | 用于实现线性表的链式存储结构 |
| 2 | 循环链表 | 用于实现线性表的链式存储结构 |
| 3 | 双向链表 | 用于实现线性表的链式存储结构 |
| 4 | 二叉链表 | 是树的二叉链表实现方式 |
| 5 | 十字链表 | （Orthogonal List)是有向图的另一种链式存储结构 |
| 6 | 邻接链表 | 邻接表是图的一种最主要存储结构 |
| 7 | 邻接多重表 | 是 无向图的 另一种表示法， |
其中单链表、循环链表、双向链表用于实现线性表的链式存储结构，其他链表多用于实现树和图等非线性结构。
4.1 单链表
单链表的存取必须从头指针开始进行，头指针指示链表的第一个节点，最后一个元素的指针为空NULL。
特点：
- 元素之间的关系有指针域指示；
- 逻辑上相邻元素，物理上不一定相邻；
- 存储结构为非顺序印象，是链式映像；
一般为了处理方便，会在单链表的第一个节点之前设置一个头结点，该头结点的数据域可以不存储任何信息，也可以存储线性表的长度信息或其它附加信息，头结点的指针域存储指向第一个节点的指针。
示例：
指针头: H –>31，如果H指向null表示为空表；
| 存储地址 | 数据域 | 指针域 |
|---|---|---|
| 1 | Li | 43 |
| 7 | qian | 13 |
| 13 | zhang | 1 |
| 1chs | null | |
| 25 | liqoan | 37 |
| 31 | lsid | 7 |
| 37 | sds | 19 |
| 43 | werwe | 25 |
要取得第i个数据元素必须从头指针出发顺链进行寻找,所以单链表是顺序存取的存取结构。
查找算法：
- 按序号查找第i个元素，时间复杂度为O(n);
- 按值查找值为e的元素，时间复杂度为O(n);
插入算法：
将值为e的节点插入到第一个节点的位置上即ai-1和ai之间 - 找到ai-1节点，并有指针p指向该节点；
- 生成新节点s；
- 设置新节点s的数据域设置为e，指针域设置为ai；
- 设置ai-1的指针域指向新节点s；
时间复杂度为O（n），主要时间是查找ai-1
删除算法： 时间复杂度为O（n），主要时间在查找ai-1
单链表的创建：
链表从一个空表开始，动态的不断插入数据，形成链表；
此时的根据节点的插入位置不同分为：前插法和后插法；
- 前插法：通过将新节点逐个插入链表的头部（头节点之后），来创建链表；
- 后插法：为了使新节点能够插入到尾部，需要增加一个指针r指向链表的未节点，初始时r也指向头节点。
前插法创建链表：前插法创建一个N个元素的值的链表，时间复杂度为O(n);
后插法创建链表：时间复杂度为O(n)；
4.2 循环链表
另一种链式存储，特点是表中的最后一个节点的指针，指向头节点，整个链表的形式形成一个环。从表中任意节点出发都可以找到其他节点。
合并两个循环链表时，只需要表1的尾->表2的第一个节点（释放表2的头节点），表2的尾指针->表1的头节点。
4.3 双向链表
修改节点的结构，之前的节点只有后继指针，现在给节点添加上前驱指针
双向链表的节点结构：
| prior | data | next |
|---|---|---|
| 前驱指针 | 数据域 | 后继指针 |
双向链表也有循环链表叫双向循环链表
5.线性表的应用
两个线性表La和Lb: La长度为m,Lb 的长度为n；
- 合并两个线性表：
for(int i=0;i<Lb.length;i++){
GetElem(Lb,i,e);
if(LocateElem(La,e)){
ListInsert(La,++La_len,e);
}
}
假设GetElem和ListInsert与表长无关，LocateElem执行的时间与表长成正比，则时间复杂度为O（m*n）
- 有序表的合并：
public class MergeOrderedList {
String TAG = "MergeOrderedList";
//顺序存储结构的两个有序线性表
int[] LA = {3, 5, 8, 11, 23};
int[] LB = {1, 2, 5, 7, 11, 15, 20, 28};
int[] LC = new int[LA.length + LB.length];//new 空表
int len = LA.length > LB.length ? LB.length : LA.length;
public void megre() {
if (len <= 0) {
return;
}
int pa = 0, pb = 0;
int pa_last = LA.length - 1, pb_last = LB.length - 1;
int pc = 0;
while (pa <= pa_last && pb <= pb_last) {
//依次取LA和LB中小的值到LC表中，知道一中一个表到最后一个元素
if (LA[pa] < LB[pb]) {
LC[pc] = LA[pa];
pa++;
} else if (LA[pa] > LB[pb]) {
LC[pc] = LB[pb];
pb++;
}else{
LC[pc] = LA[pa];
pa++;
pb++;
}
pc++;
}
while (pa <= pa_last) {
LC[pc] = LA[pa];
pc++;
pa++;
}
while (pb <= pb_last) {
LC[pc] = LB[pb];
pc++;
pb++;
}
}
public void printLC() {
if (LC.length <= 0) {
return;
}
for (int i : LC) {
Log.e(TAG, "i>>>>" + i);
}
}
}
调用
MergeOrderedList m = new MergeOrderedList();
m.megre();
m.printLC();
结果
image.png
时间复杂度O(mn）；
需要开辟新的辅助空间，所以空间复杂度也为O（mn）；
- 链式有序表的合并
时间复杂度为O(m*n)；
空间复杂度为O（1）；
