软考-数据结构

一、数据结构的概述

(一)数据结构的定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。
数据的逻辑结构和存储结构是密不可分的两个方面。一个算法的设计取决于所选的逻辑结构，而算法的实现依赖于所采用的的存储结构。

数据元素（节点）：数据的基本单位。
数据对象：性质相同的数据元素的集合，如整数集合、学生信息集合等。
抽象数据类型（ADT）：一个数学模型及定义在其上的操作集。

(二)基本数据结构类型：

线性结构

线性结构：数据元素之间存在一对一的关系，如数组、链表、栈、队列。

非线性结构

非线性结构：数据元素之间的关系不是一对一，如树、图。

二、线性结构（逻辑结构）

线性结构的特点：

常用的线性结构：线性表、栈、队列、串

(一) 线性表

定义：零个或多个数据元素的有限序列。

1.线性表的存储结构

线性表的存储结构：顺序存储、链式存储
线性表的基本操作：插入、删除、查找。

(1) 顺序存储

一组地址连续的存储单元。如：数组。
特点：逻辑上相邻的两个元素，物理位置上也相邻。
优点：随机存取；O(1)
缺点：插入、删除需要移动元素。

a.插入操作

代码：

时间复杂度/平均查找次数

b.删除操作

代码

时间复杂度/平均查找次数

c.查找操作

代码

时间复杂度/平均查找次数

(2) 链式存储

通过指针链接起来的节点存储元素

特点：
数据元素，逻辑上连续，物理上分开。
优点：
支持动态内存分配，结点空间需要时才申请，无需实现分配。
支持高效的插入、删除操作，时间复杂度为O(1)。
缺点：
不支持随机访问，需要从头节点开始遍历整个链表才能访问任意位置的元素。

单链表

单链表分为：
带头结点的单链表；
不带头结点的单链表

无论是否有头结点，头指针始终指向链表的第一个结点

a.单链表的定义

b.单链表的插入操作

带头结点的头插法

带头结点的尾插法

时间复杂度

c.单链表的删除操作

删除第K个位置的节点
重点：找到k-1位置的节点，将k-1位置的节点指向k+1位置的节点

不带头结点

①删除第一个节点（k=1）
list = list.next;
②删除除了第一个节点以外的节点

带头结点

Node s = p.next;
p.next = s.next;

时间复杂度

带头结点/不带头结点的单链表，删除操作的时间复杂度

d.单链表的查找操作

带头结点和不带头结点的代码一样

时间复杂度

双链表

定义

==特点：可以从表中任意的节点出发，从两个方向上，遍历链表。 ==

插入操作(注意顺序)

删除操作

循环单链表

特点： 可以从表中任意节点开始，遍历整个链表。
尾指针，好处：

可以直接通过尾指针，找到头结点。
在末尾（n+1）插入节点的时候，没有尾指针，则时间复杂度为（n），若是有尾指针，则时间复杂度为O（1）。
但是，在第n个位置插入节点时，还是时间复杂度为O（n）

三、栈和队列（操作受限的线性表）

栈（后进先出）

(一) 栈的定义

只允许在一端进行插入和删除操作的线性表。

栈顶：允许操作的一端
栈底:不允许操作的一端
空栈：不含1任何元素的栈
栈的典型应用：递归

(二) 栈的存储结构

顺序存储-顺序栈

用数组实现

代码

共享栈

链式存储-链式栈

用单链表作为栈的存储结构，头指针作为栈顶指针，入栈出栈都不需要遍历链表

队列（先进先出）

(一) 队列的定义

允许在表的一端插入元素，表的另一端删除元素的线性表

顺序存储-顺序队

在使用数组实现的队列中，入队的时间复杂度是O(1)，出队的时间复杂度是O(n)，查找元素的时间复杂度是O(n)。

循环队列

循环队列的操作

链式存储-链式队

循环单链表储存队，入队出队都不用遍历队列

链式队列的操作

在使用链表实现的队列中，入队和出队的时间复杂度都是O(1)，查找元素的时间复杂度是O(n)。

双端队列

四、串及其匹配模式

(一) 串的定义

由字符构成的有限序列，是一种线性表。
空串：没有任何一个字符的串称为空串。
空格串：是只包含空格的串。
注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。

1、串的比较

以字符的ASCII值作为依据。
比较操作从两个字符串的第一个字符开始，字符的码值大者所在的串大；
若其中一个串先结束，以串长较大者为大。

2. 串的个数

(二)串的模式匹配

子串的定位操作，称为串的模式匹配。
设有两个串s和t，要在串s中找到与t相等的子串。通常将s称为目标串，t称为模式串，即：子串。

