MYBLOG

0XFF编程网

先来做个小复习

上一课咱们了解了初阶的“数据结构”共有4种——

数组/链表/堆栈/队列


它们都是线性表

堆栈和队列在形式上如同数组或链表一样,但是分别加入了“后进先出”和“先进先出”的规则。数据结构并不是一成不变规定好的,其实是可以根据需要灵活使用的,甚至可以自己发明适合使用的数据结构


还有4种高阶数据结构

分别是:

树(Tree)

集(Set)

映射(Map)

图(Graph)

这些数据结构就不是“线性”的了,不如线性表那么常用,可是一旦使用,将发挥惊人的威力。

高阶数据结构不仅维护数据,还需要维护数据与数据之间的关系

树(Tree)

树,是一种善于表达数据之间“层次关系”的数据结构,废话不说,先来个图片看看——

树结构

这就是一颗典型的“树”,还挺像生活中的树吧,只不过是倒过来的哈。

看着上图,我们讲解一下树上的节点名称:

1 每个圆圈的位置称为“节点”;

2 在节点上方且用线相连的,叫“父节点”;在节点下方且用线相连的,叫“子节点”;

3 如果平级的就叫“兄弟节点”,形象吧,比如 G H I 就是兄弟节点。


再看一遍这个树结构,它有3个特征:

1 有一个节点 A,它没有父节点,我们叫 A 为“根节点”;

2 每个节点有0个/1个/2个/n个子节点,但每个节点只有一个父节点

3 树是有“高度”的,有几个层次高度就是几,比如上面结构中高度为4。

看到这里,我们完全可以把树结构看成是一种“家谱图”。

树结构怎么存储

其实树结构的存储方式很多,比如父节点法/子节点法/孩子兄弟法等,但它们的原理都是一样的:

每个节点都有一个数据域和一个指针域

上例子:

父节点法简明图解

比如上图就是典型的父节点法,首先定义好下标的顺序,这其实也是数据域在数组中的下标,然后每个节点都有一个指针域parent,根节点指向-1,意思是它没有父节点;E节点的指针为2,而2对应的是C,意思是:E节点的父节点是C。

树中之王——“二叉树”

树结构特别擅长表示层次结构,比如计算机上的目录结构/一个公司的分支机构等等,而有一种特殊的树,结构更简单,用处却更大,它就是——

二叉树”。

二叉树的形状

上图就是二叉树的形状,就是每个节点最多只有两个儿子

二叉树分两类:

完全二叉树 与 不完全二叉树

两类二叉树

从上图中的顺序存储形式来定义再好不过了,如果顺序存储形式中都存满了数,即“完全”;如果有空位,就是“不完全”。

树的讲究太多了,应用也广泛,我们后面再更详细地讲解。

集(Set)

集,也叫“集合”,跟咱们数学上说的集合完全是一回事,就是把一堆元素放在一起的总合。

严谨点儿说,集有3个特点:

无序

集里面的元素没有先后顺序,地位平等,不像树那样还会有父子关系;

互异

集里面的元素,必须没有重样的;

明确

一个对象,要么属于这个集,要么不属于,没有中间情况。

集合中每个元素必须互异

集的操作

集有哪些操作?

对集中元素操作:插入元素/删除元素/判断元素是否在集中;

集合之间的操作:求交集/并集/求差等等。

集的应用也很广泛,比如数独游戏算法中,可以使用集来管理每个小单元格的候选数列表。


阅读 200
全部留言