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

Question

第一个问题是:"我如何用C做一个简单的稀疏数组(只有一个维度)？" {亲自动手,没有图书馆.}

最后一个:"我可以只分配数组的一部分吗？"

喜欢*数组;

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

我可以做吗？

非常感谢!

Answer 1

不,你不能这样做.

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

可能最好的优化是使用细胞范围.因此,您可以使用可用范围的链接列表(或地图):

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

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

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

• 在填充或生成孔时重构块
• 只存储单个细胞

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

解决方案很多,只是表达你的创造力!:)