啥是线性数据结构的集合？计算机二级公共基础之数据结构

刷二级题遇到这个题型了，数据结构还没学，所以这边整理一下资料。

啥是数据结构，用集合表示一个数据结构$B=(D,R)$其实就是这样子：

$$\begin{aligned} &D= \{d_{i}|1\leq i\leq7\} = \{d_{1},d_{2},d_{3},d_{4},d_{5},d_{6},d_{7}\}\\[2ex] &R= \{(d_{1},d_{3}),(d_{1},d_{7}),(d_{2},d_{4}),(d_{3},d_{6}),(d_{4},d_{5})\} \end{aligned}$$

他也可以用结构图表示：

其中，没有前件的节点成为根节点，没有后件的节点称为终端节点（叶子节点）。

啥是线性数据结构：
一个非空的数据结构如果满足以下两个条件：

• 有且只有一个根节点；
• 每一个节点最多有一个前件，也最多有一个后件。
  前图所示就是一个线性结构，非线性则正相反。
  所以此类题型只需对所给数据结构判断出根节点的数量与是否只有一个前后件。

上个例题看看：

我们可以画图，也可以写出关系，每个括号前后分别代表着前者是后者的前件。
因此，
其中
A选项，2->5->4, 4->3->1 ，线性。
B选项，1->2->3->4->5，线性。
C选项，1->2->3->5, 4->3, 3有两个根节点，非线性。
如下图：

D选项，5->4->3>2->1，线性。

挺简单的。