数据结构与算法

���源地址

一 数据结构

1 堆和树之间的区别

区别就在于树是没有特定顺序的，你需要遍历整个树才能找到特定元素；而堆是有序的，你可以直接找到最大（或最小）的元素。

堆：假设你正在开发一个任务调度系统，需要根据任务的优先级进行调度。你可以使用一个最小堆来实现任务队列，将任务按照优先级插入到堆中，并始终保持最小优先级的任务在堆顶部。这样，每次从堆顶部取出任务时，你总是能够获取到当前最高优先级的任务进行处理。

树结构：计算机的文件系统通常被组织成树状结构。根目录是整个文件系统的起点，每个文件夹可以包含子文件夹和文件，从而形成层次结构。

2 所有数据结构都是基于数组、链表或二者的组合实现的

基于数组实现的数据结构也称“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构也称“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。

3 基本数据类型

就是整数，浮点，字符，布尔类型：基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1 比特。在绝大多数现代操作系统中，1 字节（byte）由 8 比特（bit）组成。

基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。例如以下代码，我们用相同的数据结构（数组）来存储与表示不同的基本数据类型，包括 int、float、char、bool 等。

4 列表=“动态数组”

5 双向队列

在队列中，我们仅能删除头部元素或在尾部添加元素。如图 5-7 所示，「双向队列 double-ended queue」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

双向列表的应用

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。

6 哈希表 = 散列表

我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value，实现高效的元素查询

1）哈希表的简单实现，仅用数组

在哈希算法中，将哈希值对桶数量（数组的长度）capacity 取模，是为了确定该 key 在数组中的索引位置。

取模运算是一种数学运算，它计算某个数除以另一个数的余数。在这个场景中，我们使用取模运算是为了将哈希值映射到数组的有效范围内。

作用如下：

1. 均匀分布：通过取模运算，我们可以将哈希值均匀地映射到桶数组的各个索引位置上。这样可以避免将大部分数据集中在某几个桶中，提高散列的均匀性。

2. 确定索引位置：取模运算得到的结果就是一个具体的索引位置，在数组中可以直接通过该索引访问或存储元素。这样可以快速定位到对应的桶，提高查找、插入、删除等操作的效率。

举个例子来说明：

假设有一个桶数组，长度为10（即capacity=10），而某个 key 经过哈希函数计算后得到的哈希值为 27。如果我们直接将哈希值作为索引，那么该 key 对应的索引位置就超出了数组的长度。但如果我们对容量取模（27 % 10），则得到的结果为 7，表示该 key 应该放在数组的第 7 个位置上。

所以，对容量取模可以将哈希值映射到合适的索引位置，确保数据分布均匀且能够准确定位到对应的桶。

2）哈希冲突

两key对应一个值了，这时候就需要扩容哈希表

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75时，系统会将哈希表扩容至原先的 2倍。

哈希表的存储可能如下所示：

桶1: 空

桶2: 学生A, 85

桶3: 学生B, 92

桶4: 空

桶5: 学生C, 78

桶6: 空

桶7: 空

桶8: 空

桶9: 空

桶10: 空

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

1、改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。

2、仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

开放寻址有三法

7 树

二叉树的基本单元是节点，每个节点（父节点）包含值、左子节点引用（指针）和右子节点引用。

插入和删除节点

遍历

前序遍历首先访问根节点，然后递归地遍历左子树和右子树

中序遍历先遍历左子树，然后访问根节点，最后遍历右子树

后序遍历先遍历左子树，然后遍历右子树，最后访问根节点

8 堆

9 图