### 数据结构实验知识点详解
#### 实验一：链表归并
**实验目的**：学习如何处理链表的归并操作，确保数据的有序性和唯一性。
**实验内容**：
给定两个递增有序的单链表ha和hb，目标是在不破坏hb的情况下，将hb中的元素归并到ha中，同时保持ha的递增顺序，且避免重复元素的加入。此过程要求深入理解链表的基本操作，包括插入、比较和遍历。
**算法设计**：
1. 初始化两个指针p和q，分别指向ha和hb的头节点。
2. 遍历两个链表，比较当前节点的值。
3. 如果q节点的值小于等于p节点的值，并且ha中不存在相同的值，将q节点插入到p节点之前。
4. 更新指针位置，继续比较下一个节点。
5. 直至其中一个链表遍历完毕，将另一个链表剩余的部分链接到ha的末尾。
#### 实验二：多项式相加
**实验目的**：掌握链式存储结构下多项式的相加操作。
**实验内容**：
通过链表实现两个一元多项式的相加，要求链表表示的多项式数据结构支持系数和指数的存储。实验中需考虑到相同指数项的合并，确保结果多项式的简洁性。
**算法设计**：
1. 初始化两个指针分别指向两个链表的头部。
2. 比较两个链表当前节点的指数大小。
3. 如果指数相等，合并系数，保留一个节点；如果指数不同，保留指数较大的节点。
4. 继续移动指针，直至一个链表遍历完毕。
5. 将未遍历完链表的剩余部分添加到结果链表的末尾。
#### 实验三：动态链表与静态链表转换
**实验目的**：理解动态链表与静态链表的区别，并掌握从动态链表到静态链表的转换方法。
**实验内容**：
给定一个动态二叉链表，要求将其转换为静态二叉链表。静态链表使用数组存储，其中的`lchild`和`rchild`字段存储子节点的下标而非指针。
**算法设计**：
1. 遍历动态链表，记录每个节点的data，lchild和rchild信息。
2. 在静态链表中找到对应的下标位置，填充data，lchild和rchild。
3. 特别注意，lchild和rchild应存储下标而非指针。
#### 实验四：图的邻接表与深度优先搜索
**实验目的**：熟悉图的邻接表表示方法及深度优先搜索算法。
**实验内容**：
构建一个无向图的邻接表表示，并使用深度优先搜索遍历所有顶点。要求算法的时间复杂度为O(n+e)，且仅使用常数级别的额外空间。
**算法设计**：
1. 创建邻接表，其中每个顶点对应一个链表，链表中存储与之相邻的所有顶点。
2. 从任意一个未访问过的顶点开始，进行深度优先搜索。
3. 使用递归或栈来跟踪当前路径上的顶点，直到所有顶点都被访问过。
#### 实验五：二叉排序树结点删除
**实验目的**：掌握在不改变二叉排序树性质的前提下删除特定结点的方法。
**实验内容**：
删除值为X的结点，确保删除后二叉排序树的性质不变，即左子树所有结点小于根结点，右子树所有结点大于根结点，且树的高度不增加。
**算法设计**：
1. 查找值为X的结点。
2. 如果结点是叶节点，直接删除。
3. 如果结点只有一个子节点，替换结点为其子节点。
4. 如果结点有两个子节点，找到右子树的最小值（即后继结点），用它替换当前结点，然后删除后继结点。
5. 调整树结构，确保二叉排序树的性质。
**实验报告撰写**：
实验报告应包括实验日期、实验题目、算法设计过程以及实验结果分析。实验结果应包含算法执行的具体步骤、输入输出示例以及对算法性能的评估。
