辟谣

    现在有针对我的很多谣言，有的说我是找不到工作，有的说能找到但找不到高工资的工作，甚至还有的
说我不会写代码。

    之所以有这么多怪异的说法，狗头泼粪是一方面；更重要的是现在的孩子被洗脑洗的太干净，都没有独
立思考能力，分不清楚真伪。师傅那么浅薄，徒弟跟着浅薄也属正常，我不怪任何一位持有类似说法的学生，
只是惊讶于竟然人云亦云到如此地步，简直把对方都想成弱智了。那逻辑思维能力和女人差不多，只看眼前，
没有 view。
    
    只好贴出这点代码来辟谣，这是我在2007年研一结束之后的暑假写的一个图程序，当时是为了回答别人
的问题，原帖还在:

    http://topic.csdn.net/u/20070711/20/bac13dcb-3cff-43b9-ba3f-25ab7090c6d4.html

    当初之所以用 VS 2005，是因为鹏鹏挺通VC，当时暑假他去参加社会实践去了，本想着以后有问题可以
多向他请教；而且当时我还没有意识到Linux 在项目中的重要性，没人告诉过我，当时还比较迷茫，不知道
学什么好；文豪他们下棋的 Checker 项目也是这个时候做，我的任务是实现一个算法，别人都写好了算法了，
我没找到改进的地方，后来就干脆没去实现，想自己找点东西做。运行测试都成功，有兴趣的可以编译运行
一下。

    能写出这样程序的人，如果谁还说他做不了这个组的项目，或者还说他没有实现能力，那我无话可说了。


我在vs2005下写了一个,经过测试完全满足你的要求.
一共两个project : 一个Graph 还有一个UnDiGraph.
其中Graph project下有3个文件Edge.h, Vertex.h, Graph.h.里面分别是 边类,顶点类和图类.
而UnDiGraph project下只有一个文件夹UnDiGraph.h,里面是UnDiGraph类的定义.
其中 类UnDiGraph 继承自 类Graph.
我是用模板写的,由于编译器不支持类模板的分离编译,所以除了main所在的文件以外,没有.cpp文件.全放在了.h文件中实现.
另外,输入输出我都截图了,可惜发现无法发上来.

/*************** Graph Project *********************/

 // Edge.h

#ifndef EDGE_H
#define EDGE_H

#include 
using namespace std;


template  class Edge {

public:

Edge(int dest, DistType cost) { //constructor

    this->dest = dets;
    this->cost = cost;
    this->link = NULL;
}

Edge(int dest, DistType cost, Edge  *link) { //constructor

    this->dest = dest;
    this->cost = cost;
    this->link = link;
}

int getDest(void) const {

    return dest;
}

DistType getCost(void) const {

        return cost;

}

Edge  * getLink(void) const {

    return link;
}
 
void setDest(int dest) {

    this->dest = dest;
}

void setCost(DistType cost) {

    this->cost = cost;
}

void setLink(Edge  *p) {

     this->link = p;
}

private:

    int dest;
    DistType cost;
    Edge  *link;
};

#endif

//Vertex.h

#ifndef VERTEX_H
#define VERTEX_H

#include "Edge.h "

template  class Vertex { 

public:

Vertex(void) {

    this->adj = NULL;
}

Vertex(NameType data) {

    this->data = data;
    this->adj = NULL;
}
 
NameType getData(void) const {

    return data;
}

Edge  * getAdj(void) const {

        return adj;
}

void setData(NameType data) {

        this->data = data;
}

void setAdj(Edge  *adj) {

    this->adj = adj;
}

private:

    NameType data;
    Edge  *adj;
};

#endif
 
 // Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include "Vertex.h "

