2010-10-30 80 views
0

那里! 我正在写图类。我在 “Graphs.h” 写了这样的代码:问题汇编C++程序

#include <vector> 
#include <iostream> 
using namespace std; 

struct Edge{ 
int v,w; 
Edge(int v=-1, int w=-1):v(v),w(w){} 
}; 

class Graph 
{ 
protected: 
int Ecnt, Vcnt; bool digraph; 
public: 
Graph(int V, bool isDirected) :Ecnt(0),Vcnt(V),digraph(isDirected) {} 
~Graph(); 
virtual int V() const; 
virtual int E() const; 
virtual bool directed() const; 
virtual void insert(Edge); 
virtual void remove(Edge) = 0; 
virtual bool edge(int, int); 
class adjIterator 
{ 
public: 
    adjIterator(const Graph &, int); 
    int beg(); 
    int nxt(); 
    bool end(); 
}; 
}; 


class DenseGraph:public Graph 
{ 
private: 
int Vcnt,Ecnt; bool digraph; 
vector <vector <bool> > adj; 
public: 
DenseGraph(int V, bool digraph=false) : Graph(V,digraph),adj(V) 
    { 
    for(int i=0;i<V;++i) 
    adj[i].assign(V,false); 
    } 
    int V() const{ return Vcnt;} 
    int E() const{return Ecnt;} 
    bool directed() { return digraph;} 
    void insert(Edge e) 
    { 
    int v=e.v, w=e.w; 
    if(adj[v][w]==false) Ecnt++; 
    adj[v][w]=true; 
    if(!digraph) adj[w][v]=true; 
    } 
    void remove(Edge e) 
    { 
    int v=e.v, w=e.w; 
    if(adj[v][w]==true) Ecnt--; 
    adj[v][w]=false; 
    if(!digraph) adj[w][v]=false; 
    } 
    bool edge(int v,int w) const 
    { 
    return adj[v][w]; 
    } 
    class adjIterator; 
    friend class adjIterator; 
}; 

class DenseGraph::adjIterator 
{ 
const DenseGraph &G; 
int i,v; 
public: 
adjIterator(const DenseGraph &G, int v): G(G), v(v), i(-1) 
{ } 
int beg() 
{ i=-1; return nxt();} 
int nxt() 
{ 
    for(i++;i<G.V();i++) 
    if(G.adj[v][i]==true) return i; 
    return-1; 
} 
bool end() 
{ return i>= G.V();} 
}; 

class SparseMultiGraph:public Graph 
{ 

struct node{ 
    int v; node* next; 
    node(int x, node* t){v=x; next=t;} 
}; 
typedef node* link; 
vector <link> adj; 
public: 
SparseMultiGraph(int V, bool digraph=false): Graph(V,digraph),adj(V) 
    { adj.assign(V,0);} 
    int V() const{ return Vcnt;} 
    int E() const{return Ecnt;} 
    bool directed() const{return digraph;} 
    void insert(Edge e) 
    { 
    int v=e.v,w=e.w; 
    adj[v]=new node(w,adj[v]); 
    if(!digraph) 
    adj[w]=new node(v,adj[w]); 
    Ecnt++; 
    } 
    void remove(Edge e) 
    { 
    // int v=e.v,w=e.w; 

    } 
    bool edge(int v, int w) const; 
    class adjIterator; 
    friend class adjIterator; 
}; 

class SparseMultiGraph::adjIterator 
{ 
const SparseMultiGraph &G; 
int v; 
SparseMultiGraph::link t; 
public: 
adjIterator(const SparseMultiGraph &G, int v): 
    G(G), v(v) {t = 0;} 
    int beg() 
    { t=G.adj[v]; return t? t->v: -1;} 
    int nxt() 
    { if(t) t=t->next; return t? t->v: -1;} 
    bool end() 
    { return t==0;} 
}; 

template<class Graph> 
class IO 
{ 
public: 
static void show(const Graph &); 
static void scanEZ(Graph &); 
static void scan(Graph &); 
}; 




template<class Graph> 
class CC 
{ 
public: 
CC(const Graph &); 
int count(); 
bool connect(int ,int); 
}; 


//return all edges included in this Graph object G 
template<class Graph> 
vector< Edge> edges(Graph &G) 
{ 
int E=0; 
vector <Edge> a(G.E()); 
for(int v=0;v<G.V();++v) 
{ 
    typename Graph::adjIterator A(G,v); 
    for(int w=A.beg(); !A.end(); w=A.nxt()) 
    if(G.directed() || v<w) 
    a[E++]=Edge(v,w); 
} 
return a; 
} 

