目录
2.1 基本概念与三要素
数据结构
- 用程序代码把现实世界的问题信息化
- 用计算机高效地处理这些信息从而创造价值
数据
数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
数据元素、数据项
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。
数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
三要素
- 逻辑结构
- 物理结构(存储结构)
- 数据的运算
逻辑结构
分为以下四类
集合
各个元素同属一个结构,别无其他关系
线性结构
数据元素之间一对一的关系。除了第一个元素,所有元素都有唯一前驱;除了最后一个元素,所有元素都有唯一后继
树形结构
数据元素之间是一对多的关系
图状结构(网状结构)
数据元素之间是多对多的关系
物理结构
顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
链式存储
逻辑上相邻的元素在物理位置上可以不相邻
索引存储
在存储元素信息的同时,还建立附加的索引表
散列存储
根据元素的关键字直接计算出该元素的存储地址,又称**哈希(Hash)**存储
2.2 算法
算法是指如何处理信息化后的现实世界问题,以解决实际问题
算法在程序中的理解
特性
有穷性
一个算法必须总在执行有穷步后结束,且每一步都可在有穷时间内完成
确定性
算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出
可行性
算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
输入
一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合
输出
一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量
算法效率的度量
时间复杂度
时间开销与问题规模n之间的关系
假设有一程序,如下
void printWhile(int n){ int i = 1; // 1 while (i <= n) // 2 { i++; // 3 printf("Hello world! *x*%d\n", i); // 4 } printf("print done! (*%d)", i); // 5}如果要计算该程序的时间复杂度
当调用printWhile(3000)时,调用语句的频率如下:
- 1次
- 3001次
- 3000次
- 3000次
- 1次
因此:
时间开销与问题规模的关系为:
简化时间复杂度当问题的规模足够大时 常数项可以忽略掉,且阶数最高的部分的系数可以忽略掉
因此以下的时间复杂度:
可以简化为:
空间复杂度
空间开销(内存开销)与问题规模n之间的关系
以上述时间复杂度的程序为例:
- null
与时间复杂度不同的是,无论问题规模怎么变,算法运行所需的内存空间都是固定的常量
该算法的空间复杂度为: (S表示Space)
算法原地工作——算法所需内存空间为常量
只需关注存储空间大小与问题规模相关的变量
函数递归调用时
函数递归调用带来的内存开销:
也就是:
大小关系对比
2.3 线性表
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列,其中 n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表示 为:
- 是线性表中的“第i个”元素线性表中的位序
- 是表头元素;是表尾元素
- 除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
顺序表与链表
对比

性能分析
| 性能类别 | 具体项目 | 顺序存储 | 链式存储 |
|---|---|---|---|
| 空间性能 | 存储密度 | =1,更优 | <1 |
| 空间性能 | 容量分配 | 事先确定 | 动态改变,更优 |
| 时间性能 | 查找运算 | O(n/2) | O(n/2) |
| 时间性能 | 读运算 | O(1),更优 | O([n+1]/2),最好情况为1,最坏情况为n |
| 时间性能 | 插入运算 | O(n/2),最好情况为0,最坏情况为n | O(1),更优 |
| 时间性能 | 删除运算 | O([n-1]/2) | O(1),更优 |
插入&删除操作
- 顺序存储:插入元素前要移动元素以挪出空的存储单元,然后再插入元素 删除元素时同样需要移动元素,以填充被删除元素的存储单元
- 链式存储:

2.4 栈和队列
栈
栈是只允许在一端进行插入或删除操作的线性表
- 栈顶:允许插入和删除的一端
- 栈底:不允许插入和删除的一端

队列
队列是一种先进先出(FIFO)的线性表,它只允许在表的一端插入元素,而在表的另一端删除元素
在队列中,允许插入元素的一端称为队尾(Rear),允许删除元素的一端称为队头(Front)

循环队列

例:

2.5 串、数组、矩阵和广义表
串
串是仅由字符构成的有限序列,是取值范围受限的线性表。
一般记为
其中S是串名,是串值
- 空串:长度为零的串,空串不包含任何字符。
- 空格串:由一个或多个空格组成的串。
- 子串:由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时,该子串的第一个字符在主串中的位置。空串是任意串的子串。
- 串相等:指两个串长度相等且对应位置上的字符也相同
- 串比较:两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行,字符的ASCII码值大者所在的串为大;若其中一个串先结束,则以串长较大者为大。
基本操作
| 序号 | 操作名称 | 函数原型 | 功能描述 |
|---|---|---|---|
| 1 | 赋值操作 | StrAssign(s, t) | 将串t的值赋给串s。 |
| 2 | 连接操作 | Concat(s, t) | 将串t接续在串s的尾部,形成一个新串。 |
| 3 | 求串长 | StrLength(s) | 返回串s的长度。 |
| 4 | 串比较 | StrCompare(s, t) | 比较两个串的大小。 |
| 5 | 求子串 | SubString(s, start, len) | 返回串s中从start开始的、长度为len的字符序列。 |
存储结构
- 串的顺序存储:定长存储结构
- 串的链式存储:块链
NOTE子串的定位操作通常称为串的模式匹配,它是各种串处理系统中最重
要的运算之一。子串也称为模式串。
数组
| 数组类型 | 存储地址计算 |
|---|---|
| 一维数组 a[n] | a[i]的存储地址为:a+i*len |
| 二维数组 a[m][n] | a[i][j]的存储地址(按行存储)为:a+(i*n+j)len a[i][j]的存储地址(按列存储)为:a+(jm+i)*len |
例:

由题目可知:
因此带入公式得:
稀疏矩阵
| 稀疏矩阵 | 示意图 | 要点 |
|---|---|---|
| 上三角矩阵 | ![]() | 在矩阵中下标分别为i和j 的元素,对应的一维数组 的下标计算公式为: |
| 下三角矩阵 | ![]() | 在矩阵中下标分别为i和j 的元素,对应的一维数组 的下标计算公式为: |
小技巧在选择题当中,这类题可通过代入法解决,见下例题
例题

通过代入法解题:
已知信息:
因此可知的内容排列如下:
易错点此处M的起始下标可能为0/1,需要根据题目调整下方公式
将的i和j分别设置为符合条件的值,代入选项计算:
- 此时A为 M应当为 也就是:对应 代入选项:
- 选项A:带入计算得:。符合条件
- 选项B:同理得:。不符合条件,排除
- 选项C:同理得:。不符合条件,排除
- 选项D:同理得:。符合条件 排除两个选项,再次带入排除
- 此时A为 M应当为 也就是:对应 代入选项(方法同上):
- 选项A:,符合条件
- 选项D:,不符合条件,排除
排除得答案:
广义表
广义表是n个表元素组成的有限序列,是线性表的推广
通常用递归的形式进行定义,记作:
NOTE其中LS是表名,a是表元素,它可以是表(称做子表),也可以是数据元素(称
为原子)。其中n是广义表的长度(也就是最外层包含的元素个数),n=0的广义表 为空表:而递归定义的重数就是广义表的深度,直观地说,就是定义中所含括号的重 数(原子的深度为0,空表的深度为1)。
基本运算
- 取表头
head(Ls):取出表的第一个元素 - 取表尾
tail(Ls):取出除了第一个元素的剩下的元素
例
若有:
则:
例题
例1
有广义表,则其长度为?深度为?
长度为表元素的数量,不管是值还是数据元素
因此长度为3
深度为表内数据元素嵌套的数量,该表最深深度为2
例2
有广义表,要将其中的b字母取出,操作为?
通过:

2.6 树和二叉树
树

基本概念:
- 节点:上图中1~8的数据代表的就是树中的节点
- 节点的度:指的是节点分支出来节点的数量,如节点1、2、6的度就为2
- 树的度:指的是树中所有节点的最大度
- 根节点:指的是树中第一个节点,在图中的根节点就为1
- 叶子结点:指的是树中末端 度为0 / 没有子节点 的节点
- 分支结点:指的是树中有子节点的节点
- 内部结点:除根节点、叶子节点以外的节点就叫做内部结点
- 父结点:指的是节点从上延伸下来作为上级节点的节点。如图中1节点就为2节点的父节点
- 子结点:指的是节点延伸出来的下一节点。如图中2节点就为1节点的子节点
- 兄弟结点:拥有同一父节点的子节点
- 层次:分支的深度。图中的树就分为1~4层
二叉树

重要特性
- 在二叉树的第i层上最多有 2^(i-1) 个结点(i≥1)
- 深度为k的二叉树最多有 2^k -1 个结点(k≥1)
- 对任何一棵二叉树,如果其叶子结点数为 n₀,度为2的结点数为 n₂,则 n₀ = n₂ + 1。
- 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到 ⌊log₂n⌋ + 1 层,每层从左到右),则对任一结点 i(1≤i≤n),有:
- 如果 i=1,则结点i无父结点,是二叉树的根;如果 ,则父结点是
- 如果 2i>n,则结点i为叶子结点,无左子结点;否则,其左子结点是结点
- 如果 2i+1>n,则结点i无右子结点,否则,其右子结点是结点 2i+1。
遍历
- 前序遍历:根左右
- 中序遍历:左根右
- 后序遍历:左右根
- 层次遍历:按层从左到右依次遍历
例题

