【408--复习笔记】数据结构

---

1.绪论

数据结构基本概念

• 请简述数据结构的定义。

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，主要包逻辑结构、存储结构、和数据运算三方面。
逻辑结构包含线性结构与非线性结构。线性结构包含数一般线性表，受限线性表（栈 队列），广义线性表（数组，串等），非线性结构包含（集合，树，图）
存储结构/物理结构是数据结构在计算机中的表示，包含顺序存储、链式存储、索引存储、散列存储。
数据运算是针对数数据逻辑结构的运算和实现。

---

• 数据结构中数据、数据元素、数据项、数据对象的区别是什么？

数据：信息载体
数据元素：数据的基本单位，一个数据元素由若干数据项组成。
数据项：构成数据元素的最小不可分割单位
数据对象：具有相同性质的数据元素的集合，是数据的子集。

---

算法相关

• 什么是算法？算法的五个重要特性是什么？

算法：对特定问题求解问题的描述，是指令的有限集合。
五个特性
有穷、确定、可行、输入、输出
好的算法目标：
正确、可读、健壮、高效（时间/空间）

---

• 如何理解算法的时间复杂度和空间复杂度？请举例说明如何计算。

时间复杂度，算法中基本运算的执行次数的数量级。
空间复杂度，算法所需的存储空间

---

• 请比较常见的时间复杂度的量级，如O(1)、O(n)、O(n^2)、O(logn)等，并说明它们在实际应用中的特点。

O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

---

数据结构的分类

• 数据结构分为逻辑结构和物理结构，它们分别有哪些类型？请举例说明。

逻辑结构
线性结构、非线性结构

物理结构
• 顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中，如数组。例如，存储一组整数的数组，元素在内存中是连续存放的，通过数组下标可以快速访问元素。
• 链式存储结构：数据元素的存储单元可以不连续，通过指针来表示元素之间的逻辑关系，如链表。链表中的每个节点包含数据域和指针域，指针指向下一个节点，这样可以灵活地插入和删除元素。
• 索引存储结构：在存储数据元素的同时，还建立一个附加的索引表，通过索引表可以快速查找数据元素。例如，在数据库中，经常会为某些字段建立索引，以提高查询效率。
• 散列存储结构：根据数据元素的关键字，通过一个散列函数计算出存储地址，将数据元素存储在该地址中。如哈希表，通过哈希函数将键值映射到数组的特定位置，实现快速的查找、插入和删除操作。

---

• 线性结构和非线性结构的区别是什么？常见的线性结构和非线性结构有哪些？

线性结构和非线性结构的区别主要体现在数据元素之间的逻辑关系上：

• 线性结构：数据元素之间存在一对一的线性关系，除了第一个和最后一个元素外，每个元素都有唯一的前驱和后继。

• 非线性结构：数据元素之间存在一对多或多对多的关系，元素的前驱和后继关系不唯一，或者不存在明显的线性顺序。

常见的线性结构有线性表、栈、队列、串等。常见的非线性结构有树（如二叉树、B树等）、图（如无向图、有向图等）、集合等。

---

抽象数据类型

• 什么是抽象数据类型？它有什么作用？

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。它是对数据类型的一种抽象描述，强调数据的逻辑特性和操作的功能，而不涉及数据的具体存储结构和操作的实现细节。

抽象数据类型具有以下作用：
• 数据封装与隐藏：将数据和操作数据的方法封装在一起，隐藏了数据的内部表示和操作的具体实现，使得用户只能通过定义好的接口来访问和操作数据，提高了数据的安全性和可靠性。
• 代码复用：可以在不同的程序中重复使用抽象数据类型，只要满足相同的逻辑需求，就可以直接使用已定义好的抽象数据类型，而无需重新编写相关代码，提高了代码的复用性。
• 模块化设计：有助于将复杂的系统分解为多个相对独立的模块，每个模块可以基于抽象数据类型进行设计和实现，使得系统的结构更加清晰，易于理解、维护和扩展。
• 提高编程效率：用户只需关注抽象数据类型提供的操作功能，而不必关心其内部实现细节，从而减少了编程的复杂度，提高了编程效率。

---

• 请用伪代码或其他方式描述一个简单的抽象数据类型，如栈或队列。

以下分别用伪代码描述栈和队列这两个抽象数据类型：

栈（Stack）抽象数据类型：
栈是一种后进先出（LIFO）的数据结构。

// 定义栈的抽象数据类型
ADT Stack {// 初始化栈Operation InitStack():// 创建一个空栈// 例如，初始化一个空数组来存储栈元素stack = []return stack// 判断栈是否为空Operation IsEmpty(stack):if length(stack) == 0 thenreturn trueelsereturn false// 入栈操作Operation Push(stack, item):stack.append(item)return stack// 出栈操作Operation Pop(stack):if IsEmpty(stack) then// 栈为空时可以根据情况返回特殊值或报错return null elseitem = stack.pop()return item// 获取栈顶元素Operation GetTop(stack):if IsEmpty(stack) thenreturn null elsereturn stack[length(stack) - 1]
}

队列（Queue）抽象数据类型：
队列是一种先进先出（FIFO）的数据结构。

