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;
}