上图中树的各种遍历结果:
- 层次遍历:12345678
- 前序遍历:12457836
- 中序遍历:42785136
- 后序遍历:48752631
反向构造二叉树
问:由前序序列为ABHFDECG;中序序列为HBEDFAGC构造叉树
因为前序遍历为根左右,因此通过前序序列可知根节点为A
因此可从中序序列中得知左子树为:HBEDF,右子树为:GC
以此类推,因为左子树为HBEDF,前序序列为ABHFDECG
因此可以推出左子树的根节点为B
… 层层分析最终得出二叉树


树转二叉树

- 孩子节点 - 左子树节点
- 兄弟节点 - 右孩子节点
每个点的左儿子是它的第一个儿子,右儿子是它从左往右数的第一个兄弟
查找二叉树
特点
- 左孩子小于根
- 右孩子大于根
插入结点
- 若该键值结点已存在,则不再插入。
- 若查找二叉树为空树,则以新结点为查找二叉树。
- 将要插入结点键值与插入后父结点键值比较,就能确定新结点是父结点的左子结点,还是右子结点。
删除结点
- 若待删除结点是叶子结点,则直接删除。
- 若待删除结点只有一个子结点,则将这个子结点与待删除结点的父结点直接连接。
- 若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除节点s,节点s必属于上述1~2情况之一。
例题
将序列 89,48,56,112,51,20 构造为查找二叉树:
- 将89作为根节点
- 48小于89,作为89的左节点
- 56小于89,且大于48,则作为48的右节点
- 112大于89,作为89的右节点
- 51小于89,且大于48,且小于56,则作为56的左节点
- 20小于89,且小于48,则作为48的左节点
构建后的查找二叉树如图:

