软考数据结构 -- （时间复杂度，线性结构，线性表，栈，队列，串，数组，矩阵，树，图）

文章目录

一、时间复杂度
二、线性结构
- 2.1 线性表
- 2.2线性表存储结构
- 2.3栈
- 2.4队列
- 2.5串
- 2.6数组
- 2.7矩阵
- 2.8树
- 2.9二叉树的存储结构
- 2.10二叉树遍历
- 2.11图

一、时间复杂度

算法时间复杂度以算法中基本操作重复执行的次数(简称为频度)作为算法的时间度量。一般不必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级即可。
计算规则

加法规则:多项相加，保留最高阶项，并将系数化为1

乘法规则:多项相乘都保留，并将系数化为1

加法乘法混合规则:小括号再乘法规则最后加法规则

渐进符号
递归的事件复杂度，空间复杂度
(1)展开式
事件复杂度=递归次数 x 每次递归的时间复杂度
(2)主观法

二、线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”

2.1 线性表

线性表是最简单、最基本也是最常用的一种线性结构。常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

一个线性表是 n(n≥0)个元素的有限序列

非空线性表的特点
(1)存在唯一的一个称作“第一个”的元素。
(2)存在唯一的一个称作“最后一个”的元素。
(3)除第一个元素外，序列中的每个元素均只有一个直接前驱。
(4)除最后一个元素外，序列中的每个元素均只有一个直接后继。

2.2线性表存储结构

线性表的存储结构分为顺序存储和链式存储。
（1）线性表的顺序存储
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

在表长为n的线性表中插入新元素时，共有n+1个插入位置，新元素在n+1个位置插入的概率相同时，插入一个新元素需要移动的元素个数期望值 E为n/2。时间复杂度最好O(1)，最坏O(n)，平均O(n)
等概率下删除元素时需要移动的元素个数期期望值 E为(n-1)/2。时间复杂度最好O(1)，最坏O(n)，平均O(n)
最好，最坏，平均的时间按复杂度都是O(1)

（2）线性表的链式存储
①时间复杂度

时间复杂度	插入	删除	查询
最好	O(1)	O(1)	O(1)
最坏	O(n)	O(n)	O(n)
平均	O(n)	O(n)	O(n)

②存储密度不高

2.3栈

（1）栈是只能通过访问它的一端来实现数据在储和检索的一种线性数据结构。
（2）入栈和出栈都不需要遍历列表
（3）递归
（4）先进后出，后进先出

2.4队列

（1）队列是一种先进先出的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear)允许删除元素的一端称为队头(Front)。
（2）入队和出队都不需要遍历列表
（3）循环队列的优点，入队出队都不需要移动其他元素

2.5串

（1）概念

空串:长度为零的串称为空串，空串不包含任何字符。
空格串:由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符,在计算串长度时要将其计算在内。
子串:由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
串相等:指两个串长度相等且对应序号的字符也相同。
串比较:两个串比较大小时以字符的ASCI码值(或其他字符编码集合)作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大:若其中一个串先结束，则以串长较大者为大。
（2）模式匹配
①时间复杂度
n主串，m模式串
最好O(m)，最坏O(n*m)，平均O(n+m)
②KMP
串的前缀：包含第一个字符并且不包含最后一个字符的字串
串的后缀：包含最后一个字符并且不包含第一个字符的字串
第i个字符的next值 =从1~(i-1)串中最长相等前后缀长度+1
特殊情况:next[1]=0

2.6数组

一维数组
LOC:第一个元素的首地址，L:元素大小
下标从0开始：ai=LOC+ixL
下标从1开始：ai=LOC+(i-1)xL
二维数组
LOC:第一个元素的首地址、N:行数、M:列数、L:元素大小
按行优先存储并且下标从0开始：aij=LOC+(ixM+j)xL
按行优先存储并且下标从1开始：ai,j=LOC+[(i-1)xM+(j- 1)]xL
按列优先存储并且下标从0开始：aii=LOC+(jxN+i)xL
按列优先存储并且下标从1开始：aij=LOC+[(j-1)xN+(i-1)]xL

2.7矩阵

对称矩阵
①Aᵢⱼ=Aⱼᵢ
②地址
i>=j
下标从0开始：Aᵢ,ⱼ = i(i+1)/2+j+1
下标从1开始：Aᵢ,ⱼ = i(i-1)/2+j
i=<j
下标从0开始：Aᵢ,ⱼ = j(j+1)/2+i+1
下标从1开始：Aᵢ,ⱼ = j(j-1)/2+i
三角对称矩阵
按行存储
下标从0开始：Aᵢ,ⱼ = 2i+j+1
下标从1开始：Aᵢ,ⱼ = 2i+j-2
稀疏矩阵
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

2.8树

