「生活可以更简单, 欢迎来到我的开源世界」
  1. 绪论
  2. 线性表
  3. 栈和队列
  4. 字符串
  5. 树与二叉树
  6. 查找
  7. 排序
数据结构概念罗列
2020-12-28

数据结构概念罗列

绪论

数据:信息的载体

数据元素:数据的基本单位

数据对象:数据的一个子集

数据类型:一个值的集合和定义在此集合上的一组操作的总称

数据结构:相互之间存在一种或多种特定关系的数据元素的集合

算法:对特定问题求解的一种描述

线性表

存储结构:

栈和队列

栈和队列:操作受限的线性表

栈:

队列:

字符串

存储结构:

模式匹配算法:

树与二叉树

特点:

结点的度:结点的孩子个数

分支结点:度大于0的结点

叶子结点:度为0的结点

结点的层次从根结点开始定义,根节点在第一层

结点的深度:从根结点自顶向下逐层累加

结点的高度:从叶结点开始自底向上累加

有序树:结点子树有次序,不可互换

无序树:结点子树无次序,可呼唤

路径:两个结点之间所经过的结点序列

路径长度:路径上所经过的边的个数

森林:M棵互不相交的树的集合

树最基本的性质:

二叉树:n个结点的有限集合

特殊的二叉树:

二叉树的性质:

二叉树存储结构:

三种常用的存储结构:

二叉树的遍历:根据根节点的访问顺序,递归

由二叉树的先序序列和中序序列可以唯一确定一棵二叉树

由二叉树的后序序列和中序序列可以唯一确定一棵二叉树

由二叉树的层序序列和中序序列可以唯一确定一棵二叉树

线索二叉树:二叉树的结点排列成一个线性序列

二叉树的线索化是将二叉链表中的空指针指向前驱或后继的线索,前驱和后继只有在遍历时才能得到,所以线索化实质是遍历一次二叉树。

树转换为二叉树规则:左孩子右兄弟

森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

二叉树的应用

图G:顶点集V和边集E组成,G=(V, E),顶点集一定非空

有向图:E是有向边(弧)的有限集合,弧是顶点的有序对,记为<v,w>

无向图:E是无向边(边)的有限集合,边是顶点的无序对,记为(v,w)

简单图:不存在重复边,不存在顶点到自身的边

多重图:两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联

(简单)完全图:任意两个顶点之间都存在边

子图:前提是图,顶点集和边集是子集。顶点集完全一样则为生成子图。

连通:无向图中,顶点v到顶点w有路径存在

连通图:无向图中,任意两个顶点都是连通的

连通分量:无向图中的极大连通子图

强连通:有向图中,从顶点v到w和从w到v之间都有路径

强连通图:有向图中,任意一对顶点都是强连通的

强连通分量:有向图中的极大强连通子图

连通图的生成树:包含图中全部顶点的一个极小连通子图,若顶点数为n,则边数为n-1

非连通图的生成森林:连通分量的生成树

顶点的度:TD(v)

顶点的入度:ID(v)

顶点的出度:OD(v)

TD(v) = ID(v) + OD(v)

带权图(网):有权值的图

稠密图、稀疏图:|E| < |V| log|V|时,为稀疏图,反之为稠密图

路径长度:路径上边的数目

回路(环):若一个图有n个顶点,并且有大于 n-1 条边,则此图有环

简单路径:顶点不重复出现

简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路

距离:顶点之间的最短路径的长度,不存在路径距离为无穷

有向树:一个顶点入度为0,其余顶点入度均为1的有向图

图的存储:

图的遍历:

图的应用:

AOV网:若用DAG图表示一个工程,其顶点表示活动,用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行的这样一种关系,则将这种有向图称为用顶点表示活动的网络,记为AOV网。每个AOV网都有一个或多个拓扑排序序列

AOE网:在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销,称之为用边表示活动的网络,简称AOE网。

查找

顺序查找:

折半查找/二分查找:

分块查找

B树(多路平衡查找树):

B+树:操作与B树类似,但叶子结点包含信息,非叶结点仅起索引作用

散列表:建立了关键字和存储地址之间的一种之间映射关系,O(1)

排序

直接插入排序:

折半插入排序:折半查找插入位置,统一移动元素

希尔排序:

冒泡排序:

快速排序:

简单选择排序:

堆排序:

归并排序:

基数排序

外部排序:

<⇧>