霍夫曼树
- 树的路径长度:指的是到根节点的距离,如下图左树的2叶子节点的路径长度为2
- 带权路径长度(树的代价):
如下为构造的树

例题
给定一组权值:5, 29, 7, 8, 14, 23, 3, 11。构造哈夫曼树

线索二叉树
根据遍历方式索引前一个和后一个节点


平衡二叉树
任意结点的左右子树深度相差不超过1,每结点的平衡度只能为-1、0或1。
平衡度:左右子树的子节点两者最大深度的差

2.7 图
分类
有向图
节点之间有箭头指示方向的图
无向图
节点之间仅使用线连接的图
完全图
- 在无向图中,若每对顶点之间都有一条边相连,则称该图为完全图。
- 在有向图中,若每对顶点之间都有二条有向边相互连接,则称该图为完全图。

度
在无向图中:一个节点有几条连线 就可以简单的理解为该节点的度为多少
在有向图中:
- 指向该节点的箭头有几个,就称之为有几个入度
- 该节点指出去的箭头有几个,就称之为有几个出度
存储结构
邻接矩阵
用一个n阶方阵R来存放图中各结点的关联信息,其矩阵元素 (R_{ij}) 定义为:


邻接表
首先把每个顶点的令接顶点用链表示出来,然后用一个一维数组来顺序存储上面每个链表的头指针。

遍历
| 遍历方法 | 说明 | 示例 |
|---|---|---|
| 深度优先 | 1.首先访问出发顶点V 2.依次从V出发搜索V的任意一个邻接点W; 3.若W未访问过,则从该点出发继续深度优先遍历 它类似于树的前序遍历。 | V₁ , V₂ V₄ , V₈ V₅ , V₃ V₆ , V₇ |
| 广度优先 | 1.首先访问出发顶点V 2.然后访问与顶点V邻接的全部未访问顶点W、X、Y…; 3.然后再依次访问W、X、Y…邻接的未访问的顶点; | V₁ , V₂ V₃ , V₄ V₅ , V₆ V₇ , V₈ |
图例:

拓扑排序
我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络,简称AOV网络。

上图的拓朴序列有:
最小生成树

普利姆算法
以一个节点为起点,不断地计算相邻(包括起点)相邻的边的权值中的最小值的节点,将其纳入相邻边,最终纳入全部点而不形成环路
克鲁斯卡尔算法
先寻找图中权值较小的节点,将权值较小的节点连起来,不断添加较小权值的连接,直到最后连接起六个节点