template  class Graph {

public:

Graph(int maxnum, int n ,int e):maxNumVertices(maxnum), numVertices(n), numEdges(e) { // constructor

    NameType name;
    nodeTable = new Vertex  [maxNumVertices]; // partly intialize, cannot initialize nodeTable within derived class

        for (int i = 0; i < n; i++) {

        cout << "Input the " << i << " th Vertex Name: ";
        cin >> name;
        nodeTable[i].setData(name);
        nodeTable[i].setAdj(NULL);
        }
 }

Graph(const Graph &otherGraph) { // copy constructor

     numVertices = otherGraph.getNumVertices();
     numEdges = otherGraph.getNumEdges();

     nodeTable = new Vertex  [numVertices]; // partly intialize, cannot initialize nodeTable within derived class
     for (int i = 0; i < numVertices; i++) {

         nodeTable[i].setData(otherGraph.getVertexValue(i));
         nodeTable[i].setAdj(NULL);
     }
}

Graph  & operator =(const Graph &otherGraph) { // =

    if (this != &otherGraph) {

        for (int i = 0; i < numVertices; i++) {
            for (Edge  *p = nodeTable[i].getAdj(); p != NULL; p = nodeTable[i].getAdj()) {

                nodeTable[i].setAdj(p->getLink());
                delete p;
            }
        }
        delete []nodeTable;
        numVertices = 0;
        numEdges = 0;
         
        numVertices = otherGraph.getNumVertices();
        numEdges = otherGraph.getNumEdges();

        nodeTable = new Vertex  [numVertices]; // partly intialize
        for (int i = 0; i < numVertices; i++) {

            nodeTable[i].setData(otherGraph.getVertexValue(i));
            nodeTable[i].setAdj(NULL);
        }
        }

    return *this;
}

virtual ~Graph(void) { // destructor

    for (int i = 0; i < numVertices; i++) {
        for (Edge  *p = nodeTable[i].getAdj(); p != NULL; p = nodeTable[i].getAdj()) {
            nodeTable[i].setAdj(p->getLink());
            delete p;
        }
    }

    numVertices = 0;
    numEdges = 0;
    delete []nodeTable;
}

int getMaxNumVertices(void) const {

    return maxNumVertices;
}

int getNumVertices(void) const{

    return numVertices;
}

int getNumEdges(void) const {

    return numEdges;
}

Vertex  *getNodeTable(void) const {

    return nodeTable;
}

int getVertexPos(NameType nodename) const {

    int i;
    for (i = 0; i < numVertices; i++) {
        if (nodeTable[i].getData() == nodename) {
            return i;
        }
    }

    return -1;
 } 

NameType getVertexValue(int v) const {

    return nodeTable[v].getData();
}

DistType getWeight(int v1, int v2) const {

    if (v1 != -1 && v2 != -1) {

        if (v1 == v2) {
            return 0;
        }

        Edge  *p = nodeTable[v1].getAdj();
        while (p != NULL) {
            if (p->getDest() == v2) {

                return p->getCost();
            }
            else {
                p = p->getLink();
            }
        }

        int temp = (2 << 29);
        return 2 * temp - 1; // 32bit 's max number
    }
    else {
        cerr << "v1 or v2 underflow in function getWeight() " << endl;
        exit(1);
    }
 }

void setVertexValue(NameType data) {

    nodeTable[i].setData(data);
}

void insertEdge(int tailpos, int headpos, DistType weight) {

    Vertex  *nodeTable = getNodeTable();
    Edge  *edge = new Edge  (headpos, weight, NULL);
    edge->setLink(nodeTable[tailpos].getAdj());
    nodeTable[tailpos].setAdj(edge);
}

void outputAdjacencyList(void) {

    cout << "The graph 's Adjacency list is : " << endl;
    for (int i = 0; i < numVertices; i++) {
        cout << nodeTable[i].getData() << "---->";
        for (Edge  *p = nodeTable[i].getAdj(); p != NULL; p = p->getLink()) {

            cout << "| " << p->getDest() << " " << p->getCost();
            if (p->getLink() != NULL) {
                cout << "|---->";
            }
            else {
                cout << "|^ " << endl;
            }
        }
        cout << endl;
    }
    cout << endl;
}

private:

    int maxNumVertices;
    int numVertices;
    int numEdges;
    Vertex  * nodeTable;
};

#endif


/***********************UnDiGraph.h*****************************/

 // UnDiGraph.h
#ifndef UNDIGRAPH
#define UNDIGRAPH

#include "..\\..\\Graph\\Graph\\Graph.h "

