How can I calculate (A + B) * (A + B) ? A, B are matrices_问答_开发者

I have 2 exercises, one uses struct and the other uses class, use +, * overloadings to calculate with matrices.

My Matrix type:

struct matrix 
{
   int** a;
   int m;
   int n;
};

Which "m", "n" are the number of rows and columns, "a" is a pointer-to-pointer that will be dynamic memory allocated in run-time.

And Operators overloaded are: +, *, +=, *=

I have no problem with 2 matrices, in both addition and multiplication. But I get in trouble when I need to display the value of (A + B) * (A + B) expression. Note that A + (A * B) is ok.

I try to display the whole of expression, it seems to be overflow. Then I declare a matrix type C, assign C = A + B, C is correct. But if I display C * C, the result remains the same, very bad, although A * A is nice.

Can someone explain my problem? How can I fix it?

I test with two 4x4 matrices, their elements are numbered from 1 to 16.

My code:

#include <iostream>
using namespace std;
struct matrix
{
    int** a;
    int m;
    int n;
};
matrix temp;

matrix InputMatrix(matrix &mat)
{
    for (int i=0; i <= mat.m-1; i++)
    {
        for (int j=0; j <= mat.n-1; j++)
        {
            cout.width(5);
            cout << "[" << i+1 << "," << j+1 << "] = ";

            *(*(mat.a + i) + j) = i*mat.m + j + 1;
            cout << *(*(mat.a + i) + j);

            /*int x = rand()%20; // random matrix
            cout << x;
            *(*(mat.a + i) + j) = x;*/
        }
        cout << endl;
    }
    return mat;
}

int AllocMatrix(matrix &mat)
{
    mat.a = new int*[mat.m];
    if (mat.a == NULL)
    {
        return 0;
    }
    for (int i=0; i <= mat.m-1; i++)
    {
        *(mat.a + i) = new int[mat.n];
        if (*(mat.a + i) == NULL)
        {
            return 0;
        }
    }
    return 1;
}
int FreeMatrix(matrix &mat)
{
    if (mat.a != NULL)
    {
        delete [] mat.a;
    }
    return 0;
}

