C, вопрос о структуре данных для разреженной 2d матрицы

Question

Мне было интересно, какую структуру данных я мог бы использовать для разреженной 2d-матрицы, если я знаю, что элемент будет коротким типом.Я собирался использовать связанный список, но тип элемента (короткий) имеет какое-то значение?Что если элементы будут целочисленным, а не коротким типом, то как это изменит структуру данных?

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;
};