What is causing heap corruption and extraneous values in my code?

Question

I'm writing code for a project in my class, and it is producing incredibly unusual results. Row and column values end up with random numbers in the millions and it eventually throws exceptions and I can't understand why.

#include <iostream>
using namespace std;

class SparseRow {
protected:
    int row;
    int col;
    int value;
public:
    SparseRow();
    SparseRow(int inRow, int inCol, int inVal);
    SparseRow(const SparseRow& newRow);
    SparseRow& operator=(const SparseRow& newRow);
    ~SparseRow();
    void display();
    int getRow();
    int getCol();
    int getValue();
    void setRow(int inRow);
    void setCol(int inCol);
    void setValue(int inVal);
};

class SparseMatrix {
protected:
    int noRows;
    int noCols;
    int commonValue;
    int noSparseValues;
    SparseRow *myMatrix;
    void setNoSparseValues(int noSV);
public:
    SparseMatrix();
    SparseMatrix(int rows, int cols, int cv, int noSV);
    SparseMatrix(const SparseMatrix& matrix);
    SparseMatrix& operator=(const SparseMatrix& matrix);
    ~SparseMatrix();
    void readMatrix();
    SparseMatrix* transpose();
    SparseMatrix* multiply(SparseMatrix& M);
    SparseMatrix* add(SparseMatrix& M);
    void display();
    void displayMatrix();
    int getNoRows();
    int getNoCols();
    int getCommonValue();
    int getNoSparseValues();
    int getValue(int row, int col);
    void setValue(int row, int col, int val);
};

SparseRow::SparseRow() {
    row = -1;
    col = -1;
    value = 0;
}

SparseRow::SparseRow(int inRow, int inCol, int inVal) {
    row = inRow;
    col = inCol;
    value = inVal;
}

SparseRow::SparseRow(const SparseRow& newRow) {
    row = newRow.row;
    col = newRow.col;
    value = newRow.value;
}

SparseRow& SparseRow::operator=(const SparseRow& newRow) {
    if (this != &newRow) {
        row = newRow.row;
        col = newRow.col;
        value = newRow.value;
    }
    return *this;
}

SparseRow::~SparseRow() {
    cout << "Deleting SparseRow with values: " << endl;
    display();
}

void SparseRow::display() {
    cout << "Row: " << row << ", Column: " << col << ", Value: " << value << endl;

}

int SparseRow::getRow() {
    return row;
}

int SparseRow::getCol() {
    return col;
}

int SparseRow::getValue() {
    return value;
}

void SparseRow::setRow(int inRow) {
    row = inRow;
}

void SparseRow::setCol(int inCol) {
    col = inCol;
}

void SparseRow::setValue(int inVal) {
    value = inVal;
}

SparseMatrix::SparseMatrix() {
    noRows = 0;
    noCols = 0;
    commonValue = 0;
    noSparseValues = 0;
}

SparseMatrix::SparseMatrix(int rows, int cols, int cv, int noSV) {
    noRows = rows;
    noCols = cols;
    commonValue = cv;
    noSparseValues = noSV;
    myMatrix = new SparseRow[rows * cols];
}

SparseMatrix::SparseMatrix(const SparseMatrix& matrix) {
    noRows = matrix.noRows;
    noCols = matrix.noCols;
    commonValue = matrix.commonValue;
    noSparseValues = matrix.noSparseValues;
    myMatrix = matrix.myMatrix;
}

SparseMatrix& SparseMatrix::operator=(const SparseMatrix& matrix) {
    if (this != &matrix) {
        delete[] myMatrix;

        noRows = matrix.noRows;
        noCols = matrix.noCols;
        commonValue = matrix.commonValue;
        noSparseValues = matrix.noSparseValues;
        myMatrix = matrix.myMatrix;
    }
    return *this;
}

SparseMatrix::~SparseMatrix() {
    cout << "Deleting SparseMatrix with values: " << endl;
    display();

    delete[] myMatrix;
}

