Convert 2D matrix to 1D

I have a problem transferring a 2D matrix into a vector (1D array) with a function in C. There is code for 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; } 

I have no errors, but it is being debugged. I cannot make somoene have an idea how I can do this. I use this function to apply zigzag linear transformation for jpeg compression. RLE coding means that for all I am trying to do this: enter image description here

 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 
+6
source share
3 answers

There are 3 unnecessary parameters in your function - i , j , k . The values ​​passed to the main() function are not initialized; the values ​​passed to i and j in the function are irrelevant, because the code sets the variables on first use. The value of k , but the value passed to the function is undefined. This needs to be changed so that there are three more parameters, and they are only local variables in the function, and they should all 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 indices of the array).

You must lose two global variables; they never refer, because local variables in main() hide them, and function parameters hide them. Two #define values ​​are never used.

Although you pass l and c (rows and columns), you ignore them and think that the upper bounds are l = 8 and c = 8 . Also, the type you are trying to pass to fonc is not int **tab2 ; it is int tab2[][8] or int tab2[8][8] . The signature of a function can also become:

 void fonc(int tab2[8][8], int *vect); 

In your function, each assignment of the form vect[k]++; should be the purpose of the form vect[k++] = tab2[i][j]; .

The zigzag algorithm is inconvenient for code. For a matrix with a fixed size of 8x8, it is tempting to simply pack the sequence of indices into an array. I assume that the upper left corner of the zigzag diagram is (0, 0) and the lower right is (7, 7). If this is wrong, you just need 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 copy operation is simple:

 for (int i = 0; i < 64; i++) vect[i] = tab[zigzag[i].x][zigzag[i].y]; 

We can discuss the issue of writing 64 vs sizeof(zigzag)/sizeof(zigzag[0]) . If in fact you have little memory (the data at the moment is only 128 bytes, so I do not believe you), then you can pack two coordinates into one byte for storage:

 static const unsigned char zigzag[] = { 0x00, 0x10, 0x01, 0x02, ... }; 

and then use a more complex expression to sign:

 vect[i] = tab[zigzag[i] >> 4][zigzag[i] & 0xF]; 

This may be faster due to fewer memory accesses - you would have to measure.

All this assumes that you are dealing with square arrays with a fixed size of 8x8. If you need to deal with any size of the array and still do the job, then you probably have to code things to indicate the starting point, you take one step to the right, you go down along the diagonal until you reach the edge (left or left) bottom), you go one step down or right, you go up diagonally right until you reach the edge (top or right), you go one step right or down and repeat until you reach the end. It is inconvenient to code the code; The copy cycle will not consist of two lines.

Tool code from question

Here is the code from the question, somewhat cleared, but with the main algorithm in fonc() unchanged - at least unchanged when processing i , j and k , except for their initialization. The main function prints the matrix earlier, and then the vector after calling fonc() . Each assignment in fonc() to the vector was fixed and instrumental.

 #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; } 

Output Example:

  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 

Note that:

  • You get access to tab2[0][8] , which is beyond the scope.
  • Your algorithm encounters problems when your diagonal movements hit the bottom or right side of the matrix.
  • If you don't have support for C99 and VLA, handling the arrays of the NxM variable will be painful.

Desktop program

 #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; } 

Output Example:

 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 

Instrumental version of code by Anonymous

Anonymous provided an answer . This is very interesting in concept, but I'm not sure if that is for sure. Instrument it so that it prints its input, and the output is not final, so I put it in the same table as in the above code, which should give vector 1..64. Code and output:

 #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; } 

Output:

 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 

This result is not quite right, but I am sure that this is the right direction. (It’s equally clear that it’s too difficult to add a comment to an anonymous question - hence the addition here.)

Conceptually, the code turns a square matrix so that it stands at its points, and then scans horizontally forward and backward along the lines (8 + 8 - 1).

ASCII Art for 3x3 Scan:

  /\ /\/\ /\/\/\ \/\/\/ \/\/ \/ 

There are (3 + 3 - 1) = 5 scan lines. In table driven code, there is regularity for data that matches this.

Fix anonymous code

In the dezigzag() function, the dezigzag() string should invert the condition. Existing code is equivalent to:

 out[n++] = (diag % 2 == 1) ? in[diag - i][i] : in[i][diag - i]; 

The correct code is:

 out[n++] = (diag % 2 == 0) ? in[diag - i][i] : in[i][diag - i]; 

Output:

 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 

Code for processing MxN arrays

 #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[ij][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][ij] = 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[ij][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][ij]; } } } static void dump_matrix(const char *tag, int rows, int cols, int matrix[rows][cols]) { printf("%s (%dx %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 an iterator structure

The structure of the iterator is quite complicated. Using multiple single-line inline functions is extreme, but avoids duplicate expressions. I'm sure there is a place for cleaning, but it's 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 (%dx %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; } 
+14
source

So you do this 17 times fewer lines:

 #define N 8 int mat2d[N][N] = { /* stuff */ }; int vec1d[N * N]; memcpy(vec1d, mat2d, sizeof vec1d); 
+7
source

Iterates over the diagonals of a square, alternating directions each time.

Here is a complete working example (in c99).

 #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(int argc, char *argv[]) { int out[64] = {-1}; int in[8][8]; for (int i = 0; i < 64; i++) { in[i % 8][i / 8] = i; } dezigzag(out, in); for (int i = 0; i < 64; i++) { printf("%d: %d\n", i, out[i]); } return 0; } 
+1
source

Source: https://habr.com/ru/post/953824/


All Articles