### 刘汝佳《基础数据结构》知识点梳理
#### 一、线性结构
线性结构是最基础的数据结构之一，主要包括数组和链表等。在本节中，我们重点介绍了几种常用的线性结构及其应用场景。
- **数组**：数组是一种线性结构，它通过连续的内存空间存储相同类型的数据元素。数组支持随机访问，即可以通过下标快速定位到数组中的任意元素。数组的优点是访问速度快，但插入和删除操作相对较慢。
- **带头结点的双链表**：双链表是一种链式存储结构，每个节点包含前驱指针、数据域和后继指针。带头结点的双链表在链表头部添加了一个虚拟的头结点，便于进行插入和删除操作。这种结构在插入和删除时无需特殊处理边界情况，使得操作更加简单。
- **队列**：队列是一种特殊的线性表，只允许在表的一端进行插入操作，在另一端进行删除操作。本节介绍了两种类型的队列——循环队列和Open-Close表。循环队列通过将数组看作是一个首尾相连的环形空间来实现，有效地避免了队列“假溢出”的现象。Open-Close表则是另一种实现队列的方法，它使用两个指针分别指向队列的前端和后端。
#### 二、数据结构应用实例
接下来通过几个具体的例子来展示如何运用这些线性结构来解决问题。
- **例1：最小值查询**
问题描述：给定一个大小为n的数组A，支持修改数组中的任意元素，并能查询闭区间[p, q]中元素的最小值。
- **解决方案**：采用分块的方法，将数组分为若干个长度为L的块，每个块维护一个最小值。当修改元素时，只需更新该元素所在的块的最小值；当查询区间最小值时，将区间[p, q]分成完整的块和非完整的块，分别处理即可。
- **时间复杂度**：O(n^(1/2))，其中L = O(n^(1/2))。
- **例2：最接近的值**
问题描述：给定一个大小为n的数组A，对于每个元素A[i]，找到它之前的所有元素中与它最接近的那个元素。
- **解决方案**：使用离线算法，首先对数组A进行排序，然后按照从小到大的顺序构建一个双向链表。对于每个元素A[i]，在链表中找到与其最接近的值，并更新结果。
- **时间复杂度**：O(nlogn)，主要是排序所需的时间。
- **例3：移动窗口**
问题描述：给定一个长度为n的数组和一个长度为k的滑动窗口，窗口从数组的左侧开始，每次向右移动一个位置，直到窗口的右边界到达数组的末尾。对于每个窗口位置，找出其中的最小值。
- **解决方案**：使用单调队列来实现。队列中保存的是数组中的索引，并且队列保持单调递增。每次窗口右移时，将队首元素出队，如果新加入的元素小于队列中的某些元素，则将这些元素从队列中删除，确保队列单调性。
- **时间复杂度**：O(n)，每个元素最多进入和退出队列各一次。
- **例4：程序复杂度**
问题描述：给出一段由OP<x>, LOOP<x>和END组成的程序，计算该程序的时间复杂度。
- **解决方案**：使用栈来辅助计算。遍历程序时，遇到LOOP<x>和OP<x>就将它们压入栈中；遇到END时，从栈顶开始弹出元素，直到遇到相应的LOOP为止，同时计算这部分的总复杂度，并将计算结果作为一个OP指令压回栈中。
- **时间复杂度**：O(n)，其中n为程序的长度。
以上内容涵盖了刘汝佳老师讲解的基础数据结构中的核心知识点及其应用实例，希望能帮助读者更好地理解和掌握这些重要的数据结构概念及其实现方法。
