Data Structure and Algorithm
2020-03-29 14:12:49 23 举报AI智能生成
大话数据结构思维导图
作者其他创作
大纲/内容
线性表
顺序存储结构
存储结构定义
顺序表存取元素 : 时间复杂度0(1)
顺序表插入、删除元素 : 时间复杂度0(n)
链式存储结构
单链表
存储结构定义
单链表读取元素 : 时间复杂度0(n)
单链表插入、删除元素 : 时间复杂度0(1)
单链表的创建
头插法
尾插法
单链表的删除
静态链表
定义 : 用数组描述的链表叫作静态链表
存储结构定义
静态链表插入操作
静态链表删除操作
循环链表
定义 : 将单链表中终端节点的指针由空指针改为指向头结点
动机 : 解决了如何从链表的任意一个节点出发, 访问到全部节点
存储结构定义
加入尾指针目的 : 以0(1)的时间复杂度访问到最后一个节点
双向链表
动机 : 方便查找上一节点
存储结构定义
双向链表插入元素 (顺序 : 插入节点S的前驱和后继 -> 后节点的前驱 -> 前节点的后继)
双向链表删除元素
栈与队列
栈(LIFO)
顺序存储结构
存储结构定义
进栈
出栈
双栈共享空间
动机 : 对于两个相同类型栈, 最大限度地利用事先开辟的存储空间来进行操作
思路 : 指针从数组两端向中间靠拢
链式存储结构
存储结构定义
进栈
出栈
栈的应用
递归
斐波那契数列
四则运算表达式求值
队列(FIFO)
顺序存储结构
循环队列
队列顺序存储的不足 : 因为要在队头出队列, 为了保证队头不为0, 后面所有的元素都要向前移动 , 时间复杂度为O(n)
动机 : 解决"假溢出"的问题
存储结构定义
入队列
出队列
链式存储结构
存储结构定义
入队列
出队列
字符串
串的存储结构
顺序存储结构
链式存储结构
朴素模式匹配算法
KMP算法
原理 : 在朴素模式匹配算法中, 主串的i值是不断地回溯来完成的, 这种回溯其实是可以不需要的, KMP算法只移动j值, 提升了效率
next数组
作用 : 存储子串各个位置的j值变化
思路 : 计算子串当前j值的字符串的最大公共前后缀长度n, 则next[j] = n+1
实现 : 计算next数组本质上也是模式匹配, 匹配的主串和子串都是当前的子串T
KMP算法实现
KMP算法的改进
原理 : 在计算出next值的同时, 若第a位字符与它next指向的第b位字符相等, 则该a位的nextval就指向第b位的nextval值, 若不相等, 则该a位的nextval值就是它自己a位的next值
树
树的相关概念
树的定义
叶子结点, 分支结点
结点的度, 树的度
兄弟, 堂兄弟
结点的层次, 树的深度
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
二叉树
二叉树定义及特点
特殊的二叉树
斜树
满二叉树
完全二叉树
二叉树的四个性质
存储结构定义
顺序存储结构
很浪费空间， 一般只适用于完全二叉树
二叉链表
遍历二叉树
前序遍历
根节点 -> 左子树 -> 右子树
中序遍历
左子树 -> 根节点 -> 右子树
后序遍历
左子树 -> 右子树 -> 根节点
层序遍历
根节点 -> 第一层 -> 第二层 -> ...
由遍历结果反推二叉树结构
二叉树的建立
使用前序遍历, 在原来访问节点处改成了生成节点
线索二叉树
动机 : n个节点的二叉树会存在n+1个空指针域, 浪费空间
定义 : 线索化的实质是在遍历的过程中将二叉链表中的空指针改为指向前驱或后继的线索
遍历 : 有了线索二叉树后, 我们对它进行遍历实际就等同于操作一个双向链表结构
树、森林与二叉树的转换
树转换为二叉树
森林转换为二叉树
二叉树转换为树
二叉树转换为森林
树与森林的遍历
赫夫曼树
定义 : 构造一棵叶子节点带权的二叉树，且带权路径长度WPL最小
构造方法
赫夫曼编码
图
图的相关概念
图
无向图
无向边
有向图
有向边(弧)
顶点的度
入度
出度
连通图相关术语
连通图
极大连通子图
强连通图
连通图的生成树
存储结构定义
邻接矩阵
邻接表
十字链表
邻接多重表
边集数组
图的遍历
深度优先搜索(DFS)
使用递归实现
使用栈实现
广度优先搜索(BFS)
使用队列实现
最小生成树
定义 : n个节点，n-1条边，边的权重和最小
普里姆(Prim)算法
克鲁斯卡尔(Kruskal)算法
最短路径
迪杰斯特拉(Dijkstra)算法
弗洛伊德(Floyd)算法
拓扑排序
动机 : 解决一个工程是否能顺利进行
关键路径
动机 : 解决工程完成所需最短时间
查找
概念
静态查找表
动态查找表
顺序表查找 : 时间复杂度0(n)
加入哨兵优化
有序表查找 : 时间复杂度0(logn)
折半(二分)查找
插值查找
元素的key与index越接近线性关系, 插值法效果越好
斐波那契查找
黄金分割原理
线性索引查找
稠密索引
分块索引 : 时间复杂度O(n^1/2)
块内无序
块间有序
倒排索引
二叉排序树
动机 : 有序表的查找效率不错, 但插入删除的效率很低, 二叉排序树可使得插入和删除效率不错, 又可以比较高效率地实现查找
定义
1. 若左子树不空, 则左子树上所有节点的值均小于它的根结构的值
2. 若右子树不空, 则右子树上所有节点的值均大于它的根结构的值
3. 它的左、右子树也分别为二叉排序树
查找操作
若其深度与完全二叉树相同, 则查找的时间复杂度为O(logn)
插入操作
删除操作
平衡二叉树(AVL树)
动机 : 二叉排序树的查找效率和树的形状有极大关系, 为了保证效率, 在插入时就维护树的形状
定义 : 平衡二叉树是一种二叉排序树, 其中每一个节点的左子树和右子树的高度差至多等于1
实现算法
多路查找树(B树)
2-3树
2-3-4树
B树
B+树
哈希表(散列表)
哈希函数的构造方法
直接定址法
数字分析法
平法取中法
折叠法
除留余数法
随机数法
处理冲突的方法
开放定址法
再散列函数法
链地址法
公共溢出区法
实现算法
若没有冲突, 时间复杂度为O(1)
排序
交换排序类
冒泡排序 : 时间复杂度O(n^2)
最简单的交换排序
缺点 : 在排序好某些关键字之后并没有对其余关键字排序有什么帮助
冒泡排序
思路 : 两两比较相邻记录的关键字, 如果反序则交换, 直到没有反序的记录为止
优化
思路 : 在已经有序的情况下停止无意义的循环判断
快速排序 : 时间复杂度O(nlogn)
插入排序类
直接插入排序 : 时间复杂度O(n^2)
思路 : 将一个记录插入到已经排好序的有序表中, 得到一个新的、记录数+1的有序表
优点 : 记录本身是有序的或记录数较少时, 效率很高
希尔排序 : 时间复杂度O(n^1.5)
思路 : 将相距某个增量的记录组成一个子序列, 对子序列使用直接插入排序
关键 : 增量increment的选取
选择排序类
简单选择排序 : 时间复杂度O(n^2)
思路 : 排序时找到合适的关键字再做交换, 只移动一次就完成一个关键字的排序, 性能略优于冒泡排序
堆排序 : 时间复杂度O(nlogn)
堆的定义 : 堆是具有下列性质的完全二叉树
1. 大顶堆 : 每个节点的值大于等于其左右孩子节点的值
2. 小顶堆 : 每个节点的值小于等于其左右孩子节点的值
思路 : 将待排序的序列构造出一个大顶堆, 将根节点与堆数组的最后一个元素互换, 此时末尾元素是最大值, 然后将剩余n-1的序列重新构造成大顶堆, 反复执行.
归并排序类
归并排序 : 时间复杂度O(nlogn)
归并定义 : 将两个或两个以上的有序表组合成一个新的有序表
思路 : 将n个有序子序列两两归并, 直到得到一个长度为n的有序序列
优化 : 使用非递归实现算法, 优化空间复杂度
缺点 : 空间复杂度较高
递归实现 : O(n+logn)
非递归实现 : : O(n)
0 条评论
下一页
