在 C (X,Y,state) 中选择正确的存储方式

Question

我刚开始写一个新项目，它应该读取 X 和 Y 坐标（可以从 0 到 4,000,000,000）并存储这些点。

因为不知道要存储多少个点，只好在程序运行的时候分配需要的内存运行。

然后我想找到相邻的点（水平和垂直）来创建"islands"并将所有连接的点存储在一个组中。

现在我不太确定哪种数据类型或如何存储坐标。我的第一个想法是拥有一个二维数组 [x][y] 来存储那个确切点的状态。因此，如果我在位置 array[5][5] 上，我可以通过添加 x+1 (array[6][5]) 轻松请求下一个点的状态。问题是我必须初始化一个数组，它也包含点，根本没有被占用，我认为数组 [4,000,000,000][4,000,000,000] 无论如何都行不通。

那么最好的存储方式是什么，以便我能够读取点状态，从而找到相邻的点？

提前致谢， D

编辑：每个岛也可以有空隙

Answer 1

使用由坐标索引的二维数组是不切实际的，因为这些坐标的范围：0..4000000000。也就是160亿个cell，不仅超过了目前可以想象的RAMspace，而且扫描如此广阔几乎空旷的区域也将非常低效

您应该研究 Quadtrees 或适合存储地理数据的类似数据结构。

Answer 2

选择数据结构需要大量关于程序要做什么以及如何使用的信息。您已向我们提供了一些信息，但需要更多信息才能找到最佳数据结构。

根据给出的信息，我的第一个想法是链表的链表。 "outer" 链表可以表示存在（排序）的行，"inner" 链表表示该行存在（排序）的列。

类似于：

struct column
{
    uint32_t cidx;
    struct column* next;
}

struct row
{
    uint32_t ridx;
    struct column* column;
    struct row* next;
}

链接列表的好处是可以很容易地按排序顺序插入元素。对这些点进行排序将有助于您查找 "islands"。例如，如果您正在查看第 18 行第 1000 列，并想检查第 19 行第 1000 列是否存在，您首先检查 next 行元素是否用于第 19 行，如果是，则通过对应列链表看是否有1000

在 C (X,Y,state) 中选择正确的存储方式

Choosing the right storage in C (X,Y,state)

c

arrays

algorithm

storage

allocation