【408学习】数据结构——线性结构
注：本文为博主学习408相关知识所撰写的学习笔记内容，如有雷同，纯属巧合。
考点1 线性表的基本操作
| 基本操作 | 顺序表 | 链表 | 静态链表 |
按位查找 (随机查找) | O(1) 顺序表支持随机访问 | O(n) 在链表查找第i个元素只能遍历 | O(n) 在链表查找第i个元素只能遍历 |
| 按值查找 | O(n) 需要一个个遍历元素并与查找元素值对比才能 | O(n) 需要一个个遍历元素并与查找元素值对比才能确定是否查找成功 | O(n) 需要一个个遍历元素并与查找元素值对比才能确定是否查找成功 |
| 插入 | O(n) 需要大量移动元素腾出空位如果剩余连续空间不够还需将整个顺序表复制粘贴到一片新的更大的连续空间 | O(n)+O(1) 需要遍历来确定插入位置的前驱节点 然后修改指针进行插入 | O(n)+O(1) 需要遍历来确定插入位置的前驱节点 然后修改数组进行插入 |
| 删除 | O(n) 需要大量移动元素覆盖被删元素 | O(n)+O(1) 需要遍历来确定删除位置的前驱节点 然后修改指针进行删除 | O(n)+O(1) 需要遍历来确定删除位置的前驱节点 然后修改数组进行删除 |
注：静态链表操作与链表操作类似
典型真题
2023年真题
题目给定，顺序存储的有序表，即顺序表，顺序表中时间复杂度的操作为按位查找，A选项查找操作，时间复杂度为O(n)，B选项，插入操作时间复杂度也为O(n)，C选项删除操作，时间复杂度也为O(n)，D选项为按值查找操作时间复杂度为O(n)。
2016年真题
该题型需要画出示意图，如下图所示
我们可以分析出双链表的删除操作，需要先对p的后继节点的前驱修改为p的前驱节点，再将p的前驱节点的后继节点修改为p的后继节点，删除p节点，即选项D为正确选项。
2021年真题
该题型在上一道题的基础上加强了代码的健壮性，给出节点指针p,为尾指针，q为临时指针，如下图所示。
在链表的删除操作中，我们需要让上一个节点的next指针指向待删除节点的下一个节点，则需要让临时指针q指向当前待删除节点，我们可知现要删除的链表的第一个元素为头节点指向的元素，即h->next节点，则排除A、B选项，C、D选项需要考虑代码健壮性问题，删除的当前节点是否为尾节点，即当删除了该节点之后，只剩头节点的时候，才能让p=h，所以选项D为正确选项。
考点2 栈和队列的基本操作
栈和队列属于受限的线性表，该题型通过画图来模拟进行解答
栈：只允许在一端操作，即后进先出
队列：允许在两端操作，一般为一端进一端出，即先进先出，也有允许两端出的双端队列
典型真题
2020年真题
我们用表格的形式展现出出入栈操作，如下所示（Pop代表已出栈）
| e(Pop) |
| d |
| c(Pop) |
| b(Pop) |
| a |
我们可以知道得到的出栈序列为b,c,e即选项D
2011年真题
该题型没有限制出入栈的顺序，只限制了出栈以元素d开头的序列，则需要我们模拟出所以出入栈的情况，元素d需要最先出栈，则在如下表格方式的栈形式，我们可以知道当d出栈之后，a、b、c的出栈情况只能为c、b、a，则e可以出现在该序列的4个空位当中，解出以元素d开头的序列个数有4个，选择D选项。
| （NULL） |
| d |
| c |
| b |
| a |
2022年真题
该题中，符号集S可能取任意字母顺序，任意的一个排列给到in或out，现对符号集进行in和out的操作，确定是否能作为一个相匹配的出入栈序列，这里假设符号集序列为a,b,c,d，则若a,b,c,d是in的入栈序列，可以得到的出栈序列可能是a,b,c,d即入栈之后立即出栈，也可能d,c,b,a所有入栈完再依次出栈的序列，则A,B,C选项排除，选择D选项。
2010年真题
该题为队列的基本操作的模拟，我们可以用表格形式展现出队列的入队方式，假设左右两端端入队左端出队，则A选项如下表格所示
| e | d | c | a | b |
B选项如下表格所示
| e | c | a | b | d |
D选项如下表格所示
| d | a | b | c | e |
选项C由于a入队之后，b不管从左端还是右端入队，都无法得到选项C的出队方式，为不可能得到出队序列
2018年真题
该题中，队列序列如下表所示
| 6 | 5 | 4 | 3 | 2 | 1 |
则A选项的输出序列，为先进行两次①②③操作，再进行三次①②操作，再进行一次③操作，最后进行一次①②③操作和两次③操作得到结果。
B选项的输出序列，先进行两次①②操作，再进行一次③操作，再一次对4，5，6分别进行一次①②③，最后进行③操作得到结果。
D选项，先进行六次①②操作，再进行六次③操作得到结果，最终不能得到的输出序列为选项C。
2016年真题
待更新