C中的稀疏数组！ 怎么做到的？ 我可以只分配数组的一部分吗？

第一个问题是：“我如何在C中做一个简单的稀疏数组（只有一个维度）？” {亲自动手，没有图书馆。}

最后一个：“我可以只分配数组的一部分吗？”

像*数组;

然后使用malloc为此分配一些mem; 所以，我们释放了我们不想要的索引。

我可以做吗？

非常感谢！

Answer 1

不，你不能这样做。

你可以做的是分配块，但你需要仔细设计它。

可能最好的优化是使用细胞范围。 因此，您可以使用可用范围的链接列表（或地图）：

struct SparseBlock { void *blockData; int beginIndex; int endIndex; struct SparseBlock *next; } 

显然，如果endIndex - beginIndex = 0你有一个单元格（在数组中被隔离），否则你有一个单元格块，允许你为它分配适量的内存。

这种方法对于不可变的稀疏向量很简单，否则你应该照顾

• 每当填充或生成一个洞时重组块
• 只存储单个细胞

此外，你必须决定如何索引这些块，你可以将它们保存在链表中，或者你可以使用一个地图来获得一个恒定的O（1）时间来检索第n个块（当然你会有如果是一个范围，则为同一个块插入许多相等的键，或者将索引减少到最接近的较低索引（）。

解决方案很多，只是表达你的创造力！ 🙂

Answer 2

在这种或那种的链接结构中实现这些并不罕见。 在一个维度中，您可以简单地生成一个被占领区域的链接列表，之前我已经在另一个上下文中讨论了二维实现 。

你确实以这种方式失去了O（1）访问时间，但如果结构真的很稀疏，那么空间上的胜利可能会相当大。