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)
循环队列
动机 : 解决\"假溢出\"的问题
入队列
出队列
字符串
串的存储结构
朴素模式匹配算法
KMP算法
next数组
作用 : 存储子串各个位置的j值变化
KMP算法实现
KMP算法的改进
树
树的相关概念
树的定义
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
二叉树
二叉树定义及特点
特殊的二叉树
斜树
满二叉树
完全二叉树
二叉树的四个性质
很浪费空间， 一般只适用于完全二叉树
二叉链表
遍历二叉树
前序遍历
根节点 -> 左子树 -> 右子树
中序遍历
左子树 -> 根节点 -> 右子树
后序遍历
左子树 -> 右子树 -> 根节点
层序遍历
根节点 -> 第一层 -> 第二层 -> ...
由遍历结果反推二叉树结构
二叉树的建立
线索二叉树
定义 : 线索化的实质是在遍历的过程中将二叉链表中的空指针改为指向前驱或后继的线索
树、森林与二叉树的转换
树转换为二叉树
森林转换为二叉树
二叉树转换为树
二叉树转换为森林
树与森林的遍历
赫夫曼树
定义 : 构造一棵叶子节点带权的二叉树，且带权路径长度WPL最小
构造方法
赫夫曼编码
图
图的相关概念
无向图
无向边
有向图
有向边(弧)
顶点的度
入度
出度
连通图相关术语
连通图
极大连通子图
强连通图
连通图的生成树
邻接矩阵
邻接表
十字链表
邻接多重表
边集数组
图的遍历
深度优先搜索(DFS)
使用递归实现
使用栈实现
广度优先搜索(BFS)
使用队列实现
最小生成树
定义 : n个节点，n-1条边，边的权重和最小
普里姆(Prim)算法
克鲁斯卡尔(Kruskal)算法
最短路径
迪杰斯特拉(Dijkstra)算法
弗洛伊德(Floyd)算法
拓扑排序
动机 : 解决一个工程是否能顺利进行
关键路径
动机 : 解决工程完成所需最短时间
查找
概念
静态查找表
动态查找表
顺序表查找 : 时间复杂度0(n)
加入哨兵优化
有序表查找 : 时间复杂度0(logn)
折半(二分)查找
插值查找
斐波那契查找
黄金分割原理
线性索引查找
稠密索引
分块索引 : 时间复杂度O(n^1/2)
块内无序
块间有序
倒排索引
二叉排序树
定义
3. 它的左、右子树也分别为二叉排序树
查找操作
插入操作
删除操作
平衡二叉树(AVL树)
实现算法
多路查找树(B树)
2-3树
2-3-4树
B树
B+树
哈希表(散列表)
哈希函数的构造方法
直接定址法
数字分析法
平法取中法
折叠法
除留余数法
随机数法
处理冲突的方法
开放定址法
再散列函数法
链地址法
公共溢出区法
排序
交换排序类
冒泡排序 : 时间复杂度O(n^2)
最简单的交换排序
缺点 : 在排序好某些关键字之后并没有对其余关键字排序有什么帮助
冒泡排序
优化
思路 : 在已经有序的情况下停止无意义的循环判断
快速排序 : 时间复杂度O(nlogn)
插入排序类
直接插入排序 : 时间复杂度O(n^2)
希尔排序 : 时间复杂度O(n^1.5)
关键 : 增量increment的选取
选择排序类
简单选择排序 : 时间复杂度O(n^2)
堆排序 : 时间复杂度O(nlogn)
堆的定义 : 堆是具有下列性质的完全二叉树
1. 大顶堆 : 每个节点的值大于等于其左右孩子节点的值
2. 小顶堆 : 每个节点的值小于等于其左右孩子节点的值
归并排序类
归并排序 : 时间复杂度O(nlogn)
归并定义 : 将两个或两个以上的有序表组合成一个新的有序表
缺点 : 空间复杂度较高
递归实现 : O(n+logn)
非递归实现 : : O(n)
0 条评论
回复 删除
下一页
