Welche Daten Strukturen lassen sich effizient speichern der 2-d "grid" - Daten?

Hier sind ein paar Ansätze. Ich werde (versuchen zu) zeigen diese Beispiele mit einer Darstellung von einem 3x3-raster.

Der flachen array

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+

a[row*width + column]

Zugriff auf Elemente auf der linken oder rechten, subtrahieren oder fügen Sie 1 hinzu (achten Sie auf die Reihe-Grenzen). Zugriff auf die Elemente oben oder unten, subtrahieren oder fügen Sie die Zeile Größe (in diesem Fall 3).

Die zwei-dimensionales array (für Sprachen wie C oder FORTRAN, die dies unterstützen)

+-----+-----+-----+
| 0,0 | 0,1 | 0,2 |
+-----+-----+-----+
| 1,0 | 1,1 | 1,2 |
+-----+-----+-----+
| 2,0 | 2,1 | 2,2 |
+-----+-----+-----+

a[row,column]
a[row][column]

Zugriff auf benachbarte Elemente ist nur Inkrementieren oder Dekrementieren entweder die Zeilen-oder Spaltennummer. Der compiler macht immer noch genau die gleichen Arithmetik wie in der flachen array.

Array von arrays (zB. Java)

+---+   +---+---+---+
| 0 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 1 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 2 |-->| 0 | 1 | 2 |
+---+   +---+---+---+

a[row][column]

In dieser Methode, eine Liste von "row-Pointer" (dargestellt auf der linken Seite) jeder ist eine neue, unabhängige array. Wie die 2-d-array, benachbarte Elemente zugegriffen werden, durch anpassen des entsprechenden index.

Vollständig verknüpften Zellen (2-d doppelt verkettete Liste)

+---+   +---+   +---+
| 0 |-->| 1 |-->| 2 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 3 |-->| 4 |-->| 5 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 6 |-->| 7 |-->| 8 |
|   |<--|   |<--|   |
+---+   +---+   +---+

Diese Methode ist jede Zelle mit bis zu vier Zeiger zu den angrenzenden Elementen. Zugang zu angrenzenden Elemente wird durch die entsprechenden Zeiger. Sie müssen noch immer eine Struktur von Zeigern auf Elemente, die (wahrscheinlich mit einer der oben genannten Methoden) zu vermeiden, Schritt durch die einzelnen verkettete Liste sequentiell. Diese Methode ist ein bisschen sperrig, aber es hat eine wichtige Anwendung in Knuth ' s Dancing Links - Algorithmus, wo die links geändert werden, die während der Ausführung des Algorithmus zu überspringen "leeren" Platz in der Startaufstellung.

Eines dynamisch reservierten Arrays von arrays macht es trivial, zeigen Sie auf die Zelle über der aktuellen Zelle, und unterstützt die beliebige grid-Größen sowie.

Sollten Sie Abstrakt aus, wie Sie Ihre Daten speichern.
Wenn Sie tun müssen, relativ Operationen im array, Scheibe ist die gemeinsame patterd, es zu tun.
Sie könnte so etwas wie dieses:

public interface IArray2D<T>
{
    T this[int x, int y] { get; }
}

public class Array2D<T> : IArray2D<T>
{
    readonly T[] _values;
    public readonly int Width;
    public readonly int Height;

    public Array2D(int width, int height)
    {
        Width = width;
        Height = height;
        _values = new T[width * height];
    }

    public T this[int x, int y]
    {
        get
        {
            Debug.Assert(x >= 0);
            Debug.Assert(x < Width);
            Debug.Assert(y >= 0);
            Debug.Assert(y < Height);

            return _values[y * Width + x];
        }
    }

    public Slice<T> Slice(int x0, int y0)
    {
        return new Slice<T>(this, x0, y0);
    }
}

public class Slice<T> : IArray2D<T>
{
    readonly IArray2D<T> _underlying;
    readonly int _x0;
    readonly int _y0;

    public Slice(IArray2D<T> underlying, int x0, int y0)
    {
        _underlying = underlying;
        _x0 = x0;
        _y0 = y0;
    }

    public T this[int x, int y]
    {
        get { return _underlying[_x0 + x, _y0 + y]; }
    }
}