1

我想在 C 中构造一个二维数组，其中每一行都有不同数量的元素。具体来说，我想构建一个三角形 7x6 数组。为了节省内存，我想避免存储零，如下例所示。

                               1 0 0 0 0 0 0
                               1 1 0 0 0 0 0
                                     ...
                               1 1 1 1 1 1 1

我怎样才能做到这一点？

4

6 回答 6

20

公式

这个索引系统不会工作吗？

0
1 2
3 4 5
6 7 8 9
...

只需将您的数据存储在一个单维数组中，使用此映射到三角矩阵/数组。

双射

一维从零开始的索引k和二维从零开始的行列i是j一样的when k = i(i+1)/2 + j(where j <= i)。

笔记

以上是针对下三角方阵/阵列的。你可以做一些非常相似的事情

  • 上三角方阵/阵列
    • 简单地交换i和j
  • 矩形下三角或上三角矩阵/阵列
    • 这有点棘手（您需要根据情况进行推理），但是可以实现将一维数组（实现）映射到概念二维数组（视图）的相同想法
于 2013-07-01T14:16:12.967 回答
1

注意——这是未经测试的伪代码，不是有效的 C 代码。

int **c;
c = malloc (7 * sizeof(int *));
for (i=0;i<7;i++)
  c[i] = malloc ( (i+1) * sizeof (int));

但是，我不确定您为什么要这样做。如果您对该数组的访问不是很小心，您很可能会出现分段错误。

于 2013-07-01T14:21:07.610 回答
0

正如您在问题中提到的一个位数组。所以我假设您想在使用非常简单的代码时优化内存使用。如果二维数组是固定的（可能在您的情况下），一种解决方案是创建一个分配位字段的结构，如下所示：

struct triangular_array {
int line1:1      __attribute__((packed));  //line1 will have only one bit storage capacity
int line2:2      __attribute__((packed));
int line3:3      __attribute__((packed));
int line4:4      __attribute__((packed));
int lint5:5      __attribute__((packed));
int lint6:5      __attribute__((packed));
int lint7:7      __attribute__((packed));
.
.
.
.
and so on
};

//create an object
struct triangular_array object1;

//initialise the object
object1.line1= 0b1;
.
.
.
.

关于这个实现的事情：

  1. 简单的方法，但可能比不使用“打包”属性时慢。权衡将是会有额外的比特打包。此外，这对于某些实现可能是不安全的（请查看下面的 stackoverflow 链接）
  2. 您有时可能需要注意字节序
  3. 这种方法有时用于需要交换数据包的网络代码中。

您可以阅读有关属性的更多信息：

  1. GCC 文档： http: //gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Type-Attributes.html
  2. 考虑：gcc 的 __attribute__((packed)) / #pragma pack 不安全吗？
于 2013-07-13T10:12:39.880 回答
0

使用一维数组并计算 声明一个数组，大小 = rows × (rows + 1) / 2 index = row x (row+1) / 2 + column 使用此解决方案，您会浪费时间进行乘法、除以 2 和加法（尽管右移将处理除以 2）。或者，您可以为每一行使用一个指针数组，并在循环中分配所需数量的元素。

于 2013-07-01T14:46:55.320 回答
0

此函数将为一维数组中的行号和列号分配索引，并且是无序的：

static inline int64_t index(const int32_t x, const int32_t y) {
    int_fast32_t min, max;
    if (x < y) {
        min = x;
        max = y;
    } else {
        min = y;
        max = x;
    }
    return ((max * (max + 1)) >> 1) + min;
}

将产生像 (x并y以0) 开头的索引：

0   1   3   6   10  15  21  28
1   2   4   7   11  16  22  29
3   4   5   8   12  17  23  30
6   7   8   9   13  18  24  31
10  11  12  13  14  19  25  32
15  16  17  18  19  20  26  33
21  22  23  24  25  26  27  34
28  29  30  31  32  33  34  35
36  37  38  39  40  41  42  43
45  46  47  48  49  50  51  52
55  56  57  58  59  60  61  62
66  67  68  69  70  71  72  73
于 2013-07-01T14:30:15.933 回答
0

您可以创建一个 1-D指针数组，而不是创建单个 1-D 数组并将其视为 2-D 数组，其中每个指针指向另一个 1-D 数组。这使您可以为数组中的每一行分配不同的大小。

例如：

// Allocate and initialize a triangular 2-D array
int** make_triangle_array(int nrows)
{
    int **  arr;

    // Allocate the 1-D array of pointers
    arr = malloc(nrows * sizeof(int *));

    // Allocate each row of the triangular array
    for (int i = 0;  i < nrows;  i++)
    {
        int     rowlen = i+1;

        // Allocate a row of ints for the array
        arr[i] = malloc(rowlen * sizeof(int));

        // Fill the row with '1' values
        for (int j = 0;  j < rowlen;  j++)
            arr[i][j] = 1;
    }

    // Return the allocated array
    return arr;
}

// Test driver
void test(int n)
{
    int **  arr;

    arr = make_triangle_array(n);
    ...
    free_triangle_array(arr, n);
}

这种方法的优点是能够为每一行分配任何大小。它还具有能够使用语法arr[x][y]访问数组中给定元素的优点。

（这与 Java 和 C# 等语言使用引用分配多维数组的方式非常相似。）

请注意，当您使用完数组后，您必须分两步释放它；首先你必须释放数组的每一行，然后你必须释放数组（指针）本身。

// Deallocate a 2-D array
void free_triangle_array(int **arr, int nrows)
{
    // Free each allocated row
    for (int i = 0;  i < nrows;  i++)
    {
        if (arr[i] != NULL)
            free(arr[i]);
        arr[i] = NULL;
    }

    // Free the pointer array
    free(arr);
}
于 2013-07-01T16:28:19.220 回答