C，稀疏二维矩阵的数据结构问题

Question

我想知道如果我知道元素将是短类型，我可以将什么数据结构用于稀疏二维矩阵。我打算使用链表，但元素类型（短）有什么区别吗？如果元素将是整数类型而不是短类型，那么它将如何改变数据结构呢？

Answer 1

不过，该值的向量

struct {
  int x;
  int y;
  short value;
}

可能最终会使用 4 个字节（结构成员通常会填充到 32 位边界）如果您确实缺乏空间并且 x,y 坐标有限，您可以将整个内容打包到 64 位的位中int

如果要添加和删除点，则可能需要使用列表，但通常稀疏数组具有一组固定的点或查找占主导地位，并且值得在添加点后按 X,Y 对它们进行排序。

如果您确实需要添加大量点并且仍然希望通过 x,y 快速访问，那么树可能值得一看

Answer 2

在纯C中，可以使用指针来存储不同类型的数据，并注意避免内存泄漏。
像这样：

struct NODE
{
    void *data;
    struct NODE *next;
};

考虑使用 C++ 模板怎么样？

template<typename T>
struct NODE
{
    T data;
    struct<T> *next;
};