数据结构与算法-基本知识
原因
这学期在复习数据结构与算法这门课程的时候，发现你电的数据结构与算法考题所涵盖的内容要大于课堂所授内容。而在数据结构与算法这个领域，没有足够的经验积累，在考场上遇到一些经典问题，想要临场给出解决方案会十分困难（真有第一次接触算法，看一眼PPT、概念、思想，就能推导出所有问题解决方案的大哥记得带带我orz）为了方便通过考试，加深对于数据结构、算法思想的理解，现对数据结构与算法的一些基本知识、以及较难的递归分治、动态规划问题通过GPT的协助进行了收集整理，考试有较大概率从以下例题、原理、性质中抽取。个人整理，可能部分有点小问题（强制鼓励大家在看的过程中加以独立思考了：））。
基本知识
存储结构
1.顺序存储（数组）：
•性质：在内存中连续存储数据元素。每个元素占用相同大小的空间，可以通过下标直接访问。
•优点：访问速度快，支持随机访问。
•缺点：大小固定，扩展困难。在数组中间插入或删除元素效率低。
•使用场景：适用于元素数量固定，频繁进行随机访问的场景，如静态数据列表。
2.链式存储：
•性质：每个元素包含数据和至少一个指向其他元素的指针，形成链式结构。
•优点：动态大小，容易扩展和缩减。插入和删除操作相对高效。
•缺点：访问特定元素时，可能需要从头开始遍历链表，效率低于数组。
•使用场景：适用于元素数量不固定，频繁进行插入和删除操作的场景，如动态数据集合。
3.哈希存储：
•性质：通过哈希函数将关键字映射到表中一个位置以访问记录，旨在实现快速查找。
•优点：理想情况下，查找、插入、删除的时间复杂度接近O（1）。
•缺点：哈希冲突处理复杂，不适合元素数量变化大的情况。
•使用场景：适用于快速查找和访问的场景，如数据库索引、缓存实现。
4.索引存储：
•性质：通过维护一个额外的索引表来快速定位数据。
•优点：提高数据检索速度，可以对非连续存储的数据进行有效访问。
•缺点：增加额外的空间复杂度，维护索引结构可能导致额外开销。
•使用场景：适用于大量数据和需要快速柃索的场景，如数据库系统。
逻辑结构：
1.栈（Stack）：
•特点：遵循后进先出（LIFO, Last In First Out）的原则。在栈中，最后一个加入的元素会被首先移除。
• 使用场景：
•函数调用：在程序执行时，栈用于存储函数调用的记录，如局部变量、返回地址等。
•表达式求值：用于算术或逻辑表达式的求值，尤其是处理括号和操作符的顺序。
•回溯问题：如深度优先搜索（DFS）算法中，用栈来记录路径或状态。
•撒销操作：在软件工具中，用于实现撒销（Undo）操作，存储历史操作记录。
2.队列（Queue）：
•特点：遵循先进先出（FIFO, First In First Out）的原则。在队列中，最先加入的元素会被首先移除。
•使用场景：
•数据缓冲：如打印任务队列，操作系统中的各种服务队列。
•资源共享：在多线程环境下，多个线程可能需要按顺序访问某些共享资源。
•宽度优先搜索（BFS）：在图或树的搜索算法中，用队列来记录待访问的节点。
•实时计算：在实时系统中，用于处理实时数据流，如网络流量控制。
查找
1.顺序查找（Sequential Search）：
•优点：
•简单易实现。
•对数据的组织形式没有特别要求，既可以用于有序数据，也可以用于无序数据。
•缺点：
•效率低，尤其是对于大数据集。
•时间复杂度较高。
•时间复杂度：平均和最坏情况下都是 O（n）。
•适用场景：适用于数据量小或者数据未排序的情况。
2.二分查找 （Binary Search）：
•优点：
•查找速度快，特别是对于大数据集。
•时间复杂度较低。
• 缺点：
•要求数据预先排序。
•不适合频繁变动的数据集，因为每次数据变动后可能都需要重新排序。
•时间复杂度：最坏和平均情况下是 O（logn）。
•适用场景：适用于数据量大且数据已经排序的情况。
3.索引查找 （Index Search）：
•优点：
•可以实现非常快的查找速度。
•适合于数据量大且经常查询的场合。
•缺点：
•增加额外的空间复杂度，需要维护索引表。
•更新数据时可能需要更新索引，增加了维护成本。
•时间复杂度：取决于索引的实现，通常是 O（log n）或更快。
•适用场景：适用于大规模数据集，且数据更新频率不高但查询频率很高的场景，如数据库。
排序
插入排序
1.直接插入排序：
•性质：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描找到相应位置并插入。
•优点：实现简单，对于小规模数据效率高。
•缺点：对于大规模数据效率低。
•时间复杂度：平均和最坏情况下O（n^2）。
•适用场景：数据量小或基本有序的数组。
2.二分插入排序：
• 性质：类似直接插入排序，但是寻找插入位置时使用二分查找。
•优点：减少比较次数。
•缺点：移动次数不变，对大数据集效率依然不高。
•时间复杂度：平均和最坏情况下 O（n^2）。
•适用场景：数据量不是很大的场合。
3.希尔排序：
•性质：一种分组插入方法。通过将整个待排序的记录序列分割成若干子序列分别进行直接插入排序。
•优点：中等规模数据效率较好，实现相对简单。
•缺点：不稳定，复杂度不易精确预测。
•时间复杂度：平均O（nlogn）到 O（n^2）。
•适用场景：中等大小的数据集。
交换排序
1.冒泡排序：
•性质：通过重复遍历要排序的数列，一次比较两个元素，顺序错误就交换。
•优点：实现简单，稳定排序。
•缺点：效率低，尤其是对于大数据集。
•时间复杂度：平均和最坏情况下O（n^2）。
•适用场景：小数据量排序。
2.快速排序：
•性质：分治法思想，选择一个元素作为基准，将数组分为两部分，一部分都比基准小，另一部分都比基准大，然后递归排序两部分。
•优点：平均情况下效率很高。
•缺点：最坏情况下效率低，不稳定。
• 时间复杂度：平均O（nlogn），最坏情况下 O（n^2）。
•适用场景：大数据量排序。
选择排序
1.简单选择排序：
•性质：通过选择最小（或最大）元素放到排序序列的起始位置，然后再从剩余未排序元素中继续选择最小（或最大）元素，然后放到已排序序列的未尾。
•优点：简单。
•缺点：效率低，不稳定。
•时间复杂度：平均和最坏情况下 O（n^2）。
•适用场景：数据量较小的情况。
归并排序
1.归并排序：
•性质：采用分治法，将已有序的子序列合并，得到完全有序的序列。
•优点：稳定，效率高，适合大数据量排序。
•缺点：需要额外的存储空间。
•时间复杂度：平均和最坏情况下均为 O（nlogn）。
•适用场景：大数据量排序，特别是链表类型的数据结构。
总结
•小数据量排序：直接插入排序、冒泡排序、简单选择排序。
•大数据量排序：快速排序、归并排序。
•特殊情况（如部分有序）：希尔排序、二分插入排序。
•归并排序适合于数据量非常大的情况，尤其是链表结构，但需要额外空间。
•快速排序是大多数情况下效率最高的排序算法，但在最坏情况下效率会下降。
•稳定的排序算法：直接插入排序、二分插入排序、冒泡排序、归并排序。
•不稳定的排序算法：希尔排序、快速排序、简单选择排序。
树
二叉树的类型
1.二叉树（Binary Tree）
• 性质：
•每个节点最多有两个子节点，通常称为左子节点和右子节点。
•不要求有序，可以用于表示具有层次结构的数据。
• 适用场景：
•表达具有层次结构的数据，如文件系统的目录结构。
•作为其他更特化树结构（如二叉搜索树、平衡二叉树）的基础。
•在算法中，如二叉树遍历、堆结构实现等。
2.平衡二叉树 （Balanced Binary Tree）
• 性质：
•是一种特殊的二叉树，任一节点的两个子树的高度差不超过1。
•常见的平衡二叉树有AVL树、红黑树等。
•平衡二叉树可以保证树的深度均匀，从而保证操作的效率。
•适用场景：
•用于需要高效查找的场合，如数据库索引。
•在需要保证查找、插入、删除等操作都相对平衡的情况下非常有用。
•适用于数据集经常变动，需要频繁维护平衡的场景。
3.二叉排序树 （Binary Search Tree, BST）
• 性质：
•是一种特殊的二叉树，对于每个节点，其左子树上所有节点的值都小于它的根节点的值，其右子树上所有节点的值都大于它的根节点的值。
•可以快速进行查找，插入和删除操作。
•适用场景：
•适用于经常进行查找操作的数据集。
•在数据量不是特别大或者不经常更新的场景下效率较高。
•二又搜索树可以用于实现动态集合数据结构、构建索引等。
总结
•二又树是最基本的树结构，适用于表示具有层次的数据。
•平衡二叉树保证了树的平衡，适用于频繁操作的场景，确保操作效率。
•二又排序树适用于需要频繁进行查找的场合，但若经常插入或删除，可能导致树变得不平衡，影响效率。
遍历还原
要还原一个二叉树，理论上需要两种不同的遍历序列，其中至少有一种是中序遍历，中序遍历是关键，因为它提供了节点相对于彼此的位置信息。
1.先序遍历＋中序遍历
2.中序遍历＋后序遍历
3.中序遍历＋层次遍历
不过，需要注意的是，如果二叉树中有节点的值相同，那么单纯依靠遍历序列可能无法唯一确定一棵二叉树的结构。在实际应用中，通常假定所有节点的值各不相同。
二叉树的查找
1.二叉排序树 （BST）
• 性质：
•对于每个节点，其左子树中所有节点的值小于该节点的值，右子树中所有节点的值大于该节点的值。
•不一定是平衡的。
•查找方法：
•从根节点开始。
•如果查找的值小于当前节点的值，则移动到左子节点；如果大于当前节点的值，则移动到右子节点。
•继续这个过程直到找到目标值或达到叶节点。
• 查找时间：
•平均情况：O（log n），这里的 n 是树中节点的数量。
•最坏情况：O（n），当树退化成链表时。
2.平衡二叉树（AVL树）
• 性质：
•是一种高度平衡的二叉排序树。
•任一节点的两个子树的高度最大差为1。
•自动维护平衡，插入和删除操作可能需要通过旋转来保持平衡。
•查找方法：
•查找方法与普通二叉排序树相同，但由于树是平衡的，效率更高。
•从根节点开始，根据目标值与当前节点值的比较结果向左或向右移动。
• 查找时间：
•平均和最坏情况：O（log n），由于树的平衡性，查找效率更稳定。
•二叉排序树在最坏情况下可能会退化成链表，导致效率下降。
•AVL树通过维持树的平衡来保证在所有情况下查找操作的效率都是对数级别的。
• 在需要经常插入和删除的场景下，AVL树由于维持平衡的需要可能会有更多的旋转操作，导致这些操作比在普通的二又排序树上要慢。
堆
堆排序
堆排序是一种高效的排序方法，基于二叉堆（Binary Heap）数据结构。堆是一种特殊的完全二叉树，可以分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。堆排序利用堆的这些性质进行排序。
实现方法
堆排序的实现通常包括以下步骤：
1.建堆（Heapify）：将无序数组构建成一个最大堆或最小堆。
2.排序：
•将堆顶元素（最大或最小）与最后一个元素交换，然后減少堆的大小。
•重新调整堆，恢复堆的性质。
•重复上述过程直到堆的大小为1。
性质
•堆的特性：在一个最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。
•不稳定排序：堆排序是不稳定的排序算法，相同元素的相对位置可能会改变。
•原地排序：堆排序不需要额外的存储空间，除了输入数组之外。
所需时间
•时间复杂度：
•最好、最坏和平均情况下的时间复杂度都是 O（n log n）。
•构建堆的时间复杂度：O（n）。
•调整堆的时间复杂度：O（log n），因为需要对堆进行下沉操作，时间复杂度与堆的高度相关。
堆排序是一种非常高效的排序方法，特别适合于处理大数据集。它的主要优势是时间复杂度在所有情况下都是 O（n log n），并且不需要额外的存储空间。然而，由于堆排序是不稳定的，所以在需要稳定排序的场景中可能不是最佳选择。
为什么堆适合用数组实现
堆通常使用数组来实现，主要基于以下几个原因：
1.空间效率：
•使用数组存储堆（特别是二叉堆）是空间效率最高的方法，因为它充分利用了堆作为完全二叉树的特性。在完全二叉树中，除了最后一层，其他每层都是完全填满的，这使得数组这种紧凑的存储方式非常适合。
2.简易访问：
•在二叉堆中，如果父节点的索引是‘主，则其左子节点的索引为2i+1，右子节点的索引为2i+2（这里假设数组索引从0开始）。这种简单的关系使得在数组中访问任何节点的父节点或子节点变得非常方便。
3.避免指针开销：
•使用数组实现堆避免了使用指针的开销。在指针的实现中，每个节点需要额外的空间来存储指向其子节点的指针。而数组实现不需要这样的额外空间，从而提高了空间利用率。
4.缓存友好：
•由于数组是连续存储的，这使得它在内存中是缓存友好的（Cache-Friendly）。这意味着当我们访问数组中的元素时，相邻的元素很可能已经被预加载到缓存中，从而提高访问速度。
5.简化操作：
•在执行堆操作（如插入、删除）时，数组可以通过简单的索引操作来实现。这些操作在数组上通常比在基于节点和指针的树结构上更简单、更直接。
关于二叉树的存储
1.二叉堆（特别是优先队列）
•使用数组：通常使用数组来实现二叉堆，特别是在实现优先队列时。由于二叉堆是完全二叉树，使用数组可以有效地利用空间，且容易计算父节点和子节点的位置。
2.二叉搜索树、AVL树、红黑树等
•使用链表：对于这些树，通常使用链表（每个节点含有指向其子节点的指针）来实现。这是因为这些树经常进行插入和删除操作，这些操作在链表实现中更有效。链表结构方便节点间的动态链接和断开，适合频繁变动的树结构。
3.完全二叉树
•使用数组：对于完全二叉树，数组是一个好的选择，因为它可以有效地利用数组索引来表示父子关系，且不会有数组空间的浪费。
4.普通二叉树
•使用链表：对于普通二叉树（特别是结构不规则的），链表通常是更合适的选择，因为它可以更灵活地处理各种形状的二叉树。数组实现可能会导致大量空间浪费，特别是当树是非完全二叉树时。
5.Huffman树等特殊用途的二叉树
•情况特定：对于如Huffman树这样的特殊用途的二叉树，存储结构的选择取决于具体应用。例如，在构建Huffman编码树时，链表可能更合适，因为它支持频繁的节点操作。
图
基本概念
有向图 (Directed Graph)
•概念：图中的边具有方向。
•性质：每条边从一个顶点指向另一个顶点。
•适用场景：表示具有明确方向的关系，如网络流、社交网络分析、依赖关系等。
•注意点：在有向图中，路径和连通性依赖于边的方向。
无向图 (Undirected Graph)
•概念：图中的边没有方向。
•性质：边仅仅连接两个顶点，没有方向性。
•适用场景：表示双向或无方向性的关系，如无向网络、朋友关系等。
•注意点：在无向图中，任何两个相邻的节点都可以互相到达。
子图（Subgraph）
•概念：由原图的一部分顶点和边组成的图。
•性质：子图的顶点和边都属于原图。
•适用场景：分析原图的局部结构或属性。
•注意点：子图不一定保留原图的所有连接特性。
连通分量 (Connected Component)
•概念：在无向图中，若两个顶点间存在路径，则它们属于同一个连通分量。
•性质：无向图可以分解为若干连通分量，每个分量内部任两点都连通。
•适用场景：分析网络的连通性，如社交网络中的团体检测。
•注意点：只适用于无向图。
强连通分量 （Strongly Connected Component）
•概念：在有向图中，若任意两个顶点都相互可达，则这些顶点构成一个强连通分量。
•性质：表明在有向图中，某个子集内的任意两点都可以互达。
•适用场景：分析有向图的结构，如网页链接的结构分析。
•注意点：只适用于有向图，且判断标准比无向图的连通分量更严格。
度（Degree）
•概念：一个顶点的度是指与该顶点相连的边的数量。
•性质：在无向图中，每条边贡献两个度；在有向图中，分入度和出度。
•适用场景：网络分析、图的结构特性分析等。
•注意点：有向图和无向图计算度的方式不同。
完全图 （Complete Graph）
•概念：图中任意两个顶点之间都存在一条边的图。
•性质：顶点之间高度连通。
•适用场景：理论研究，建模完全连通的网络。
•注意点：随着顶点数的增加，边的数量呈指数级增长。
生成树（Spanning Tree）
•概念：图的生成树是包含图中所有顶点的无环连通子图。
•性质：生成树包含原图的所有顶点，但只有足够的边来形成树结构。
•适用场景：网络设计、电路设计、最小生成树问题等。
•注意点：一张图可以有多个不同的生成树。
算法以及作用
1.有向图算法（如拓扑排序、Dijkstra算法）
•拓扑排序：仅适用于有向无环图（DAG）。如果图中存在环，拓扑排序不可能完成。
•Dijkstra算法：不适用于包含负权边的图。在这种情况下，应使用贝尔曼-福特算法（Bellman-Ford algorithm）。
2.无向图算法（如连通分量算法、Kruskal/Prim算法）
•连通分量算法：仅适用于无向图。在有向图中，应考虑使用强连通分量算法。
•Kruskal/Prim算法：适用于寻找最小生成树，但要注意图中不能有负权重的边。同时，这些算法在稠密图上可能不够高效。
3.子图同构算法
•子图同构问题是计算上非常困难的，对于大图可能非常耗时。应当谨慎处理大规模图数据。
4.强连通分量算法（如Kosaraju、Tarjan算法）
•这些算法通常比较复杂，实现时需要确保正确处理堆栈等数据结构，以避免错误。
5.度的计算
•在有向图中，需区分入度和出度。同时，对于大图，度的计算可能非常耗时。
6.完全图的算法（如哈密顿路径和圈问题）
•哈密顿问题是NP完全问题，在大图上求解可能非常困难和耗时。
7.生成树算法（如最小生成树算法）
•在实现这些算法时，需要特别注意避免形成环。特别是在Kruskal算法中，需要使用并查集等数据结构来有效地处理这个问题。
•在使用这些算法时，需要考虑图的特性（如有向性、是否有环、边的权重等）以及算法的适用性和限制。
•对于大规模图，算法的时间复杂度和空间复杂度变得尤为重要。
•实现这些算法时，正确和高效地处理数据结构是关键。
•在某些情况下，可能需要考虑使用近似算法或启发式算法来处理计算上的难题。
Kruskal算法
•适用性：更适合于稀疏图。
•原因：
。Kruskal算法的核心是对边进行排序，并逐一检查每条边以构建最小生成树。
•在稀疏图中，边的数量相对较少，所以排序和处理边的过程比较高效。
•Kruskal算法的时间复杂度主要由边的排序决定，通常是O（Elog E），其中E是边的数量。
Prim算法
•适用性：更适合于稠密图。
• 原因：
• Prim算法从一个顶点开始，逐步增加新的边来构建最小生成树。
•在稠密图中，由于边的数量很多，Kruskal算法中对所有边排序的步骤会比较耗时。而Prim算法可以有效地通过使用最小优先队列（如二叉堆）来选择下一条最短的边。
•Prim算法的时间复杂度主要取决于用于维护候选边的数据结构，使用最小优先队列时，时间复杂度为O（E+Vlog V），其中V是顶点的数量。
