三角數組

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?