目录

• 第六章.数据结构与算法基础（重点）
• • 第一节.数组与矩阵
  • • 数组
    • 稀疏矩阵
  • 第二节.数据结构的定义
  • 第三节.线性表
  • • 链表详解
    • 顺序存储与链式存储对比
    • 队列与栈
  • 第四节.广义表
  • 第五节.树与二叉树
  • • 树的概念
    • 二叉树的分类
    • 二叉树的重要特性
    • 二叉树的遍历
    • 反向构造二叉树
    • 树转二叉树
    • 查找(排序)二叉树
    • 最优二叉树（哈夫曼树）
    • 线索二叉树
    • 平衡二叉树
  • 第六节.图
  • • 图的基本概念
    • 图的存储-邻接矩阵(用的比较少，浪费空间， O ( n 2 ) O(n^{2}) O(n2))
    • 图的存储-邻接表(用的最多)
    • 图的遍历
    • 拓扑排序
    • 图的最小生成树
    • 普里姆算法
    • 克鲁斯卡尔算法
  • 第七节.算法基础
  • • 算法的特性
    • 算法的复杂度
  • 第八节.数据的查找
  • • 顺序查找
    • 二分查找
    • 散列（hash）表
  • 第九节.数据的排序
  • • 排序的概念
    • 排序方法分类
    • 直接插入排序
    • 希尔排序
    • 直接选择排序
    • 堆排序
    • 冒泡排序
    • 快速排序
    • 归并排序
    • 基数排序

第六章.数据结构与算法基础（重点）

ps：上午下午都会考到且难度最高
重点：线性表、树与二叉树、排序与查找、算法基础及常见算法

第一节.数组与矩阵

数组

• 数组的首地址是数组名，a[0] = a，因为a[0]是整个数组存储第一个元素。
• 数组的下标从0开始。
• len表示 每一个数组元素所占用的字节数。

例题：已知5行5列的二维数组a中的各元素占两个字节，求元素 a [ 2 ] [ 3 ] a [2] [3] a[2][3]按行优先存储的存储地址?
解：元素 a [ 2 ] [ 3 ] a[2][3] a[2][3]按行优先存储的存储地址为 a + ( 2 × 5 + 3 ) × 2 = ( a + 26 ) b i t a + (2 \times 5 + 3) \times 2 = (a + 26)bit a+(2×5+3)×2=(a+26)bit

稀疏矩阵

常考题型：计算稀疏矩阵当中某一个元素对应的一维数组的下标。
什么是稀疏矩阵？
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

大量的元素都是零，那么我们是不是可以考虑存储矩阵的一部分内容就已经把有效数据都存进去了，如果是这样的话，这是不是就能节省出很多空间了。所以就提出这一概念来，存储稀疏矩阵一般是存储上三角或者下三角。为什么另一半不用存呢？因为另一半可能跟现在的这一半是重复的数据。什么情况是重复的呢？比方说图是可以通过矩阵的方式进行存储，如果说你要存储的图是一个无向图，那么存储下来的就是三角矩阵而已。

二维数组存入计算机中都是以一维数组顺次的形式存储下来的，这种对应关系很重要。
解：数组M的下标是从1开始的，根据图片可知，先算前i行的个数，即 i ( i + 1 ) 2 \frac{i(i + 1)}{2} 2i(i+1)​，又因为下标是从1开始的，所以还有一行，这一行的个数为 j + 1 j + 1 j+1，那么答案就是A。
当然代入法，也能够做，A[0, 0]对应M[1]，依次将二维坐标带入到一维数组当中进行判断。

第二节.数据结构的定义

1.数据结构的概念
数据结构就是计算机存储以及组织数据的方式而已。
为什么要研究数据结构？
之所以研究数据结构是因为选择不同的数据结构可能带来的运行效率会非常之大。在同样的数据结构当中稍作调整也可以让效率有很大的改变。比方说：在数组的存储当中，行存储和列存储在既定的处理的机制之下，会有非常大的性能方面的差异，这也就是我们研究数据结构的基本价值与意义。

2.数据逻辑结构
数据结构从逻辑层面上分成