简单的模式匹配

算法代码

例子

时间复杂度

子串长度为m，目标串长度为n：
最好：O(m)
最坏：O(n*m)，(n-m+1)*m
平均：O(n+m)

KMP算法

朴素模式匹配的改进。

改进之处：匹配过程，出现相比较的字符串不相等时，不需要回溯主串的指针，利用已经得到的部分匹配结果，将子串向后滑动尽可能远的距离，再继续比较。

前缀：包含第一个字符，但不包含最后一个字符的子串。
后缀：包含最后一个字符，但不包含第一个字符的子串。
最长相等前后缀：前缀和后缀相等的最长子串。

例如字符串“abca”
前缀：{a,ab,abc}
后缀：{a,ca,bca}
最长相等前后缀：a

求NEXT数组

解法：
next数组第1、2位分别为0，1
从第三位开始，找前面前缀后缀相等的个数+1
问题：已知串S= ‘ababaaababaa ’ , 求其 Next 数值序列

五、数组与矩阵

数组

(一) 数组的定义

数组：一组地址连续的空间。

(二) 一维数组

对于多维数组有两种映射方式：行优先、列优先

求A[i]的地址

数组从0开始：
A[i]的地址 = LOC + (i)*L
A[i]的前面有i个元素

数组从1开始：
A[i]的地址 = LOC + (i-1)*L
A[i]的前面有i-1个元素

LOC是首元素的地址，L是每个数组元素所占的空间

(三) 二维数组

a[N][M]：N行、M列

1.a[N][M]按行优先存储

求a[i][j]的地址：

① 数组下标从0开始：a[0][0]
先求出 a[i][j]前面有多少行：i行
再求出 a[i][j]前面有多少列：j列
a[i][j] = LOC + (i * M + j) * L

M在这里表示了一行有多少个，如果题目只给了行列的范围
(行：0 ~ h1,列：0 ~ h2)
a[i][j] = LOC + (i * （h2+1） + j) * L

②数组下标从1开始：a[1][1]
a[i][j] = LOC + [(i-1) * M + (j-1)] * L

(行：0 ~ h1,列：0 ~ h2)
a[i][j] = LOC + [(i-1) * (h2+1) + (j-1)] * L

2.a[N][M]按列优先存储

求a[i][j]的地址：

① 数组下标从0开始：a[0][0]
先求出 a[i][j]前面有多少列：j列
再求出 a[i][j]前面有多少行：i行
a[i][j] = LOC + (j * N + i) * L
(行：0 ~ h1,列：0 ~ h2)
a[i][j] = LOC + (j * (h1+1) + i) * L

②数组下标从1开始：a[1][1]
a[i][j] = LOC + [(j-1) * N + (i-1)] * L
(行：0 ~ h1,列：0 ~ h2)
a[i][j] = LOC + (j-1 * (h1+1) + i-1) * L

3.特殊情况a[N][N]

对于N行N列数组
求a[i][i]时(i==j)，不管是按行存储还是按列存储，其存储的地址和该元素前面的元素个数，都是相同的。

矩阵

一个二维数组就是一个矩阵。
矩阵的存储，将一个二维数组的元素，压缩存储在一个一维数组中。

(一) 矩阵的压缩存储

多个值相同的元素，分配一个存储单元；0不分配存储单元。

(二) 特殊矩阵

指值相同的元素或0元素在矩阵中有一定的规律

1.对称矩阵

上三角区的元素==下三角区的元素 A[i][j]==A[j][i]
对称矩阵的存储：只存储主对角线的元素 + 下三角区/上三角区的元素
将对此矩阵A[i][j]存放在B[n(n+1)/2]中。B数组下标从0开始

(1) 按行存储-求A[i][j]在B[k]中的地址

计算方法：
** 1.前i-1行有多少个元素？ i*(i+1)/2 **

第0行 a00 共1个元素
第1行 a10 a11 共2个元素
第2行 a10 a11 a12 共3个元素
第i-1行 共i个元素
总共 1+2+3+…+i=i*(i+1)/2个元素

2.第i行，前j列有几个元素？ j
3.再加上自己

矩阵下标从0开始、数组下标从0开始

矩阵下标从0开始、数组下标从1开始

矩阵下标从1开始、数组下标从0开始

矩阵下标从1开始、数组下标从1开始

最后一个元素的位置：(1+n) * n/2 - 1

二维数组下标从1开始

B数组下标从0开始

B数组下标从1开始

2.三对角矩阵

3.稀疏矩阵

矩阵中，非0元素的个数远少于0元素的个数，非0元素分布没有规律。

稀疏矩阵的压缩存储

三元组顺序表（顺序存储）
十字链表（链式存储）

