导图社区 数据结构课程框架
本人复习数据结构制作的导图，希望可以帮到大家~详细的总结了数据结构的查找，图，树，排序，线性表的考点知识内容。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数据结构复习
线性表
顺序存储对应随机存取，链式存储对应顺序存取
线性存储
归并
注意最后判断两个表空不空
查找
时间复杂度：
插入
删除
线性表的应用——就地逆置
不断交换线性表最前面和最后面的元素
链式存储
单链表的插入
注意代码的顺序
单链表的删除
注意代码顺序
单链表的就地逆置
不断做头删除，头插入
单循环链表
双向链表
栈和队列
栈
栈顶指针永远指向栈顶元素
栈是特殊的线性表（先入后出、后入先出）
空栈不出、满栈不入
栈用一个线性表实现，栈顶指针（其实是个数）top为-1表示空栈，而top=MAX-1表示满栈
栈满入栈成为上溢，栈空出栈成为下溢
队列
队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置
队列只能在队头（front）删除，只能在队尾（rear）插入
初始front=rear=-1
队列的假上溢现象
解决办法是构建循环队列（front=(front+1)%MAX）,rear=(rear+1)%MAX
堆满和队空的判断：front=rear
解决办法1：设立一个标志位，判断上一次操作是入栈还是出栈
解决办法2：设置一个数记录队列中元素的个数
解决办法3：牺牲一个存储空间（rear+1）%MAX==front
队列的链式存储结构
数组
几种特殊矩阵
上下三角矩阵
对称矩阵
三对角矩阵
稀疏矩阵
三元组表存储
树
二叉树的定义
二叉树或为空树，或为一个根节点再加上两棵分别成为左子树和右子树的互不相交二叉树构成
特殊的二叉树
满二叉树
完全二叉树
二叉树的性质
二叉树的第i层至多有个
k层的二叉树至多有
对于任意一棵二叉树，设叶子结点数为n0，二度结点数为n2，则有n0=n2+1
将二叉树按层序编号，编号为i的结点的左孩子结点为2i，右孩子结点为2i+1
二叉树的顺序存储
只存储完全二叉树，将0号空间空出来，参见性质4
二叉树的链式存储——二叉链表
三叉链表（每一个结点都存储其父节点）
二叉树的遍历
先序遍历、中序遍历、后序遍历
层序遍历
用队列，每访问一个结点将其左右孩子入队
非递归遍历
二叉树的应用
求二叉树的深度
求二叉树的叶子数
树和森林
树的孩子兄弟表示法
普通表示法的先序遍历等于孩子兄弟表示法的先序遍历，普通表示法的后序遍历等于孩子兄弟表示法的中序遍历
线索二叉树
规定：如果有左子树，则lchild指向其左子树，否则指向其前驱，如果有右子树，则rchild指向其右子树，否则指向其后继
二叉排序树
二叉排序树要么是一棵空树，要么具有如下性质，如果其左子树不空，则左子树上所有结点值都小于根节点的值，如果其右子树不空，则右子树上所有结点的值都大于根节点的值。左右子树都是排序二叉树。
BST的查找是一个不断比较和分支的过程
构造
BST的构造是一个不断查找并添加叶子结点的过程
删除叶子结点，直接删除之
删除度为1的结点，以其非空子节点替代之
删除度为2的结点，以其前驱替代之
查找性能分析
平均查找长度的概念
平衡二叉树
平衡二叉树首先是一棵排序二叉树，其左右子树都是平衡二叉树，且左右子树深度之差不超过1
平衡二叉树的构造采用平衡旋转技术
最优二叉树
带权路径长度最短的树
贪心算法构造哈夫曼树
传送报文的四步骤
1、统计字符出现频度
2、构造哈夫曼树
3、制定哈夫曼码表
4、进行字符翻译
堆积树（Heap）
堆积树是一棵完全二叉树，大顶堆的父节点的值大于其孩子结点，小顶堆的父节点的值小于其孩子结点
堆的梳理
堆排序
海量元素的topK问题
图
图的概念
有向图
有向完全图(边数为n(n-1)的有向图)
链接称为弧
无向图
无向完全图（边数是有向完全图的一半）
链接成为边
权
网
顶点的度
连通图的概念
连通分量
无向图中的极大连通子图称为连通分量
有向图中的极大强连通子图称为强连通分量
子图
顶点集合是母图的一个子集且边集也是母图的一个子集的图成为母图的子图
生成树
对于一个有n的顶点的图，其生成树是含有n个顶点且有n-1条边的连通子图
图上顶点的邻接
无向图中如果有边连接两个顶点，则这两个点互为邻接
有向图中如果有一条弧，则接收方邻接发送方
图的存储
邻接矩阵
空间复杂度
邻接表
求出度容易，求入度难
逆邻接表求入度容易，求出度难
十字链表
求入度出度都比较容易
图的遍历
深度优先搜索
广度优先搜索
图的算法
无向图求最小生成树
Prim算法
以连通为主，每次选择连通的最小权值的边
算法复杂度
Kruskal算法
以代价最小为主，每次选择权值最小的边看看能否加入最小生成树
环的检查——拓扑排序
不断删除入度为0的顶点
拓扑排序做不下去表示图中含有环
有向无环图（AOV）网——关键路径算法
标号法，正向求和之最大，逆向求差之最小，正逆相等的结点为关键结点
最短路径算法
单元Dijikstra算法
动态规划
全源Floyd算法
矩阵自乘
查找分类
静态查找
动态查找
动态查找如果要插入一个元素则插在low指针的位置上
关键字
关键字若能表示唯一的元素，则称为主关键字
若只能表示若干元素，则称为次关键字
线性表上的查找
顺序查找
查命中时平均需要比较
查失败则需要比较n次
折半查找
折半查找查不命中时high和low交错
查成功最多比较logn次，最少1次
查失败需要比较logn次
索引查找
查找过程分两部——块间顺序查找、块内顺序查找
假设n为表长，每块中含有s个数据，则平均查找长度
散列表中的查找（哈希查找）
哈希函数的构造方法
直接哈希函数法
取关键字本身或者关键字的某个线性函数作为哈希地址
数字分析法
H(key)=key中数字均匀分布的s位
平方取中法
H(key)=key2的中间几位
折叠法
将关键字分为几部分，将几部分的叠加和作为哈希地址
除留取余法
取某个不大于长度的某个素数，去除这个素数的余数作为哈希地址
随机数法
H(key)=random(key)
解决冲突的方法
开放地址法
平方探测再散列
线性探测再散列
随机探测再散列
再哈希法
用不同的哈希函数再哈希
链地址法
将所有哈希地址相同的值储存在一个链表中
公共区溢出法
建立一个溢出表
哈希表的平均查找长度
哈希表的ASL是装填因子的函数而不是n的函数
排序
插入类
直接插入排序
折半插入排序
在有序序列中进行折半查找
希尔排序
时间复杂度介于
选择类
选择排序是不稳定的排序
简单选择排序
每次从无序数据中选出一个最小的加入有序序列
使用大顶堆，不断删除堆顶元素并筛选之
交换类
冒泡排序
快速排序
快速排序一次划分：找一个记录作为枢轴，凡比其小的都移到前面，凡比其大的都移到后面
快速排序是递归程序
快速排序的改进，选取首元、尾元、中间元中位于中间的那个，作为枢轴，避免性能恶化
空间复杂度主要体现在递归上
归并类
二路归并排序
稳定性的比较
将时间复杂度和空间复杂度与n的平方作对比（简单选择排序是特例）
不稳定排序
堆排序、快速排序、希尔排序、简单选择排序
稳定排序
冒泡排序、直接插入排序、折半插入排序、二路归并排序