void SparseMatrix::readMatrix() {
    int count = 0;
    int val;

    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            cin >> val;
            if (val != commonValue) {
                myMatrix[count].setRow(i);
                myMatrix[count].setCol(j);
                myMatrix[count].setValue(val);
                // Why does C++ prevent me from calling a constructor on objects in an array? It doesn't make sense.
                count++;
            }
        }
    }

    if (count != noSparseValues) {
        cout << "ERROR: Incorrect number of sparse values! Changing to correct number." << endl;
        noSparseValues = count;
    }
}

SparseMatrix* SparseMatrix::transpose() {
    SparseMatrix *newMatrix = new SparseMatrix(noCols, noRows, commonValue, noSparseValues);

    for (int i = 0; i < noSparseValues; i++) {
        newMatrix->setValue(myMatrix[i].getCol(), myMatrix[i].getRow(), myMatrix[i].getValue());
    }

    return newMatrix;
}

SparseMatrix* SparseMatrix::multiply(SparseMatrix& M) {
    if (noCols != M.getNoRows()) {
        cout << "ERROR: Matrices cannot be multiplied!" << endl;
        return NULL;
    }

    SparseMatrix *newMatrix = new SparseMatrix(noRows, M.getNoCols(), commonValue, noRows * M.getNoCols());
    // Why does C++ prevent me from creating an array to store this information? It doesn't make sense.

    int SVCount = 0;
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < M.getNoCols(); j++) {
            int sum = 0;
            for (int k = 0; k < noCols; k++) {
                sum += getValue(i, k) * M.getValue(k, j);
            }
            if (sum != newMatrix->getCommonValue()) {
                SVCount++;
            }
            newMatrix->setValue(i, j, sum);
        }
    }
    newMatrix->setNoSparseValues(SVCount);

    return newMatrix;
}

SparseMatrix* SparseMatrix::add(SparseMatrix& M) {
    if (noRows != M.getNoRows() || noCols != M.getNoCols()) {
        cout << "ERROR: Matrices cannot be added!" << endl;
        return NULL;
    }

    SparseMatrix *newMatrix = new SparseMatrix(noRows, noCols, commonValue + M.getCommonValue(), noRows * noCols);

    int SVCount = 0;
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            int sum = getValue(i, j) + M.getValue(i, j);
            if (sum != newMatrix->getCommonValue()) {
                SVCount++;
            }
            newMatrix->setValue(i, j, sum);
        }
    }

    newMatrix->setNoSparseValues(SVCount);

    return newMatrix;
}

void SparseMatrix::display() {
    for (int i = 0; i < noSparseValues; i++) {
        myMatrix[i].display();
    }
}

void SparseMatrix::displayMatrix() {
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            cout << getValue(i, j) << " ";
        }
        cout << endl;
    }
}

int SparseMatrix::getNoRows() {
    return noRows;
}

int SparseMatrix::getNoCols() {
    return noCols;
}

int SparseMatrix::getCommonValue() {
    return commonValue;
}

int SparseMatrix::getNoSparseValues() {
    return noSparseValues;
}

void SparseMatrix::setNoSparseValues(int noSV) {
    noSparseValues = noSV;
}

int SparseMatrix::getValue(int row, int col) {
    for (int i = 0; i < noSparseValues; i++) {
        if (myMatrix[i].getRow() == row && myMatrix[i].getCol() == col) {
            return myMatrix[i].getValue();
        }
    }
    return commonValue;
}

