数据结构、算法

数据结构

数据结构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个键值对

算法设计

分治：二分查找，快速排序

递推

动态规划：子问题不独立，递归定义最优值

贪心：局部最优

回溯：深度优先搜索解空间，子树中不存在解则回溯，迷宫，八皇后

分支定界法：广度优先搜索解空间，划分子空间，通过评估函数排除非最优子空间

随机性（概率）：数值概率（随机抽样得到近似解），蒙特卡洛（大量随机样本近似求解），拉斯维加斯（随机算法求解）和舍伍德（随机性改造算法）