int DispMatrix(const matrix &mat)
{
    for (int i=0; i <= mat.m-1; i++)
    {
        for (int j=0; j<= mat.n-1; j++)
        {
            cout.width(7);
            cout << *(*(mat.a + i) + j);
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

matrix & operator +(const matrix &mat1, const matrix &mat2)
{
    for (int i=0; i <= temp.m-1; i++)
    {
        for (int j=0; j <= temp.n-1; j++)
        {
            *(*(temp.a + i) + j) = *(*(mat1.a + i) + j) + *(*(mat2.a + i) + j);
        }
    }
    return temp;
}

matrix & operator +(const matrix &mat1, const int k)
{
    for (int i=0; i <= temp.m-1; i++)
    {
        for (int j=0; j <= temp.n-1; j++)
        {
            *(*(temp.a + i) + j) = *(*(mat1.a + i) + j) + k;
        }
    }
    return temp;
}

matrix & operator +=(matrix &mat1, const matrix &mat2)
{
    for (int i=0; i <= mat1.m-1; i++)
    {
        for (int j=0; j <= mat1.n-1; j++)
        {
            *(*(temp.a + i) + j) = *(*(mat1.a + i) + j) + *(*(mat2.a + i) + j);
        }
    }
    for (int i=0; i <= temp.m-1; i++)
    {
        for (int j=0; j <= temp.n-1; j++)
        {
            *(*(mat1.a + i) + j) = *(*(temp.a + i) + j);
        }
    }
    return mat1;
}

matrix &  operator *(const matrix &mat1, const matrix &mat2)
{
    for (int i=0; i <= mat1.m-1; i++)
    {
        for (int j=0; j <= mat2.n-1; j++)
        {
            int tong = 0;
            for (int k=0; k <= mat2.m-1; k++)
            {
                tong += (*(*(mat1.a + i) + k)) * (*(*(mat2.a + k) + j开发者_如何学C));
            }
            *(*(temp.a + i) + j) = tong;
        }
    }
    return temp;
}
matrix &  operator *(const matrix &mat1, const int k)
{
    for (int i=0; i <= temp.m-1; i++)
    {
        for (int j=0; j <= temp.n-1; j++)
        {
            *(*(temp.a + i) + j) = *(*(mat1.a + i) + j) * k;
        }
    }
    return temp;
}

matrix &  operator *=(matrix &mat1, const matrix &mat2)
{
    for (int i=0; i <= mat1.m-1; i++)
    {
        for (int j=0; j <= mat2.n-1; j++)
        {
            int tong = 0;
            for (int k=0; k <= mat2.m-1; k++)
            {
                tong += (*(*(mat1.a + i) + k)) * (*(*(mat2.a + k) + j));
            }
            *(*(temp.a + i) + j) = tong;
        }
    }
    for (int i=0; i <= temp.m-1; i++)
    {
        for (int j=0; j <= temp.n-1; j++)
        {
            *(*(mat1.a + i) + j) = *(*(temp.a + i) + j);
        }
    }
    return mat1;
}

int main()
{
    matrix mat1, mat2, mat3;
    int m1 = 0, n1 = 0, m2 = 0, n2 = 0;

    m1 = m2 = n1 = n2 = 4;

    mat1.m = m1;
    mat1.n = n1;

    mat2.m = m2;
    mat2.n = n2;

    mat3.m = m1;
    mat3.n = n1;
    AllocMatrix(mat3);

    if (!AllocMatrix(mat1))
    {
        cout << "Out of memory!" << endl;
        FreeMatrix(mat1);
        return 1;
    }
    if (!AllocMatrix(mat2))
    {
        cout << "Out of memory!" << endl;
        FreeMatrix(mat1);
        FreeMatrix(mat2);
        return 1;
    }
    cout << "Matrix - 1:" << endl;
    mat1 = InputMatrix(mat1);
    cout << "Matrix - 2:" << endl;
    mat2 = InputMatrix(mat2);

    if ((mat1.m == mat2.m)&&(mat1.n == mat2.n))
    {
        temp.m = mat1.m;
        temp.n = mat1.n;
        if (!AllocMatrix(temp))
        {
            cout << "Out of memory!" << endl;
            FreeMatrix(mat1);
            FreeMatrix(mat2);
            FreeMatrix(temp);
            return 1;
        }
        cout << "Ressult: " << endl;
        mat3 = mat1 + mat2;
        DispMatrix(mat3);
        DispMatrix(mat3 * mat3);
        FreeMatrix(temp);
    }

    FreeMatrix(mat1);
    FreeMatrix(mat2);
    system("pause");
    return 0;
}

Result:

Matrix - 1:
    [1,1] = 1    [1,2] = 2    [1,3] = 3    [1,4] = 4
    [2,1] = 5    [2,2] = 6    [2,3] = 7    [2,4] = 8
    [3,1] = 9    [3,2] = 10    [3,3] = 11    [3,4] = 12
    [4,1] = 13    [4,2] = 14    [4,3] = 15    [4,4] = 16
Matrix - 2:
    [1,1] = 1    [1,2] = 2    [1,3] = 3    [1,4] = 4
    [2,1] = 5    [2,2] = 6    [2,3] = 7    [2,4] = 8
    [3,1] = 9    [3,2] = 10    [3,3] = 11    [3,4] = 12
    [4,1] = 13    [4,2] = 14    [4,3] = 15    [4,4] = 16
Ressult:
      2      4      6      8
     10     12     14     16
     18     20     22     24
     26     28     30     32

    360   1832  28180 708768
   43888039688236210260317821152
  95260335311192-6444114522130541536
2990856-14161730721164069912-1507182592

Some comments:

1: Use member methods rather than functions
2: Don't use using namespace std.
3: If an array has m members it is more traditional to use < in the for loops.

for (int i=0; i <= mat.m-1; i++)

// More traditional to use:

for (int i=0; i < mat.m; ++i)

4: Use longer variables names than i. Try searching the code for all the instance of the variable 'i'. You will get a lot of false positive hits. Something like loopM would be easier to read.

5: Use the [] operator

*(*(mat.a + i) + j) = BLA;

// Cab be written as:

mat.a[i][j] = BLA;

6: Under normal situations new will never return NULL. So do not write code that checks for it. If it fails an exception will be thrown. This allows you to remove error detection code from normal code flow and handle the errors in exceptions.

mat.a = new int*[mat.m];
// This is a waste of time. Here mat.a will NEVER be NULL
if (mat.a == NULL)
{
    return 0;
}

7: It is OK to delete NULL objects. So don' test for NULL before a delete.

if (mat.a != NULL)
{
    delete [] mat.a;
}

// If it is NULL nothing bad will happen.

delete [] mat.a

8: You forgot to delete all the members.
Note: I would be more confident this is correct if you had used constructor/destructor as the compiler will guarantee that destructor is not called if the constructor throws an exception. On the other hand your use of functions does not guarantee this and you may catch an exception and still execute the FreeMatrix() on an invalid matrix object. But since your current code has no exception handling I feel safe it will work.

 for(int loop = 0;loop < m;++loop)
 { 
     delete [] mat.a[loop];
 }
 delete [] mat.a;

9: Your operator + seems to use some random temp variable?
Prefer to declare temp inside the function and return a copy. But for this to work you will need correct copy constructor and assignment operator (see below).

matrix operator +(const matrix &mat1, const matrix &mat2) 
{
    matrix temp;  // add mat1 and mat2 into temp
}
return temp;

10: In your += function. You sum the values into a temp variable then re-assign back to the mat1. There is no reason not to do this in place.

11: Only declare one variable per line.

matrix mat1, mat2, mat3;

// All coding standards say use:

matrix     mat1;
matrix     mat2;
matrix     mat3;

The reason is it catches a couple of problems associated with pointers. In my opinion it also makes the code easier to read (which is also a plus). All compaies will inisit on it so just get used to it.

12: Your matrix allocation will never fail (as pointed out previously). It will throw an expcetion. So the fillowing will never print "Out of memory". Also I would note you are returning an integer where a bool would have been a better type to indicate failure (if you could have indicated failure).

if (!AllocMatrix(mat1))
{
    //
    // This will never be executed. EVER.
    //
    cout << "Out of memory!" << endl;
    FreeMatrix(mat1);
    return 1;
}

13: Here we have a potential problem. Your code is executing operator + as you expect. But it is also executing matrix::operator=. You did not define this but the compiler automatically generated the code for this method. And it is not doing what you think. Luckily you do not free mat3 thus it is not blowing up.

    mat3 = mat1 + mat2;

Any code where where a class (or struct) contains pointers that are owned by (you allocate then pointers and delete them), needs to obey the rule of 3 (plus have a correct constructor).

struct matrix 
{
   int** a;
   int m;
   int n;
};

The reason is that if you do not actually specifically disable them the compiler will generate 4 methods for you. If you start manually allocating/deleting the memory two of these methods (copy construct and assignment operator) will do stuff that makes your deallocation hard to do correctly. As a result you should either disable them or explicitly define all 4 compiler generated methods.

In your case the compiler is generates the following 4 methods:

matrix::matrix() { /* Do nothing or value initialize */ }
matrix::~matrxc(){ /* Do nothing */ }
matrix::matrix(matrix const& rhs)
    : a(rhs.a)
    , m(rhs.m)
    , n(rhs.n)
{}
matrix& matrix::operator+(matrix const& rhs)
{
    a = rhs.a;
    m = rhs.m;
    n = rhs.n;
    return *this;
}

Now consider what the following code will do:

matrix  m1;
m1.m = 5;
m1.n = 5;
AllocMatrix(m1));

matrix  m2;
m2.m = 5;
m2.n = 5;
AllocMatrix(m2));

m2 = m1;  /* Simplified version of m3 = m1 + m2; */
          // The problem is that the a member is being copied from m1 to m2.
          // But the copy is a shallow copy. So now both m1 and m2 point at the same
          // piece of memory.

FreeMatrix(m2);  // Frees m2.a
FreeMatrix(m1);  // Whops. This Frees m1.a but it points at the same memory as m2.a
                 //        So now you have a double delete.

14: Separation of concerns.

This is an important technique to learn. It means a class should do one thing. Either it should contain the logic to perform some business logic or it should contain memory management (or other management stuff). It should not do both.

This means your matrix object should concentrate on the logic of doing matrix operations and delegate the memory management to another object type that is specifically designed for memory management. I will leave it at that as Charles Bailey covers that in detail in his answer.

This definition matrix temp; at namespace scope is a huge alarm bell. You absolutely shouldn't need to use this as a part of your overloaded operators.

Your operator+ and operator* overloads shouldn't return a reference, they should return a matrix by value. This would eliminate the problem where temp is being invisibly re-used in multiple slots in complex expressions. This is causing your unexpected values in the observed results.

To get this to work you need to ensure that your matrix class is copyable and assignable. You either need to use higher level containers such as std::vector to remove all of the manual memory management or you need to give your class a used-defined copy constructor, copy assignment operator and destructor.

Your manual memory management is currently incorrect. FreeMatrix deletes the mat.a member but it does not free any of the allocated arrays that the elements of mat.a pointed to. Also, checking whether a new expression resulted in NULL is futile. new will either succeed or throw an exception.

For me, I think that the simplest approach would be to give your matrix a constructor and implement it using std::vector.

E.g.:

struct matrix
{
    matrix( int m, int n )
        : a( std::vector< std::vector<int> >( m, std::vector<int>( n, 0 ) );
    {
    }

    std::vector< std::vector<int> > a;
};

This way your matrix will be copyable and assignable and you can do away with AllocMatrix and FreeMatrix and return matrix by value where appropriate.

You will, of course, need to change expressions such as *(*(temp.a + i) + j) to the equivalent, but much more readable, temp.a[i][j] before switching to vector.

A*A works but C*C does not? Maybe the problem is not in your code but in the choice of matrices: is the number of columns in the first matrix equal to the number of rows in the second matrix? It has to be for matrix multiplication! (In the case of A*A and C*C that would mean those matrices have to be square unless you use implicit transposition.)

If this is not the solution, please post