main.h:#include <iostream>#include <queue>#define DefaultSize 10#define maxWeight -1using namespace std;template<typename T,typename E>struct Edge{int dest;E cost;Edge<T,E> *link;Edge(int d=0,int c=0):dest(d),cost(c),link(NULL){}};template<typename T,typename E>struct Vertex{T data;Edge<T,E> *adj;};template<typename T,typename E>class Base{public:virtual T getValue(int i)=0;virtual E getWeight(int v1,int v2)=0;virtual bool insertVertex(const T& vertex)=0;virtual bool insertEdge(const T& l,const T& r,E cost)=0;virtual void Show()=0;virtual bool removeEdge(int v1,int v2)=0;virtual bool removeVertex(int v)=0;virtual int getFirstNeighbor(int v)=0;virtual int NumberOfEdge()=0;virtual int getNextNeighbor(int v,int w)=0;};template<typename T,typename E>class Graphlnk:public Base<T,E>{public:Graphlnk(int sz=DefaultSize){numVertices=0;maxVertices=DefaultSize;numEgde=0;NodeTable = new Vertex<T,E>[sz];for(int i=0;i<sz;i++){NodeTable[i].adj=NULL;}}int NumberOfEdge(){return numEgde;}int getFirstNeighbor(int v){if(v<0||v>=numVertices)return -1;Edge<T,E> *p = NodeTable[v].adj;if(p!=NULL){return p->dest;}return -1;}int getNextNeighbor(int v,int w){if(v<0 || v>=numVertices || w<0 || w>=numVertices){return -1;}Edge<T,E> *p = NodeTable[v].adj;while(p!=NULL){if(p->dest == w){if(p->link!=NULL)return p->link->dest;}p = p->link;}return -1;}bool removeVertex(int v){Edge<T,E> *p = NodeTable[v].adj;while(p!=NULL){removeEdge(v,p->dest);p=p->link;}NodeTable[v].data = NodeTable[numVertices-1].data;NodeTable[v].adj = NodeTable[numVertices-1].adj;p = NodeTable[numVertices-1].adj;Edge<T,E> *q = NULL;while(p!=NULL){int index = p->dest;q = NodeTable[index].adj;while(q!=NULL){if(q->dest==(numVertices-1)){q->dest = v;break;}q=q->link;}p=p->link;}numVertices–;}bool removeEdge(int v1,int v2){if(v1<0||v1>=numVertices||v2<0||v2>=numVertices){return false;}Edge<T,E> *p = NodeTable[v1].adj;Edge<T,E> *q = NULL;while(p!=NULL && p->dest!=v2){q=p;p=p->link;}if(q==NULL && p==NULL){return false;}if(q==NULL && p!=NULL && p->dest==v2){NodeTable[v1].adj=p->link;delete p;}if(p==NULL){return false;}else if(q!=NULL){q->link=p->link;delete p;}p = NodeTable[v2].adj;q = NULL;while(p!=NULL && p->dest!=v1){q=p;p=p->link;}if(q==NULL && p==NULL){return false;}if(q==NULL && p!=NULL && p->dest==v1){NodeTable[v2].adj=p->link;delete p;}if(p==NULL){return false;}else if(q!=NULL){q->link=p->link;delete p;}numEgde–;}bool insertEdge(const T& l,const T& r,E cost){int v1 = getValuePos(l);int v2 = getValuePos(r);Edge<T,E> *p = NodeTable[v1].adj;Edge<T,E> *s = new Edge<T,E>(v2,cost);Edge<T,E> *q = NULL;while(p!=NULL && p->dest!=cost){q=p;p=p->link;}if(p!=NULL && p->dest==cost){return false;}if(q==NULL){NodeTable[v1].adj = s;}if(p==NULL && q!=NULL){s->link = NodeTable[v1].adj;NodeTable[v1].adj=s;}p = NodeTable[v2].adj;s = new Edge<T,E>(v1,cost);q = NULL;while(p!=NULL && p->dest!=cost){q=p;p=p->link;}if(p!=NULL && p->dest==cost){return false;}if(q==NULL){NodeTable[v2].adj = s;}if(p==NULL&&q!=NULL){s->link = NodeTable[v2].adj;NodeTable[v2].adj=s;}numEgde++;}bool insertVertex(const T& vertex){NodeTable[numVertices++].data=vertex;return true;}void Show(){Edge<T,E> *p=NULL;for(int i=0;i<numVertices;i++){cout<<NodeTable[i].data<<"> ";p=NodeTable[i].adj;while(p!=NULL){cout<<p->dest<<"–"<<p->cost<<" ";p=p->link;}cout<<endl;}}E getWeight(int v1,int v2){if(v1<0 || v1>=numVertices || v2<0 || v2>=numVertices){return -1;} Edge<T,E> *p = NodeTable[v1].adj;// Edge<T,E> *m = NULL; while(p!=NULL){//m = p;if(p->dest==v2)break;p=p->link;}if(p!=NULL){return p->cost;}else{return maxWeight;}}T getValue(int i){returnNodeTable[i].data; } int NumberOfVertices(){return numVertices;}int getValuePos(const T &t){for(int i=0;i<numVertices;i++){if(NodeTable[i].data==t)return i;}return -1;}Edge<T,E> * getNodeptr(int i){return NodeTable[i].adj;}private:int numVertices;int maxVertices;int numEgde;Vertex<T,E> *NodeTable;};template<typename T,typename E>void DFS(Graphlnk<T,E>& G,const T& v,bool visted[]){int index = G.getValuePos(v);cout<<G.getValue(index)<<endl;visted[index]=true;int w = G.getFirstNeighbor(index);while(w!=-1){if(!visted[w])DFS(G,G.getValue(w),visted);w = G.getNextNeighbor(index,w);}/*while(index!=-1){int x = 0;while(!visted[index]){cout<<G.getValue(index)<<endl;visted[index]=true;x = G.getFirstNeighbor(index);DFS(G,G.getValue(x),visted);}index = G.getNextNeighbor(x,index);}*/}template<typename T,typename E>void DFS(Graphlnk<T,E>& G,const T& v){int n = G.NumberOfVertices();bool *visted = new bool[n];for(int i=0;i<n;i++){visted[i] = false;}DFS(G,v,visted);}template<typename T,typename E>void BFS(Graphlnk<T,E>& G,const T& v){int n = G.NumberOfVertices();bool *visted = new bool[n];for(int i=0;i<n;i++){visted[i] = false;}int i = G.getValuePos(v);queue<int> Q;Q.push(i);int index;while(!Q.empty()){index = Q.front();Q.pop();if(!visted[index]){cout<<G.getValue(index)<<endl;visted[index] = true;}int x = G.getFirstNeighbor(index);while(x!=-1) {if(!visted[x]){Q.push(x);}x = G.getNextNeighbor(index,x); }}}template<typename T,typename E>void Search(Graphlnk<T,E> &G){bool *visted = new bool[G.NumberOfVertices()];for(int i=0;i<G.NumberOfVertices();i++){if(!visted[i])DFS(G,G.getValue(i),visted);}}
main.cpp:
青春气贯长虹，勇敢盖过怯懦，进取压倒苟安。