template<class Graph> 
void IO<Graph>::show(const Graph &G) 
{ 
for(int s=0;s<G.V(); ++s) 
{ 
    cout.width(2); cout<<s<<":"; 
    typename Graph::adjIterator A(G,s); 
    for(int t=A.beg(); !A.end(); t=A.nxt()) 
    { cout.width(2); cout<<t<<" ";} 
    cout<< endl; 
} 
} 

//17_12 
template<class Graph> 
static void randE(Graph& G, int E) 
{ 
for(int i=0;i<E;++i) 
{ 
    int v=int(G.V()*rand()/(1.0+RAND_MAX)); 
    int w=int(G.V()*rand()/(1.0+RAND_MAX)); 
    G.insert(Edge(v,w)); 
} 
} 

//17_13 
template<class Graph> 
static void randG(Graph &G, int E) 
{ 
double p=2.0*E/G.V()/(G.V()-1); 
for(int i=0;i<G.V();++i) 
    for(int j=0;j<i;++j) 
    if(rand()<p*RAND_MAX) 
    G.insert(Edge(i,j)); 
} 

并在Test.cpp的

#include "stdafx.h" 
#include <stdlib.h> 
#include "Graph_7_1.h" 
using namespace std; 

void _tmain(int argc, char* argv[]) 
{ 
int V=atoi(argv[1]); 
Graph* G= new DenseGraph(V) ; 
IO<Graph>::scan(*G); 
if(V<20) IO<Graph>::show(*G); 
cout<<G->E()<<" edges "; 
CC<Graph> Gcc(*G); 
cout<< Gcc.count() <<" components"<<endl; 
} 

而且我有这样的错误列表:

error LNK1120: 13 unresolved externals C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\Debug\TestGraph.exe TestGraph 
error LNK2001: unresolved external symbol "public: virtual bool __thiscall Graph::directed(void)const " ([email protected]@@UBE_NXZ) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2001: unresolved external symbol "public: virtual bool __thiscall Graph::edge(int,int)" ([email protected]@@[email protected]) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2001: unresolved external symbol "public: virtual int __thiscall Graph::E(void)const " ([email protected]@@UBEHXZ) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2001: unresolved external symbol "public: virtual int __thiscall Graph::V(void)const " ([email protected]@@UBEHXZ) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2001: unresolved external symbol "public: virtual void __thiscall Graph::insert(struct Edge)" ([email protected]@@[email protected]@@Z) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: __thiscall CC<class Graph>::CC<class Graph>(class Graph const &)" ([email protected]@@@@[email protected]@@@Z) referenced in function _wmain C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: __thiscall Graph::~Graph(void)" ([email protected]@[email protected]) referenced in function [email protected]@[email protected][email protected]$0 C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: __thiscall Graph::adjIterator::adjIterator(class Graph const &,int)" ([email protected]@@[email protected]@[email protected]) referenced in function "public: static void __cdecl IO<class Graph>::show(class Graph const &)" ([email protected][email protected]@@@@[email protected]@@Z) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: bool __thiscall Graph::adjIterator::end(void)" ([email protected]@[email protected]@QAE_NXZ) referenced in function "public: static void __cdecl IO<class Graph>::show(class Graph const &)" ([email protected][email protected]@@@@[email protected]@@Z) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: int __thiscall CC<class Graph>::count(void)" ([email protected][email protected]@@@@QAEHXZ) referenced in function _wmain C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: int __thiscall Graph::adjIterator::beg(void)" ([email protected]@[email protected]@QAEHXZ) referenced in function "public: static void __cdecl IO<class Graph>::show(class Graph const &)" ([email protected][email protected]@@@@[email protected]@@Z) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: int __thiscall Graph::adjIterator::nxt(void)" ([email protected]@[email protected]@QAEHXZ) referenced in function "public: static void __cdecl IO<class Graph>::show(class Graph const &)" ([email protected][email protected]@@@@[email protected]@@Z) C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 
error LNK2019: unresolved external symbol "public: static void __cdecl IO<class Graph>::scan(class Graph &)" ([email protected][email protected]@@@@[email protected]@@Z) referenced in function _wmain C:\Users\Роман\documents\visual studio 2010\Projects\TestGraph\TestGraph\TestGraph.obj TestGraph 

可能有人帮我? 谢谢!

回答

3

您还没有定义成员函数Graph::directed。要么定义它,要么使其成为纯虚拟的:

virtual bool directed() const = 0; 

其他错误也一样。

+0

只需添加,使函数为纯虚拟将使类Abstract,并且您不能再创建它的一个实例。 – 2010-10-30 13:59:56

1

你要么必须实现所有这些函数(Graph :: directed()等等),要么声明它们是纯虚函数。