概念
(1)双亲、孩子和兄弟。结点的子树的根称为该结点的孩子;相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
(2)结点的度。一个结点的子树的个数记为该结点的度。
(3)叶子结点。叶子结点也称为终端结点，指度为0的结点。
(4)内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
(5)结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第 i+1 层。
(6)树的高度。一棵树的最大层数记为树的高度(或深度)
性质
性质1：树中的结点总数等于树中所有结点的度数之和加1
性质2：度为 m 的树中第i层上最多有 mⁱ⁻¹个结点(i>1)
性质3：高度为 h的 m 次树最多有(mʰ-1)/(m-1)个结点
性质 4:具有n个结点、度为m的树的最小高度为 [logₘ(n(m-1)+1)] (上取整)
二叉树
分为左右子树，二叉树的节点最大为2
二叉树性质1：二叉树第层(i≥1)上最多有2ⁱ⁻¹个结点
二叉树性质2：高度为h的二叉树最多有2ʰ-1个结点
二叉树性质3：对于任何一棵二叉树，度为0的结点数等于度为2的结点数+1
二叉树性质4：具有几个结点的完全二叉树的高度为[log₂n]+1(下取整)或[log₂(n+1)]（上取整）
满二叉树
深度为k的二叉树有2ᵏ-1个结点，则称其为满二叉树
完全二叉树
深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

当节点数确定时，完全二叉树的高度最小

平衡二叉树
①二叉树中的任意一个结点的左右子树高度之差的绝对值不超过1
②完全二叉树一定是平衡二叉树，平衡二叉树不一定是完全二叉树
③叶子节点满足平衡二叉树的条件要求
二叉排序树
①根结点的关键字

大于左子树所有结点的关键字，

小于右子树所有结点的关键字，

左右子树也是一颗二叉排序树

中序遍历得到的序列是有序序列

②查找效率最差的是单支树
8. 最优二叉树（哈夫曼树）
①最优二叉树又称为哈夫曼树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
②树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。在这里插入图片描述
n为带权叶子结点数目，wk为叶子结点的权值，lk为叶子结点到根的路径长度。

③何构造最优二叉树

构造最优二叉树的哈夫曼算法如下
    (1)根据给定的个权值{w1，w2，…,wn}，构成n棵二叉树的集合 F={T1,T2,…,Tn}，其中,每棵树Ti中只有一个带权为wi的根结点，其左、右子树均空。
    (2)在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
    (3)从F中删除这两棵树，同时将新得到的二叉树加入到F中。
    重复(2)、(3)步，直到F中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。
    由此算法可知，以选中的两棵子树构成新的二叉树，哪个作为左子树，哪个作为右子树，并没有明确。所以，具有n个叶子结点的权值为 w1,w2,…,wn 的最优二叉树不唯一，但其 WPL值是唯一确定的。

④哈夫曼编码
若对每个字符编制相同长度的二进制码则称为等长编码。左0右1

2.9二叉树的存储结构

二叉树的顺序存储结构
假设有编号为i的结点，则有:
若 i=1，则该结点为根结点，无双亲;若i>1，则该结点的双亲结点为[i/2]
若 2i <= n，则该结点的左孩子编号为2i，否则无左孩子。
若 2i+l1<=n，则该结点的右孩子编号为 2i+1，否则无右孩子。
在最坏情况下，一个深度为k且只有k个结点的二叉树(单支树)需要2ᵏ-1个存储单元。
二叉树的链式存储结构
①n个节点有2n个指针域
②n个节点有n-1个分支

2.10二叉树遍历

先序遍历
中序遍历
后序遍历
层次遍历
先序遍历+中序遍历可构造二叉树
后序遍历+中序遍历可构造二叉树
层次遍历+中序遍历可构造二叉树
先序遍历+后序遍历不可构造二叉树

2.11图

定义
图是由集合V和E构成的二元组,记作G=(V，E)，其中，V是图中顶点的非空有限集合,E是图中边的有限集合。
有向图，无向图

(1)有向图。若图中每条边都是有方向的，那么顶点之间的关系用<vi,vj>表示，它说明从vi到vj有一条有向边(也称为弧)。vi是有向边的起点，vj称为弧尾;是有向边的终点，称为弧头。所有边都有方向的图称为有向图。
(2)无向图。若图中的每条边都是无方向的，顶点vi和vj之间的边用(vi,vj)表示。因此，在有向图中<vi,vj>与<vj,vi>分别表示两条边，而在无向图中(vi,vj)与(vj,vi)表示的是同一条边。

完全图
若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边则称之为无向完全图。显然，含有n个顶点的无向完全图共有n(n-1)/2条边。类似地，有 n 个顶点的有向完全图中弧的数目为 n(n-1),即任意两个不同顶点之间都有方向相反的两条弧存在。
度、出度和入度。
预点v的度是指关联于该顶点的边的数目，记作 D(v)。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为 ID(v)和 OD(v)。无论是有向图还是无向图，顶点数 n、边数e与各顶点的度之间有以下关系。
路径。
在无向图 G 中，从顶点vp到顶点vq的路径是指存在一个顶点序列vp，vi1，vi2，…，vin，vq，使得(vp，vi1)，(vi1，vi2)，…，(vin，vq)均属于E(G)。若G是有向图，其路径也是有方向的，它由 E(G)中的有向边<vp,vi1>,<vi1，vi2>,…,<vin，vq>组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称其为简单路径。
连通图与连通分量。
在无向图G中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果无向图 G中任意两个顶点都是连通的，则称其为连通图。无向图G的极大连通子图称为G的连通分量。
强连通图与强连通分量。
在有向图G中，如果对于每一对顶点vi,vj∈V且vi不等于vj,从顶点vi到顶点vj和从顶点vj到顶点vi都存在路径，则称图G为强连通图。有向图中的极大连通子图称为有向图的强连通分量。
图的存储结构
图的基本存储结构有邻接矩阵表示法和邻接链表表示法两种
（1）邻接矩阵表示法