Wie lautet der Name einer Datenstruktur, die wie Stifte Bowling?

Question

Zunächst einmal, sorry für den Titel. Jemand schlagen Sie bitte ein besserer, ich weiß wirklich nicht, wie meine Frage richtig auszudrücken.

Im Grunde genommen, ich suche nur für den Namen einer Datenstruktur, wo die Elemente wie folgt aussehen (ignorieren die Punkte):

...... 5

.... 3 ... 2

.. 4 ... 1 ... 6

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

Zuerst dachte ich könnte es eine gewisse Art von „Baum“, aber, wie wikipedia sagt:

  

Ein Baum ist [...] ein acyclischer verbundenen Graphen, wo jeder Knoten null oder mehr Kindknoten und höchstens einen übergeordneten Knoten

Da kann es mehr als einen Elternteil durch den Knoten in der Datenstruktur, die ich suche, ist es wahrscheinlich kein Baum.

So, hier ist meine Frage:

Was ist der Name einer Datenstruktur, die Daten mit den folgenden Links zwischen den Elementen darstellen kann? (/ Und \ die Links zu sein, wieder, ignorieren Sie die Punkte):

...... 5

..... / .. \

.... 3 ... 2

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

.. 4 ... 1 ... 6

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

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

Answer 1

Ich denke, es ist nicht ganz falsch ist es, einen Baum zu nennen, obwohl „ Digraph "(Graphen) wäre ein richtiger Begriff sein.

  

Zunächst einmal, sorry für den Titel.   Jemand bitte schlagen eine bessere, ich   wirklich nicht wusste, wie meine auszudrücken   Frage richtig.

Der Titel ist in Ordnung, ich LOL'd hart, wenn ich die Frage geöffnet. Ich werde sie „Bowling Pins“ jetzt lostelefonieren:)

      5

    3   2

  4   1   6

9   2   3   1

Answer 2

Die beliebtesten, was ich rechnen, die wie folgt angelegt wurde, ist Pascals Dreieck . Es ist die Struktur verwendet, um zu berechnen Binominalkoeffizienten ; jeder Knoten ist die Summe seiner Eltern:

http: // info .ee.surrey.ac.uk / Personal / L.WOOD / Publikationen / MSc-Thesis / fig36.gif .

usuallly, wenn es um die Implementierung solcher Algorithmen (wie Klasse kommt, wird gemeinhin als „dynamische Programmierung“ ), ist diese „Struktur“ ist in der Regel als einfaches zweidimensionales Array dargestellt. Siehe hier , zum Beispiel:

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

Ich glaube, dass es keinen offiziellen Namen für eine solche Struktur, aber in dynamischen Programmierung solche Sachen ist nur ... Arrays.

Aber von jetzt an, wie NullUserException schlägt ich es total bin calling "Bowling-Pins": -)

Answer 3

A „dag“ oder gerichteter azyklischer Graph ist ein Graph mit gerichteten Rand, in dem es mehrere Pfade zu einem Knoten sein kann, und einige Knoten können sowohl ein- und ausgehende Kanten, aber es gibt keine Möglichkeit, einen beliebigen Knoten zu verlassen, und Rückkehr zu ihm (es gibt keine Zyklen). Beachten Sie, dass in einer endlichen DAG mindestens einen Knoten nichts muss aber ausgehenden Kanten und mindestens eine muss nur eingehende Kanten aufweisen. Wäre das nicht der Fall ist, wäre es möglich, kontinuierlich durch den Graphen zu bewegen, ohne jemals eine Sackgasse erreicht (da jeder Knoten einen Ausgang haben würde), und ohne jeden Knoten zweimal zu besuchen (da die Graph azyklisch ist). Wenn es nur eine endliche Anzahl von Knoten, die offensichtlich unmöglich ist.

Answer 4

  

Da kann es mehr als einen Elternteil durch den Knoten in der Datenstruktur, die ich suche, ist es wahrscheinlich kein Baum.

Was Sie suchen ist wahrscheinlich ein Graph . Ein Baum ist ein Spezialfall eines Graphen, wo jeder Knoten genau einen Elternteil hat. (Mit Ausnahme der Wurzel, die keine hat)