将2D矩阵转换为1D [英] transform matrix 2D to 1D
问题描述
我在将矩阵2D传递到带有C函数的vector(1D array)时遇到问题.有我要创建的代码:
I have an issue passing a matrix 2D to a vector(1D array)with function in C. There is the code of what i want to create:
#include <stdio.h>
#define N 64
#define A 8
int tab2[A][A];
int vect[N];
void fonc(int i,int j,int k,int l,int c,int **tab2,int *vect);
void fonc(int i,int j,int k,int l,int c,int **tab2,int *vect){
vect[k]=tab2[0][0];
printf("%d",vect[k]);
while(i!=8 && j!=8)
{
//bas
i=i;
j=j+1;
vect[k]++;
printf("%d\t",vect[k]);
//descente
while(j !=0)
{
i=i+1;
j=j-1;
vect[k]++;
}
//droite
i=i;
j=j+1;
vect[k]++;
//montée
while(i !=0)
{
i=i-1;
j=j+1;
vect[k]++;
}
}
}
int main (){
int vect[64] ;
int tab2[8][8]={
{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}};
int i;
int j;
int k;
fonc(i,j,k,8,8,tab2,vect);
//printf("%d\n", ) ;//limpide !
return 0;
}
我没有错误，但是它调试我无法使somoene产生结果，我不知道该怎么办，我使用该函数对jpeg压缩RLE编码应用了Zigzag线性变换，谢谢大家 我尝试这样做:
i don't have errors but it debug i can't the result somoene have an idea how can i do , i use the function to applied a zigzag linear transform for jpeg compression RLE codingthank you for all i try to do this :
0, 0
0, 1 1, 0
2, 0 1, 1 0, 2
0, 3 1, 2 2, 1 3, 0
4, 0 3, 1 2, 2 1, 3 0, 4
0, 5 1, 4 2, 3 3, 2 4, 1 5, 0
6, 0 5, 1 4, 2 3, 3 2, 4 1, 5 0, 6
0, 7 1, 6 2, 5 3, 4 4, 3 5, 2 6, 1 7, 0
7, 1 6, 2 5, 3 4, 4 3, 5 2, 6 1, 7
2, 7 3, 6 4, 5 5, 4 6, 3 7, 2
推荐答案
您的函数有3个不必要的参数-i，j，k.在main()中传递给函数的值未初始化.函数中在i和j中传递的值无关紧要，因为代码在首次使用时会设置变量.使用了k中的值，但是传递给该函数的值是不确定的.需要进行更改，以减少三个参数，它们只是函数中的局部变量，并且都需要设置为零. (k是向量中应分配矩阵下一个值的索引； i和j是数组的下标).
Your function has 3 unnecessary parameters — i, j, k. The values passed in main() to the function are uninitialized; the values passed in i and j in the function are irrelevant because the code sets the variables on first use. The value in k is used but the value passed to the function is indeterminate. That needs to be changed so that there are three fewer parameters and they're just local variables in the function, and they all need to be set to zero. (k is the index in the vector where the next value from the matrix should be assigned; i and j are the subscripts of the array).
您应该丢失两个全局变量；永远不会引用它们，因为main()中的局部变量会将它们隐藏，而函数的参数会将它们隐藏.这两个#define值都不会使用.
You should lose the two global variables; they're never referenced because the local variables in main() hide them and the parameters to the function hide them. The two #define values are never used either.
尽管您传递了l和c(行和列)，但是您忽略了它们并假定上限为l = 8和c = 8.另外，您尝试传递给fonc的类型不是int **tab2；它是int tab2[][8]或int tab2[8][8].函数签名也可能变为:
Although you pass l and c (lines and columns), you ignore them and assume the upper bounds are l = 8 and c = 8. Also, the type you try to pass to fonc is not int **tab2; it is int tab2[][8] or int tab2[8][8]. The function signature may as well become:
void fonc(int tab2[8][8], int *vect);
在您的函数中，形式为vect[k]++;的每个赋值都应为形式为vect[k++] = tab2[i][j];的赋值.
In your function, every assignment of the form vect[k]++; should be an assignment of the form vect[k++] = tab2[i][j];.
之字形算法很容易编码.对于8x8固定大小的矩阵，很容易将索引序列打包到数组中.我假设之字形图的左上角是(0，0)，而右下角是(7，7).如果那是错误的，则只需修复表的初始化程序.
The zig-zag algorithm is fiddly to code. For an 8x8 fixed-size matrix, it is tempting just to pack the the sequence of indexes into an array. I'm assuming that the top-left corner of the zig-zag diagram is (0, 0) and the bottom-right is (7, 7). If that's wrong, you simply have to fix the initializer for the table.
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 },
};
那么正确的复制操作就很简单:
The correct copying operation is then simple:
for (int i = 0; i < 64; i++)
vect[i] = tab[zigzag[i].x][zigzag[i].y];
我们可以争论编写64与sizeof(zigzag)/sizeof(zigzag[0])的关系.如果您确实内存不足(目前数据只有128个字节，那么我不相信您)，那么您可以将两个坐标打包到一个字节中进行存储:
We can debate about writing 64 vs sizeof(zigzag)/sizeof(zigzag[0]). If you're really short of memory (the data is only 128 bytes at the moment, so I don't believe you), then you could pack the two coordinates into one byte for storage:
static const unsigned char zigzag[] =
{
0x00, 0x10, 0x01, 0x02, ...
};
，然后使用更复杂的下标表达式:
and then use a more complex subscripting expression:
vect[i] = tab[zigzag[i] >> 4][zigzag[i] & 0xF];
由于较少的内存访问，它可能会更快-您必须进行测量.
It might be faster due to fewer memory accesses — you'd have to measure.
所有这些都假设您正在处理8x8固定大小的正方形数组.如果必须处理任何大小的数组并且仍然要完成工作，那么您可能必须对事物进行编码，以便指定起点，向右走一步，向左对角向下走，直到到达边缘(向左或向右).底部)，您可以向右下或向右走一步，直到您到达对角线(顶部或右边)，然后沿对角线向右上走，然后向右或向下走一步，然后重复一次，直到到达终点为止.巧妙地编写代码是很愚蠢的.复制循环不会是两行.
This all assumes you're dealing with 8x8 fixed size square arrays. If you have to deal with any size of array and still do the job, then you probably have to encode things so that you specify the starting point, you go one step right, you go down diagonally left until you reach an edge (left or bottom), you go one step down or right, you go up diagonally right until you reach an edge (top or right), you go one step right or down, and repeat until you reach the end. That is fiddly to code neatly; the copying loop won't be two lines.
这是问题中的代码，已进行了一些整理，但fonc()中的核心算法未更改-至少对i，j和k的处理未更改，但对其进行了初始化.主函数在fonc()的调用之前打印出矩阵，并在其后打印出矢量. fonc()中对向量的每个分配均已修复并检测.
Here is the code from the question, somewhat cleaned up but with the core algorithm in fonc() unchanged — at least, unchanged in the handling of i, j, and k except for initializing them. The main function prints out the matrix before, and the vector after, the call to fonc(). Each assignment in fonc() to the vector has been fixed and instrumented.
#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
匿名编写的代码的版本
匿名提供了答案.这在概念上非常有趣，但是我不确定它是正确的.对其进行检测以使其能够打印其输入和输出不是决定性的，因此我将其放置在与上面的代码相同的表格中，该表格应产生矢量1..64.代码和输出是:
Instrumented version of code by Anonymous
Anonymous provided an answer. It's very interesting in concept, but I'm not sure it is accurate. Instrumenting it so that it prints its input and output is not conclusive, so I put in the same table as in the code above which should yield the vector 1..64. The code and output are:
#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
该结果不太正确，但我确定这是正确的方向. (同样很明显，这太复杂了，无法对匿名问题提出评论，因此在这里添加.)
That result isn't quite right, but I'm sure it is the correct direction. (Equally clearly, this is too complex to put in a comment to Anonymous's question — hence this addition here.)
从概念上讲，该代码正在旋转方阵以使其站在其点上，然后在(8 + 8-1)行上水平地来回扫描.
Conceptually, the code is turning the square matrix so that it is standing on its points, and then scanning horizontally back and forth over the (8 + 8 - 1) lines.
3x3扫描的ASCII图形:
ASCII art for a 3x3 scan:
/\
/\/\
/\/\/\
\/\/\/
\/\/
\/
有(3 + 3-1)= 5个扫描行.在表驱动的代码中，与此相关的数据具有规律性.
There are (3 + 3 - 1) = 5 scan rows. In the table driven code, there is a regularity to the data that corresponds to this.
在功能dezigzag()中，分配行需要反转条件.现有代码等效于:
In the function dezigzag(), the assignment line needs to invert the condition. The existing code is equivalent to:
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;
}
使用迭代器结构的代码
迭代器的结构相当复杂.极端的是使用多个单行内联函数，但要避免重复表达式.我敢肯定有清理的空间，但是是时候停止玩乐了.
Code using iterator structure
The iterator structure is fairly complex. The use of multiple one-line inline functions is extreme, but avoids repeating expressions. There is room for cleanup, I'm sure, but it was time to stop having fun.
#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;
}
这篇关于将2D矩阵转换为1D的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
