数据结构、算法
原创
数据结构
数据结构DS=(A,R) A是数据空间，R是A的关系空间
抽象数据类型ADT=(A,R,P)，P是操作空间
时间复杂度：n趋于无穷时，取O上界
线性表
- 线性表：分为顺序和链式
顺序的存储空间连续，链式通过动态分配内存
- 栈、队列
栈只能在一端操作（push pop），属于后进先出LIFO
栈的应用：表达式求值、递归调用
队列在尾端push，首端pop，属于先进先出FIFO
循环队列设front和rear两个指针，元素个数=(front-rear+Maxsize)%Maxsize
分析：
rear >= front时, len=rear-front
rear < front时, len=Maxsize-front+rear=rear-front+Maxsize
表达式求值：后缀形式，操作符作为parent节点放在child节点后边
46+5 *（120-37）：46 5 120 37 - * +
运算数入栈，遇到运算符，栈顶取运算数进行运算
队列：enqueue修改rear指针，dequeue修改front指针
循环队列：队空或者队满 rear==front，指针指在同一个元素
- 串
子串：任意长度的连续字符
子串的位置：定位后字串的首个字符的位置
字符串运算：赋值、连接、比较、求串长，求子串
- 模式匹配：
朴素的模式匹配：ij两个指针逐个比较
KMP：不相等时利用前缀和更新下一次比较的开始位置
- 数组：长度固定，类型相同
二维数组2dim，顺序存储线性表
特殊矩阵使用一维数组压缩存储
稀疏矩阵：三元组存储（行号，列号，元素值）
树结构
每个节点链接有2个及以上的后继结点
度：节点链接的节点个数，leaf度为0
- 二叉树：度≤2，分左子树和右子树
Bintree第i层至多有i^2-1个节点，第1层0个
Bintree深度为k，最多有2^k-1个节点：2^0+2^1+...+2^(k-1) = 2^k -1
n个节点的完全二叉树深度为log2n往下取整再+1
Bintree顺序存储：i节点的双亲为i/2向下取整，左子树2i，右子树2i+1
- 遍历：preorder，inorder，postorder，递归访问左子树、右子树，复杂度O(n)
最优二叉树huffman：带权路径长度最短，WPL=sum(位权*长度)
构造Huffman：选w最小的树作为左右子树，更新树的权值
编码：0代表左子树，1代表右子树
- BinSearchTree：左子树码值小于root，右子树大于root，递归遍历可以得到升序序列
图结构
图：任意两节点之间存在连接
G(V,E),V顶点集，E边集
有向图<vi,vj>和<vj,vi>是不同的弧
无向图(vi,vj)和(vj,vi)表示同一边E
完全图：n个顶点的完全无向图有n(n-1)/2条边E
度D(v)，入度ID，出度OD，路径（环路）
连通图：任意两个顶点V之间都有路径P
强连通图：有向图中任意两个顶点V之间都有路径P
- 网：边E带权值w
图不存在次序关系，不形成序列
- 存储结构：
邻接矩阵：i*j表示任意两个顶点V之间有边E及权w
邻接链表：每个顶点V使用一个链表存储相邻顶点V
算法
算法：有穷、确定、可行、输入、输出
- 程序流程图：方框处理，六棱框准备，预定义方框两边有竖线
- NS盒图，只有上下方向作为入出口，嵌套表示循环
排序
排序：稳定性（交换位置）
简单排序：直接插入排序，原有的元素后移，稳定O(n^2)
冒泡：逆序交换位置，稳定O(n^2)
简单选择：查找min值与对应位置交换，不稳定O(n^2)
希尔排序：gap大于（直接插入对应的）1，减少交换次数，逐步缩小增量，稳定O(n^2)
快速排序：从两边向中间扫描，出现小于或者大于pivot就交换位置，不稳定O(nlog2n)
堆排序：一维数组序列作为完全二叉树，p值大于左右c值，不稳定O(nlog2n)
归并排序：合并有序子序列，稳定O(nlog2n)
比较：n较小-选择，基本有序-冒泡，n较大-快排，堆排，归并（稳定）
外部排序：归并
查找
查找：长度为n的表，平均查找长度ASL=sum(PiCi)，P概率C比较次数
顺序查找：n/2
折半查找：二分log2n，查找树的高度
索引顺序：分块之间有序(b+bl)/2
哈希查找：Hash函数减少冲突（出现冲突时再次探测，线性探测顺序右移，链地址存储避免冲突）
- 动态查找：
二叉搜索树
平衡二叉树AVL：左子树与右子树深度差绝对值0或1
B树：自平衡，度数t表示非根节点至少t-1个键值对，最多2t-1个键值对
算法设计
分治：二分查找，快速排序
递推
动态规划：子问题不独立，递归定义最优值
贪心：局部最优
回溯：深度优先搜索解空间，子树中不存在解则回溯，迷宫，八皇后
分支定界法：广度优先搜索解空间，划分子空间，通过评估函数排除非最优子空间
随机性（概率）：数值概率（随机抽样得到近似解），蒙特卡洛（大量随机样本近似求解），拉斯维加斯（随机算法求解）和舍伍德（随机性改造算法）
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。