# 基本定义
『数据(data)』是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。『数据』是计算机程序加工的原料。
『数据元素』是『数据』的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干「数据项」组成。
「数据项(data element)」是构成数据元素的不可分割的最小的单位,也成为字段、域、属性
。
如:学生记录作为一个数据元素,它由学号、姓名、性别等数据项组成。
「数据对象(data object)」是具有相同性质的数据元素
的集合,是数据的一个子集。
如,整数数据对象的集合
;大写字母的数据对象就是集合{'A','B',...,'Z'}
『图(Graph)』,由顶点集V和边集E组成,记为G=(V,E)或G=<V,E>
,其中V(G)
表示图G中定点的有限非空集,E(G)
表示图G中顶点之间的关系(即边)集合。
顶点:vertex 边:edeg
图分为:有向图、无向图。
将无顺序的数字,按照一定规则进行排序。
分类:插入排序、交换排序、选择排序、归并排序。
排序方式 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
---|---|---|---|---|---|---|
平均情况 | 最坏情况 | 最好情况 | ||||
插入排序 | O(n) | O(1) | 稳定 | 简单 | ||
希尔排序 | O(1) | 不稳定 | 较复杂 | |||
冒泡排序 | O(n) | O(1) | 稳定 | 简单 | ||
快速排序 | 不稳定 | 较复杂 | ||||
选择排序 | O(1) | 不稳定 | 简单 | |||
堆排序 | O(1) | 不稳定 | 较复杂 | |||
归并排序 | O(n) | 稳定 | 较复杂 | |||
基数排序 | O(r) | 稳定 | 较复杂 |
不稳定是指2个相等的元素,位置可能会发生变化。
『树』(Tree),是n(
- 有且只有一个特定的称为「根」的节点;
- 当 n>1 时,其余节点可分为 m(m>0) 个互不相交的有限集 T1,T2,...,Tm, 其中每个集合本身又是一棵树,并且称为根的「子树】。
笔记
树的特点:
- 树的根结点没有前驱,除根结点外的所有节点有且只有一个前驱;
- 书中所有节点可以有零个或多个后继。
树的层数称为树的「高度」。从
1
开始。
「『二叉树』是另一种树形结构。每个结点是每个结点至多只有2棵子树(即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其顺序不能任意颠倒。
『队列』(Queue),简称「队」,也是一种操作受限的线性表,只允许在表的一端进行插入,表的另一端进行删除。插入操作称为「进队」或「入队」,删除操作称为「出队」或「离队」。FIFO
(First In First Out)。
对头(Front),又称为「队首」。
队尾(Rear)
上一页
下一页