数据结构刷题笔记
一、绪论
- 通常从四个方面评价算法的质量：可读性、正确性、健壮性、高效性。
- 某算法时间复杂度为O(n*n)，说明算法执行时间与n *n成正比，其中n是问题规模
- 逻辑结构主要从数据元素之间的相邻关系考虑。用B=(D,R)表示，其中B表示一种逻辑数据结构，D是数据元素的集合，R是所有关系的集合
- 若某元素没有前驱节点，称其为开始元素，若没有后继节点，称其为终端元素
- 逻辑结构的类型：集合、线性结构、树形结构、图形结构
- 存储结构的类型：顺序存储结构、链式存储结构、索引存储结构、哈希（或散列）存储结构
- 数据运算包括功能描述和功能实现
二、线性表
- 线性表是一个元素个数大于等于0的有限序列
- 双向链表搜索指定元素从两个方向搜索和从一个方向搜索的时间复杂度相同（遍历一个节点所需时间不变）
- 带头结点的单链表为空的判断条件：Head->next = nullptr
- 带头结点的循环单链表为空的判断条件：Head->next = Head
- 无论是链表还是数组，若使用new或malloc创建则统一存入堆中，若作为局部变量则存入栈中
- 链表插入或删除任意元素的时间复杂度也为O(n)，因为需要遍历链表找到所指定的位置
- 从一个具有n个节点的单链表中查找指定节点，平均比较次数为 (n+1)/2
- 在对单链表进行头插法时，注意单链表有头指针还是头结点
- 链表中的“已知节点”指的是可以直接调用其指针的节点
三、栈和队列
- 栈和队列的共同点：只允许在端点处插入和删除元素
- 栈和队列都是线性表
- 用链式存储结构存储的队列，在插入新节点时可能要同时修改队首和队尾的指针（循环队列）
- 顺序循环队列Q[0:n-1]中，队列头指针为F，队尾指针为R，则循环队列中元素的个数是(R-F+n)%n
- 不是每一种数据结构都有查找功能（比如栈和队列）
- 链栈中不含不存储数据的头结点，栈顶指针直接指向第一个元素所在节点
- hanoi的搬运次数：2 * hanoi (n-1) + 1 且 hanoi(1) = 1
- 用链式存储方式存储的队列，在进行出队运算时删除尾指针所指节点，在进行入队操作时使用头插法
- 用链式存储方式存储的队列，如果没有头结点，则在进行出队操作时可能需要同时修改头指针和尾指针，因为当没有虚拟头结点的链表中仅有一个节点时，头指针和尾指针同时指向该节点
四、串
- void strcpy(dest, model) 有两个参数，是两个指向char数组首地址的指针，前为目标后为模板，函数执行复制操作
- 使用strlen可得到字符串中包括空格和标点符号在内的字符数。
- 使用sizeof运算符，得到的数会更大，因为它会把字符串末尾不可见的空字符\0也计算在内。
- 子串定义：串中任意个连续的字符组成的子序列
- 子序列定义：子序列则不要求连续，即可以是离散截取的，但字符之间的相对位置关系不变。
- KMP算法时间复杂度为O(m+n)
五、数组和稀疏矩阵
- 存取数组元素 != 插入，数组存取元素的时间复杂度为O(1)
- 数组中元素的起始地址 = 上一元素地址的结束
- 数组的首地址 = 数组中首个元素的起始地址 = a[0][0] 或 a[1][1]
- 对称矩阵一般存下三角（看题中具体问哪一部分的元素位置）
- 稀疏矩阵的压缩存储方法有：十字链表、三元组
六、递归
- 递归先序遍历一个节点为n，深度为d的二叉树，需要栈空间的大小为O(d)
七、树和二叉树
- 树的高度等于树中最深节点的深度
- 树的深度等于树的高度
- 节点的深度等于节点的层次，根节点在第一层
八、图
- 拓扑图：即有向无环图，因为拓扑排序中每个顶点只出现一次，而且对于图中的任何一条边，起点必须在终点之前。
- dfs和bfs一般默认为优先选择序号较小的节点
- 图的dfs类似于二叉树的先序遍历，bfs类似于二叉树的层序遍历
- 最小生成树不唯一（图中有权值相同的边），最小生成树的代价唯一
- 对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点
-
连通： 若节点i,j之间存在路径，则称两节点连通，连通这一概念仅在有向图中出现
-
连通图： 若无向图中任意两个节点间均连通，则称该图为连通图
-
强连通图： 若有向图中任意两个节点之间均存在路径，则称该图是强连通图
- Prim算法：用于从指定节点开始生成一个最小生成树，适用于稠密图
- Kruskal算法：用于生成一个最小生成树，不需要指定初始节点，适用于稀疏图。
- 关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期
- p（p > 2） 个顶点 p 条边的连通图中至少有3个生成树，因为该图中必有一环，环的边数最小为3，最大为p，生成子树的过程就是拆环的过程
- 带权有向图中有权值相同的边，最小生成树也可能唯一
- 无向图和有向图的总度和均为偶数，入度和与出度和可能为奇数
九、查找
- 中序遍历二叉有序树可得递增有序序列
- hash函数可以把字符串等任意长度的输入映射成固定长度的整数，也就是哈希值，不同的信息产生相同的哈希值叫哈希冲突
- Hash碰撞的解决办法：
- 双重散列（使用一个散列函数计算初始位置，使用另一个散列函数计算步长）
- 多重散列（使用一个散列函数计算初始位置，使用其余多个散列函数同时计算出多个可能的地址，然后选择其中空余的地址存入数据）
- 拉链法（也称链地址法，哈希表中包含若干槽，每一个槽都是一个链表（不包含数据）的头节点）
- 线性探测
- 二次探测（使用二次方程确定步长）
- 哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构
- 哈希查找次数 != 哈希探测次数 哈希查找次数还包含对计算所得初始位置的查找，而哈希探测次数只包含在发生哈希冲突后重新探测的次数
- 哈希查找次数：指将数据进行比较的总次数，在拉链法中头结点不存储数据，故不计入查找次数
- 红黑树查找的时间会比AVL树慢一点，因为最大高度为2logn，添加和删除操作比AVL树要快一些,因为红黑树是黑节点平衡的二叉树，所有不平衡必然在三次旋转以内解决。
- 红黑树和AVL树的查找、删除、插入操作的时间复杂度均为O(logn)
- 分块查找中若线性表一共有N个元素，则每一个块内最佳节点个数为N1/2，此时平均查找长度为N1/2+1
- 折半查找在最坏情况下的查找次数为[logn] + 1，注意logn向下取整
