P
I need to write a program in c++ to find the saddle point of a matrix, and the order of the matrix should be user defined.Plz can anyone help me?
Nah... i just need it to display whether the entered matrix has a saddle point or not and if yes display that number.sakumar79 said:
#include <iostream.h>
#include <alloc.h>
#include <stdlib.h>
#include <limits.h>
class SaddlePoint
{
private:
struct spstruct
{
int value;
int idx;
};
/*int *imatrix;*/
spstruct *mincol; //LUT of max of each cols.
spstruct *maxrow; //LUT of max of each rows.
int rccount; //Number of rows or cols in the LUTs.
char isLoaded;//Flag to check if the LUTs have been initialized.
int spcount; //Saddle point count.
public:
SaddlePoint()
{
isLoaded = 0;
spcount = -1;
}
~SaddlePoint ()
{
delete[] mincol;
delete[] maxrow;
}
char LoadMatrix (int *thematrix, int rows, int cols)
{
/*Do some preliminary checks*/
//Is it a valid row and col value?
if (rows > 0 && cols > 0)
{
//Is it a square matrix?
if (rows == cols)
{
//if (sizeof (thematrix) == rows * cols * sizeof(int))
//{
rccount = cols;
//}
//else
//{
// cout<< "Matrix size does not match size params!";
// return (-1);
//}
}
else
{
cout<<"Only square matrices (for now)";
return (-1);
}
}
isLoaded = 0;
maxrow = new spstruct[rccount];
mincol = new spstruct[rccount];
for (int i = 0; i < rccount; i++)
{
maxrow[i].value = INT_MIN;
mincol[i].value = INT_MAX;
}
/*TODO::Allocate space for a local copy of the input matrix
imatrix = (int *)malloc (rccount * 2 * sizeof (int));
int i = 0;
for i = 0 to
*/
/*Find the max from column and min from row
and fill teh LUT*/
int irow, icol;
for (irow = 0; irow < rccount; irow++)
{
for (icol = 0; icol < rccount; icol++)
{
if (thematrix[icol + (irow * rccount)] > maxrow[irow].value)
{
//Record the value and the col index of the value.
maxrow[irow].value = thematrix[(irow * rccount) + icol];
maxrow[irow].idx = icol;
}
if (thematrix[irow + (icol * rccount)] < mincol[irow].value)
{
//Record the value and record the row index of the value.
mincol[irow].value = thematrix[irow + (icol * rccount)];
mincol[irow].idx = irow;
}
}
}
/*//Print the LUT for debugging.
cout<< endl<< "This is the matrix and the LUTs:"<< endl;
for (irow = 0; irow < rccount; irow++)
{
cout<< "|";
for (icol = 0; icol < rccount; icol++)
{
cout<< thematrix [icol + (irow * (rccount))];
if (icol < rccount-1)
cout<< "\t";
}
cout<< "| |"<< maxrow[irow].value<< "|"<< endl;
}
cout<< endl<< "|";
for (icol = 0; icol < rccount; icol++)
{
cout<< mincol[icol].value;
if (icol < rccount-1)
cout<< "\t";
}
cout<< "|"<< endl;*/
isLoaded = 1;
return (1);
}
int SaddlePointPresent ()
{
if (isLoaded != 1)
{
/*Load a matrix first using the LoadMatrix() function.*/
spcount = -1;
return (-1);
}
/*See if there's a saddle point at all
and return the number of saddle points.*/
spcount = 0;
for (int i = 0; i < rccount; i++)
{
if (mincol[i].value == maxrow[i].value)
{
spcount++;
}
}
return (spcount);
}
int PrintSaddlePoints ()
{
if (SaddlePointPresent () == -1)
{
return (-1);
}
cout<< endl<< "Found "<< spcount<< " saddle points."<< endl;
if (spcount < 1)
{
return (0);
}
/*Now to extract them saddles*/
//int **spoints;
//spoints = malloc(spcount * sizeof (int) * 2);
for (int i = 0; i < rccount; i++)
{
if (mincol[i].value == maxrow[i].value)
{
cout<< mincol[i].value<< " at ("<< maxrow[i].idx<< ", "<<mincol [i].idx<< ")"<< endl;
}
}
return (spcount);
}
};//End of class
void main()
{
int *imatrix;
int rows = 0, cols = 0;
int irow, icol;
cout<< "\nHow many rows?->";
cin>> rows;
cout<< "How many cols?->";
cin>> cols;
imatrix = new int[rows * cols];
//if ( (imatrix = (int *)malloc (rows * cols * sizeof(int))) == NULL)
if (imatrix == NULL)
{
cout<< "Not enough memory to allocate buffer\n";
exit (1); /* terminate program if out of memory */
}
cout<< "\n:Now enter the elements of the matrix:"<< endl;
for (irow = 0; irow < rows; irow++)
{
for (icol = 0; icol < cols; icol++)
{
cout<< "("<< irow<< ", "<< icol<< ")-->";
cin>> imatrix [icol + (irow * (cols))];
}
}
cout<< endl<< "This is the matrix:"<< endl;
for (irow = 0; irow < rows; irow++)
{
cout<< "|";
for (icol = 0; icol < cols; icol++)
{
cout<< imatrix [icol + (irow * (cols))];
if (icol < cols-1)
cout<<"\t";
}
cout<< "|"<< endl;
}
SaddlePoint sp;
if (sp.LoadMatrix (imatrix, rows, cols) == -1)
{
cout<< "Unable to load the matrix.";
exit (1);
}
sp.PrintSaddlePoints();
delete[] imatrix;
system ("PAUSE");
}