3

首先，对不起标题。有人请提出一个更好的，我真的不知道如何正确表达我的问题。

基本上，我只是在寻找元素看起来像这样的数据结构的名称（忽略点）：

......5

....3...2

..4...1...6

9...2...3...1

我首先认为它可能是某种“树”，但是，正如维基百科所说：

树是 [...] 一个非循环连通图，其中每个节点有零个或多个子节点，最多有一个父节点

由于在我正在寻找的数据结构中可以有多个父节点，它可能不是一棵树。

所以，这是我的问题：

可以用元素之间的以下链接表示数据的数据结构的名称是什么？（/ 和 \ 是链接，再次忽略点）：

......5

...../..\

....3...2

.../..\./..\

..4...1...6

../.\./..\./..\

9...2...3...1

4

4 回答 4

4

我认为称它为树并不是完全错误的，尽管“有向图”（有向图）将是一个更合适的术语。

首先，对不起标题。有人请提出一个更好的，我真的不知道如何正确表达我的问题。

标题很好，当我打开问题时，我很难过。我现在要开始称它们为“保龄球”了：）

替代文字

      5

    3   2

  4   1   6

9   2   3   1
于 2010-08-22T03:38:30.010 回答
3

我认为像这样布置的最受欢迎的东西是帕斯卡三角形。它是用于计算二项式系数的结构；每个节点都是其父节点的总和：

http://info.ee.surrey.ac.uk/Personal/L.Wood/publications/MSc-thesis/fig36.gif。

通常，当涉及到实现这样的算法（这样的类通常被称为“动态编程”）时，这个“结构”通常表示为一个简单的二维数组。见这里，例如：

n\k  0  1  2  3  4
------------------
0    1  0  0  0  0 
1    1  1  0  0  0 
2    1  2  1  0  0 
3    1  3  3  1  0 
4    1  4  6  4  1 
5    1  5 10 10  5 
6    1  6 15 20 15

我认为，这样的结构没有正式的名称，但在动态编程中，这样的东西只是......数组。

但从现在开始，正如NullUserException 所暗示的，我完全称它为“保龄球”:-)

于 2010-08-22T06:54:32.343 回答
2

由于在我正在寻找的数据结构中可以有多个父节点，它可能不是一棵树。

您正在寻找的可能是一个图表。树是图的一种特殊情况，其中每个节点都只有一个父节点。（没有的根除外）

于 2010-08-22T03:43:47.733 回答
2

“dag”或有向无环图是一个有向边的图，其中一个节点可能有多条路径，并且一些节点可能同时具有传入和传出边，但没有办法离开任何一个节点并返回它（没有循环）。请注意，在有限 DAG 中，至少一个节点必须只有输出边，并且至少一个节点必须只有输入边。如果不是这种情况，则可以在图中连续移动而不会到达死胡同（因为每个节点都会有出口），并且不会访问任何节点两次（因为图是非循环的）。如果只有有限数量的节点，那显然是不可能的。

于 2010-08-22T04:30:33.580 回答