2.8 查找
在数据集合中寻找满足某种条件的数据元素的过程称为查找。
- 查找表(查找结构):用于查找的数据集合称为查找表,它由同一类型的数据元素(或记录)组成。
- 关键字:数据元素中唯一标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的。
- 查找长度:在查找运算中,需要对比关键字的次数称为查找长度。
- 平均查找长度:又叫ASL(Average Search Length),指的是所有查找过程中进行关键字的比较次数的平均值。

顺序查找
又称“线性查找”,通常用于线性表
算法思想:从头到尾挨个找(或是从尾到头)
一般情况下,(c_i = n-i+1),因此在等概率情况下,顺序查找成功的平均查找长度为
折半查找
又称“二分查找”,仅适用于有序的顺序表。

折半查找在查找成功时关键字的比较次数最多为 次。
折半查找的时间复杂度为 。
分块查找
特点:块内无序,块间有序
查找方式:第一步在索引表中确定待查记录所在的块,第二步在块内顺序查找。
NOTE也就是前两者查找方式的折中

哈希表
又称“散列表”,是一种数据结构,特点是:数据元素的关键字与其存储地址直接相关
例题
有一堆数据元素,关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79,
散列函数为:H(key)=key%13

若不同的关键字通过散列函数映射到同一个值,则称它们为“同义词”
通过散列函数确定的位置已经存放了其他元素,则称这种情况为“冲突“
解决上述冲突的方式通常有:
- 开放地址法
- 链地址法
- 再哈希法
- 建立一个公共溢出区
2.9 排序
指的是重新排列表中的元素,使表中的元素满足按关键字有序的过程。
分类
- 稳定性:稳定/不稳定(排序后相同的数字在是否会保持相对方向)
- 数据来源:内部排序/外部排序(数据来源内存/数据来源外部设备)
| 排序类别 | 具体算法 |
|---|---|
| 插入类排序 | 直接插入排序、希尔排序 |
| 交换类排序 | 冒泡排序、快速排序 |
| 选择类排序 | 简单选择排序、堆排序 |
| 其他 | 归并排序、基数排序 |
排序算法
直接插入排序
算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。
希尔排序
算法思想:先将待排序表分割成若干形如的“特殊”子表,对各个子表分别进行直接插入排序。缩小增量d,重复上述过程,直到d=1为止。

冒泡排序
算法思想:从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即),则交换它们,直到序列比较完。称这样过程为”一趟”冒泡排序。

快速排序
算法思想:在待排序表 L[1...n] 中任取一个元素 pivot作为枢轴(或基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分 L[1...k-1] 和 L[k+1...n],使得 L[1...k-1] 中的所有元素小于 pivot,L[k+1...n] 中的所有元素大于等于 pivot,则 pivot 放在了其最终位置 L(k) 上,这个过程称为 一次“划分”。然后分别递归地对两个子表重复上述过程,直到每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。

简单选择排序
算法思想:每一趟在待排序元素中选取关键字最小的元素加入有序子序列。

堆排序
设有n个元素的序列{K1, K2, … Kn},当且仅当满足下述关系之时,称之为堆。 (1) ;且 (2) ;且 其中(1)称为小顶堆,(2)称为大顶堆

例题
假设有数组,创建大顶堆过程如下:

归并排序
算法思想:把两个或多个已经有序的序列合并成一个。

基数排序
算法思想:借助多关键字排序思想对单逻辑关键字进行排序的方法。
基数的选择和关键字的分解是根据关键字的类型来决定的。
例如:关键字是十进制数,则按个位、十位来分解。

评价指标
| 类别 | 排序方法 | 时间复杂度 (平均情况) | 时间复杂度 (最坏情况) | 空间复杂度 (辅助存储) | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | Shell排序 | O(n¹·³) | O(n²) | O(1) | 不稳定 |
| 选择排序 | 直接选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 选择排序 | 堆排序 | O(nlog₂n) | O(nlog₂n) | O(1) | 不稳定 |
| 交换排序 | 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 交换排序 | 快速排序 | O(nlog₂n) | O(n²) | O(log₂n) | 不稳定 |
| 归并排序 | - | O(nlog₂n) | O(nlog₂n) | O(n) | 稳定 |
| 基数排序 | - | O(d(r+n)) | O(d(r+n)) | O(r+n) | 稳定 |

