DS数据结构
在复习过程中，要特别注意以下重点知识点：
线性表：包括顺序表和链表的存储结构、基本操作以及应用场景。
栈与队列：掌握栈和队列的特性、存储结构、基本操作以及它们在算法中的应用。
树与二叉树：理解树和二叉树的定义、性质、存储结构以及遍历算法。特别要注意二叉树的特殊类型（如二叉搜索树、平衡二叉树等）及其操作。
图：了解图的定义、存储结构（如邻接矩阵、邻接表等）以及遍历算法（如深度优先搜索、广度优先搜索等）。
查找与排序：掌握各种查找算法（如顺序查找、二分查找等）和排序算法（如冒泡排序、快速排序、归并排序等）的原理、实现以及性能分析。
基本概念
线性表
一、线性表的定义与性质
定义：线性表是由零个或多个数据元素组成的有限序列。
性质：
线性表中的元素之间是有序的，即存在唯一的第一个元素和唯一的最后一个元素。
除第一个元素之外，每个元素有且仅有一个直接前驱。
除最后一个元素之外，每个元素有且仅有一个直接后继。
二、线性表的存储结构
顺序存储结构（顺序表）：
线性表的顺序存储是用一段地址连续的存储单元依次存储线性表的数据元素。
特点：逻辑上相邻的元素在物理位置上也相邻；可以随机存取表中任一元素。
缺点：插入和删除操作需要移动大量元素；预先分配的空间可能浪费或不足。
链式存储结构（链表）：
线性表的链式存储是用一组任意的存储单元存放线性表的元素。
每个元素称为一个结点，每个结点除包含元素本身的信息外，还包括指向其后继元素的指针。
特点：插入和删除操作不需要移动元素；存储空间动态分配，不会浪费也不会不足。
缺点：不能随机存取表中任一元素，只能从头结点开始顺序访问。
链表有多种形式，如单链表、双链表、循环链表等。
三、线性表的基本操作
初始化：创建一个空的线性表。
销毁：销毁一个线性表，释放其占用的存储空间。
插入：在线性表的指定位置插入一个新元素。
删除：删除线性表的指定位置的元素。
查找：查找线性表中是否存在某个特定元素，若存在则返回其位置。
遍历：依次访问线性表中的每个元素。
四、线性表的应用
数组：可以看作是线性表的顺序存储结构的一种特殊形式，常用于存储固定大小的同类型数据。
栈和队列：栈和队列都是线性表的特殊形式，具有特定的操作规则和应用场景。
多项式表示：可以用线性表来表示多项式，其中每个元素表示一个多项式项。
其他应用：如稀疏矩阵的压缩存储、图的邻接表表示等。
五、线性表的性能分析
时间复杂度：分析各种操作（如插入、删除、查找等）在最坏情况下的时间复杂度。
空间复杂度：分析线性表存储结构所占用的存储空间。
六、线性表的扩展与变形
静态链表：用数组来实现链表的功能，通过数组的下标来模拟指针的指向。
动态数组：在顺序表的基础上，通过动态分配和释放存储空间来实现动态大小的线性表。
循环链表：将链表的尾结点指向头结点，形成一个循环结构。
双向链表：每个结点包含指向前驱和后继的指针，可以方便地实现双向遍历。
栈、队列
一、栈（Stack）
定义与特性
栈是一种后进先出（LIFO，Last In First Out）的线性表。
栈只允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端则被称为栈底。
栈的主要操作包括初始化栈、判断栈是否为空、进栈（Push）、出栈（Pop）、读取栈顶元素等。
存储结构
栈可以采用顺序存储结构（顺序栈）或链式存储结构（链栈）。
顺序栈使用一组地址连续的存储单元存放栈中元素，并利用栈顶指针指示当前栈顶元素的位置。
链栈则采用链表的形式来实现，栈顶指针指向链表的表头。
特殊栈
共享栈：为了更有效地利用存储空间，可以让两个顺序栈共享一个一维数组空间。将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
栈的应用：栈在括号匹配、表达式求值、递归调用等场景中有着广泛的应用。
二、队列（Queue）
定义与特性
队列是一种先进先出（FIFO，First In First Out）的线性表。
队列允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。
队列的主要操作包括初始化队列、判断队列是否为空、入队（Enqueue）、出队（Dequeue）、读取队头元素等。
存储结构
队列同样可以采用顺序存储结构（顺序队列）或链式存储结构（链队列）。
顺序队列通常使用循环队列来实现，以充分利用存储空间。
链队列则采用链表的形式来实现，队头指针和队尾指针分别指向链表的表头和表尾。
特殊队列
双端队列：允许在队列的两端都进行插入和删除操作。
队列的应用：队列在任务调度、消息传递、广度优先搜索（BFS）等场景中有着广泛的应用。
三、栈与队列的比较
| 栈（Stack） | 队列（Queue） | |
|---|---|---|
| 定义与特性 | 后进先出（LIFO） | 先进先出（FIFO） |
| 操作限制 | 只能在栈顶进行插入和删除操作 | 只能在队尾进行插入操作，在队头进行删除操作 |
| 存储结构 | 顺序栈、链栈 | 顺序队列（循环队列）、链队列 |
| 特殊类型 | 共享栈 | 双端队列 |
| 应用场景 | 括号匹配、表达式求值、递归调用等 | 任务调度、消息传递、广度优先搜索（BFS）等 |
四、栈与队列的共同点
栈和队列都是线性表的一种特殊形式，它们的逻辑结构都与线性表相同，只是操作规则上有所不同。
栈和队列都可以采用顺序存储结构或链式存储结构来实现。
栈和队列在算法和数据结构设计中都有着广泛的应用，是解决特定问题的重要工具。
串、矩阵、广义表
一、串（字符串）
定义与性质
串是由零个或多个字符组成的有限序列。
串的长度是指串中字符的个数，空串的长度为0。
串中任意多个连续的字符组成的子序列称为该串的子串。
存储结构
定长顺序存储：使用固定长度的字符数组来存储串。
堆分配存储：使用动态分配的字符数组来存储串，可以根据需要调整串的长度。
块链存储：使用链表结构来存储串，每个节点包含多个字符，以提高存储密度。
基本操作
初始化、判空、求长、复制、连接、求子串、比较、定位等。
串的基本操作通常以子串作为操作对象。
模式匹配
朴素模式匹配算法（BF算法）：通过遍历主串和模式串来查找匹配位置。
KMP算法：利用已经部分匹配的结果来加快模式串的滑动速度，提高匹配效率。
二、矩阵
定义与性质
矩阵是一个按照长方阵列排列的复数或实数集合。
矩阵的行数和列数可以确定矩阵的维度。
存储结构
二维数组：矩阵最常用的存储结构，按行优先或列优先存储元素。
压缩存储：对于特殊矩阵（如对称矩阵、三角矩阵、稀疏矩阵等），可以采用压缩存储来节省空间。
特殊矩阵
对称矩阵：矩阵中的元素满足a[i][j]=a[j][i]，可以采用一维数组按行优先或列优先存储上三角（或下三角）元素。
三角矩阵：分为上三角矩阵和下三角矩阵，可以只存储上三角（或下三角）元素。
稀疏矩阵：矩阵中非零元素的个数相对矩阵元素的个数来说非常少，可以采用三元组、邻接表或十字链表等表示法。
三、广义表
定义与性质
广义表是线性表的推广，由零个或多个单元素或子表组成的有限序列。
广义表的元素可以是原子（不可再分的单元素）或子表（广义表）。
表示方法
广义表通常采用递归的方式来表示，即广义表中的元素本身又可以是一个广义表。
基本操作
求表头：非空广义表的第一个元素称为表头。
求表尾：除表头元素之外，由其余元素所构成的表称为表尾，表尾一定是一个表。
存储结构
由于广义表是递归的，且元素可以是子表，因此通常采用链式存储结构（如头尾链表或扩展线性表）来表示广义表。
总结
串：主要用于处理文本数据，支持各种字符串操作，模式匹配是其重要应用之一。
矩阵：在数学、物理、工程等领域有广泛应用，特殊矩阵的压缩存储是重要知识点。
广义表：用于表示具有层次结构的数据，其递归性和链式存储结构是其特点。
树与二叉树
一、树的基本概念与性质
树的定义：树是n个节点的有限集（n≥0），当n=0时，称为空树。在任意一个非空树中，有且只有一个根节点，其余节点可以分为m个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。
节点关系：包括双亲（父节点）、孩子、兄弟、祖先、子孙等。
树的度：树中节点的最大度数称为树的度。
节点深度与高度：节点的深度是从根节点到该节点的唯一路径上的节点数（从1开始计数）；节点的高度是以该节点为根的子树的高度。
树的路径长度：从根节点到树中每一个节点的路径长度之和。
有序树与无序树：有序树中，节点的子树是有序的；无序树中，节点的子树是无序的。
二、二叉树及其性质
二叉树定义：二叉树是n个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
二叉树性质：
在二叉树的第i层上至多有2^(i-1)个节点（i≥1）。
深度为k的二叉树至多有2^k-1个节点（k≥1）。
对于一棵非空二叉树，如果度为0的节点数为n0，度为2的节点数为n2，则n0=n2+1。
特殊二叉树：
满二叉树：一棵深度为h的满二叉树有2^h-1个节点，且每一层上的节点数都达到最大。
完全二叉树：若设二叉树的深度为h，除第h层外，其它各层的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。
三、二叉树的遍历
遍历定义：遍历是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。
遍历方式：
前序遍历：根节点-左子树-右子树。
中序遍历：左子树-根节点-右子树。
后序遍历：左子树-右子树-根节点。
层序遍历：按照树的层次从上到下、从左到右进行遍历。
四、线索二叉树
定义：为了加快在二叉树中查找节点前驱和后继的速度，在每个节点中，除了存放节点值本身外，还增加两个指示器，分别指示当前节点的前驱和后继节点。
类型：前序线索二叉树、中序线索二叉树、后序线索二叉树。
五、树与二叉树的转换及存储
树转换为二叉树：
每个节点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。
由于根节点没有兄弟，所以树转换得到的二叉树没有右子树。
二叉树转换为树：逆着树转换为二叉树的过程即可。
树的存储结构：包括双亲表示法、孩子表示法、孩子兄弟表示法等。
六、树与森林的遍历
树的遍历：先根遍历（对应二叉树的前序遍历）、后根遍历（对应二叉树的中序遍历）。
森林的遍历：先序遍历森林（先访问森林中第一棵树的根节点，然后依次遍历第一棵树中根节点的子树森林，最后遍历除去第一棵树之后剩余的树构成的森林）、中序遍历森林（先遍历第一棵树中根节点的子树森林，然后访问第一棵树的根节点，最后遍历除去第一棵树之后剩余的树构成的森林）。
七、树的应用
哈夫曼树：用于数据压缩，通过构建哈夫曼树并生成哈夫曼编码，可以实现对数据的无损压缩。
并查集：用于处理一些不交集的合并及查询问题，如网络连通性判断等。
图
一、基本概念
图的定义：图G由顶点集V和边集E组成，记为G=(V,E)。图不能为空，但边集可以为空。
有向图和无向图：有向图的边有方向，用<v,w>表示，v为弧尾，w为弧头；无向图的边没有方向，用(v,w)或(w,v)表示。
简单图、多重图、完全图：简单图不存在重复边和顶点到自身的边；多重图允许两个顶点间有多条边，且顶点可以和自己关联；完全图则是任意两个顶点之间都存在边（有向完全图则是有向边）。
顶点的度、入度和出度：无向图中，顶点的度是与该顶点相连的边的数量；有向图中，顶点的入度是指向该顶点的边的数量，出度是从该顶点出发的边的数量。
路径、回路、路径长度：路径是顶点之间的序列；回路是起点和终点相同的路径；路径长度是路径上边的数量。
连通、强连通：在无向图中，若任意两个顶点之间都存在路径，则图是连通的；在有向图中，若任意两个顶点之间都存在双向路径，则图是强连通的。
子图、生成子图：若图G'的顶点集和边集分别是图G的顶点集和边集的子集，则G'是G的子图。若子图包含原图的所有顶点，则称为生成子图。
连通分量、强连通分量：无向图中的极大连通子图称为连通分量；有向图中的极大强连通子图称为强连通分量。
生成树、生成森林：连通图的生成树是包含图中所有顶点且边数最少的连通子图；非连通图的连通分量的生成树构成了该图的生成森林。
边的权、带权图：边上带有权值的图称为带权图，权值可以表示距离、成本等。
二、图的存储
邻接矩阵：用一个二维数组存储图中顶点的邻接关系。无向图的邻接矩阵是对称的，有向图则不一定。空间复杂度为O(n^2)，适合稠密图。
邻接表：对每个顶点建立一个单链表，链表中存储与该顶点相邻的顶点。空间复杂度为O(n+e)，适合稀疏图。
十字链表：用于存储有向图，可以方便地表示顶点的出度和入度。
邻接多重表：用于存储无向图，可以方便地表示两条边之间的共享顶点。
三、图的遍历
深度优先搜索（DFS）：从某个顶点出发，沿着未访问过的边尽可能深地搜索，直到无法继续，然后回溯并继续搜索其他未访问的顶点。
广度优先搜索（BFS）：从某个顶点出发，先访问其所有邻接顶点，再依次访问这些邻接顶点的未访问邻接顶点，直到所有顶点都被访问。
四、图的应用
最小生成树：在加权无向图中，找到一棵包含所有顶点且边权值之和最小的生成树。常用的算法有Prim算法和Kruskal算法。
最短路径：在加权图中，找到从一个顶点到另一个顶点的路径，使得路径上边的权值之和最小。常用的算法有Dijkstra算法和Floyd算法。
拓扑排序：对有向无环图（DAG）进行顶点排序，使得对于每一条有向边<u,v>，顶点u在排序中都出现在顶点v之前。
关键路径：在带权有向无环图（AOE网）中，找到从源点到汇点的最长路径，该路径决定了整个工程的完成时间。
有向无环图表达式：利用有向无环图来表示和计算表达式的值，如中缀表达式转后缀表达式、表达式求值等。
排序
一、排序的基本概念
排序：将一组数据按某种逻辑顺序重新排列的过程。
关键字：数据元素中用作比较的依据的字段。
稳定性：排序过程中，如果两个数据元素的关键字相等，排序前后它们的相对位置不变，则称这种排序方法是稳定的，否则是不稳定的。
内部排序与外部排序：内部排序是在内存中进行的排序，外部排序是由于数据量过大，不能全部放入内存，需要在内存和外部存储设备（如磁盘）之间多次交换数据进行排序。
二、插入排序
直接插入排序：将未排序的数据元素逐个插入到已排序的序列中，从而得到一个新的、元素增加1的已排序序列。时间复杂度为O(n^2)，但在最好情况下（即数据已经接近有序）时间复杂度为O(n)。
折半插入排序：在直接插入排序的基础上，使用折半查找确定插入位置，从而减少比较次数。然而，由于移动元素的次数没有改变，所以时间复杂度仍为O(n^2)。
希尔排序：又称缩小增量排序，是插入排序的一种优化。通过设定间隔序列，将待排序序列分成若干子序列分别进行直接插入排序，然后逐步缩小间隔，直至间隔为1，最后再进行一次直接插入排序。时间复杂度与间隔序列的选取有关，最好情况下为O(nlogn)，最坏情况下为O(n^2)。
三、交换排序
冒泡排序：通过重复遍历要排序的数列，比较相邻元素的值，若发现顺序错误则交换它们的位置，直到没有需要交换的元素为止。时间复杂度为O(n^2)，但在最好情况下（即数据已经有序）时间复杂度为O(n)。冒泡排序是稳定的。
快速排序：通过选择一个基准元素，将待排序序列分成两个子序列，其中一个子序列的元素值均小于基准元素，另一个子序列的元素值均大于基准元素，然后递归地对两个子序列进行快速排序。平均时间复杂度为O(nlogn)，最坏情况下为O(n^2)（当输入序列已经有序或逆序时）。快速排序不是稳定的。
四、选择排序
简单选择排序：从未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。时间复杂度为O(n^2)，不是稳定的。
堆排序：将待排序序列构造成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的元素。将其与末尾元素进行交换，此时末尾就是最大值（或最小值）。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值（或次大值）。如此反复执行，便能得到一个有序序列了。时间复杂度为O(nlogn)，不是稳定的。
五、归并排序
归并排序：采用分治法，将待排序序列分成若干个子序列，分别进行排序，然后再将已排序的子序列合并成一个有序的序列。时间复杂度为O(nlogn)，是稳定的。归并排序的空间复杂度也为O(n)，因为需要额外的空间来存储临时合并的子序列。
六、基数排序
基数排序：是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较排序。基数排序有两种方法：LSD（Least significant digital）从最低位开始排序和MSD（Most significant digital）从最高位开始排序。基数排序的时间复杂度为O(d*(n+r))，其中d为位数，n为数据个数，r为基数（如十进制中的r为10）。基数排序是稳定的。
七、排序算法的选择与优化
排序算法的选择：在实际应用中，应根据数据的规模、初始状态、稳定性要求以及内存限制等因素选择合适的排序算法。例如，对于小规模数据或基本有序的数据，可以选择直接插入排序或冒泡排序；对于大规模数据，可以选择快速排序、归并排序或堆排序等。
排序算法的优化：可以通过一些优化技巧来提高排序算法的效率。例如，在快速排序中，可以通过三数取中法来选择基准元素，以减少最坏情况的发生；在归并排序中，可以通过小顶堆来优化合并过程等。
这些是关于408数据结构中排序主题的一些重要知识点。在复习时，需要重点理解各种排序算法的思想、实现方式、时间复杂度、空间复杂度以及稳定性等特性，并学会根据实际应用场景选择合适的排序算法。
查找
一、查找的基本概念
查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。
查找表：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。查找表可以分为静态查找表和动态查找表，静态查找表的操作只涉及查找操作，不需要动态地修改查找表；而动态查找表除了查找操作外，还需要动态地插入或删除数据元素。
关键字：数据元素中唯一标识该元素的某个数据项的值。使用基于关键字的查找时，查找结果应该是唯一的。
平均查找长度（ASL, Average Search Length）：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。它是衡量查找算法效率的最主要指标。
二、顺序查找（线性查找）
定义：顺序查找又称线性查找，适用于顺序表和链表。它从表头（或表尾）开始，逐个检查关键字是否满足给定的条件，直到找到满足条件的元素或查找到表的另一端。
查找效率：对于长度为n的查找表，在最坏情况下，顺序查找需要进行n次比较。因此，顺序查找的平均查找长度ASL为(n+1)/2（查找成功时）和n+1（查找失败时）。
优化：在查找之前，如果已知表是有序的，可以在查找到关键字大于（或小于）待查找关键字时停止查找，从而降低查找失败的平均查找长度。
三、折半查找（二分查找）
定义：折半查找又称二分查找，仅适用于有序的顺序表。它首先将给定值与查找表中中间位置的元素比较，若相等则查找成功；否则根据比较结果缩小查找范围，继续在缩小后的范围内进行同样的查找，直到找到满足条件的元素或确定表中没有所需要查找的元素。
查找效率：折半查找的时间复杂度为O(logn)，其中n是查找表的长度。在最坏情况下，需要进行log2(n+1)次比较。
判定树：折半查找的过程可以用一棵二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，表示查找失败的区间。
四、分块查找（索引顺序查找）
定义：分块查找又称索引顺序查找，它结合了顺序查找和折半查找的优点。首先将查找表分为若干子块，块内的元素可以无序，但块间的元素是有序的。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
查找过程：首先在索引表中确定待查记录所在的块（可以使用顺序查找或折半查找），然后在块内顺序查找。
查找效率：分块查找的平均查找长度取决于索引查找和块内查找的平均查找长度。
五、树形查找
二叉排序树（BST）：二叉排序树是一种特殊的二叉树，它的左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。二叉排序树的查找、插入和删除操作的时间复杂度都与树的高度有关，最坏情况下为O(n)，最好情况下为O(logn)。
平衡二叉树（AVL树）：为了避免二叉排序树的高度增长过快，引入了平衡二叉树的概念。平衡二叉树要求任意结点的左、右子树高度差的绝对值不超过1。在插入和删除结点时，需要通过旋转操作保持树的平衡。
红黑树：红黑树是一种自平衡二叉查找树，它在每个结点上增加了一个表示颜色的位。红黑树的插入、删除和查找操作的时间复杂度都是O(logn)。
六、散列查找
散列表（Hash Table）：散列表是一种通过散列函数将关键字映射到表中的一个位置来存储和查找记录的数据结构。
散列函数：散列函数是散列查找的核心，它决定了关键字在散列表中的存储位置。常见的散列函数有除留余数法、直接定址法、数字分析法、平方取中法等。
冲突处理：在散列表中，不同的关键字可能会映射到同一个位置，这种现象称为冲突。处理冲突的方法有拉链法、开放定址法（包括线性探测法、平方探测法、伪随机序列法等）等。
查找效率：散列查找的平均查找长度与填装因子（表中填入的记录数与表长的比值）有关，填装因子越小，冲突的可能性越小，查找效率越高。
DS应用题
代码题策略
面对代码题，首先不要慌张。即使无法立即想到最优解，也可以采取以下策略：
暴力解法尝试：如果直接求解复杂，可以先尝试编写暴力解法，即最直接、但可能效率不高的方法。这不仅能确保获得部分分数，还可能为优化解法提供思路。
构建代码框架：如果暴力解法也难以实现，可以先写出相关的结构体定义、函数声明和基本的算法框架，如排序算法的框架代码，为后续填充具体逻辑打下基础。
文字描述思路：时间紧迫时，至少应文字描述你的解题思路，包括算法的大致步骤、预期的数据结构等，这也能展示你的思考过程和问题解决能力。
参考：