void SparseMatrix::setValue(int row, int col, int val) {
    bool replacingSparse = (getValue(row, col) != commonValue);
    bool replacingWithSparse = (val != commonValue);

    int index = -1;

    if (replacingSparse) {
        for (int i = 0; i < noSparseValues; i++) {
            if (myMatrix[i].getRow() == row && myMatrix[i].getCol() == col) {
                index = i;
                break;
            }
        }
        if (replacingWithSparse) {
            myMatrix[index].setValue(val);
        }
        else {
            for (int i = index; i < noSparseValues; i++) {
                myMatrix[i] = myMatrix[i + 1];
            }
            noSparseValues--;
        }
    }
    else {
        if (replacingWithSparse) {
            for (int i = 0; i < noSparseValues; i++) {
                if (myMatrix[i].getRow() > row || (myMatrix[i].getRow() >= row && myMatrix[i].getCol() > col)) {
                    index = i;
                    break;
                }
            }
            for (int i = noSparseValues; i > index; i--) {
                myMatrix[i] = myMatrix[i - 1];
            }
            myMatrix[index].setRow(row);
            myMatrix[index].setCol(col);
            myMatrix[index].setValue(val);
            noSparseValues++;
        }
    }
}

int main() {
    int n, m, cv, noNSV;
    SparseMatrix* temp;

    cin >> n >> m >> cv >> noNSV;
    SparseMatrix* firstOne = new SparseMatrix(n, m, cv, noNSV);
    firstOne->readMatrix();

    cin >> n >> m >> cv >> noNSV;
    SparseMatrix* secondOne = new SparseMatrix(n, m, cv, noNSV);
    secondOne->readMatrix();

    cout << "First one in sparse matrix format" << endl;
    firstOne->display();

    cout << "First one in normal matrix format" << endl;
    firstOne->displayMatrix();

    cout << "Second one in sparse matrix format" << endl;
    secondOne->display();

    cout << "Second one in normal matrix format" << endl;
    secondOne->displayMatrix();

    cout << "After Transpose first one in normal format" << endl;
    temp = firstOne->transpose();
    temp->displayMatrix();

    cout << "After Transpose second one in normal format" << endl;
    temp = secondOne->transpose();
    temp->displayMatrix();

    cout << "Multiplication of matrices in sparse matrix form:" << endl;
    temp = secondOne->multiply(*firstOne);
    temp->display();

    cout << "Addition of matrices in sparse matrix form:" << endl;
    temp = secondOne->add(*firstOne);
    temp->display();
}

Input:

3 3 0 3
2 2 2
0 0 0
0 0 0

3 3 0 3
2 2 2
0 0 0
0 0 0

Expected output: (not formatted exactly the same, but the numbers should be identical)

First one in sparse matrix format
0, 0, 2
0, 1, 2
0, 2, 2
First one in normal matrix format
2     2     2
0     0     0
0     0     0
Second one in sparse matrix format
0, 0, 2
0, 1, 2
0, 2, 2
Second one in normal matrix format
2     2     2
0     0     0
0     0     0
After Transpose first one
2     0     0
2     0     0
2     0     0
After Transpose second one
2     0     0
2     0     0
2     0     0
Multiplication of matrices in sparse matrix form:
0, 0, 4
0, 1, 4
0, 2, 4
Addition of matrices in sparse matrix form:
0, 0, 4
0, 1, 4
0, 2, 4

Actual output:

First one in sparse matrix format
Row: 0, Column: 0, Value: 2
Row: 0, Column: 1, Value: 2
Row: 0, Column: 2, Value: 2
First one in normal matrix format
2 2 2
0 0 0
0 0 0
Second one in sparse matrix format
Row: 0, Column: 0, Value: 2
Row: 0, Column: 1, Value: 2
Row: 0, Column: 2, Value: 2
Second one in normal matrix format
2 2 2
0 0 0
0 0 0
After Transpose first one in normal format
0 0 0
2 0 0
2 0 0
After Transpose second one in normal format
0 0 0
2 0 0
2 0 0
Multiplication of matrices in sparse matrix form:
Row: 0, Column: 1, Value: 4
Row: 0, Column: 2, Value: 4
Row: 369, Column: -33686019, Value: 9
Addition of matrices in sparse matrix form:
(Exceptions thrown here, line 222 in code)

Exceptions thrown:

Project1.exe has triggered a breakpoint.

Unhandled exception at 0x777E8499 (ntdll.dll) in Project1.exe: 0xC0000374: A heap has been corrupted (parameters: 0x77825890).

