王道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. 插入结点

插入结点的代码片段如下

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

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

6. 删除结点

代码片段如下

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

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

7. 求表长

时间复杂度O(n)

三、 双链表

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

1. 插入

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

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

2. 删除

p后删除q

1
2
3
p->next = q->next;
q->next->prior = p;
free(q);

四、循环链表

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

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

五、静态链表

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

六、顺序表和链表的比较

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

如何选取存储结构:

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

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

七、特殊矩阵的压缩储存

数组的定义

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

数组的存储结构

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

设二维数组Ah1×h2A_{h_1\times h_2}的行下标和列下标范围分别为[l1,h1][l2,h2][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. 三对称矩阵(带状矩阵)

三对角线上的元素ai,ja_{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)=()


王道408数据结构——第二章 线性表
https://buttering.github.io/EasyBlog/2021/09/25/王道408数据结构——第二章 线性表/
作者
Buttering
发布于
2021年9月25日
许可协议