三元组顺序表

十字链表

六、树与二叉树

树

(一) 树的定义

树是n个节点的有限集合。当n=0时，称为空树。
树的定义是递归的。

(二) 基本术语

结点的度：一个结点的子树个数。
树的度：树中最大的结点的度数。如B的度2，D的度3，树的度3
叶子结点：度为0的结点。
分支结点：度不为0的结点。
树的深度：从根自顶向下逐层累加。
树的高度：从叶子结点开始自顶向下逐层累加。
树的高度(深度)=一棵树的最大层数。如图高度(深度)=4

(三) 树的性质

二叉树

(一) 二叉树的定义

二叉树是特殊树型结构，二叉树是n个结点的有限集合，二叉树每个结点的最大度为2。

二叉树的个数

3个结点的二叉树有5个形态

计算n个结点的二叉树有多少种，可以用

(二) 二叉树与树的区别

1.二叉树可以为空树
2.二叉树有左右子树之分

(三) 二叉树与度为2的树的区别

1.度为2的树至少有三个结点，二叉树可以为空
2.二叉树有左右子树之分

(四) 特殊二叉树(满二叉/完全二叉)

(五) 二叉树的性质

(六) 二叉树的存储结构

1.二叉树的顺序存储

完全二叉树和满二叉树采用顺序存储比较合适
n个结点的二叉树顺序储存所需空间 2^(n-1) 完全二叉树

2.二叉树的链式存储

二叉树K个结点采用二叉链表存储，有K+1个空指针

二叉链表

二叉链表：
有n个结点，就有2n个指针域；
有n-1个分支，就有n-1个有效指针域；
所以，二叉链表，n个结点，有n+1个空指针域。

三叉链表

三叉链表，n个结点，有n+2个空指针域。

(七) 二叉树的遍历

先序遍历

根节点、左子树、右子树
A B D G C E F

中序遍历

左子树、根节点、右子树
B D G A E C F
中序遍历n在m之前的条件：m在n的右边

后序遍历

左子树、右子树、根节点
G D B E F C A

层次遍历

从上到下、从左到右的访问结点。
A B C D E F G

根据遍历序列构造二叉树

4种遍历，单独看，都不能唯一确定一个二叉树。

1.先序遍历 + 中序遍历

从先序中得到每个子树的根节点（第一个节点），在中序中用根节点，划分出左右子树。

2.后序遍历 + 中序遍历

从后序中得到每个子树的根节点（最后一个节点），在中序中用根节点，划分出左右子树。

3.层次遍历 + 中序遍历

(八) 平衡二叉树

平衡二叉树：是一棵空树或它的左右两个子树的高度差的绝对值不超过 1， 并且左右两个子树都是一棵平衡二叉树。
完全二叉树是平衡二叉树

(九) 二叉排序树

1.二叉排序树的定义

二叉排序树，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大（如果有相同的值，则该节点放在左子节点或右子节点都可）或者是空树。
左子树节点的值 < 根节点的值 < 右子树结点的值
中序遍历，得到的序列是有序序列。

2.二叉排序树的性质

1.任何节点的值一定大于其左子树中的每一个节点的值，并小于其右子树中的每一个节点的值。如下便是一颗二叉排序树

2.二叉排序树的中序遍历得到递增的有序序列

3.二叉排序树的构造

构造方式：第一个关键字是根节点，然后依次遍历后面的关键字，比根节点小的，就往左挂，比根节点大的就往右挂。
不同的关键字序列可以构造相同的二叉排序树

4.二叉排序树的删除

对于二叉排序树中的节点A，对它的删除分为两种情况：
1、如果A只有一个子节点，就直接将A的子节点连至A的父节点上，并将A删除；

2、如果A有两个子节点，我们就以右子树内的最小节点取代A。

(十) 最优二叉树(哈夫曼树)

1.哈夫曼树的定义

路径：从树中的一个结点到另一个结点之间的分支构成这两点之间的路径
路径长度：路径上的分支数目称作路径长度
树的路径长度：从树根到每一个结点的路径长度之和
结点的带权路径长度：该节点到树根之间的路径长度 * 该节点的权值
树的带权路径长度 = 树中所有叶子结点的带权路径长度之和。
哈夫曼树指带权路径长度最短的树。

2.构造哈夫曼树

例1

例2

3.哈夫曼树的性质

１，只有度为0或２的结点，没有度为１的结点
２，包含n个叶子结点的哈夫曼树中共有2n-1个结点
3.权值越大的叶结点越靠近根结点。
权值越小的叶结点越远离根结点。
4、结点总数为奇数

4.哈夫曼编码

5.压缩比