関数にはi、j、 の3 つの不要なパラメーターがありますk。main()関数に渡される値は初期化されていません。コードは最初の使用時に変数を設定するため、関数で渡される値は無関係iです。jの値kが使用されますが、関数に渡される値は不確定です。これを変更して、パラメーターが 3 つ少なくなり、それらが関数内の単なるローカル変数になり、すべてゼロに設定する必要があります。(kは行列の次の値を割り当てるベクトル内のインデックスで、iはj配列の添字です)。
2 つのグローバル変数を失う必要があります。のローカル変数がmain()それらを非表示にし、関数へのパラメーターがそれらを非表示にするため、それらは決して参照されません。2 つの#define値も使用されません。
land (行と列)を渡しますがc、それらを無視し、上限がl = 8andであると想定しc = 8ます。また、渡そうとする型foncは notint **tab2です。int tab2[][8]またはですint tab2[8][8]。関数のシグネチャは次のようになります。
void fonc(int tab2[8][8], int *vect);
あなたの関数では、フォームのすべての代入はフォームvect[k]++;の代入でなければなりませんvect[k++] = tab2[i][j];。
ジグザグ アルゴリズムは、コーディングが面倒です。8x8 の固定サイズの行列の場合、一連のインデックスを配列にパックしたくなるだけです。ジグザグ ダイアグラムの左上隅が (0, 0) で、右下隅が (7, 7) であると想定しています。それが間違っている場合は、テーブルの初期化子を修正するだけです。
static const struct ZigZag
{
unsigned char y, x; // Reversed from original
} zigzag[] =
{
{ 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 },
{ 1, 1 }, { 2, 0 }, { 3, 0 }, { 2, 1 },
{ 1, 2 }, { 0, 3 }, { 0, 4 }, { 1, 3 },
...
{ 7, 5 }, { 7, 6 }, { 6, 7 }, { 7, 7 },
};
正しいコピー操作は簡単です。
for (int i = 0; i < 64; i++)
vect[i] = tab[zigzag[i].x][zigzag[i].y];
64 vs を書くことについて議論することができsizeof(zigzag)/sizeof(zigzag[0])ます。メモリが本当に不足している場合 (データは現時点で 128 バイトしかないので、信じられません)、2 つの座標を 1 バイトにまとめて保存できます。
static const unsigned char zigzag[] =
{
0x00, 0x10, 0x01, 0x02, ...
};
次に、より複雑な添字式を使用します。
vect[i] = tab[zigzag[i] >> 4][zigzag[i] & 0xF];
メモリアクセスが少ないため、より高速になる可能性があります-測定する必要があります.
これはすべて、8x8 の固定サイズの正方配列を扱っていることを前提としています。任意のサイズの配列を処理する必要があり、それでもジョブを実行する必要がある場合は、開始点を指定し、右に 1 ステップ移動し、エッジ (左または左) に到達するまで左斜め下に移動するようにエンコードする必要があります。下)、1 歩下または右に移動し、エッジ (上または右) に到達するまで右斜め上に移動し、1 歩右または下に移動し、最後に到達するまで繰り返します。これはきちんとコーディングするのが面倒です。コピーループは2行になりません。
質問からインストルメント化されたコード
質問のコードを次に示します。多少クリーンアップされていますが、コア アルゴリズムは変更fonc()されていません。main 関数は、 の呼び出しの前に行列を出力し、呼び出しの後にベクトルを出力します。ベクトルへの各割り当ては修正され、インストルメント化されています。ijkfonc()fonc()
#include <stdio.h>
void fonc(int tab2[8][8], int *vect);
void fonc(int tab2[8][8], int *vect)
{
int i = 0;
int j = 0;
int k = 0;
vect[k] = tab2[i][j];
printf("v[%2d] = m[%2d][%2d] = %d\n", k, i, j, tab2[i][j]);
while (i != 8 && j != 8)
{
// bas
i = i;
j = j+1;
vect[k++] = tab2[i][j];
printf("v[%2d] = m[%2d][%2d] = %d\n", k, i, j, tab2[i][j]);
// descente
while (j != 0)
{
i = i+1;
j = j-1;
vect[k++] = tab2[i][j];
printf("v[%2d] = m[%2d][%2d] = %d\n", k, i, j, tab2[i][j]);
}
// droite
i = i;
j = j+1;
vect[k++] = tab2[i][j];
printf("v[%2d] = m[%2d][%2d] = %d\n", k, i, j, tab2[i][j]);
// montée
while (i != 0)
{
i = i-1;
j = j+1;
printf("v[%2d] = m[%2d][%2d] = %d\n", k, i, j, tab2[i][j]);
vect[k++] = tab2[i][j];
}
}
}
int main(void)
{
int vect[64];
int tab2[8][8] =
{
// Up to element value 28, the data should appear in
// the order 1, 2, 3, ... in the output vector
{1, 2, 6, 7, 15, 16, 28, 1},
{3, 5, 8, 14, 17, 27, 29, 1},
{4, 9, 13, 18, 26, 30, 39, 1},
{10, 12, 19, 25, 31, 38, 40, 1},
{11, 20, 24, 32, 37, 41, 46, 1},
{21, 23, 33, 36, 42, 45, 47, 1},
{22, 34, 35, 43, 44, 48, 49, 1},
{22, 34, 35, 43, 44, 48, 49, 1}
};
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
printf("%3d", tab2[i][j]);
putchar('\n');
}
fonc(tab2, vect);
for (int i = 0; i < 8 * 8; i++)
{
printf("%3d", vect[i]);
if (i % 8 == 7)
putchar('\n');
}
return 0;
}
出力例:
1 2 6 7 15 16 28 1
3 5 8 14 17 27 29 1
4 9 13 18 26 30 39 1
10 12 19 25 31 38 40 1
11 20 24 32 37 41 46 1
21 23 33 36 42 45 47 1
22 34 35 43 44 48 49 1
22 34 35 43 44 48 49 1
v[ 0] = m[ 0][ 0] = 1
v[ 1] = m[ 0][ 1] = 2
v[ 2] = m[ 1][ 0] = 3
v[ 3] = m[ 1][ 1] = 5
v[ 3] = m[ 0][ 2] = 6
v[ 5] = m[ 0][ 3] = 7
v[ 6] = m[ 1][ 2] = 8
v[ 7] = m[ 2][ 1] = 9
v[ 8] = m[ 3][ 0] = 10
v[ 9] = m[ 3][ 1] = 12
v[ 9] = m[ 2][ 2] = 13
v[10] = m[ 1][ 3] = 14
v[11] = m[ 0][ 4] = 15
v[13] = m[ 0][ 5] = 16
v[14] = m[ 1][ 4] = 17
v[15] = m[ 2][ 3] = 18
v[16] = m[ 3][ 2] = 19
v[17] = m[ 4][ 1] = 20
v[18] = m[ 5][ 0] = 21
v[19] = m[ 5][ 1] = 23
v[19] = m[ 4][ 2] = 24
v[20] = m[ 3][ 3] = 25
v[21] = m[ 2][ 4] = 26
v[22] = m[ 1][ 5] = 27
v[23] = m[ 0][ 6] = 28
v[25] = m[ 0][ 7] = 1
v[26] = m[ 1][ 6] = 29
v[27] = m[ 2][ 5] = 30
v[28] = m[ 3][ 4] = 31
v[29] = m[ 4][ 3] = 32
v[30] = m[ 5][ 2] = 33
v[31] = m[ 6][ 1] = 34
v[32] = m[ 7][ 0] = 22
v[33] = m[ 7][ 1] = 34
v[33] = m[ 6][ 2] = 35
v[34] = m[ 5][ 3] = 36
v[35] = m[ 4][ 4] = 37
v[36] = m[ 3][ 5] = 38
v[37] = m[ 2][ 6] = 39
v[38] = m[ 1][ 7] = 1
v[39] = m[ 0][ 8] = 3
2 3 5 6 7 8 9 10
12 13 14 15 16 17 18 19
20 21 23 24 25 26 27 28
1 29 30 31 32 33 34 22
34 35 36 37 38 39 1 3
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
ご了承ください：
tab2[0][8]範囲外にアクセスします。- 対角線の動きが行列の下部または右側に当たると、アルゴリズムに問題が発生します。
- C99 と VLA がサポートされていない場合、変数 NxM 配列を扱うのは面倒です。
テーブル駆動プログラム
#include <stdio.h>
void fonc(int tab2[8][8], int vect[8]);
void fonc(int tab2[8][8], int vect[8])
{
static const struct ZigZag
{
unsigned char y, x;
} zigzag[8*8] =
{
{ 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 },
{ 1, 1 }, { 2, 0 }, { 3, 0 }, { 2, 1 },
{ 1, 2 }, { 0, 3 }, { 0, 4 }, { 1, 3 },
{ 2, 2 }, { 3, 1 }, { 4, 0 }, { 5, 0 },
{ 4, 1 }, { 3, 2 }, { 2, 3 }, { 1, 4 },
{ 0, 5 }, { 0, 6 }, { 1, 5 }, { 2, 4 },
{ 3, 3 }, { 4, 2 }, { 5, 1 }, { 6, 0 },
{ 7, 0 }, { 6, 1 }, { 5, 2 }, { 4, 3 },
{ 3, 4 }, { 2, 5 }, { 1, 6 }, { 0, 7 },
{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 },
{ 5, 3 }, { 6, 2 }, { 7, 1 }, { 7, 2 },
{ 6, 3 }, { 5, 4 }, { 4, 5 }, { 3, 6 },
{ 2, 7 }, { 3, 7 }, { 4, 6 }, { 5, 5 },
{ 6, 4 }, { 7, 3 }, { 7, 4 }, { 6, 5 },
{ 5, 6 }, { 4, 7 }, { 5, 7 }, { 6, 6 },
{ 7, 5 }, { 7, 6 }, { 6, 7 }, { 7, 7 },
};
for (int i = 0; i < 64; i++)
vect[i] = tab2[zigzag[i].x][zigzag[i].y];
}
// The output vector should be in order 1..64
int main(void)
{
int vect[64];
int tab2[8][8] =
{
{ 1, 2, 6, 7, 15, 16, 28, 29 },
{ 3, 5, 8, 14, 17, 27, 30, 43 },
{ 4, 9, 13, 18, 26, 31, 42, 44 },
{ 10, 12, 19, 25, 32, 41, 45, 54 },
{ 11, 20, 24, 33, 40, 46, 53, 55 },
{ 21, 23, 34, 39, 47, 52, 56, 61 },
{ 22, 35, 38, 48, 51, 57, 60, 62 },
{ 36, 37, 49, 50, 58, 59, 63, 64 }
};
puts("Matrix:");
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
printf("%3d", tab2[i][j]);
putchar('\n');
}
fonc(tab2, vect);
puts("Vector:");
for (int i = 0; i < 8 * 8; i++)
{
printf("%3d", vect[i]);
if (i % 8 == 7)
putchar('\n');
}
return 0;
}
出力例:
Matrix:
1 2 6 7 15 16 28 29
3 5 8 14 17 27 30 43
4 9 13 18 26 31 42 44
10 12 19 25 32 41 45 54
11 20 24 33 40 46 53 55
21 23 34 39 47 52 56 61
22 35 38 48 51 57 60 62
36 37 49 50 58 59 63 64
Vector:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Anonymous によるインストルメント化されたコードのバージョン
匿名さんが答えてくれました。コンセプトとしては非常に興味深いですが、正確かどうかはわかりません。入力と出力を出力するようにインストルメント化することは決定的ではないため、ベクトル 1..64 を生成する上記のコードと同じテーブルに入れます。コードと出力は次のとおりです。
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
void dezigzag(int out[64], int in[8][8])
{
int n = 0;
for (int diag = 0; diag < 15; diag++)
{
for (int i = max(0, diag - 7); i <= min(7, diag); i++)
out[n++] = diag % 2 ? in[diag - i][i] : in[i][diag - i];
}
}
int main(void)
{
int out[64] = {-1};
int in[8][8];
for (int i = 0; i < 64; i++)
in[i % 8][i / 8] = i;
puts("Matrix:");
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
printf("%3d", in[i][j]);
putchar('\n');
}
dezigzag(out, in);
puts("Vector:");
for (int i = 0; i < 8 * 8; i++)
{
printf("%3d", out[i]);
if (i % 8 == 7)
putchar('\n');
}
//for (int i = 0; i < 64; i++) {
// printf("%d: %d\n", i, out[i]);
//}
int tab2[8][8] =
{
{ 1, 2, 6, 7, 15, 16, 28, 29 },
{ 3, 5, 8, 14, 17, 27, 30, 43 },
{ 4, 9, 13, 18, 26, 31, 42, 44 },
{ 10, 12, 19, 25, 32, 41, 45, 54 },
{ 11, 20, 24, 33, 40, 46, 53, 55 },
{ 21, 23, 34, 39, 47, 52, 56, 61 },
{ 22, 35, 38, 48, 51, 57, 60, 62 },
{ 36, 37, 49, 50, 58, 59, 63, 64 },
};
puts("Matrix:");
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
printf("%3d", tab2[i][j]);
putchar('\n');
}
dezigzag(out, tab2);
puts("Vector:");
for (int i = 0; i < 8 * 8; i++)
{
printf("%3d", out[i]);
if (i % 8 == 7)
putchar('\n');
}
return 0;
}
出力：
Matrix:
0 8 16 24 32 40 48 56
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
Vector:
0 1 8 16 9 2 3 10
17 24 32 25 18 11 4 5
12 19 26 33 40 48 41 34
27 20 13 6 7 14 21 28
35 42 49 56 57 50 43 36
29 22 15 23 30 37 44 51
58 59 52 45 38 31 39 46
53 60 61 54 47 55 62 63
Matrix:
1 2 6 7 15 16 28 29
3 5 8 14 17 27 30 43
4 9 13 18 26 31 42 44
10 12 19 25 32 41 45 54
11 20 24 33 40 46 53 55
21 23 34 39 47 52 56 61
22 35 38 48 51 57 60 62
36 37 49 50 58 59 63 64
Vector:
1 3 2 6 5 4 10 9
8 7 15 14 13 12 11 21
20 19 18 17 16 28 27 26
25 24 23 22 36 35 34 33
32 31 30 29 43 42 41 40
39 38 37 49 48 47 46 45
44 54 53 52 51 50 58 57
56 55 61 60 59 63 62 64
その結果は完全に正しいとは言えませんが、正しい方向であると確信しています。(同様に明らかに、これは匿名の質問にコメントするには複雑すぎるため、ここに追加します。)
概念的には、コードは正方行列を回転させてその点に立つようにし、(8 + 8 - 1) 行を水平に前後にスキャンします。
3x3 スキャンの ASCII アート:
/\
/\/\
/\/\/\
\/\/\/
\/\/
\/
(3 + 3 - 1) = 5 スキャン行があります。テーブル駆動型のコードでは、これに対応するデータに規則性があります。
Anonymous のコードを修正するには
functiondezigzag()では、代入行で条件を反転する必要があります。既存のコードは次と同等です。
out[n++] = (diag % 2 == 1) ? in[diag - i][i] : in[i][diag - i];
正しいコードは次のとおりです。
out[n++] = (diag % 2 == 0) ? in[diag - i][i] : in[i][diag - i];
出力は次のとおりです。
Matrix:
0 8 16 24 32 40 48 56
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
Vector:
0 8 1 2 9 16 24 17
10 3 4 11 18 25 32 40
33 26 19 12 5 6 13 20
27 34 41 48 56 49 42 35
28 21 14 7 15 22 29 36
43 50 57 58 51 44 37 30
23 31 38 45 52 59 60 53
46 39 47 54 61 62 55 63
Matrix:
1 2 6 7 15 16 28 29
3 5 8 14 17 27 30 43
4 9 13 18 26 31 42 44
10 12 19 25 32 41 45 54
11 20 24 33 40 46 53 55
21 23 34 39 47 52 56 61
22 35 38 48 51 57 60 62
36 37 49 50 58 59 63 64
Vector:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
MxN 配列を処理するコード
#include <stdio.h>
static inline int max(int a, int b) { return (a > b) ? a : b; }
static inline int min(int a, int b) { return (a < b) ? a : b; }
static void print_info(int rows, int cols)
{
int n = rows + cols - 1;
printf("R = %d, C = %d, N = %d\n", rows, cols, n);
for (int i = 0; i < n; i++)
{
int max_x = min(i, cols-1);
int min_x = max(0, i - n + cols);
int max_y = min(i, rows-1);
int min_y = max(0, i - n + rows);
printf("i = %d, min_x = %d, max_x = %d, min_y = %d, max_y = %d\n",
i, min_x, max_x, min_y, max_y);
}
for (int i = 0; i < n; i++)
{
printf("%2d:", i);
if (i % 2 == 0)
{
int max_x = min(i, cols-1);
int min_x = max(0, i - n + cols);
for (int j = min_x; j <= max_x; j++)
/* (row,col) */
printf(" (r=%d,c=%d)", i - j, j);
}
else
{
int max_y = min(i, rows-1);
int min_y = max(0, i - n + rows);
for (int j = min_y; j <= max_y; j++)
printf(" (r=%d,c=%d)", j, i - j);
}
putchar('\n');
}
}
static void set_zigzag(int rows, int cols, int matrix[rows][cols])
{
int x = 0;
int n = rows + cols - 1;
for (int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
int max_x = min(i, cols-1);
int min_x = max(0, i - n + cols);
for (int j = min_x; j <= max_x; j++)
matrix[i-j][j] = x++;
}
else
{
int max_y = min(i, rows-1);
int min_y = max(0, i - n + rows);
for (int j = min_y; j <= max_y; j++)
matrix[j][i-j] = x++;
}
}
}
static void zigzag(int rows, int cols, int matrix[rows][cols], int vector[rows*cols])
{
int n = rows + cols - 1;
int v = 0;
for (int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
int max_x = min(i, cols-1);
int min_x = max(0, i - n + cols);
for (int j = min_x; j <= max_x; j++)
vector[v++] = matrix[i-j][j];
}
else
{
int max_y = min(i, rows-1);
int min_y = max(0, i - n + rows);
for (int j = min_y; j <= max_y; j++)
vector[v++] = matrix[j][i-j];
}
}
}
static void dump_matrix(const char *tag, int rows, int cols, int matrix[rows][cols])
{
printf("%s (%d x %d):\n", tag, rows, cols);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
printf("%3d", matrix[i][j]);
putchar('\n');
}
}
static void dump_vector(const char *tag, int rows, int cols, int vector[rows * cols])
{
printf("%s (%d : %d):\n", tag, rows, cols);
for (int i = 0; i < rows * cols; i++)
{
printf("%3d", vector[i]);
if (i % cols == cols - 1)
putchar('\n');
}
}
static void test_rows_x_cols(int rows, int cols)
{
int vector[rows * cols];
int matrix[rows][cols];
printf("\nTest %dx%d\n\n", rows, cols);
print_info(rows, cols);
set_zigzag(rows, cols, matrix);
dump_matrix("Matrix", rows, cols, matrix);
zigzag(rows, cols, matrix, vector);
dump_vector("Vector", rows, cols, vector);
}
int main(void)
{
struct
{
int rows;
int cols;
} test[] =
{
{ 4, 4 }, { 6, 4 }, { 4, 7 }, { 7, 14 }, { 6, 16 }, { 3, 33 },
};
enum { NUM_TEST = sizeof(test) / sizeof(test[0]) };
for (int i = 0; i < NUM_TEST; i++)
test_rows_x_cols(test[i].rows, test[i].cols);
return 0;
}
イテレータ構造を使用したコード
イテレータ構造はかなり複雑です。1 行のインライン関数を複数使用するのは極端ですが、式の繰り返しは避けてください。クリーンアップの余地はあると思いますが、楽しむのをやめる時が来ました。
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
typedef struct RC
{
int row;
int col;
} RC;
typedef struct RLE
{
RC curr;
RC size;
int zigzag;
int sequence;
} RLE;
static inline int max(int a, int b) { return (a > b) ? a : b; }
static inline int min(int a, int b) { return (a < b) ? a : b; }
static inline int get_num_zigzags(const RLE *rle)
{
return rle->size.row + rle->size.col - 1;
}
static inline int get_max_row(const RLE *rle)
{
return min(rle->zigzag, rle->size.row - 1);
}
static inline int get_min_row(const RLE *rle)
{
return max(0, rle->zigzag - get_num_zigzags(rle) + rle->size.row);
}
static inline int get_max_col(const RLE *rle)
{
return min(rle->zigzag, rle->size.col - 1);
}
static inline int get_min_col(const RLE *rle)
{
return max(0, rle->zigzag - get_num_zigzags(rle) + rle->size.col);
}
static inline int get_row_from_col(const RLE *rle)
{
return rle->zigzag - rle->curr.col;
}
static inline int get_col_from_row(const RLE *rle)
{
return rle->zigzag - rle->curr.row;
}
static RLE RLE_init(int rows, int cols)
{
RLE rle;
assert(rows > 0 && cols > 0);
assert(INT_MAX / rows >= cols);
rle.curr.row = 0;
rle.curr.col = 0;
rle.size.row = rows;
rle.size.col = cols;
rle.zigzag = 0;
rle.sequence = 0;
return(rle);
}
static inline RC RLE_position(const RLE *rle)
{
return rle->curr;
}
static inline int RLE_row(const RLE *rle)
{
return rle->curr.row;
}
static inline int RLE_col(const RLE *rle)
{
return rle->curr.col;
}
static inline int RLE_sequence(const RLE *rle)
{
return rle->sequence;
}
static inline int RLE_zigzag(const RLE *rle)
{
return rle->zigzag;
}
static inline RC RLE_size(const RLE *rle)
{
return rle->size;
}
static inline bool RLE_finished(const RLE *rle)
{
return(rle->sequence == rle->size.row * rle->size.col);
}
static void RLE_check(const RLE *rle)
{
assert(rle->size.row > 0);
assert(rle->size.col > 0);
assert(rle->curr.row < rle->size.row && rle->curr.row >= 0);
assert(rle->curr.col < rle->size.col && rle->curr.col >= 0);
assert(rle->zigzag >= 0 && rle->zigzag < rle->size.row + rle->size.col - 1);
assert(rle->sequence >= 0 && rle->sequence <= rle->size.row * rle->size.col);
}
#if defined(REL_DUMP_REQUIRED)
static void RLE_dump(const char *tag, const RLE *rle)
{
printf("Dump RLE (%s):", tag);
RC size = RLE_size(rle);
assert(size.row == rle->size.row);
assert(size.col == rle->size.col);
printf(" Rows = %2d, Cols = %2d, Zigzags = %2d; ",
rle->size.row, rle->size.col, rle->size.row + rle->size.col - 1);
RC posn = RLE_position(rle);
assert(posn.row == rle->curr.row);
assert(posn.col == rle->curr.col);
assert(posn.row == RLE_row(rle));
assert(posn.col == RLE_col(rle));
printf(" Position: r = %d, c = %d; ", RLE_row(rle), RLE_col(rle));
assert(RLE_zigzag(rle) == rle->zigzag);
assert(RLE_sequence(rle) == rle->sequence);
printf(" Zigzag = %d, Sequence = %d\n", rle->zigzag, rle->sequence);
RLE_check(rle);
}
#endif
static void RLE_next(RLE *rle)
{
RLE_check(rle);
/* Already finished? */
if (RLE_finished(rle))
return;
rle->sequence++;
/* Finished now? */
if (RLE_finished(rle))
return;
if (rle->zigzag % 2 == 0)
{
if (rle->curr.col < get_max_col(rle))
{
/* Same zigzag */
rle->curr.col++;
rle->curr.row = get_row_from_col(rle);
}
else
{
/* Next zigzag */
rle->zigzag++;
rle->curr.row = get_min_row(rle);
rle->curr.col = get_col_from_row(rle);
}
}
else
{
if (rle->curr.row < get_max_row(rle))
{
/* Same zigzag */
rle->curr.row++;
rle->curr.col = get_col_from_row(rle);
}
else
{
/* Next zigzag */
rle->zigzag++;
rle->curr.col = get_min_col(rle);
rle->curr.row = get_row_from_col(rle);
}
}
}
static void print_info(int rows, int cols)
{
int n = rows + cols - 1;
printf("R = %d, C = %d, N = %d\n", rows, cols, n);
for (int zigzag = 0; zigzag < n; zigzag++)
{
int max_col = min(zigzag, cols-1);
int min_col = max(0, zigzag - n + cols);
int max_row = min(zigzag, rows-1);
int min_row = max(0, zigzag - n + rows);
printf("zigzag = %2d, min_col = %2d, max_col = %2d, min_row = %2d, max_row = %2d\n",
zigzag, min_col, max_col, min_row, max_row);
}
for (int zigzag = 0; zigzag < n; zigzag++)
{
printf("%d:", zigzag);
if (zigzag % 2 == 0)
{
int max_col = min(zigzag, cols-1);
int min_col = max(0, zigzag - n + cols);
for (int col = min_col; col <= max_col; col++)
/* (row,col) */
printf(" (r=%d,c=%d)", zigzag - col, col);
}
else
{
int max_row = min(zigzag, rows-1);
int min_row = max(0, zigzag - n + rows);
for (int row = min_row; row <= max_row; row++)
printf(" (r=%d,c=%d)", row, zigzag - row);
}
putchar('\n');
}
}
static void dump_matrix(const char *tag, int rows, int cols, int matrix[rows][cols])
{
printf("%s (%d x %d):\n", tag, rows, cols);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
printf("%3d", matrix[i][j]);
putchar('\n');
}
}
static void dump_vector(const char *tag, int rows, int cols, int vector[rows * cols])
{
printf("%s (%d : %d):\n", tag, rows, cols);
for (int i = 0; i < rows * cols; i++)
{
printf("%3d", vector[i]);
if (i % cols == cols - 1)
putchar('\n');
}
}
static void RLE_demonstration(int rows, int cols)
{
int matrix[rows][cols];
int vector[rows*cols];
/* Set matrix */
for (RLE rle = RLE_init(rows, cols); !RLE_finished(&rle); RLE_next(&rle))
{
//RLE_dump("Set Matrix", &rle);
RC rc = RLE_position(&rle);
matrix[rc.row][rc.col] = RLE_sequence(&rle);
}
dump_matrix("Matrix", rows, cols, matrix);
/* Convert matrix to vector */
for (RLE rle = RLE_init(rows, cols); !RLE_finished(&rle); RLE_next(&rle))
{
//RLE_dump("Get Matrix", &rle);
RC rc = RLE_position(&rle);
vector[RLE_sequence(&rle)] = matrix[rc.row][rc.col];
}
dump_vector("Vector", rows, cols, vector);
}
int main(int argc, char **argv)
{
struct
{
int rows;
int cols;
} test[] =
{
{ 4, 4 }, { 6, 4 }, { 4, 7 }, { 7, 14 }, { 6, 16 }, { 3, 33 },
};
enum { NUM_TEST = sizeof(test) / sizeof(test[0]) };
/* argv != 0 avoids unused variable warning */
int verbose = (argv != 0 && argc > 1) ? 1 : 0;
for (int i = 0; i < NUM_TEST; i++)
{
if (verbose)
print_info(test[i].rows, test[i].cols);
RLE_demonstration(test[i].rows, test[i].cols);
}
return 0;
}
