Transposing a matrix in C++

Question

I'm writing a program to transpose a given matrix using allocated memory. The function works perfect with square matrix NxN (rows==cols) but it crashes with MxN matrix (rows != cols). Please help

void transpose(int **matrix, int *row, int *col)
{
    // dynamically allocate an array
    int **result;
    result = new int *[*col]; //creates a new array of pointers to int objects
    // check for error
    if (result == NULL)
    {
        cout << "Error allocating array";
        exit(1);
    }
    for (int count = 0; count < *col; count++)
    {
        *(result + count) = new int[*row];
    }

    // transposing
    for (int i = 0; i<*row; i++)
    {
       for (int j = i+1; j<*col; j++)
       {
        int temp = *(*(matrix + i) + j);
        *(*(matrix + i) + j) = *(*(matrix + j) + i);
        *(*(matrix + j) + i) = temp;
       }
    }

    for (int i = 0; i<*row; i++)
    {
       for (int j = 0; j<*col; j++)
       {
          *(*(result + i) + j) = *(*(matrix + i) + j);
          cout << *(*(result + i) + j) << "\t";
       }
       cout << endl;
    }
}

Solution 1

The lines:

for (int i = 0; i<*row; i++)
{
   for (int j = i+1; j<*col; j++)
   {
    int temp = *(*(matrix + i) + j);
    *(*(matrix + i) + j) = *(*(matrix + j) + i);
    *(*(matrix + j) + i) = temp;
   }
}

are the issue. The problem is that matrix is indexed by i then j, not j then i like you are doing in the second and third line in the while loop. Image that matrix is a 2x3 matrix, then you try to perform matrix[2][3] = matrix[3][2], but matrix[3][2] does not exist.

It is best to go about simply initializing result directly in this loop:

for (int i = 0; i<*row; i++)
   for (int j = 0; j<*col; j++)
     result[j][i] = matrix[i][j];

Then you can output like below, or delete matrix and reassign matrix to be result as you wish. My entire transpose function became the following code (row and col need not be pointers to int pass by value is just fine. Also accessing matrices should use array subscripts as it is nicer style):

void transpose(int **matrix, int row, int col)
{
  // dynamically allocate an array
  int **result;
  result = new int *[col]; //creates a new array of pointers to int objects
  for (int i = 0; i < col; i++)
    result[i] = new int[row];

  // transposing
  for (int i = 0; i<row; i++)
   for (int j = 0; j<col; j++)
     result[j][i] = matrix[i][j];

  //output resulting matrix
  for (int i = 0; i<col; i++) {
   for (int j = 0; j<row; j++)
    cout << result[i][j] << "\t";
   cout << endl;
  }
}

Solution 2

You are trying to transpose matrix "in place" :

((matrix + i) + j) = ((matrix + j) + i);

you shouldn't do this. If count of columns is greater then count of rows, allocated for matrix, you'll read and write non-allocated memory.

IMHO, It would be better to store whole matrix in continuous memory. Not in different pieces. In this manner the code would look like this:

void transpose( int *matrix, int row, int col )
{
    for ( int i = 0; i < row; i++ )
    {
       for ( int j = i + 1; j < col; j++ )
       {
           int temp = matrix[ i * col + j ];
           matrix[ i * col + j ] = matrix[ j * col + i ];
           matrix[ j * col + i ] = temp;
       }
    }
}

The only minus of this allocation, that you can't address an element like matrix[ i ][ j ] but only matrix[ i + col + j ]. Pluses are: 1) easy to allocate/deallocate memory (just matrix = new int[ col * row ] and delete [] matrix) 2) a little bit faster access to elements (because of continuous location of them)

At the end, I think, that it would be the best way to look at std::vector. If you want, I can show you, how will you function look with vector