c - 三角配列

Question

各行の要素数が異なる C で 2 次元配列を作成したいと考えています。具体的には、三角形の 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
...

この三角行列/配列へのマッピングを使用して、データを 1 次元配列に格納するだけです。

バイジェクション

1 次元のゼロベースのインデックスkと 2 次元のゼロベースの行iと列は、 (where )jの場合と同じです。k = i(i+1)/2 + jj <= i

ノート

上記は、下三角正方行列/配列用です。あなたは非常に似たようなことをすることができます

• 上三角正方行列/配列
  • 単純に交換iしてj
• 長方形の下三角行列または上三角行列/配列
  • これは少しトリッキーですが (場合によって推論する必要があります)、1 次元配列 (実装) を概念的な 2 次元配列 (ビュー) にマッピングするという同じアイデアを実現できます。

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

1 次元配列を使用して計算 サイズ = 行 × (行 + 1) / 2 の配列を宣言します。インデックス = 行 x (行 + 1) / 2 + 列右シフトは 2 による除算を処理します)。または、各行にポインターの配列を使用し、必要な数の要素をループに割り当てることもできます。