11 数据结构
优质
小牛编辑
132浏览
2023-12-01
数据结构
线性结构
线性表
栈和队列
串
数组、矩阵、广义表
数组
矩阵
广义表
树
遍历（根据根的位置）
先序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根
层序遍历：1层根，2层左-右，3层左-右
线索二叉树
每个结点只有一个前驱、一个后继，即线性化
最优二叉树(哈夫曼树)
哈夫曼树：最小带权(结点有大小数字)路径长度的二叉树
在结点数相同的二叉树中，完全二叉树路径长度最短
树和森林
图
遍历
深度优先遍历：可跳回分支继续出发，无须一线
从某顶点出发，依次访问未访问的邻接点
直到无邻接点，则以该点为起点重复过程
广度优先遍历：
从某顶点出发，先访问自己邻接点
再访问已访问点的邻接点，最后未邻接点
生成树
拓扑排序和关键路径
最短路径
查找问题
静态查找表
顺序查找
折半查找(二分查找)
与mid=(low+high)/2对比后齐mid
分块查找
动态查找表
二叉排序树
左<根<右
平衡二叉树
B-树
哈希表
(注意处理冲突的方法)
将数据元素的关键字K作为自变量，通过一定的函数关系(称为哈希函数)，计算出元素的存储地址
所以在构造哈希函数时应尽量使关键字的所有组成部分起作用