ACMテンプレート--隣接マトリクス有向図
3861 ワード
/**
* C++:
*
* @author judyge
* @date 2014/04/19
*/
#include
#include
#include
using namespace std;
#define MAX 100
class MatrixDG {
private:
char mVexs[MAX]; //
int mVexNum; //
int mEdgNum; //
int mMatrix[MAX][MAX]; //
public:
// ( )
MatrixDG();
// ( )
MatrixDG(char vexs[], int vlen, char edges[][2], int elen);
~MatrixDG();
//
void print();
private:
//
char readChar();
// ch mMatrix
int getPosition(char ch);
};
/*
* ( )
*/
MatrixDG::MatrixDG()
{
char c1, c2;
int i, p1, p2;
// " " " "
cout << "input vertex number: ";
cin >> mVexNum;
cout << "input edge number: ";
cin >> mEdgNum;
if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
{
cout << "input error: invalid parameters!" << endl;
return ;
}
// " "
for (i = 0; i < mVexNum; i++)
{
cout << "vertex(" << i << "): ";
mVexs[i] = readChar();
}
// " "
for (i = 0; i < mEdgNum; i++)
{
//
cout << "edge(" << i << "): ";
c1 = readChar();
c2 = readChar();
p1 = getPosition(c1);
p2 = getPosition(c2);
if (p1==-1 || p2==-1)
{
cout << "input error: invalid edge!" << endl;
return ;
}
mMatrix[p1][p2] = 1;
}
}
/*
* ( )
*
* :
* vexs --
* vlen --
* edges --
* elen --
*/
MatrixDG::MatrixDG(char vexs[], int vlen, char edges[][2], int elen)
{
int i, p1, p2;
// " " " "
mVexNum = vlen;
mEdgNum = elen;
// " "
for (i = 0; i < mVexNum; i++)
mVexs[i] = vexs[i];
// " "
for (i = 0; i < mEdgNum; i++)
{
//
p1 = getPosition(edges[i][0]);
p2 = getPosition(edges[i][1]);
mMatrix[p1][p2] = 1;
}
}
/*
*
*/
MatrixDG::~MatrixDG()
{
}
/*
* ch mMatrix
*/
int MatrixDG::getPosition(char ch)
{
int i;
for(i=0; i> ch;
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
*
*/
void MatrixDG::print()
{
int i,j;
cout << "Martix Graph:" << endl;
for (i = 0; i < mVexNum; i++)
{
for (j = 0; j < mVexNum; j++)
cout << mMatrix[i][j] << " ";
cout << endl;
}
}
int main()
{
char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char edges[][2] = {
{'A', 'B'},
{'B', 'C'},
{'B', 'E'},
{'B', 'F'},
{'C', 'E'},
{'D', 'C'},
{'E', 'B'},
{'E', 'D'},
{'F', 'G'}};
int vlen = sizeof(vexs)/sizeof(vexs[0]);
int elen = sizeof(edges)/sizeof(edges[0]);
MatrixDG* pG;
// " "( )
//pG = new MatrixDG();
// " "
pG = new MatrixDG(vexs, vlen, edges, elen);
pG->print(); //
return 0;
}