### 数据结构笔记知识点详解
#### 一、静态链表与顺序表、链表的比较
**静态链表**是利用一维数组的形式来模拟链表的一种数据结构。它结合了数组和链表的优点，能够有效地解决传统链表空间浪费的问题。
- **静态链表的特点**：
- 使用一维数组来存储链表的节点。
- 数组中的每个元素不仅存储数据，还存储一个指向下个节点位置的信息。
- 与动态链表相比，静态链表预先分配内存，因此不会出现内存碎片问题。
**顺序表与链表的比较**：
- **顺序表**：
- 数据元素在内存中是连续存放的。
- 插入和删除操作需要移动大量的元素，效率较低。
- 查找速度快，因为可以通过下标直接访问任意位置的元素。
- **链表**：
- 数据元素在内存中不一定连续存放，而是通过指针链接起来。
- 插入和删除操作不需要移动元素，只需修改指针即可，效率较高。
- 查找速度较慢，需要从头节点开始逐个遍历。
**顺序表的插入元素算法**：
1. 查找插入位置。
2. 如果数组未满，则将插入位置之后的所有元素向后移动一位。
3. 将新元素插入空出的位置。
4. 更新数组长度。
**顺序表的删除操作**：
1. 查找要删除元素的位置。
2. 将被删除元素之后的所有元素向前移动一位。
3. 更新数组长度。
#### 二、单链表的构建
- **尾插法创建单链表**：
- 遍历输入数据。
- 每个数据都作为新节点加入到链表的尾部。
- 这种方法适用于已知数据集合的情况。
- **头插法建立单链表**：
- 每个数据都作为新节点加入到链表的头部。
- 这种方法适用于实时添加数据的情况。
- **尾插法建立双链表**：
- 类似于单链表的尾插法，但需要同时维护前后指针。
#### 三、栈与队列
- **顺序栈的出入栈算法**：
- 入栈：如果栈未满，则在栈顶位置插入元素。
- 出栈：如果栈非空，则移除栈顶元素。
- **栈的应用**：
- 用于程序调用的管理。
- 表达式的转换和求值。
- 括号匹配等问题。
- **循环队列**：
- 循环队列解决了普通队列的“假溢出”问题。
- **队尾指针rear**指向刚进队的元素位置。
- **队首指针front**指向刚出队的元素位置。
- 当rear和front都指向数组末端时，即使队列中还有空闲位置也无法继续入队。
#### 四、排序算法
- **插入排序**：
- **基本思想**：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。
- **直接插入排序**：对于未排序数据，在已排序序列中从后向前扫描。
- **折半插入排序**：使用折半查找确定插入位置。
- **表插入排序**：类似于直接插入排序，但使用链表作为存储结构。
- **希尔排序**：
- **基本思想**：不是将待排序元素一次性进行排序，而是将待排序元素分组，每组采用插入排序的方式排序。
- **交换类排序**：
- **冒泡排序**：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
- **快速排序**：通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
- **选择类排序**：
- **简单选择排序**：每趟从待排序记录中选出最小（或最大）的一个记录，顺序放在已排序的记录序列的最后。
- **归并排序**：
- **2-路归并排序**：采用分治策略，将数组分成两半，分别对这两半进行排序，然后将两个已排序的部分合并。
#### 五、稀疏矩阵和广义表
- **稀疏矩阵**：
- **三元组表表示法**：
- **Row**：非零元素所在的行值。
- **Col**：非零元素所在的列值。
- **Value**：非零元素的值。
- **快速转置算法**：使用两个辅助数组`num[]`和`position[]`来加速转置过程。
- **广义表**：
- **第一种存储结构**：每个节点包含三个域，用于存储原子或子表。
- **第二种存储结构**：同样使用三个域的节点结构，但具体实现细节可能有所不同。
#### 六、二叉树
- **线索二叉树**：
- 是一种特殊的二叉树结构，通过添加线索使得遍历操作更高效。
- **中序线索化算法**：将二叉树的空指针指向其前驱或后继节点。
- **图**：
- 图是一种非线性的数据结构，用于表示对象之间的关系。
#### 七、查找
- **基于线性表的查找**：
- **折半查找**：仅适用于有序线性表，通过不断将搜索区间减半来提高查找效率。
- **基于树的查找法**：
- **二叉排序树（二叉查找树）**：每个节点的左子树只包含小于该节点键值的节点；右子树只包含大于该节点键值的节点。
- **二叉排序树的插入算法**：从根节点开始，根据比较结果决定插入位置。
- **在二叉排序树中删除节点**：需要考虑三种情况：无子节点、有一个子节点、有两个子节点。
- **B_树**：
- **m路查找树**：每个节点最多有m棵子树。
- **性质**：
- 每个节点最多有m棵子树。
- 根结点至少有两棵子树。
- 除根节点之外的所有非叶子节点至少有\[m/2\]棵子树。
- 所有叶子结点出现在同一层上。
- 子树也是m路查找树。
- **计算式查找法——哈希法**：
- **处理冲突的方法**：
- **开放定址法**：当发生冲突时，根据一定的规律寻找下一个可用位置。
- **线性探测再散列**：每次冲突后，顺序检查下一个位置是否可用。
以上内容涵盖了数据结构的基础知识点，包括静态链表、各种排序算法、栈与队列、稀疏矩阵、广义表以及查找方法等。这些概念和技术是计算机科学领域不可或缺的基础知识，对于理解和设计高效的算法有着重要意义。