• 线性结构（顾名思义，线性结构跟一条线一样）
• 非线性结构(树型结构）
• 图
  

树和图的最大区别就是树中没有环路，图有可能存在环路。
广义的图包含树和线性结构；广义的树包含线性结构。

第三节.线性表

1.线性表的概念：线性表是线性结构的基本表现。如 ( a 1 , a 2 , … , a n ) \left(a_{1}, a_{2}, \ldots, a_{n}\right) (a1​,a2​,…,an​)

2.线性表常见的两种存储结构

• 顺序存储结构：顺序表
• 链式存储结构：链表

3.顺序表（连续的空间下存储数据）：开辟了连续的空间顺次的数据存储到表中，其实就是采用一维数组进行顺次存储信息。

链表详解

• 链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。另外，链表是在不连续的空间下存储数据。
• 链表的第一个节点和最后一个节点，分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空（null）。链表中每个节点的 next 引用都相当于一个指针，指向另一个节点，借助这些 next 引用，我们可以从链表的头节点移动到尾节点。

为什么会有指针域存在呢？
因为空闲的存储空间不见的都是连续的，比如说这样一种情况，磁盘上面有一个地方是空闲的，隔几个地方是空闲的，我们通过指针把这些离散的空间连接起来就形成了链表。顺序表是开辟了连续的空间顺次存储，磁盘中必须有一个能够放置10个元素的连续空间。所以两者从形态来讲是不一样的。

链表数据结构中主要包含单(向)链表、双向链表及循环链表：

1. 单链表：只有一个指针域，在整个节点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的节点。
   单链表可以分成 有头节点和没有头节点两种类型的链表。

有头节点的链表会有什么好处呢？
头结点的数据域可以不存储任何信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。头结点的作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。

2. 双向链表：要在单向链表中找到某个节点的前驱节点，必须从链表的头节点出发依次向后寻找，但是需要Ο(n)时间。为此我们可以扩展单向链表的节点结构，使得通过一个节点的引用，不但能够访问其后续节点，也可以方便的访问其前驱节点。扩展单向链表节点结构的方法是，在单链表节点结构中新增加一个域，该域用于指向节点的直接前驱节点。该链表称为双向链表。单向链表只能从一个方向遍历，双向链表可以从两个方向遍历。其中两个指针分别称为前驱指针和后继指针。

将尾结点指向头节点的好处是什么？
要在单向链表中找到某个节点的前驱节点，必须从链表的头节点出发依次向后寻找，但是需要Ο(n)时间。但是现在我们直接就能够取出直接前驱节点。

3. 循环链表：头节点和尾节点被连接在一起的链表称为循环链表，这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点，反之亦然。

链表的基本操作

图注

1. 单链表删除结点。删除a3就是将a2的指针指向a3的地址即可，但是现在不知道a3的地址，根据单链表中上一个结点的指针存储下一个结点的地址，故代码为 p − > n e x t = q − > n e x t p->next=q->next p−>next=q−>next。
2. 单链表插入结点。假设需要加入x结点，并且s指针指向x结点，故代码为 s − > n e x t = p − > n e x t ( 因 为 现 在 p 指 针 存 储 a 2 的 地 址 ) ， p − > n e x t = s s->next=p->next(因为现在p指针存储a2的地址)，p->next=s s−>next=p−>next(因为现在p指针存储a2的地址)，p−>next=s。
3. 双向链表的操作复杂，但也大同小异。
4. 在插入、删除节点时，要先获取到必要的指针，才能删除或添加。

链表的特点

1. 链表可以没有表示整体的对象，只需要用节点就够了。表示一整条链表可以用“头节点”，也就是第一个节点来表示整条链
2. 局限性：总是可以用一个节点的next指针走到下一个节点。而且大部分情况下只有这一种方法——链表没有下标，也不能直接跳转到某一环。只能从一个节点出发，一步一步往后挪
3. 查询慢：由于链表中地址不是连续的，每次查询元素都必须从头开始
4. 增删快：链表结构，增加/删除一个元素，对链表整体结构没有影响，所以增删快，与链表的长度无关
5. 查询困难：链表的查找需要从头遍历，与数组类似，越长速度越慢。但由于没有下标可用，链表的遍历实际上比数组更慢一些。

总结
随着编程语言的进步，在实践中直接使用链表的情况变得越来越少。
但是强烈推荐初学者在学习编程时，掌握好链表这种基础而强大的数据结构。能够理解它的原理，举一反三，从而领悟到更多相关的知识。

顺序存储与链式存储对比

从空间性能方面对比
1.存储密度：顺序存储的存储密度为1（更优），而链式存储的密度则小于1
2.容量分配：顺序存储信息需要多少空间需要事先确定才能够分配连续的空间，而链式存储能够动态更改容量的分配（更优）
从时间性能方面对比
1.查找运算：使用顺序存储比较方便。当内容没有顺序的前提下依次查找，两种方式的时间复杂度是一样的即 O ( n 2 ) O(\frac{n}{2}) O(2n​)，涉及到二分查找，顺序存储就更优一些。
2.读运算：即读取该位置的值。顺序存储时间复杂度为 O ( 1 ) O(1) O(1)（更优），因为a[5]就是数据值，链式存储时间复杂度为 O ( n + 1 2 ) O(\frac{n+1}{2}) O(2n+1​)，最好情况为1，最坏情况为n，因为链表的局限性。
3.插入运算：顺序存储的时间复杂度为 O ( n 2 ) O(\frac{n}{2}) O(2n​)，最好情况为0，最坏情况为n，而链式存储的时间复杂度为 O ( 1 ) O(1) O(1)（最优）。
4.删除运算：顺序存储的时间复杂度为 O ( n − 1 2 ) O(\frac{n - 1}{2}) O(2n−1​)，而链式存储的时间复杂度为 O ( 1 ) O(1) O(1)（更优）。

队列与栈

循环队列队满情况分析

1. 规定尾指针的下一个元素是头指针表示队满。如果说所有空间都存储上信息后，那么头指针与尾指针又安置到一起，导致队空和队满的条件相同。
2. 公式中取余是因为循环队列中会有弹出的操作，即头指针向后移动。故头指针可能不在下标为0的位置。

习题：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。
答：实际上，以某种次序入栈的元素出栈顺序是多种多样的。因为不一定要按照前进后出的规则来进行。abc、acb、bca、bac、cba五种情况。

复杂例题

解：队列是先进先出的，那么输出序列就是在队列中排列的数据，那么根据选项进行放入，得不到输出序列是D。

第四节.广义表

补充：

• 表头是最外层的第一个表的元素
• 表尾是除了第一层第一个元素之外的所有元素所组成的广义表。

例1，有广义表LS1=(a，(b，c)，(d，e))，则其长度为?深度为?
其长度为3层，深度为2层。
例2，有广义表LS1=(a，(b，c)，(d，e))，要将其中的 b 字母取出，操作就为 ?
先取表尾再取表头，最后再取表头。即 h e a d ( h e a d ( t a i l ( L S 1 ) ) ) head(head(tail(LS1))) head(head(tail(LS1)))

第五节.树与二叉树

树的概念

• 结点：图中的1、2、3…数字圆形都表示结点
• 结点的度：即一个结点的所有孩子结点个数称为度（如结点1的度就是2，结点3的度就是1）
• 树的度：即一个树当中，结点中度的最大值称为树的度
• 根结点：即树顶部的结点
• 叶子结点：没有孩子结点的结点（如结点4、5、7、8）
• 分支结点：有分支的结点（如结点1、2、6）
• 内部结点：不是根结点，也不是叶子结点的结点（如结点2、3、6）
• 父结点和子结点是一个相对的概念（如2和4而言，2是父节点，4是子节点）
• 兄弟结点：拥有同一个父结点的子节点之间称为兄弟结点，当然也存在当堂弟结点
• 层次：树的层次，该树有4个层次

二叉树的分类

• 二叉树：每个结点最多只有两个叶子结点的树
• 满二叉树：二叉树中所有非叶子结点的度都是2，且叶子节点都在同一层次上
• 完全二叉树：如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树
  也就是说，如果把满二叉树从右至左、从下往上删除一些节点，剩余的结构就构成完全二叉树
• 不完全二叉树：不是完全二叉树的树

二叉树的重要特性

补充

• 满二叉树每一层的结点个数能够组成等比数列
  第1、2两条的特性就是等比数列的通项公式 a n = a 1 ⋅ q n − 1 a_{n}=a_{1} \cdot q^{n-1} an​=a1​⋅qn−1和求和公式 S n = a 1 ( 1 − q n ) 1 − q ( q ≠ 1 ) S_{n}=\frac{a_{1}\left(1-q^{n}\right)}{1-q}(q \neq 1) Sn​=1−qa1​(1−qn)​(q​=1)的应用。
• 向下取整即比括号中还要小的整数。
• 第4条特性反映了为什么要按照层序编号。因为这样就能够通过当前结点确认父节点和左右子节点。以及能够极大的简便我们的运算。

二叉树的遍历

• 前序遍历：根结点、左子树结点、右子树结点
• 中序遍历：左子树结点、根结点、右树子结点
• 后序遍历：左子树结点、右子树结点、根节点
  顺序遍历关键在于根结点如何访问。
• 层次遍历：按层序编号进行遍历

• 图中前序遍历结果是12457836
• 图中中序遍历结果是42785136
• 图中后序遍历结果是48752631
• 图中层次遍历结果是12345678

反向构造二叉树

概念：知道一定的二叉树的遍历序列，然后反向推出二叉树的构造。
注：前序和中序或者中序和后序都能够将这个二叉树推出。

例题：  由前序序列为ABHFDECG； 中序序列为HBEDFAGC构造二叉树。  \text { 由前序序列为ABHFDECG； 中序序列为HBEDFAGC构造二叉树。 }  由前序序列为ABHFDECG； 中序序列为HBEDFAGC构造二叉树。 
解：根据前序序列能够知道二叉树的根结点，即为A，然后根据中序序列就能够知道左子树HBEDF和右子树GC，然后再看前序序列，左子树的根结点为B，右子树的根结点为C，那么根据中序序列可知G为左叶子结点，H也为左叶子结点，EDF在右子树上且F为右子树根结点，然后ED都为左结点。

对于普通的树其实没有太多人去做研究和分析，所以要想研究树一般的做法就是把普通的树转成二叉树进行分析和讨论。

树转二叉树

如何将普通的树转成二叉树呢？
这是有一个基本的原则。

• 树的某个结点的孩子结点转化成二叉树的左子树结点。
• 树的某个结点的兄弟结点转化成二叉树的右子树结点(右孩子结点)。
  

其实还有更简单的方法，即连线法。将兄弟结点连接起来，对于有多个孩子的只保留第一个孩子的连线，最后把树旋转就能够得到二叉树了。

查找(排序)二叉树

查找二叉树是一类特殊的二叉树，又称二叉排序树。
特点：①左孩子小于根 ②右孩子大于根

这种树的提出有什么价值和意义呢？
能够极大地提高查询的速度和效率。比方说采用顺序查找的方法需要按照顺序从前往后找到符合条件的；如果采用排序二叉树进行查找，先和根节点进行比较，然后根据比大还是比小来确定下一个比较的结点是根左子树根节点还是右子树结点。如果你构造的查找二叉树更均衡一些，查找速率就会提高。

• 插入运算：
  ①若该键值已存在，则不再插入，如上图插入48是不行的；
  ②若查找二叉树为空树，则以新结点为查找二叉树；
  ③将要插入结点键值与插入后父结点键值比较，就能确定新结点的位置是父结点的左子结点，还是右子结点。
• 删除结点
  ①若待删除结点是叶子结点，则直接删除；
  ②若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，如上图删除56；
  ③若待删除结点p有两个子结点，则在其左子树上，用中序遍历寻找键值最大的结点s，用结点s的值代替结点p的值，然后删除原结点s，结点s必属于上述(1)或(2)，按照这两种情况进行处理。

最优二叉树（哈夫曼树）

这种二叉树是一种工具，用于哈夫曼编码，哈夫曼树中每一个父结点的键值都等于其子结点之和(不是子树结点)。
哈夫曼编码有哪些用呢？
它是一种无损压缩编码的方式，能够将原始编码的长度变得更短一些，从而节省存储空间和传输带宽。
这种编码在多媒体领域的压缩技术当中经常使用到。

需要了解的基本概念：

• 树的路径长度：就是从根结点到叶子结点所经过的每段路径的个数之和。如下图中左边的树，结点15到结点2的路径长度为2
• 权：就是某个叶子结点的数值，代表着某一个字符出现的频度。
• 带权路径长度：就是某个树的路径长度乘以该路径的权值。如结点15到结点2的带权路径长度为 2 × 2 2 \times 2 2×2
• 树的带权路径长度（树的代价）：就是所有叶子结点的带权路径长度之和。
  

构造一个哈夫曼树需要达到什么样的效果呢？
要达到的效果就是让树的带权路径长度是最短的情况。就好比上图相同的几个结点(1、2、3、4、7、8、15)构成的树的带权路径长度是不相同的。

例：假设有一组权值 5,29,7,8,14,23,3,11请尝试构造哈夫曼树。
首先我们应该从数列当中选择权值最小的两个数垒上去，这时权重序列发生变化，将3和5取出和将8放入，这时权值序列为29,7,8,14,23,11, 8。接着继续选择权值最小的两个数7和8，这时权重序列发生变化，将7和8取出和将15放入，这时权值序列为29,14,23,11, 8, 15。接着继续选择权值最小的两个数8和11，这时发现需要另开一个子树，权重序列发生变化，将8和11取出和将19放入，这时权值序列为29,14, 23, 15, 19。依次类推，一层一层往上垒即可。

通过这个例题和图，我们知道了为什么树的带权路径长度只包含叶子节点的带权路径长度之和，而没有加上中间结点的带权路径长度呢？因为只有叶子节点才是初始权重集合，所有的中间结点是构造哈曼夫树时产生的中间产物。

线索二叉树

概念：就是在二叉树的基础上，会有很多的虚线的渐显将结点连接起来。

为什么要有线索二叉树呢？
在二叉树当中，很多结点是属于空闲的状态。很多指针都是空的，它们没有被利用起来。比如下图的二叉树的D结点的左指针和右指针都是空的，E结点的右指针是空的等等。

人们就想能不能把这些空闲的资源利用起来呢？
利用起来方便树的遍历。正是因为方便遍历，所以就提出了前序线索、中序线索、后序线索。

线索二叉树的表示

如何将二叉树转化为线索二叉树呢？
以前序线索二叉树为例。前序线索二叉树的箭头是按前序遍历生成的。当前结点的左指针形成绿色箭头指向前序遍历的前驱结点，当前结点的右指针形成红色箭头指向前序序列的后继结点。前提条件是该指针是空闲的。
上图中前序线索二叉树的前序序列：ABDEHCFGI。

平衡二叉树

平衡二叉树的提出原因
同样的一个序列，排序二叉树可能有多颗，形态不一样（如下方例题）。而排序二叉树提出的目的就是为了查询方便。一个排序二叉树越平衡，查询效率就越高，所以这里就有了平衡二叉树的定义。

平衡二叉树的定义
①任意结点的左右子树深度不能相差超过1
②每结点的平衡度只能为-1、0或1

每个结点的平衡度如何求？
对于所有叶子结点而言，平衡度都为0。因为叶子结点的左子树深度为0，右子树深度为0，左子树的深度减去右子树的深度即为该结点的平衡度。深度就是层数，即要求当前结点的平衡度就是拿左子树的深度减去右子树的深度即为平衡度。

平衡树的建立过程
对于不平衡的二叉树需要做相应的调整才能够达到这种平衡度。找中位数构造，中位数作为根节点，然后再找左右子树的中位数，并且遵循查询二叉树的规则。

例：对数列 { 1 , 5 , 7 , 9 , 8 , 39 , 73 , 88 } \{1,5,7,9,8,39,73,88\} {1,5,7,9,8,39,73,88} 构造排序二叉树，可以构造出多棵形式不同的排序二叉树。
答：显然右边构成的是平衡二叉树。

第六节.图

图的基本概念

图分成无向图和有向图。
完全图
⋆ \star ⋆在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图 (complete graph )
⋆ \star ⋆在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。

图的存储-邻接矩阵(用的比较少，浪费空间， O ( n 2 ) O(n^{2}) O(n2))

图的存储-邻接表(用的最多)

用链表的方式存储与当前结点相连的结点的距离和结点序号。

图的遍历

深度优先遍历=前序遍历，广度优先遍历=层次遍历。

结合存储的结构来看图的遍历

• 深度优先遍历：v0, v4,v6,v7到这里深度就走到底了，然后回馈到v1然后再继续深入即可。
• 广度优先遍历：先访问v0,v4,v3,v1，因为这时v0所邻接的一系列结点，将链表中的结点全部访问完然后开始访问v4的邻接结点，依次类推即可。
  

拓扑排序

拓扑排序实际上就是用一个序列来表达事件执行的先后顺序。拓扑排序可能产生多个序列。
因为在项目中会有多个活动完成的任务，这些任务之间可能存在一定的约束关系，我们可以通过拓扑排序将任务按照先后顺序进行排列。

我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示 活动网络，简称AOV网络。
上图的拓朴序列有 : 02143567 ， 01243657 ， 02143657 ， 01243567。
如何求拓扑排序呢？
从入度为0的结点开始，选择后将该结点的出度的箭头删除，接着寻找入度为0的结点，这时入度为0的结点可能有很多，代表着拓扑序列会有多种情况。然后依次类推即可。
入度表示有几个约束。只要入度为0就表示没有约束可以执行。

图的最小生成树

图的最小生成树就是把图的若干条边去掉，留下若干条边能够将所有结点连接起来并且留下来的边的权值之和最小，那么剩下的边和点就构成了图的最小生成树。

探讨树和图有什么区别呢？
树和图最大的一个区别就是树没有环路。
树的边和结点有一个特点：就是一棵树的结点是n，那么这棵树的边的条数最多就是n - 1。
如果边的条数是n的话，那么该结构就是一个图。

如何求最小生成树呢？
原则：从n个结点的图中选出n-1条边作为树的枝，这n-1条边的权重之和最小的情况就是最小生成树。
</font color=“red”>注意：选择的边时有一个原则——不能够形成环。

标准已经定了，这里有两种算法能够解决这样的问题。

普里姆算法

以下图为例，从结点A出发，把结点A纳入到红点集，其它结点纳入到蓝点集，然后从红点集到蓝点集的边中选择最短的距离并连接起来，这时连接的边中蓝点集的点将被纳入到红点集中，直到选出5条边为止。注意：选择的边不能构成环。

克鲁斯卡尔算法

以下图为例，首先选择5条最短的边，注意不能够构成环，如果构成环，就退而求次选择次短的边或者其它相同的边。

第七节.算法基础

算法的特性

• 有穷性：执行有穷步之后结束。
• 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清。
• 算法必须有0个或者0个以上的输入。
• 算法必须有1个或者1个以上的输出。
• 有效性：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0，b/a就无效

补充：随机函数也具有确定性。 因为计算没有标准输入，随机函数也会从系统中获取到某些信息作为输入。所有的算法都应该具有确定性，否则这个算法是没有价值的无意义的。

算法的复杂度

算法的复杂度包括 时间复杂度（必考）和空间复杂度。

时间复杂度是指程序运行从开始到结束所需要的时间。
通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，在算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。
其定义如下：
如 果 存 在 两 个 常 数 c 和 m ， 对 于 所 有 的 n ， 当 n ≥ m 时 有 f ( n ) ≤ c g ( n ) ， 则 有 f ( n ) = O ( g ( n ) ) 。 也 就 是 说 ， 随 着 n 的 增 大 ， f ( n ) 渐 进 地 不 大 于 g ( n ) 。 例 如 ， 一 个 程 序 的 实 际 执 行 时 间 为 T ( n ) = 3 n 3 + 2 n 2 + n ， 则 T ( n ) = O ( n 3 ) 。 常 见 的 对 算 法 执 行 所 需 时 间 的 度 量 : O ( 1 ) < O ( log ⁡ 2 n ) < O ( n ) < O ( n log ⁡ 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) 如果存在两个常数 c 和 m ，对于所有的 n ，当 n \geq m 时有 f(n) \leq c g(n) ， 则有 f(n)=O(g(n)) 。也就是说，随着 n 的增大， f(n) 渐进地不大于 \mathbf{g}(\mathbf{n}) 。\\ 例如，一个程序的实际执行时间为 \mathrm{T}(\mathbf{n})=3 \mathbf{n}^{3}+2 \mathbf{n}^{2}+\mathbf{n} ，则 \mathrm{T}(\mathrm{n})=\mathrm{O}\left(\mathrm{n}^{3}\right) 。\\ 常见的对算法执行所需时间的度量 :O(1)<O\left(\log _{2} n\right)<O(n)<O\left(n \log _{2} n\right)<O\left(n^{2}\right)<O\left(n^{3}\right)<O\left(2^{n}\right) 如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n3+2n2+n，则T(n)=O(n3)。常见的对算法执行所需时间的度量:O(1)<O(log2​n)<O(n)<O(nlog2​n)<O(n2)<O(n3)<O(2n)

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

第八节.数据的查找

顺序查找

1. 顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素 进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则 查找失败。
2. 查找成功时, 顺序查找的平均查找长度为 (等概率情况下):
   A S L = ∑ i = 1 n P i ∗ ( n − i + 1 ) = 1 + 2 + L + n n = n + 1 2 \mathrm{ASL}=\sum_{i=1}^{n} P_{i}^{*}(n-i+1)=\frac{1+2+\mathrm{L}+n}{n}=\frac{n+1}{2} ASL=i=1∑n​Pi∗​(n−i+1)=n1+2+L+n​=2n+1​
   等差数列求平均数即第一项+最后一项除以2即得平均数。
3. 顺序查找的时间复杂度：O(n)
4. 顺序查找的优缺点：常见而简单的查找方式，但是整体的效率不高。

二分查找

1. 该查询的使用前提是该序列的关键字是有序排列的。(如从小到大或从大到小) ，故不是所有序列都能用二分查找。
2. 折半查找在查找成功时关键字的比较次数最多为 ⌊ log ⁡ 2 n ⌋ + 1 \left\lfloor\log _{2} n\right\rfloor+1 ⌊log2​n⌋+1次。
3. 折半查找的时间复杂度为 O ( log ⁡ 2 n ) O\left(\log _{2} n\right) O(log2​n) 。
4. 二分查找的优缺点：查询效率比顺序查找要高，而且查找的数据越多，相比顺序查找的优势越明显。

【 例 题 】 请 给 出 在 含 有 12 个 元 素 的 有 序 表 { 1 , 4 , 10 , 16 , 17 , 18 , 23 , 29 , 33 , 40 , 50 , 51 } 中 二 分 查 找 关 键 字 17 的 过 程 。 【例题】请给出在含有12个元素的有序表 \{1,4,10,16,17,18,23,29,33 , 40,50,51\} 中二分查找关键字 17 的过程。 【例题】请给出在含有12个元素的有序表{1,4,10,16,17,18,23,29,33,40,50,51}中二分查找关键字17的过程。

注意
二分查找每次都跟中间的数进行比较，但需要注意细节。

1. mid的值为 最 小 坐 标 + 最 大 坐 标 2 \frac{最小坐标+最大坐标}{2} 2最小坐标+最大坐标​（商如果带有小数需要取整）
2. mid所对应的位置已经比较过，肯定不能纳入到下一次比较的区间当中，所以下一次的区间是[low，mid-1]或者[mid+1，high]。

散列（hash）表

散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一 个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T [0…n-1] (n<<m) 中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。

为什么说“散列表是一种按内容存储的机制”呢？
就好比很多人住酒店，常规的情况是张三住哪号房，李四住哪号房，查找某个人住哪一号房的时候，首先应该定位到张三这一条记录，然后再看张三所住的房号是多少。顺序查找和二分查找都是按这种顺序进行查找的。而散列就不是这样子，它是在存储的时候就已经想好一定的规则存储到相应的空间中，查找的时候就很方便。如按照笔画进行存储，张三的笔画数中间加个0即703号房间。如果我们这样做，在查找房间号时，我们就可以根据刚才的规则再算一遍即可。不用再去查表了。

散列表冲突的解决方法

• 开放定址法是指当构造散列表发生冲突时，使用某种探测手段，产生一个 探测的散列地址序列，并且逐个查找此地址中是否存储了数据元素，如果 没有，则称该散列地址开放，并将关键字存入，否则继续查找下一个地址。 只要散列表足够大，总能找到空的散列地址将数据元素存入。（重点）
• 线性探测法
• 伪随机数法

散列表会出现冲突，出现冲突就需要调整空间，调整空间使得效率降低。
那么如何提高效率呢？

• 对哈希函数进行精心的设计，这样效率才能提高。
• 扩大映射区间，这样冲突的概率就会减小。

例： 记 录 关 键 码 为 ( 3 ， 8 ， 12 ， 17 ， 9 ) ， 取 m = 10 ( 存 储 空 间 为 10 ) ， p = 5 ， 散 列 函 数 h = k e y % p 。 记录关键码为 (3 ， 8 ， 12 ， 17 ， 9) ，取 m=10 (存储空间为10) ， \mathrm{p}=5 ，散列函数 \mathrm{h}=\mathrm{key} \% \mathrm{p} 。 记录关键码为(3，8，12，17，9)，取m=10(存储空间为10)，p=5，散列函数h=key%p。

第九节.数据的排序

ps：上午和下午都会考到排序

排序的概念

稳定与不稳定排序
21 32 13 45 27 38 76 21 \begin{array}{llllllll} 21 & 32 & 13 & 45 & 27 & 38 & 76 & {\color{Red} 21} \end{array} 21​32​13​45​27​38​76​21​

• 稳定排序能够使红色的21一直保持在黑色的21后面。
• 不稳定排序可能会将红色的21放置到黑色的21前面。

内排序与外排序

• 内排序：指在排序期间数据对象全部存放在内存的排序。
• 外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

排序方法多种多样，因为排序应用是非常广泛的，所以人们对排序的研究非常深入，才产生了非常多的排序算法。

排序方法分类

直接插入排序

直接插入排序 : 即当插入第 i \mathrm{i} i 个记录时， R 1 ， R 2 ， … , R i − 1 \mathbf{R}_{1} ， \mathbf{R}_{2} ， \ldots, \mathbf{R}_{\mathrm{i}-1} R1​，R2​，…,Ri−1​ 均已排好序，因此，将第 i \mathrm{i} i 个记录 R i \mathbf{R}_{\mathbf{i}} Ri​ 依次与 R i − 1 ， ⋯   , R 2 , R 1 \mathbf{R}_{\mathbf{i}-1} ， \cdots, \mathbf{R}_{\mathbf{2}}, \mathbf{R}_{\mathbf{1}} Ri−1​，⋯,R2​,R1​ 进行比较，找到合适的位置插入。它简单明了，但 速度很慢。

基本工序
先比较前面两个数进行排序，接下来就是按照上述概念进行排序了。

希尔排序

希尔 (Shell) 排序 : 先取一个小于 n 的整数 d 1 d_{1} d1​ 作为第一个增量，把文件的全部记录分 成 d 1 \boldsymbol{d}_{1} d1​ 个组。所有距离为 d 1 \boldsymbol{d}_{1} d1​ 的倍数的记录放在同一个组中。先在各组内进行直接插入排序； 然后，取第二个增量 d 2 < d 1 d_{2}<d_{1} d2​<d1​ 重复上述的分组和排序，直至所取的增量 d t = 1 为 止 ( d t < d t − 1 < ⋯ < d 2 < d 1 ) d_{t}=1为止\left(d_{t}<d_{t-1}\right. \left.< \dots <\boldsymbol{d}_{2}<\boldsymbol{d}_{1}\right) dt​=1为止(dt​<dt−1​<⋯<d2​<d1​) ，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

基本工序

经过前面两轮的排序之后，整个序列就变得基本有序。当增量d为1时就使用直接插入排序，元素挪动的位置就大大减少了。因为我们能够明显的看到偏小的数都在前面的区间，偏大的数都在后面的区间，所以直接插入排序时你不需要比较很多次。这是在统计学中做过分析和研究的。

注：希尔排序的效率比整个数据使用直接插入排序的效率要高。尤其当数据量比较大时，就更加明显，这也是希尔排序提出的原因——代替直接插入排序处理数据量大的场景。

直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换 ⋯ ⋯ \cdots \cdots ⋯⋯依次类推，直到所有记录排完为止。过程如图所示，使用括号阔出来的部分是有序的。

堆排序

在学习堆排序之前，首先需要了解堆的含义：在含有 n 个元素的序列中，如果序列中的元素满足下面其中一种关系时，此序列可以称之为堆。

1. k i ≤ k 2 i 且 k i ≤ k 2 i + 1 k_{i} ≤ k_{2i} 且 k_{i} ≤ k_{2i+1} ki​≤k2i​且ki​≤k2i+1​（在 n 个记录的范围内，第 i 个关键字的值小于第 2i 个关键字，同时也小于第 2i+1 个关键字）
2. k i ≥ k 2 i 且 k i ≥ k 2 i + 1 k_{i} ≥ k_{2i} 且 k_{i} ≥ k_{2i+1} ki​≥k2i​且ki​≥k2i+1​（在 n 个记录的范围内，第 i 个关键字的值大于第 2i 个关键字，同时也大于第 2i+1 个关键字）

其中1称为小顶堆，2称为大顶堆。

对于堆的定义也可以使用完全二叉树来解释，因为在完全二叉树中第 i 个结点的左孩子恰好是第 2i 个结点，右孩子恰好是 2i+1 个结点。如果该序列可以被称为堆，则使用该序列构建的完全二叉树中，每个根结点的值都必须不小于（或者不大于）左右孩子结点的值。

以无序表{49，38，65，97，76，13，27，49}来讲，其对应的堆用完全二叉树来表示为：

提示：堆用完全二叉树表示时，其表示方法不唯一，但是可以确定的是树的根结点要么是无序表中的最小值，要么是最大值。

通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，取出次大值或者次小值，如此反复执行就可以得到一个有序序列，此过程为堆排序。

堆排序过程的代码实现需要解决两个问题：

1. 如何将得到的无序序列转化为一个堆？
2. 在输出堆顶元素之后（完全二叉树的树根结点），如何调整剩余元素构建一个新的堆？

首先先解决第 2 个问题。上图所示为一个完全二叉树，若去除堆顶元素，即删除二叉树的树根结点，此时用二叉树中最后一个结点 97 代替，如下图所示：

此时由于结点 97 比左右孩子结点的值都大，破坏了堆的结构，所以需要进行调整：首先以 堆顶元素 97 同左右子树比较，同值最小的结点交换位置，即 27 和 97 交换位置：

由于替代之后破坏了根结点右子树的堆结构，所以需要进行和上述一样的调整，即令 97 同 49 进行交换位置：

通过上述的调整，之前被破坏的堆结构又重新建立。从根结点到叶子结点的整个调整的过程，被称为“筛选”。

解决第一个问题使用的就是不断筛选的过程，如下图所示，无序表{49，38，65，97，76，13，27，49}初步建立的完全二叉树，如下图所示：

在对上图做筛选工作时，规律是从底层结点开始，一直筛选到根结点。对于具有 n 个结点的完全二叉树，筛选工作开始的结点为第 ⌊n/2⌋个结点（此结点后序都是叶子结点，无需筛选）。
所以，对于有 9 个结点的完全二叉树，筛选工作从第 4 个结点 97 开始，由于 97 > 49 ,所以需要相互交换，交换后如下图所示：

然后再筛选第 3 个(即⌊n/2⌋ - 1)结点 65 ，由于 65 比左右孩子结点都大，则选择一个最小的同 65 进行交换，交换后的结果为：

然后筛选第 2 个(即⌊n/2⌋ - 2)结点，由于其符合要求，所以不用筛选；最后筛选根结点 49 ，同 13 进行交换，交换后的结果为：

交换后，发现破坏了其右子树堆的结构，所以还需要调整，最终调整后的结果为：

堆排序由于利用到了树的数据结构，因此效率要比直接选择排序高很多。
堆排序应用在什么场合比较好呢？
就是n个元素，我不需要对所有元素进行排序，只需要求出前m个最值即可。因为堆排序每一轮会选择出一个最值，而且是很高效的选择出来。

冒泡排序

冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。缺点就是要频繁的读写数据。

基本工序
一组数据中若有n个元素，对其采用冒泡排序：将第n个元素与第n-1个元素进行比较，若第n个元素较小，则将其与第n-1个元素交换位置，再将n-1位置的元素与第n-2位置的元素进行比较…重复该操作即可。

快速排序

快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归的方式解决这些子问题，然后再将这些子问题的解组成原问题的解。

快速排序通常包括两个步骤：
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为基准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。
第二步，采用相同的方式对左、右两组分别进行排序，直到所有记录都排到相应的位置为止。

图示过程
定义两个指针，先指向左边第一个数，再指向右边第一个数，再指向左边第二个数，再指向右边第二个数…（保证基准始终在一个指针上）
将基准与另一个指针指向的数进行比较，若该数小于基准，则和基准交换位置并且基准的指针移动一格；若大于基准则不用交换并且另一个指针向右移动一格。
最后将得到一个以基准为分割的序列，右边大于基准的数组集合，左边小于基准的数组集合。

归并排序

归并也称合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。

图注
首先两两分组，每两个一组进行相应的排序，然后是每两组数据进行归并，这时如何进行操作呢？合并的过程是：比较A[i]与A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到第一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。经过多轮的归并最终就得到一个完整的有序表。

为什么说归并排序的效率高呢？
因为对有序表进行合并要比对无序表进行合并的效率高，归并虽然看上去元素比较多，但事实上归并速度是很快的。

为什么将问题拆分成若干个小的问题呢？
从之前学过的多种排序算法都可以看出一种共同的思想就是排序算法在很多地方都是把问题规格缩小来解决问题，为什么呢？当问题不断扩大的时候，你所消耗的时间不一定是按照线性增长的，它们可能是按照几何级数增长的，所以一定要想办法将问题拆成更小的问题，虽然看着问题很多，但是每个问题规模很小耗时会短一些，这就是归并排序。

基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。
基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。
基数的选择和关键字的分解是根据关键字的类型来决定的， 例如关键字是十进制数，则按个位、十位来分解。也可以说基数排序会关键字拆成多个维度的东西。

这个序列的排序视角就是先排个位，再排十位，最后是百位。
先排个位，使用hash函数及拉链法进行操作，hash函数就是 h = k e y % 10 \mathrm{h}=\mathrm{key} \% \mathrm{10} h=key%10，然后排十位时，这时序列顺序就发生了变化，还是按照个位的方法进行操作，hash函数就是 h = k e y / 10 % 10 \mathrm{h}=\mathrm{key} / \mathrm{10} \% \mathrm{10} h=key/10%10，以此类推即可。最后按照存储的顺序和链表的顺序进行排序即可。