template  class UnDiGraph : public Graph  {

public:

UnDiGraph(int maxnum, int n, int e) : Graph(maxnum, n, e) { // constructor
    NameType tailname, headname;
    DistType weight;
    int tailpos, headpos;
    for (int i = 0; i < e; i++) {

        cout << "Input the " << i << " th Edge, ";
        cout << "Input edge 's tailname: ";
        cin >> tailname;
        cout << "Input edge 's headname: ";
        cin >> headname;
        cout << "Input edge 's weight: ";
        cin >> weight;
         
        tailpos = getVertexPos(tailname);
        headpos = getVertexPos(headname);

        insertEdge(tailpos, headpos, weight);
        insertEdge(headpos, tailpos, weight);
    }
}

UnDiGraph(const UnDiGraph  &otherUnDiGraph) : Graph(otherUnDiGraph) { // copy constructor

    int numVertices = getNumVertices(); 
    Vertex  *otherNodeTable = otherUnDiGraph.getNodeTable();

    int otherDest;
    DistType otherCost;
    Edge  *p = NULL;

    for (int i = 0; i < numVertices; i++) {
        for (p = otherNodeTable[i].getAdj(); p != NULL; p = p->getLink()) {
            otherDest = p->getDest();
            otherCost = p->getCost();
            insertEdge(i, otherDest, otherCost);
        } 
    }
}

UnDiGraph  & operator = (const UnDiGraph  otherUnDiGraph) { // =
    if (this == &otherUnDiGraph) {

        return *this;
    }

    Graph::operator =(otherUnDiGraph);
 
    int numVertices = getNumVertices();
    Vertex  *otherNodeTable = otherUnDiGraph.getNodeTable();
    int otherDest;
    DistType otherCost;
    Edge  *p = NULL; 

    for (int i = 0; i < numVertices; i++) {
        for (p = otherNodeTable[i].getAdj(); p != NULL; p = p->getLink()) {
            otherDest = p->getDest();
            otherCost = p->getCost();
            insertEdge(i, otherDest, otherCost);
            insertEdge(otherDest, i, otherCost);
        } 
    }

    return *this;
}

/* 
* Find an UnDiGraph 's minimun spanning tree
*
*/

void primSpanTree(void) { // Prim 's Minimum Spanning Tree Algorithm

    cout << "Prim Minimum Spanning Tree is : " << endl;
    int numVertices = getNumVertices();
    Vertex  *nodeTable = getNodeTable();
    DistType *lowcost = new DistType[numVertices];
    int *nearvex = new int[numVertices];
     
    for (int i = 1; i < numVertices; i++) {
        lowcost[i] = getWeight(0, i);
        nearvex[i] = 0;
    }
    nearvex[0] = -1;
 
    int tail, head;
    DistType cost;

    int temp = (2 << 29);
    double max32bitNumber = 2 * temp - 1;
    for (int i = 1; i < numVertices; i++) {

        int minIndex = 0;
        DistType minValue = max32bitNumber;
        for (int j = 0; j < numVertices; j++) {
            if (nearvex[j] != -1 && lowcost[j] < minValue) {
                minIndex = j;
                minValue = lowcost[j];
            }
        }
        if (minIndex != 0) {
            tail = nearvex[minIndex];
            head = minIndex;
            cost = lowcost[minIndex];
            cout << " " << nodeTable[tail].getData() << "---->" << nodeTable[head].getData() << ", cost is : " << cost << endl;
            nearvex[minIndex] = -1;

            for (int j = 1; j < numVertices; j++) {
                if ((nearvex[j] != -1) && (getWeight(minIndex, j) < lowcost[j])) {
                    lowcost[j] = getWeight(minIndex, j);
                    nearvex[j] = minIndex;
                }
            }
        }
    }

    delete []nearvex;
    delete []lowcost;
}

/*
* output vertex degree
*
*/
 
void outputDegree(void) {

    cout << "Every vertex 's degree is : " << endl;
    int numVertices = getNumVertices();
    Vertex  *nodeTable = getNodeTable();
    for (int i = 0; i < numVertices; i++) {

        int count = 0;
        cout << nodeTable[i].getData() << " 's degree is : ";
        for (Edge  *p = nodeTable[i].getAdj(); p != NULL; p = p->getLink()) {
            count++;
        }
        cout << count << endl;
    }
}

};

#endif

// Test.h
#include "UnDiGraph.h "

int main(int argc, char *argv[]) {
 
    int maxnum = 10000;
    int n;
    cout << "Input number of vertices(n < " << maxnum << " vertices): ";
    cin >> n;
    if (n > maxnum) {
        cerr << "exceeding maxnumber! " << endl;
        exit(1);
    }

    cout << "Input Number of Edges: ";
    int e; 
    cin >> e;

    UnDiGraph  undigraph(maxnum, n, e);
    undigraph.outputAdjacencyList();
    undigraph.outputDegree();
    undigraph.primSpanTree();

    return 0;
}