王道408数据结构——第二章 线性表

一、线性表的定义和基本操作

线性表

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，n=0是为一个空表。除第一个元素外，每一个元素有且仅有一个直接前驱，除最后一个元素外，每一个元素有且仅有一个直接后驱。

顺序表

线性表的顺序存储称为顺序表，是用一组地址连续的存储单元一次存储线性表中的数据结构，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
线性表的位序是从1开始的，而数组元素的下标从0开始。

1.插入操作

最好情况：表尾插入，时间复杂度O(1)
最坏情况：表头插入，时间复杂度O(n)
平均情况：n/2
平均时间复杂度：O(n)

2.删除操作

最好情况：删除表尾元素，时间复杂度O(1)
最坏情况：删除表头元素，时间复杂度O(n)
平均情况：(n-1)/2
平均时间复杂度：O(n)

顺序表插入和删除的时间主要耗费在移动元素上，而移动元素的个数取决于插入删除元素的位置。

3.按值查找（顺序查找）

最好情况：查找的元素在表头，时间复杂度O(1)
最坏情况：查找的元素在表尾或不存在，时间复杂度O(n)
平均情况：(n+1)/2
平均时间复杂度：O(n)

二、单链表

线性表的链式存储又称单链表，指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表结点，除存放元素自身信息外，还需要存放一个指向其后继节点的指针。
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，存在浪费空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构。

如果要访问某个结点的前去前驱结点，只能从头开始遍历。

头节点：在单链表的第一个结点前附加一个结点。头结点可以不设任何信息，也可以记录表长等信息。引入头结点可以带来两个优点：

1. 链表的第一个位置的操作可以和其他位置相统一。
2. 无论链表是否为空，其头指针都指向头结点，因此空表和非空表的操作得到统一。

1. 头插法

将新结点插入当前链表的表头，即头结点之后。
读入数据的顺序和生成链表中的元素顺序是相反的，总时间复杂度为O(n)

2. 尾插法

增加一个尾指针，使其始终指向当前链表的尾结点。可使导入数据和链表元素的顺序一致，总时间复杂度为O(n)。

3. 按序号查找

时间复杂度O(n)

4. 按值查找

时间复杂度O(n)

5. 插入结点

插入结点的代码片段如下

p = getElem(L, i-1);  // 移动到插入位置前一个结点
s->next = p->next;
p->next = s;

算法时间开销主要在于查找第i-1个元素，时间复杂度为O(n)；如果在给定结点后插入，时间复杂度仅为O(1)。

6. 删除结点

代码片段如下

p = getElem(L, i-1);
q = p->next;
p->next = q->next;
free(q);
// 第二、三步顺序不能颠倒

该算法的时间复杂度也耗费找查找操作上，时间复杂度为O(n)。

7. 求表长

时间复杂度O(n)

三、 双链表

双链表结点有两个指针，分别指向其前驱结点和后继结点。

1. 插入

在p所指结点之后插入*s

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
/// 第一、二步必须在第四步之前

2. 删除

在p后删除q

p->next = q->next;
q->next->prior = p;
free(q);

四、循环链表

将单链表最后一个结点的指针改为指向头结点，形成循环单链表。判空条件是头结点的指针是否指向自身。

循环单链表可以从表中任意一个结点开始遍历整个链表。
有时单链表常用操作是在表头和表尾进行的，此时不设头指针而仅设尾指针。

五、静态链表

借助数组来描述线性表的链式结构，结点也有数据域和指针域。与链表的指针不同，静态链表的指针是结点的相对地址（数组下标），又称游标。
静态链表需要预先分配一块连续的内存空间。

六、顺序表和链表的比较

——————	顺序表	链表
存取（读写）方式	既可以顺序存取，也可以随机存取	只能从表头顺序存取元素
逻辑结构与物理结构	逻辑上相邻的元素，对应的物理存储位置也相邻	逻辑上相邻的元素，物理存储位置不一定相邻，其对应的逻辑关系通过指针链接来表示
按值查找	顺序表有序时，可采用折半查找，时间复杂度为$O(log_2n)$，若无序，时间复杂度为O(n)	时间复杂度为O(n)
按序号查找	顺序表支持随机访问，时间复杂度仅为O(1)	时间复杂度为O(n)
插入、删除	平均需要移动半个表长的元素	只需修改相关结点的指针域
空间分配	在静态存储分配情形，一旦存储空间装满就不能扩充，加入新元素会导致内存溢出，因此需要预先分配足够大的空间。但预先分配过大，会导致后部空间大量闲置；动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，若内存没有更大块的连续存储空间，则会导致分配失败。	链式存储的结点空间只需在需要是申请，只要内存有空间就可以分配，操作灵活、高效。

如何选取存储结构：

• 基于存储考虑：难以估计线性表的长度或存储规模时，不宜采用顺序表；链表实现不用估计存储规模，但链表的存储密度较低。
• 基于运算考虑：如经常做的运算时按序号访问元素，则顺序表优于链表；如经常进行插入、删除操作，链表较优。
• 基于环境考虑：任何高级语言都有数组类型，顺序表较容易实现；链表的操作是基于指针的。

通常，较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（动态性强）宜选择链式存储。

七、特殊矩阵的压缩储存

数组的定义

数组是由n（n $\ge$ 1）个相同类型的数据元素构成的有序序列。
每个元素在线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
数组是线性表的推广：一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表。
数组一旦被定义。其维数和维界就不再改变，因此除初始化和销毁外，数组只有存取元素和修改元素的操作。

数组的存储结构

对于多维数组，有按行优先和按列优先两种映射方法。

设二维数组$A_{h_1\times h_2}$的行下标和列下标范围分别为$[l_1,h_1]，[l_2, h_2]$。
其按行优先存储时，$$LOC(a_{i,j})=LOC(a_{l_1,l_2})+[(i-l_1)\times (h_2-l_2+ 1)+(j-l_2)]\times L$$其按列优先存储时,$$LOC(a_{i,j})=LOC(a_{l_1,l_2})+[(j-l_2)\times (h_1-l_1+1)+(i-l_1)]\times L$$

矩阵的压缩存储

为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是节省空间。

1. 对称矩阵

将对称矩阵A[1…n][1…n]存放在一维数组B[n(n+1/2)]中，只存放下三角部分的元素。

2. 三角矩阵

下三角矩阵中，上三角区的所有元素均为同一常量，其储存思想与对称矩阵类似，不同之处在于储存完下三角区和主对角线上的元素后，在储存上三角取的常量一次。

943 2019年选择第9题默认矩阵下标从0开始

3. 三对称矩阵（带状矩阵）

三对角线上的元素$a_{i,j}$在一维数组中的下标为k=2+3(i-1)+(j-i+1)-1=2i+j-1（数组和元素下标均从0开始）。

4. 稀疏矩阵

矩阵中非零元素个数远小于矩阵元素的矩阵。
通常将非零元素及其相应的行和列构成一个三元组，然后按照一定规则储存这些三元组。
稀疏矩阵压缩存储后便失去了随机存储的特性。

八、广义表

c++中union关键字详见

广义表的定义

广义表的操作

getHead()：获得广义表的第一个元素；
getTail()：获得以广义表出第一个元素外的其余元素构成的广义表。

如：A=(a), B=(b,c,d)，C=(()),那么
getHead(A)=a, getHead(B)=b, getHead(C)=()
getTail(B)=(), getTail(B)=(c,d), getTail(C)=()