Page 84, Exercise 2 : Modify fastTranspose() so it uses only 1 array.

This modification uses a slightly different array structure for a. Ra†her than using an 1-d array of a struct, it uses a 2-d array where column 0 contains the row value, column 1 contains the column value and column 2 contains the contains of the cell. Using the example array in the book we have :

Modified array structure 
Matrix a contains: 
     [0] [1]  [2]
[0]   6    6    8
[1]   0    0   15
[2]   0    3   22
[3]   0    5  -15
[4]   1    1   11
[5]   1    2    3
[6]   2    3   -6
[7]   4    0   91
[8]   5    2   28

The function creates a new 2-d array, row_starting, in which the original row_terms array entries occupy column 0 and the starting_pos entries occupy column 1.The new matrix, using the example in the book is:

row_starting matrix 
row_starting contains: 
     [0]         [1]  
     row_terms   starting_pos
[0]   1            1   
[1]   2            2   
[2]   2            4   
[3]   2            6  
[4]   0            8   
[5]   1            8

The new function defintion appears below. The function call is unchanged.

 

void fast_transpose(int a[][3], int b[][3])

{/* the transpose of a is placed in b and is found in O(n+t) time,

     where n is the number of columns and t is the numbers of terms */



  int row_starting[MAX_COL][2];

  int i,j,  num_cols = a[0][1],  num_terms = a[0][2];



  b[0][0] = num_cols;  b[0][1] = a[0][0];

  b[0][2] = num_terms;



  if (num_terms > 0)  {  /* nonzero matrix */

    for (i = 0; i <= num_cols; i++)

      row_starting[i][0] = 0;

    for (i = 1; i <= num_terms; i++)

      row_starting[a[i][1]][0]++;



    row_starting[0][1] = 1;

    for (i = 1; i <= num_cols; i++)

      row_starting[i][1] = row_starting[i-1][1] + row_starting[i-1][0];



    for (i = 1; i <= num_terms; i++) {

      j = row_starting[a[i][1]][1];

      b[j][0] = a[i][1];   b[j][1] = a[i][0];

      b[j][2] = a[i][2];

      row_starting[a[i][1]][1]= j+1;

    }

  }

}