```vbnet
// 定义队列的抽象数据类型
ADT Queue {// 初始化队列Operation InitQueue():// 创建一个空队列// 例如，初始化一个空数组来存储队列元素queue = []return queue// 判断队列是否为空Operation IsEmpty(queue):if length(queue) == 0 thenreturn trueelsereturn false// 入队操作Operation Enqueue(queue, item):queue.append(item)return queue// 出队操作Operation Dequeue(queue):if IsEmpty(queue) then// 队列为空时可以根据情况返回特殊值或报错return null elseitem = queue.pop(0)return item// 获取队头元素Operation GetFront(queue):if IsEmpty(queue) thenreturn null elsereturn queue[0]
}

---

---

---

2.线性表

基本概念

---

什么是线性表？它有哪些基本特征？
线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列，通常记为 (a1,a2,…,ai,ai+1,…,an)，其中 n 为线性表的长度，当 n = 0 时，称为空表。它具有以下基本特征：
有限性：线性表中数据元素的个数是有限的。
顺序性：数据元素之间存在着顺序关系，即除了第一个和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继。
同质性：线性表中的所有数据元素必须是同一数据类型。
可操作性：可以对线性表进行插入、删除、查找、修改等操作，以实现对数据的处理和管理。
抽象性：表中元素具有抽象性，仅讨论其逻辑关系，不考虑内容。
第一个元素只有一个直接后继，最后一个元素只有一个直接前驱。其他元素都有只有一个直接前驱和一个直接后继。

---

线性表的逻辑结构与存储结构有什么区别？
线性表的逻辑结构与存储结构是两个不同层面的概念，它们的区别如下：

定义角度
逻辑结构：是从数据元素之间的逻辑关系角度来描述线性表，它只关注元素之间的前后顺序关系，而不考虑数据在计算机中的具体存储方式。比如，在一个学生成绩表中，每个学生的成绩记录之间存在着顺序关系，这种顺序关系就是线性表的逻辑结构。
存储结构：是指线性表在计算机内存中的存储方式，它需要考虑如何将数据元素及其逻辑关系有效地存储在计算机的存储空间中，以便于计算机进行数据的访问和操作。

表现形式
逻辑结构：通常用线性序列的形式来表示，如 (a1, a2, a3, …, an)，强调的是元素之间的线性顺序关系，每个元素都有唯一的前驱（除第一个元素外）和唯一的后继（除最后一个元素外）。
存储结构：有顺序存储和链式存储等多种形式。顺序存储结构是将数据元素依次存储在连续的内存单元中，就像数组一样；链式存储结构则是通过指针将各个数据元素链接起来，每个元素除了存储自身数据外，还包含指向下一个元素的指针（单链表情况）。

操作特性
逻辑结构：主要定义了一系列基于逻辑关系的操作，如查找第 i 个元素、在第 i 个位置插入元素、删除第 i 个元素等，这些操作是基于元素的逻辑位置进行的，不涉及具体的存储细节。
存储结构：不同的存储结构对操作的实现方式和效率有很大影响。例如，顺序存储结构可以直接通过数组下标快速访问元素，时间复杂度为 O (1)，但插入和删除元素可能需要移动大量后续元素，时间复杂度为 O (n)；链式存储结构访问元素需要从头指针开始遍历链表，时间复杂度为 O(n)，但插入和删除元素只需修改指针，时间复杂度为 O (1)。

独立性
逻辑结构：独立于计算机的硬件和软件环境，它是对数据之间关系的一种抽象描述，不依赖于具体的存储和实现方式，可以在不同的存储结构中实现相同的逻辑结构。
存储结构：与计算机的内存结构和编程语言等密切相关，需要根据具体的硬件环境和编程语言的特点来选择合适的存储方式，以提高数据处理的效率和空间利用率。

---

线性表的主要操作有哪些？请简要描述。
线性表的主要操作包括初始化、插入、删除、查找、修改、求长度、判空、遍历等

---

顺序存储结构

顺序表是如何实现的？它有什么优缺点？
实现方式
顺序表是将线性表中的数据元素依次存储在一组连续的存储单元中，使得逻辑上相邻的数据元素在物理位置上也相邻。在高级程序设计语言中，通常可以用数组来实现顺序表。数组的下标可以直接对应数据元素在线性表中的位置，通过数组的存储单元依次存放线性表的各个元素，从而实现顺序表的顺序存储。

优点
随机访问效率高：由于数据元素在内存中是连续存储的，因此可以通过数组下标直接访问任意位置的元素，时间复杂度为 O(1)。这使得对于顺序表中元素的随机访问操作非常高效，能够快速地获取或修改指定位置的元素值。
存储密度高：顺序表中每个数据元素只存储自身的数据值，没有额外的指针等辅助信息来表示元素之间的逻辑关系（除了数组本身的结构信息外），所以存储密度大，空间利用率高。

缺点
插入和删除操作效率低：在顺序表中进行插入和删除操作时，需要移动大量的元素。例如，在表头或表中间插入一个元素，需要将插入位置之后的所有元素都向后移动一个位置；删除一个元素时，需要将删除位置之后的元素都向前移动一个位置。在最坏情况下，插入和删除操作的时间复杂度为O(n)，其中 n为顺序表的长度，这在数据量较大时效率较低。
空间大小固定：顺序表的存储空间是在程序运行前静态分配的，一旦确定了大小，在程序运行过程中就很难动态改变。如果事先分配的空间过大，可能会造成内存空间的浪费；如果分配的空间过小，当数据元素个数超过预先分配的大小时，就会出现溢出错误，导致程序无法正常运行。

---

阐述顺序表中插入和删除操作的基本步骤和时间复杂度。

---

如何在顺序表中实现元素的查找？请描述查找算法的思路和时间复杂度。

---

链式存储结构

链表与顺序表有什么不同？在什么情况下适合使用链表？
链表与顺序表在存储结构、数据访问方式、插入删除操作等方面存在不同，以下是具体分析以及链表适用场景的介绍：

存储结构
顺序表：采用连续的存储空间来存储数据元素，就像数组一样，在内存中是一块连续的区域，逻辑上相邻的元素在物理位置上也相邻。
链表：采用=离散的存储方式，每个数据元素（节点）除了存储自身的数据外，还需要存储指向下一个节点的指针（单链表）或指向前驱和后继节点的指针（双链表），节点在内存中的位置是不连续的，通过指针来链接各个节点，形成逻辑上的线性结构。

数据访问方式
顺序表：支持随机访问，可以通过下标直接访问任意位置的元素，时间复杂度为O(1) ，能快速定位到需要的元素，就像在一排连续的座位中，直接根据座位号就能找到对应的人。
链表：不支持随机访问，只能从链表的头节点开始，通过指针逐个遍历节点来访问数据，访问第i个元素的时间复杂度为O(n)，类似于在一条串联的珠子项链上，要找到某颗特定的珠子，需要从一端开始逐个查找。

插入和删除操作
顺序表：插入和删除元素时，通常需要移动大量元素。比如在表头插入一个元素，需要将后面的所有元素都向后移动一位，时间复杂度为 O(n)。
链表：插入和删除操作相对简单，只需修改相关节点的指针即可。例如在链表中插入一个新节点，只需找到插入位置的前一个节点，将其指针指向新节点，新节点再指向原来的下一个节点，时间复杂度为O(1)（前提是已经找到插入位置的前一个节点）。

空间分配
顺序表：需要预先分配固定大小的存储空间，如果数据量变化较大，可能会出现空间浪费或空间不足的情况。
链表：不需要预先分配大量空间，它的空间是根据实际需求动态分配的，只要内存还有空间，就可以不断地插入新节点，更灵活地适应数据量的变化。

根据以上特点，链表适用于以下情况：
数据量不确定且经常需要进行插入和删除操作：例如，在一个实时处理数据的系统中，数据的到来是不确定的，可能随时需要插入新数据，或者根据某些条件删除已有的数据，使用链表可以高效地完成这些操作，而不会像顺序表那样因为大量元素的移动而消耗过多时间。
内存空间有限且需要动态管理内存：当程序运行时可用的内存空间有限，并且数据的大小和数量在运行过程中会动态变化时，链表的动态内存分配特性可以更好地利用有限的内存资源，避免顺序表可能出现的内存溢出问题。
实现一些需要频繁插入和删除节点的算法和数据结构：如实现栈、队列等数据结构，以及一些图算法中的邻接表表示等，链表能够提供更高效的操作支持。

---

请描述单链表、双链表和循环链表的结构特点和适用场景。
单链表、双链表和循环链表是常见的链表结构，它们的结构特点各有不同，在不同的应用场景中发挥着各自的优势，具体如下：

单链表
结构特点：每个节点包含数据域和指针域，指针域指向下一个节点，最后一个节点的指针域为 NULL，表头指针指向第一个节点，通过指针依次访问各个节点，形成线性结构。
适用场景：适用于数据元素的插入和删除操作较为频繁，且不需要频繁地反向遍历数据的场景。例如，在简单的线性数据集合管理中，如学生信息的简单存储与动态更新，新学生的插入和退学学生信息的删除操作较多，而查询操作主要是从前往后顺序进行，使用单链表可以高效地实现这些操作。

双链表
结构特点：每个节点除了数据域外，还包含两个指针域，一个指向前驱节点，一个指向后继节点。表头指针指向第一个节点，第一个节点的前驱指针为 NULL，最后一个节点的后继指针为 NULL，这样可以双向遍历链表，既可以从前往后，也可以从后往前访问节点。
适用场景：当需要频繁地在链表中进行双向遍历操作时，双链表更为合适。比如在实现文本编辑器的撤销和重做功能时，用户既可以撤销最近的操作（向前遍历），也可以重做已撤销的操作（向后遍历），双链表能够方便地实现这种双向的操作记录和访问。

循环链表
结构特点：循环链表分为单循环链表和双循环链表。单循环链表中，最后一个节点的指针不是指向 NULL，而是指向表头节点，形成一个环形结构；双循环链表中，表头节点的前驱指针指向最后一个节点，最后一个节点的后继指针指向表头节点，也构成一个环形。
适用场景：适用于需要循环处理数据的场景，如约瑟夫环问题，在一个环形的人员队列中，按照一定的规则依次淘汰人员，直到只剩下最后一个人，循环链表可以很好地模拟这种环形的结构和循环处理的过程。又如，在操作系统的进程调度中，将所有就绪进程用循环链表连接起来，调度程序可以依次遍历链表来分配 CPU 时间片，当遍历到链表末尾时，又回到表头继续循环，实现进程的轮流执行。

---

如何实现单链表的遍历？请写出遍历单链表的代码。
遍历单链表是指按照链表中节点的顺序依次访问每个节点的数据。基本思路是从链表的头节点开始，通过节点的指针域依次访问下一个节点，直到遍历完整个链表（即遇到指针域为 NULL 的节点）。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 定义单链表类
class LinkedList:def __init__(self):self.head = None# 遍历单链表的方法def traverse(self):current = self.headwhile current:print(current.val)current = current.next# 创建单链表并添加节点
linked_list = LinkedList()
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
linked_list.head = node1
node1.next = node2
node2.next = node3# 遍历单链表
linked_list.traverse()

---

解释一下链表中的头结点和头指针的作用，是否可以省略头结点？
在链表中，头结点和头指针起着不同但又相互配合的重要作用，以下是对它们的详细解释以及关于头结点是否可以省略的分析：

头结点的作用
简化插入和删除操作：头结点是为了操作的统一与方便而设立的，它的数据域可以不存储任何信息，也可以存储如链表长度等附加信息。有了头结点，在链表的头部进行插入和删除操作时，就无需特殊处理，和在其他位置的操作一致，都可以通过修改指针来完成。例如，要在链表头部插入一个新节点，只需将新节点的指针指向原头结点的下一个节点，然后将头结点的指针指向新节点即可，无需像没有头结点时那样，需要单独处理头指针的更新。
标识链表的开始：它作为链表的第一个节点，明确标识了链表的起始位置，使得对链表的遍历等操作有一个确定的起点。即使链表为空，头结点也存在，此时头结点的指针域指向
NULL。

头指针的作用：头指针是指向链表头结点（或第一个数据节点，如果没有头结点的话）的指针变量。它是访问链表的唯一入口，通过头指针可以找到链表中的任意节点，进而实现对链表的各种操作，如遍历、插入、删除等。无论链表是否为空，头指针都始终存在，并且不会改变其指向链表头部的性质。

是否可以省略头结点：在实际应用中，头结点是可以省略的。当链表的操作主要集中在链表的中间和尾部，且对链表头部的插入、删除操作很少或者不需要统一处理边界情况时，可以不设置头结点。这样可以节省一个节点的存储空间，并且代码实现上相对简单一些，因为不需要额外处理头结点相关的逻辑。然而，省略头结点可能会使链表头部的操作变得复杂，需要单独处理插入和删除第一个节点的情况，容易导致代码的可读性和可维护性下降。所以在大多数情况下，尤其是在需要频繁进行各种链表操作的场景中，使用头结点可以使代码更加清晰、简洁，减少出错的可能性。

---

如何在单链表中插入和删除一个节点？请描述具体的操作过程，并分析时间复杂度。

---

算法相关

请编写一个算法，实现将两个有序链表合并成一个新的有序链表。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists(l1, l2):dummy = ListNode(0)current = dummywhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextif l1:current.next = l1if l2:current.next = l2return dummy.next# 辅助函数：将列表转换为链表
def list_to_linked_list(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 辅助函数：将链表转换为列表
def linked_list_to_list(head):result = []current = headwhile current:result.append(current.val)current = current.nextreturn result# 示例用法
l1 = list_to_linked_list([1, 2, 4])
l2 = list_to_linked_list([1, 3, 4])
merged_head = merge_two_lists(l1, l2)
print(linked_list_to_list(merged_head))

---

如何判断一个链表是否存在环？请描述算法思路，并分析时间复杂度和空间复杂度。
判断一个链表是否存在环可以使用快慢指针法（Floyd 判圈算法），以下是详细步骤：
初始化指针：
定义两个指针，一个快指针 fast 和一个慢指针 slow，它们都初始化为链表的头节点。
指针移动：
慢指针 slow 每次移动一步，即 slow = slow.next。
快指针 fast 每次移动两步，即 fast = fast.next.next。
判断是否有环：
在指针移动过程中，如果链表中存在环，那么快指针 fast 最终会追上慢指针 slow，即 fast == slow，此时就可以判定链表存在环。
如果链表中不存在环，那么快指针 fast 会先到达链表的末尾（即 fast 或者 fast.next 为 None），此时可以判定链表不存在环。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef has_cycle(head):if not head or not head.next:return Falseslow = headfast = head.nextwhile slow != fast:if not fast or not fast.next:return Falseslow = slow.nextfast = fast.next.nextreturn True

---

编写一个函数，删除单链表中指定值的所有节点。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef remove_elements(head, val):# 创建一个虚拟头节点，方便处理头节点需要删除的情况dummy = ListNode(0)dummy.next = headcurrent = dummywhile current.next:if current.next.val == val:# 如果下一个节点的值等于指定值，跳过该节点current.next = current.next.nextelse:# 否则移动到下一个节点current = current.nextreturn dummy.next# 辅助函数：将列表转换为链表
def list_to_linked_list(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 辅助函数：将链表转换为列表
def linked_list_to_list(head):result = []current = headwhile current:result.append(current.val)current = current.nextreturn result# 示例用法
head = list_to_linked_list([1, 2, 6, 3, 4, 5, 6])
new_head = remove_elements(head, 6)
print(linked_list_to_list(new_head))

---

给定一个单链表，如何反转该链表？请给出算法思路和代码实现。
反转单链表可以使用迭代和递归两种常见的方法，下面分别介绍这两种方法的思路：
迭代法
初始化指针：定义三个指针，prev 初始化为 None，curr 初始化为链表的头节点，next_node 用于临时保存 curr 的下一个节点。
遍历链表：在遍历过程中，首先保存 curr 的下一个节点到 next_node，然后将 curr 的 next 指针指向 prev，接着更新 prev 为 curr，curr 为 next_node，不断重复这个过程，直到 curr 为 None。
返回结果：当 curr 为 None 时，prev 就指向了原链表的最后一个节点，也就是反转后链表的头节点，返回 prev。

递归法
终止条件：如果链表为空或者只有一个节点，直接返回该链表，因为空链表或者只有一个节点的链表反转后还是其本身。
递归调用：递归地反转当前节点之后的链表，得到反转后的子链表。
调整指针：将当前节点的下一个节点的 next 指针指向当前节点，然后将当前节点的 next 指针置为 None。
返回结果：返回反转后的子链表的头节点。

# 定义单链表节点类
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 迭代法反转链表
def reverseList_iterative(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev# 递归法反转链表
def reverseList_recursive(head):if not head or not head.next:return headnew_head = reverseList_recursive(head.next)head.next.next = headhead.next = Nonereturn new_head# 辅助函数：将列表转换为链表
def list_to_linked_list(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 辅助函数：将链表转换为列表
def linked_list_to_list(head):result = []current = headwhile current:result.append(current.val)current = current.nextreturn result# 示例用法
head = list_to_linked_list([1, 2, 3, 4, 5])
# 使用迭代法反转链表
reversed_head_iterative = reverseList_iterative(head)
print("迭代法反转后的链表:", linked_list_to_list(reversed_head_iterative))# 重新创建链表用于递归法测试
head = list_to_linked_list([1, 2, 3, 4, 5])
# 使用递归法反转链表
reversed_head_recursive = reverseList_recursive(head)
print("递归法反转后的链表:", linked_list_to_list(reversed_head_recursive))

---

其他

线性表在实际应用中有哪些常见的场景？请举例说明。
线性表是一种基本的数据结构，在实际应用中有许多常见的场景，以下是一些例子：

数据存储与管理：在数据库系统中，数据表中的数据通常以线性表的形式进行存储和管理。例如，一个存储学生信息的表，每一行代表一个学生的记录，包括学号、姓名、年龄等字段，这些记录就可以看作是线性表中的元素。通过线性表的操作，可以方便地进行数据的插入、删除、查找等操作，如添加新学生记录、删除退学学生记录、根据学号查找学生信息等。

文本处理：在文本编辑器中，文本内容可以看作是一个字符的线性表。用户对文本的各种操作，如插入字符、删除字符、查找特定字符串等，都可以通过对线性表的相应操作来实现。例如，当用户在文档中插入一个新的段落时，实际上就是在线性表中特定位置插入一系列字符元素；查找某个关键词时，就是在线性表中遍历查找匹配的字符序列。

图的邻接表表示：在图论中，图的邻接表是一种常用的存储方式，其中就用到了线性表。对于图中的每个顶点，用一个线性表来存储与该顶点相邻的顶点信息。例如，在一个有向图中，顶点A与顶点B、C相邻，那么可以用一个线性表[B,C]来表示顶点A的邻接顶点。通过这种方式，可以方便地存储和遍历图的边信息，进行图的各种算法操作，如深度优先搜索、广度优先搜索等。

内存管理：操作系统中的内存管理也会用到线性表。系统会维护一个空闲内存块的线性表，每个元素代表一个空闲的内存块，记录其起始地址、大小等信息。当有程序申请内存时，系统会在这个线性表中查找合适的空闲块，进行分配；当程序释放内存时，又会将释放的内存块合并到空闲内存块线性表中。这样可以有效地管理内存资源，提高内存的利用率。

---

对比线性表的顺序存储和链式存储，在不同的应用场景下，你会如何选择？
线性表的顺序存储和链式存储是两种常见的存储方式，前者逻辑上相邻的元素在物理位置上也相邻，后者通过指针将物理位置上不一定相邻的节点链接起来。在不同应用场景下，可根据以下几个方面的特性来选择合适的存储方式：

随机访问需求
顺序存储：它支持随机访问，可通过数组下标直接访问元素，时间复杂度为O(1)。比如在一个需要频繁根据索引查找元素的场景，如学生成绩管理系统中，若经常要根据学生的学号（假设学号是连续的，可作为数组下标）快速查询成绩，顺序存储就很合适。
链式存储：不支持随机访问，要访问第i个元素，需从表头开始遍历链表，时间复杂度为O(n)。所以对于有大量随机访问需求的场景，链式存储不是最佳选择。

插入和删除操作频率
顺序存储：在顺序表中插入和删除元素，平均要移动大约一半的元素，时间复杂度为 O(n)。如果在一个线性表中需要频繁地进行插入和删除操作，比如在一个实时处理数据的系统中，新数据不断插入，旧数据不断删除，使用顺序存储会导致大量的数据移动，效率较低。
链式存储：在链表中插入和删除元素，只需修改相关节点的指针，时间复杂度为O(1)（前提是已找到要操作的位置）。因此，对于插入和删除操作频繁的场景，如文本编辑中，用户频繁地插入和删除字符，链式存储更能体现出其优势。

内存空间管理
顺序存储：顺序存储需要一块连续的内存空间，当线性表长度变化较大时，可能会出现空间浪费或溢出的情况。例如，事先分配了较大的空间，但实际使用的元素很少，就会造成内存空间的浪费；而如果元素数量超出了预分配的空间，又需要进行扩容操作，这可能涉及到数据的重新复制，效率较低。
链式存储：链式存储的节点空间是动态分配的，不需要连续的内存空间，能更灵活地利用内存。在内存资源紧张且数据量不确定的情况下，链式存储更合适。比如在一些嵌入式系统中，内存资源有限，且数据的产生和销毁是动态的，使用链式存储可以更好地管理内存。

数据规模可预测性
顺序存储：如果数据规模在初始化时就可以确定，且不会有太大变化，顺序存储可以根据预计的数据量分配合适的空间，能有效地利用内存，并且可以利用数组的特性进行一些优化，提高访问效率。例如，在一个固定大小的缓存系统中，已知最多需要存储N个数据项，使用顺序存储可以预先分配好空间，简单高效。
链式存储：当数据规模不确定，可能会动态增长或缩小，链式存储可以根据实际需求动态地分配和释放节点空间，不会因为数据规模的变化而导致内存管理上的困难。比如在一个网络数据包处理系统中，数据包的数量是不确定的，使用链式存储可以方便地处理不同数量的数据包。

---

3.栈、队列、数组

栈和队列的定义与特性：

请简述栈的定义和特点。
栈是只允许在一端进行插入或删除操作的线性表，允许操作的一端称为栈顶，另一端称为栈底。其特点是后进先出（LIFO），就像一个只允许从顶部取放物品的容器，最后放入的物品会最先被取出。

---

队列与栈有什么区别？
队列是只允许在一端插入，在另一端删除的线性表，插入端称为队尾，删除端称为队头，遵循先进先出（FIFO）原则，如同排队一样，先到的人先接受服务。

而栈是后进先出。另外，栈的插入和删除都在栈顶进行；队列在队尾插入，队头删除。用链表存储时，栈可以实现多栈空间共享，队列一般不行。

---

顺序栈与链栈：

简述顺序栈的基本操作。
顺序栈是用顺序存储结构实现的栈，
基本操作包括判空，通过判断栈顶指针是否指向栈底来确定栈是否为空；
进栈操作，将元素压入栈顶，同时栈顶指针上移；
出栈操作，弹出栈顶元素，栈顶指针下移；
读取栈顶元素，获取栈顶元素的值但不改变栈的状态。

---

链栈有什么特点？

链栈是用链式存储结构实现的栈，
一般不存在栈满的情况，
空栈的判定条件通常定为栈顶指针top == null。
它的优点是可以动态地分配内存空间，适应数据量的变化；
缺点是需要额外的指针域来存储后继节点的地址，会占用一定的空间。

顺序队列与循环队列：

什么是循环队列？它是如何解决顺序队列的问题的？
循环队列是把顺序队列的存储空间想象成一个首尾相接的圆环，将数组 “掰弯” 形成的。
它解决了顺序队列中可能出现的 “假溢出” 问题，即当队尾指针已经到达数组末尾，但队头前面还有空闲空间时，无法继续插入元素的情况。在循环队列中，队尾指针可以循环回到数组开头，充分利用数组空间。

---

如何判断循环队列是空还是满？

方法一：设置标志位tag，当tag = 0且队头指针front等于队尾指针rear时表示队空；当tag = 1且front等于rear时表示队满。每次删除成功操作时，令tag = 0；每次插入成功操作时，令tag = 1。
方法二：把front = rear仅作为队空的判定条件，当队列满的时候，令数组中仍然保留一个空余单元，即当(rear + 1) % maxsize == front时认为队列已满，其中maxsize是队列的最大容量。

---

栈和队列的应用：

栈在括号匹配问题中是如何应用的？
算法思想是：
1.若是左括号，入栈；
2.若是右括号，出栈一个左括号判断是否与之匹配。
3.在检验到字符串尾时，还要检查栈是否为空，只有栈空，整个字符串才是括号匹配的。
例如，对于字符串 “{[()]}”，依次将 “{”“[”“(” 入栈，遇到 “)” 时，将栈顶元素 “(” 出栈进行匹配，以此类推，最后栈为空，说明括号匹配。

---

如何利用栈将中缀表达式转换为后缀表达式？
手算：首先按运算符优先级对所有运算符和它的运算数加括号（原本的括号不用加），然后把运算符移到对应括号后，最后去掉括号即可。

例如，中缀表达式 “3 + 4 * 2”，转换过程为 “((3)+(42))” -> “((3)(4 2))+” -> “3 4 2 * +”，得到后缀表达式 “3 4 2 * +”。
计算机

---

后缀表达式求值

---

队列在层次遍历二叉树中是如何应用的？
利用队列的先进先出特性，先将根节点入队，然后每次取出队头节点进行访问，并将其左右子节点（如果存在）依次入队，重复这个过程，直到队列为空，就实现了二叉树的层次遍历。这样可以保证按照从上到下、从左到右的顺序访问二叉树的每个节点。

---

双端队列

---

队列在计算机系统中的应用
缓冲区
计算机资源竞争请求

---

代码实现

队列

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10 // 定义循环队列的最大容量typedef struct {int data[MAXSIZE];int front; // 队头指针int rear; // 队尾指针
} CirQueue;// 初始化循环队列
void InitQueue(CirQueue *Q) {Q->front = Q->rear = 0;
}// 入队操作
void EnQueue(CirQueue *Q, int x) {if ((Q->rear + 1) % MAXSIZE == Q->front) {printf("Queue is full.\n");return;}Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MAXSIZE;
}// 出队操作
int DeQueue(CirQueue *Q) {if (Q->front == Q->rear) {printf("Queue is empty.\n");return -1;}int x = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSIZE;return x;
}int main() {CirQueue Q;InitQueue(&Q);EnQueue(&Q, 1);EnQueue(&Q, 2);EnQueue(&Q, 3);printf("DeQueue: %d\n", DeQueue(&Q));printf("DeQueue: %d\n", DeQueue(&Q));printf("DeQueue: %d\n", DeQueue(&Q));return 0;
}

---

栈

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100 // 定义栈的最大容量typedef struct {int data[MAXSIZE];int top; // 栈顶指针
} SqStack;// 初始化栈
void InitStack(SqStack *S) {S->top = -1;
}// 进栈操作
void Push(SqStack *S, int x) {if (S->top == MAXSIZE - 1) {printf("Stack is full.\n");return;}S->data[++S->top] = x;
}// 出栈操作
int Pop(SqStack *S) {if (S->top == -1) {printf("Stack is empty.\n");return -1;}return S->data[S->top--];
}int main() {SqStack S;InitStack(&S);Push(&S, 1);Push(&S, 2);Push(&S, 3);printf("Pop: %d\n", Pop(&S));printf("Pop: %d\n", Pop(&S));printf("Pop: %d\n", Pop(&S));return 0;
}

---

数组

数组的定义与特点

什么是数组？它有哪些特点？
数组是由相同类型的数据元素构成的有限序列，每个元素可以通过下标来唯一标识。数组的特点包括：数据元素具有相同的数据类型；数组的长度是固定的，一旦定义，其大小通常不能轻易改变；数组在内存中是连续存储的，这使得可以通过数组名和下标快速地访问数组元素，时间复杂度为
O(1)。

---

多维数组

请解释多维数组的存储方式，以二维数组为例说明。
多维数组在内存中是按照线性方式存储的。以二维数组a[m][n]为例，有两种常见的存储方式：行优先存储和列优先存储。

行优先存储是先存储第一行的所有元素，接着存储第二行，以此类推，就像我们按行读取表格数据一样。在 C 语言中，二维数组就是采用行优先存储方式。

列优先存储则是先存储第一列的所有元素，再存储第二列，依此类推，例如 FORTRAN 语言中二维数组默认是列优先存储。

---

如何计算二维数组中元素的地址？

假设二维数组a[m][n]，每个元素占k个字节，起始地址为base，按行优先存储，求a[i][j]的地址。
根据行优先存储的规则，a[i][j]之前有i行，每行有n个元素，再加上当前行中前面有j个元素，所以a[i][j]的地址计算公式为：LOC(a[i][j]) = base + (i * n + j) * k。

---

特殊矩阵的压缩存储

什么是特殊矩阵？常见的特殊矩阵有哪些？
特殊矩阵是指矩阵中存在大量相同元素或零元素，且这些元素的分布有一定规律的矩阵。常见的特殊矩阵有对称矩阵、对角矩阵、三角矩阵等。
例如，对称矩阵满足a[i][j] = a[j][i]，其数据元素关于主对角线对称；
对角矩阵是除主对角线及其附近若干条对角线的元素外，其余元素都为零的矩阵；
三角矩阵又分为上三角矩阵和下三角矩阵，上三角矩阵是指矩阵的下三角部分（不包括主对角线）的元素均为零，下三角矩阵则是上三角部分（不包括主对角线）的元素均为零。

---

如何对对称矩阵进行压缩存储？
由于对称矩阵的元素关于主对角线对称，所以只需要存储主对角线及其以上（或以下）的元素即可。可以将这些元素按行优先（或列优先）的顺序存储到一个一维数组中。假设对称矩阵A[n][n]，用一维数组B[m]来存储，其中m = n * (n + 1) / 2（这是因为对称矩阵需要存储的元素个数为n(n + 1)/2个）。对于矩阵中的元素A[i][j]，若i >= j（按行优先存储下三角部分），则它在一维数组B中的存储位置k = i * (i + 1) / 2 + j；若i < j（即存储上三角部分），则A[i][j] = A[j][i]，可通过上述公式计算A[j][i]的存储位置。

---

稀疏矩阵

什么是稀疏矩阵？如何表示稀疏矩阵？
稀疏矩阵是指矩阵中绝大多数元素为零的矩阵。为了节省存储空间，可以采用三元组表或十字链表来表示稀疏矩阵。
三元组表是用一个三元组(i, j, a[i][j])来表示矩阵中的非零元素，其中i表示行下标，j表示列下标，a[i][j]表示该元素的值，然后将所有非零元素的三元组按一定顺序存储起来。

十字链表则是一种更复杂的链式存储结构，它为每个非零元素建立一个节点，节点中除了存储元素的值、行下标和列下标外，还包含指向同一行和同一列下一个非零元素的指针，通过这些指针将矩阵中的非零元素链接成一个十字交叉的链表结构，适用于对稀疏矩阵进行频繁的插入、删除等操作的情况。

---

简述稀疏矩阵的加法运算过程（基于三元组表存储）。
设有两个稀疏矩阵A和B，都以三元组表的形式存储。首先，分别初始化两个指针pa和pb，指向A和B的三元组表的第一个非零元素。

然后，比较pa和pb所指向的元素的行下标和列下标：
如果行下标和列下标都相等，则将两个元素的值相加，若和不为零，则在结果矩阵C的三元组表中添加一个新的三元组；

如果行下标相等但列下标不等，则将列下标较小的元素直接复制到结果矩阵C的三元组表中；

如果行下标不等，则将行下标较小的元素复制到结果矩阵C的三元组表中。

重复上述过程，直到A和B的三元组表中有一个被遍历完，再将另一个三元组表中剩余的元素全部复制到结果矩阵C的三元组表中。

---

数组与其他数据结构的关系

数组与线性表有什么关系？
数组可以看作是线性表的一种扩展。线性表是一种线性结构，其中的数据元素之间存在一对一的线性关系。
而数组是一种特殊的线性表，它的每个元素本身可以是一个线性表（如二维数组可以看作是由多个一维数组组成的线性表），或者是具有相同数据类型的元素的集合。
数组与线性表的主要区别在于数组的长度通常是固定的，而线性表的长度可以动态变化；数组可以通过下标直接访问元素，时间复杂度为 O(1)，而线性表如果采用顺序存储结构也可以通过下标访问，但如果采用链式存储结构，则需要从头节点开始遍历查找元素，时间复杂度为 O(n)。

---

数组在实现其他数据结构（如栈、队列）时有什么作用？
数组是实现顺序栈和顺序队列的基础数据结构。
在顺序栈中，通过数组来存储栈中的元素，利用栈顶指针来指示栈顶元素在数组中的位置，通过对栈顶指针的操作实现进栈和出栈等操作。在顺序队列中，同样使用数组来存储队列元素，通过队头指针和队尾指针来管理队列的元素进出，当队尾指针指向数组末尾时，可能需要考虑循环利用数组空间（如循环队列）来避免 “假溢出” 问题。

---

4.串 广义表

串的基本概念

串与线性表的关系：串是一种特殊的线性表，其特殊性在于数据元素是单个字符。它在逻辑结构上与线性表类似，但在操作和存储上有自身特点。
例如，串通常更关注字符序列的整体操作，如查找子串、替换等，而线性表的操作可能更侧重于单个元素的插入、删除等。
串的长度：指的是串中字符的个数。需要注意的是，空串是长度为 0 的串，而空格串是由一个或多个空格字符组成的串，它的长度不为 0。

串的存储结构

顺序存储：串的顺序存储是用一组连续的存储单元依次存放串中的字符。它可以是静态分配的数组，也可以是动态分配的数组。
静态分配时，数组大小固定，可能会出现空间浪费或溢出的问题；
动态分配则可以根据实际需要调整数组大小，但操作相对复杂一些。
例如，在 C 语言中可以用字符数组来实现串的顺序存储，通过 ‘\0’ 字符来标识串的结束。

链式存储：串的链式存储是通过链表来存储串中的字符。每个结点可以存储一个或多个字符，结点之间通过指针相连。
与顺序存储相比，链式存储插入和删除字符更方便，但存储密度较低，且访问效率相对较低，因为需要通过指针来遍历链表。
例如，若每个结点只存储一个字符，那么要查找串中的第 i 个字符，就需要从链表头开始遍历 i 次。

串的模式匹配算法

简单的模式匹配算法（暴力匹配）：

该算法的基本思想是从主串的第一个字符开始，与子串的第一个字符比较，如果相同则继续比较下一个字符；如果不同则从主串的第二个字符开始，重新和子串的第一个字符比较，依次类推，直到找到匹配的子串或者主串遍历完毕。其时间复杂度在最坏情况下为 O (m*n)，其中 m 是主串长度，n 是子串长度。
例如，主串 S = “abcdefg”，子串 T = “cde”，算法会先比较 S [0] 与 T [0]，不匹配后再比较 S [1] 与 T [0]，直到比较 S [2] 与 T [0] 开始匹配，然后继续比较后续字符。

KMP 算法：

KMP 算法是对简单模式匹配算法的改进，它利用已经匹配过的信息，避免了不必要的回溯。
关键在于求解子串的 next 数组（或 nextval 数组），next 数组表示当匹配失败时，子串应该向右移动的位数。
其时间复杂度为 O (m+n)。
例如，对于子串 “abab”，其 next 数组为 [0, 1, 1, 2]，表示在匹配过程中，如果当前字符不匹配，根据 next 值可以直接将子串向右移动相应的位数，而不需要像暴力匹配那样回溯主串指针。
常考的问题包括 next 数组的计算、KMP 算法的执行过程以及与简单模式匹配算法的比较等。

前缀：除了最后一个字符外的所有元素的子串
后缀：除了第一个字符后的所有元素的字串
部分匹配值PM：最长相等的前后缀长度

---

广义表

广义表的定义与基本概念

定义：广义表是由零个或多个单元素或子表所组成的有限序列。通常用括号括起来，元素之间用逗号分隔，例如：L=(a,(b,c,d),e)。
表头和表尾：
表头是广义表中的第一个元素，可以是一个单元素，也可以是一个子表。
表尾是广义表中除表头之外的其余元素组成的子表。
例如，对于广义表L=(a,(b,c,d),e)，表头为a，表尾为((b,c,d),e)。需要注意的是，表尾一定是一个广义表。

广义表的性质

层次性：广义表中的元素可以是原子，也可以是子表，子表还可以有自己的子表，从而形成一种层次结构。例如
A=(a,(b,(c,d)))，
a是第一层元素，
(b,(c,d))是第二层子表，
(c,d)是第三层子表。
长度：广义表中直接包含的元素个数称为广义表的长度。例如，广义表(a,(b,c,d),e)的长度为3，因为它有a、(b,c,d)、e这三个直接元素。
深度：广义表中括号嵌套的最大层数称为广义表的深度。例如，广义表(a,(b,(c,d)))的深度为3，因为其括号最大嵌套层数是3层。

广义表的存储结构

链式存储：通常采用链式存储结构来表示广义表，每个结点可以是原子结点或表结点。原子结点包含数据域和指向下一个元素的指针域；表结点包含指向表头的指针域、指向下一个元素的指针域以及标志位（用于区分是原子结点还是表结点）。通过这种方式，可以方便地表示广义表的层次结构和各种操作。

广义表的操作

取表头（Head）操作：返回广义表的第一个元素。例如，对于广义表
L=(a,(b,c))，Head(L)=a。
取表尾（Tail）操作：返回广义表除表头元素之外的其余元素组成的子表。例如，对于广义表
L=(a,(b,c))，Tail(L)=((b,c))。

广义表与线性表的比较

数据元素类型：
线性表中的数据元素类型是单一的，通常是基本数据类型或自定义的结构体类型等；
广义表中的数据元素可以是不同类型的，既可以是原子（如整数、字符等），也可以是子表，具有更强的灵活性和表达能力。

结构复杂度：
线性表是一种线性结构，元素之间是一对一的关系，逻辑结构简单；
广义表是一种非线性结构，具有层次化的结构，元素之间的关系更为复杂，其操作和处理也相对复杂一些。
在考研复试中，可能会要求考生分析广义表的结构、计算广义表的长度和深度、根据给定的广义表进行表头和表尾的提取操作，或者考查广义表的存储结构以及相关操作的算法实现等。

5.树与二叉树

6.图

7.查找

8.排序