Well... the good news is that the algorithm is not all that hard conceptually. The bad news is that it is rather long and involved.
The first thing you need to do is decide on a data format for your matrix... an NxM array works nicely. Then work out a few functions to do row manipulations. That is swap two rows, multiply a row by a constant, add 1 row to another, and add a multiple of one row to another row (this can also be used to make the "subtract a row" by using -1 as a multiplier). Note that that it is possible to make all of these function using only the "multiply by a constant" and "add two rows" though you may wish to make each funciton explicitly.
Once you have the functions then work on converting the logic of the GJ elimination.
so, to get your started. Lets look at a function for adding two rows of an N by M array:
CODE
#include <iostream>
using std::cout;
using std::endl;
typedef struct
{
int Rows;
int Cols;
int *Mat; //array to hold the matrix... Cell(col, row) = Mat[col+row*Cols]
} Matrix;
bool addRow(Matrix Mat, int row1, int row2);
void printMat(Matrix Max);
int main()
{
Matrix m;
m.Mat = new int(4*5); //rows * cols
m.Rows=4;
m.Cols=5;
//hard coded matrix...
// | 1 2 3 4 5|
// | 2 2 2 2 2|
// | 2 4 6 8 10|
// |-1 -2 -3 -4 -5|
m.Mat[0+0]=1; m.Mat[1+0]=2; m.Mat[2+0]=3; m.Mat[3+0]=4; m.Mat[4+0]=5;
m.Mat[0+5]=2; m.Mat[1+5]=2; m.Mat[2+5]=2; m.Mat[3+5]=2; m.Mat[4+5]=2;
m.Mat[0+10]=2; m.Mat[1+10]=4; m.Mat[2+10]=6; m.Mat[3+10]=8; m.Mat[4+10]=10;
m.Mat[0+15]=-1;m.Mat[1+15]=-2;m.Mat[2+15]=-3;m.Mat[3+15]=-4;m.Mat[4+15]=-5;
printMat(m);
addRow(m, 2, 3); //note that in the computer the rows are 0 to 3, to humans they would be 1 to 4.
cout << "Added row 4 to row 3\n";
printMat(m);
addRow(m, 0, 2);
cout << "Added row 3 to row 1\n";
printMat(m);
addRow(m, 3, 0);
cout << "Added row 1 to row 4\n";
printMat(m);
return 0;
}
//Row1 <-- Row1 + Row2
bool addRow(Matrix Mat, int row1, int row2)
{
//lets assume that the function fails, so our return value is flase.
bool retValue = false; //Value to be passed by return
//First lets make sure the user of this function is using it right...
if ((row1 < Mat.Rows && row1 >= 0) && (row2 < Mat.Rows && row2 >= 0))
{
//Ok the user knows what they are doing.
int i; // counter...
//The next two lines help simplify calculations inside the loop.
int row1Ptr = row1*Mat.Cols; //Offset to the begining of row1.
int row2Ptr = row2*Mat.Cols; //Offset to the begining of row2.
//We need to scroll though the
for (i=0; i<Mat.Cols; ++i)
{
//For each cell in row1, add in the corisponding cell in row2.
Mat.Mat[i+row1Ptr] += Mat.Mat[i + row2Ptr];
}
//That should do it...
retValue = true;
}
return retValue;
}
void printMat(Matrix Mat)
{
int i, j;
for (i=0; i<Mat.Rows; ++i)
{
for (j=0; j<Mat.Cols; ++j)
{
cout << Mat.Mat[j+i*Mat.Cols] << '\t';
}
cout << '\n';
}
cout << endl;
return;
}
Extending that to the other functions is not hard. I would note that this would be much better implemented in a class rather than with a struct. I only wanted to offer an example.
| 