导图社区 数据结构
考研专业课数据结构基础框架思维导图，包括线性表、栈和队列、树和二叉树、图、查找、排序等内容，需要的自取。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数 据 结 构 与 算 法
绪论
数据
数据元素是数据的基本单位 数据项是数据的最小单位 数据对象是性质相同的数据元素的集合
算法
重要特征：有穷性、确定性、可行性、输入输出
优劣的评定：正确性、可读性、健壮性、高效性
时间复杂度
空间复杂度
线性表
顺序存储
顺序表
随机存储，但插入删除需要移动大量数据
链式存储
链表
静态链表
循环链表
双向链表
单链表
内存分布可不连续 插入和删除方便 查找需从一端开始
特殊
栈
先进后出，元素的输入输出在同一端进行
队列
先进先出，队尾输入，队头输出
特征
除了第一个和最后一个数据元素，每个数据元素都有唯一的前驱和后继
串、数组、广义表
串
存储结构
顺序存储和链式存储
模式匹配算法
BF算法
KMP算法
需要求next数组
数组
矩阵的压缩存储
稠密矩阵
行优先
列优先
稀疏矩阵
三元组
广义表
数据元素可以是原子，也可以是广义表
图
基本概念
子图
假设有两个图，其中一个图的顶点和边都是另一个图的顶点和边的子集，就称这个图是另一个图的子图
有向完全图和无向完全图
无向图有n（n-1）/2条边，有向图有n(n-1)条弧
稀疏图
边或弧的条数很少
稠密图
边或弧的条数很多
权
边上具有意义的数值。个人理解可以同理于哈夫曼树的权
邻接点
有边连接的两个点互为邻接点，边依附于顶点，边与顶点相关联
出（入）度
针对有向图而言，被指向为入度，指出为出度
路径
回路
起点和终点相同的路径
邻接矩阵
表示顶点间相邻关系的矩阵
邻接表
一种图的链式存储结构，对图中每个顶点建立单链表，并把与之相邻的顶点放在链表中
十字链表
是有向图的另一种链式存储结构
尾域
头域
链域
指向弧头相同的下一条弧hlink
指向弧尾相同的另一条弧tlink
相关信息
邻接多重表
是无向图的另一种链式存储结构
遍历
深度优先
从某个顶点出发进行访问 找出刚访问的顶点的第一个未被访问的邻接点，重复执行 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出下一个未被访问的邻接点
广度优先
从某个顶点出发进行访问 依次访问此顶点的各个未被访问的邻接点 分别从这些邻接点出发，依次访问他们的邻接点
最小生成树
普里姆算法
克鲁斯卡尔算法
最短路径
迪杰斯特拉算法
弗洛伊德算法
拓扑排序
在有向图中，访问无前驱的顶点并输出 删除此顶点。 重复执行上述操作
关键路径
从入度为0的点（源点），到汇点的带权路径最长的路径
树
基本术语
结点
树中的一个独立单元
结点的度
结点拥有的子树数称为结点的度
叶子
度为0的结点称为叶子或终端结点
树的深度
树中结点的最大层次称为树的深度或高度
树的度
树的度是树内各结点度的最大值
双亲、孩子、兄弟、祖先、子孙、堂兄弟
二叉树
满二叉树
深度为k且含有2∧k-1个结点的二叉树
特点
每一层上的结点数都是最大的结点数
完全二叉树
深度为k，有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树
叶子结点只可能在层次最大的两层上出现
对任一结点，其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1
一般二叉树
线索二叉树
以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索，加上线索的二叉树称之为线索二叉树
typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; int LTag ,RTag; }BiThrNode,*BiThrTree;
先序遍历
中序遍历
后序遍历
所谓的先、中、后是指访问根结点的时机，对于遍历二叉树，必然会以某种顺序访问左右子树和根结点，不同的访问顺序就是不同的遍历方式
森林
是m（m≥0）棵互不相交的树的集合
哈夫曼树
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度
路径长度路径上的分支数目称作路径长度
树的路径长度
从树根到每一个结点的路径长度之和
赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。我个人的理解为重要程度，数值越大越重要
哈夫曼树的构造
给定n个权值，构造n棵只有根结点的二叉树，构成森林 从森林中选取权值最小的两棵树作为左右子树，构造新的二叉树，新二叉树根节点的权值为两个子树的权值和，将新的二叉树加入森林中，同时删除成为子树的两棵树 重复执行，直至森林中只剩一棵树时，这棵树就是哈夫曼树
个人的理解为，将最小的两棵树构造成新的二叉树，循环执行这个操作，会使权值越小，即重要程度越低的数据存储在哈夫曼树的最底层，权值大重要程度高的数据存储在树的上层，方便使用
哈夫曼编码
对有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，从根到叶子的路径上，各分支的赋值构成的二进制串就是哈夫曼编码。
个人理解：哈夫曼编码像是一个导航，0为向左走，1为向右走，
WPL值的计算
查找
查找表
由同一类型的数据元素构成的集合
关键字
数据元素中某个数据项的值
根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素
线性表的查找
顺序查找
从表的一端开始，依次进行比较
折半查找（二分查找）
从表的中间开始进行比对，若大于则在大于的那一半再进行折半比对，若小于则在小于的那一半进行折半比对，直到查找成功或无结果
分块查找
建立索引表，根据索引表指向的块，在块中进行顺序查找
树表的查找
二叉排序树
左子树不为空，则一定小于其根节点
右子树不为空，则一定大于其根节点
左右子树均为二叉排序树
平衡二叉树
在二叉排序树的基础上多了一个限制条件，即左右子树的深度差的绝对值不超过1
散列表
排序
是按关键字的非递减或非递增顺序对一组记录重新排序的操作
排序的稳定性
当排序的关键字都不同时，任何一个记录的无序序列经排序得到的结果唯一，反之不唯一
内部排序和外部排序
内部排序
待排序记录全部存放在计算机内存中的排序过程
外部排序
待排序记录的数量很大，内存无法一次容纳全部，在排序过程中尚需对外存进行访问的排序过程
插入排序
直接插入排序
当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移
折半插入排序
用low、mid、high划分两个成区域【low，mid-1】和【mid+1，high】 如果key值小于序列的中间值mid，则代表key值应该插入左边的区域【low，mid-1】，然后对【low，mid-1】再重复划分区域，直到low>high为止，最后的插入位置应该是high+1，将high之后位置的数据整体后移，然后将key赋值给【mid+1】
希尔排序
实质上是一种分组插入方法，通过不断缩短布长来进行排序
交换排序
冒泡排序
将小的元素或大的元素，逐个找出，通过相邻元素的比较和交换位置实现
快速排序
是对冒泡排序的改进，选择分界值将其分为两部分，左侧为小于右侧为大于，重复执行
选择排序
简单选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
树形选择排序
将n个待排序的元素，两两一组进行比较，取出较小的，然后在这n/2个较小者中再两两一组进行比较，取出较小的，重复上述步骤，直到取出最小元素。
堆排序
将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点就是序列中最大的元素。将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。
归并排序
将n个元素分成两个含n/2元素的子序列 用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列） 合并两个已排序好的序列
基数排序
多关键字排序
最高位优先法
最低位优先法
链式基数排序