Answer 1

I'll address only some of the issues in the posted code.

pointers

Their explict use is always prone to error and it's increasingly discouraged at every new version of the standard. In OP's code they own the responsability of managing memory resources, but in C++ they don't automatically call the destructor of an object when it goes out of scope. That's what a smart pointer like std::unique_ptr can do.

Let's see what happens in main:

int n, m, cv, noNSV;
SparseMatrix* temp;  // <- Declaration far from initialization

cin >> n >> m >> cv >> noNSV;
SparseMatrix* firstOne = new SparseMatrix(n, m, cv, noNSV);
//          ^^^^^^^^^^^^^^^^ Why?    
// ...
temp = firstOne->transpose();  // <- Here the pointer is initialized
// ...
temp = secondOne->transpose(); // <- Here the pointer is overwritten, but the allocated memory
                               //    isn't released, it leaks.
// ...
temp = secondOne->multiply(*firstOne); // <- Again...
// ...
temp = secondOne->add(*firstOne);  // <- ...and again
// ...
// No 'delete' calls at the end, so no destructor is called for the previously allocated objects 

The only reason to use pointers here, is that SparseMatrix::transpose() is designed to return one, but it could easily retrun a SparseMatrix instead (Return Value Optimization would avoid unnecessary copies).

To every call of new should correspond a delete and since functions like transpose return a pointer to a newly allocated objects, delete temp; should be called before overwriting temp, to make sure that the proper destructor is called.

In C++, though, we should take advantage of RAII (Resource Acquisition Is Initialization, also named Scope-Bound Resource Management):

{   // <- Start of a scope
    int n, m, cv, noNSV;

    std::cin >> n >> m >> cv >> noNSV;
    // Declare a variable using the constructor. Its lifetime begins here.     
    SparseMatrix firstOne(n, m, cv, noNSV);
    // The same for 'secondOne'
    // ...
    // SparseSparse::transpose() here should return a SparseMatrix, not a pointer
    SparseMatrix temp = firstOne.transpose(); 

    // ...
    // Here the matrix is reassigned (which can be cheap if move semantic is implemented) 
    temp = secondOne.transpose();
    // ...
    temp = secondOne.multiply(firstOne); // <- Again...
    // ...
 }  // <- End of scope, all the destructors are called. No leaks. 

special member functions

That's actually related to previous point, looking at how e.g. the copy assignment operator is implemented in the posted snippet:

 SparseMatrix& SparseMatrix::operator=(const SparseMatrix& matrix) {
     if (this != &matrix) {     // <- debatable, see copy-and-swap idiom
         delete[] myMatrix;     // <- putted here makes this function not exception safe ^^

         noRows = matrix.noRows;
         noCols = matrix.noCols;
         commonValue = matrix.commonValue;
         noSparseValues = matrix.noSparseValues;
         myMatrix = matrix.myMatrix; // <- The pointer is overwritten, but this is shallow copy
                                     //    what you need is a deep copy of the array
     }
     return *this;
 }

A proper implementation of this and the other special functions would take advantage of the copy-and-swap idiom, which is masterfully described here:

What is the copy-and-swap idiom?

Also, regarding this comment in OP's reading function:

for (int i = 0; i < noRows; i++) {
    for (int j = 0; j < noCols; j++) {
        cin >> val;
        if (val != commonValue) {
            myMatrix[count].setRow(i);
            myMatrix[count].setCol(j);
            myMatrix[count].setValue(val);
            // Why does C++ prevent me from calling a constructor on objects in an array? It doesn't make sense.
            count++;
        }
    }
}

The asker could use the placement parameter of new (placement new), there:

for (int i = 0; i < noRows; i++) {
    for (int j = 0; j < noCols; j++) {
        cin >> val;
        if (val != commonValue) {

            new (myMatrix + count) SparseRow(i, j, val);

            count++;
        }
    }
}

Many other issues are left to the OP to solve.