三角数组

Question

我想在C中构造一个2d数组，其中每一行都有不同数量的元素。具体而言，我想构建一个三角形7x6阵列。为了节省内存，我想避免像下面的例子那样存储零。

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

我该怎么做？

Answer 1

配方

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

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

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

双向注入

一维从零开始索引k和基于零的二维行i和列j是相同的时k = i(i+1)/2 + j（其中j <= i）。

注意

以上是针对下三角矩阵/数组。你可以做

• 的上三角方阵/阵列
  • 简单地交换i和j非常类似的东西
• 矩形较低或上三角矩阵/阵列
  • 这是一个有点棘手的问题（你需要通过案例来推理），但是可以完成将一维数组（实现）映射到概念二维数组（视图）的相同想法

Answer 2

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

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

但是，我不知道为什么你想这样做。如果您对访问此阵列时不够谨慎，则很可能最终出现分段错误。

Answer 3

此功能将在一个一维阵列分配的行和列数的指标，是无序：

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 

Answer 4

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

Answer 5

您可以创建一个指针，其中每个指针指向另一个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); 
} 

Answer 6

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

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. 简单的方法，但可能比不使用'packed'属性时慢。权衡将是会有额外的比特包装。这也可能是不安全的一些implimentaitons（检查下面的计算器链接）
2. 您可能必须在次
3. 这种方法是在网络代码中的数据包需要用时间来交换承担端照顾。

你可以阅读更多关于属性：

1. GCC文档：http://gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Type-Attributes.html
2. 代价：Is gcc's __attribute__((packed))/#pragma pack unsafe?