Pixiv - Miracle
2-数据结构-绪论
1375 字
7 分钟
2-数据结构-绪论
算法
大端整数闭区间的长度b - a + 1 中端整数半开区间的长度b - a 小端整数开区间的长度b - a - 1
时间复杂度
渐进上界
渐进同阶
数据结构
逻辑结构的粒度只到集合，线性表，树形结构，网状结构
graph TB
DS["数据结构"]
SS["存储结构"]
LS["逻辑结构"]
DC["数据运算"]
LinearS["线性结构(线性表)"]
NLinearS["非线性结构"]
SqSto["顺序存储"]
ChainSto["链式存储"]
IndexSto["索引存储"]
HashSto["散列存储"]
LinearList["一般线性表"]
String["串"]
Stack["栈"]
Queue["队列"]
Array["数组"]
Graf["图状结构"]
Tree["树形结构"]
DS -------> SS
DS --> LS
DS ----> DC
LS --> LinearS
LS --> NLinearS
LinearS --> LinearList
LinearS --> String
LinearS --> Stack
LinearS --> Queue
LinearS --> Array
NLinearS --> Graf
NLinearS --> Tree
SS --> SqSto
SS --> ChainSto
SS --> IndexSto
SS --> HashSto
链表
头结点指的是哑结点
不带头结点循环链表的头结点变化要改变尾结点的指针域，带头结点的不需要，如果没有表尾指针则需要O(n)
| 单双 | 头结点 | 循环 | 表头结点指针 | 表尾结点指针 | 头插 | 头删 | 尾插 | 尾删 |
|---|---|---|---|---|---|---|---|---|
| 单链表 | 无 | 不循环 | 无 | 无 | - | - | - | - |
| 单链表 | 无 | 不循环 | 无 | 有 | - | - | - | - |
| 单链表 | 无 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 无 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 无 | 循环 | 无 | 无 | - | - | - | - |
| 单链表 | 无 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 无 | 循环 | 有 | 无 | O(n) | O(n) | O(n) | O(n) |
| 单链表 | 无 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 不循环 | 无 | 无 | - | - | - | - |
| 单链表 | 有 | 不循环 | 无 | 有 | - | - | - | - |
| 单链表 | 有 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 有 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 循环 | 无 | 无 | - | - | - | - |
| 单链表 | 有 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 有 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 双链表 | 无 | 不循环 | 无 | 无 | - | - | - | - |
| 双链表 | 无 | 不循环 | 无 | 有 | O(n) | O(n) | O(1) | O(1) |
| 双链表 | 无 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 双链表 | 无 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 无 | 无 | - | - | - | - |
| 双链表 | 无 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 有 | (无) | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 不循环 | 无 | 无 | - | - | - | - |
| 双链表 | 有 | 不循环 | 无 | 有 | O(n) | O(n) | O(1) | O(1) |
| 双链表 | 有 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 双链表 | 有 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 无 | 无 | - | - | - | - |
| 双链表 | 有 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 有 | (无) | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
双链表性质
-
双链表当且仅当头尾指针都没有的时候没有意义
-
头结点对双链表没有时间优化作用
-
循环双链表全O(1)
-
不循环双链表有O(1)没O(n)
单链表性质
- 单链表当且仅当，没有头指针，且不是，有尾指针并且循环的情况，的时候没有意义
- 单链表头部操作当且仅当，无头结点且有头无尾且循环的时候为O(n)
- 任何情况的单链表的尾删全部O(n)
- 单链表当且仅当有尾指针的时候尾插O(1)，其他O(n)
总结
- 循环双链表全O(1)
- 不循环双链表有O(1)没O(n)
- 任何情况的单链表的尾删全部O(n)
- 单链表有尾指针尾插O(1)其他O(n)
- 只有无头结点有头无尾循环单链表头部操作为O(n)
先看单双，再看操作或循环，再看是否为有头无尾无头结点循环，最多三次判断
栈
序列的合法性
三种序列之间的关系
graph LR
operationSequence["操作序列"]
enterSequence["入栈序列"]
exitSequence["出栈序列"]
operationSequence -->|"决定唯一"| enterSequence
operationSequence -->|"决定唯一"| exitSequence
enterSequence -->|"否决312类型的"| exitSequence
exitSequence -->|"否决231类型的"| enterSequence
注意到231和312互为逆置换
入栈序列+出栈序列决定唯一操作序列
标准化转换
设入栈序列对应的置换是a, 出栈序列对应的置换是b，把所有入栈序列位置对应到相应的出栈位置的映射为f，直觉上，f和操作序列是一一对应的，事实上也如此，暂时不在此处证明，故一对已知的入栈序列和出栈序列的合法性等价于操作序列的合法性等价于f的合法性，和实际的a和b无关，在解题过程中，将入栈序列标准化为恒等置换往往会更好做，怎么做呢。
由定义可知
由置换乘法的性质可得
也就是说可以将出栈序列乘上a的逆置换得到一个等价的标准合法问题，无论入栈序列已知还是未知，这种方法同样适用。
约束
出栈序列下一个元素要么栈顶，要么是未入栈的元素,
更接近正确的表述是：
-
若 (x<i) 且 (x) 在元素 (i) 之后出栈，则
因而真正不可能出现的区间是 ([j+1,i-x])。
-
若 (x>i)，需要额外加上“(x) 确实在元素 (i) 之前出栈”，此时才有
穷举
树的前序遍历=入栈序列，中序遍历=后序遍历，原因是左右子树遍历方式，新开函数帧为了返回来会把当前结点入栈，函数帧结束后结点会出栈。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章 智能推荐
1
3-数据结构-图
模板 考研
2
3-数据结构-树
模板 考研
3
1-数据结构-前置基础
模板 考研
4
10-Obsidian设置模板
杂项 杂项
5
2-mysql
web 无
随机文章 随机推荐