有向加权图邻接图表示

#include

using namespace std;

const int max_num = 20;
template   class graph;

template
class node {
        private:
                T id;
                int weight;
                node * next;
        public: 
                friend class graph;
                node() {}       
                node(T v, int w, node * next_node = NULL):
                        id(v), weight(w), next(next_node){}
}; 

template
class graph {
        private:
                node * table;
                int node_num;
                int getPos(const T &);
        public:
                ~graph();       
                graph(){table = new node[max_num]; node_num = 0;}
                graph(const T * [], int);
                bool addNode(const T &);
                bool addArc(const T &, const T &, const int);
                void print();
};

template
int graph::getPos(const T &v) {
        for (int i = 0; i < node_num; i++) {
                if (table[i].id == v) return i;
        }
        return -1;
}

template
graph::graph(const T * v[], int num) {
        if (num > max_num) {
                cout << "too many!" << endl;    
                return;
        }
        table = new node[max_num];
        node_num = 0;
        for (int i = 0; i < num; i++) {
                addNode(v[i]);
        }
}

template
graph::~graph() {
        node * p;
        for (int i = 0; i < node_num; i++) {
                p = table[i].next;      
                while(p != NULL) {
                        table[i].next = p->next;
                        delete p;
                        p = table[i].next;
                }
        } 
        delete [] table ;
}
                
template
bool graph::addNode(const T &v) {
        if (node_num >= max_num) {
                cout << "full!" << endl;
                return false;
        } else {
                table[node_num].id = v;
                table[node_num].weight = 0;
                table[node_num].next = NULL;
                node_num++;
                return true;
        }
}

template
bool graph::addArc(const T &v1, const T &v2, const int w) {
        int m;  
        if ((m = getPos(v1)) < 0 || getPos(v2) < 0) {
                cout << "v1 or v2 not exist!" << endl;
                return false;
        } else {
                node *tmp = table[m].next;
                table[m].next = new node (table[getPos(v2)].id,w,tmp);
                return true;
        }
}

template
void graph::print() {
        node * p;    
        for (int i = 0; i < node_num; i++) {
                cout << table[i].id << ":";
                p = table[i].next;
                while(p != NULL) {
                        cout << "->" << p->id << "(" << p->weight << ")";
                        p = p->next;
                }
                cout << endl;
        }
}

//main.cpp
//figure 214-7-8
int main()
{
        graph a;
        a.addNode('a');
        a.addNode('b');
        a.addNode('c');
        a.addNode('d');
        a.addArc('a','c', 9);
        a.addArc('b','c', 3);
        a.addArc('b','a', 7);
        a.addArc('c','b', 6);
        a.addArc('d','b', 2);
        a.addArc('d','a', 8);
        a.print();
}