1>e:\tempc++\test10\test10\vector.h(20): error C2440: “default argument”: 无法从“int”转换为“Vertex”,这是为什么?定义向量的时候是用Vertex代替模板T,怎么就无法从“int”转换为“Vertex”?
main
#include<iostream>
using namespace std;
#include"GraphMatrix.h"
int main()
{
string vertex;
GraphMatrix<string,int> graph;
int choice=0;
cout<<"添加节点请输入1,添加边请输入2,删除节点请输入3,删除边请输入4,显示图请输入5。"<<endl;
cin>>choice;
/*switch(choice)
{
case 1:
}*/
return 0;
}
Graph.h
#ifndef _GRAPH__H_
#define _GRAPH__H_
#include<limits.h>
typedef enum{UNDISCOVERED,DISCOVERED,VISITED} VStatus;
typedef enum{UNDETERMINED,TREE,CROSS,FORWARD,BACKWARD} EType;
template<typename Tv,typename Te>
class Graph{
private:
void reset(){
for(int i=0;i<n;i++){
status(i)=UNDISCOVERED;
dTime(i)=fTime(i)=-1;
parent(i)=-1;
priority(i)=INT_MAX;
for(int j=0;j<n;j++)//所有边的
if(exists(i,j))
type(i,j)=UNDETERMINED;//类型
}
}
void BFS(int,int&);//广度优先
public:
//顶点
int n;
virtual int insert(Tv const&)=0;
virtual Tv remove(int)=0;
virtual Tv& vertex(int)=0;//顶点v数据
virtual int inDegree(int)=0;
virtual int outDegree(int)=0;
virtual int firstNbr(int)=0;
virtual int nextNbr(int,int)=0;
virtual VStatus& status(int)=0;
virtual int& dTime(int)=0;
virtual int& fTime(int)=0;
virtual int& parent(int)=0;
virtual int& priority(int)=0;
//边
int e;
virtual bool exists(int,int)=0;
virtual void insert(Te const&,int,int,int)=0;
virtual Te remove(int,int)=0;
virtual EType& type(int,int)=0;
virtual Te& edge(int,int)=0;
virtual int& weight(int,int)=0;
void bfs(int);
};
#endif
GraphMatrix.h
#ifndef _GRAPHMATRIX__H_
#define _GRAPHMATRIX__H_
#include"Vector.h"
#include"Graph.h"
#include"Queue.h"
#include<string>
//城市
struct city
{
string cname;
city(string name){cname=name;}
};
//道路
struct road
{
road(){}
};
//顶点对象
template <typename Tv>
struct Vertex{
Tv data;
int inDegree,outDegree;
VStatus status;
int dTime,fTime;
int parent;
int priority;
Vertex(Tv const& d=(Tv)0):
data(d),inDegree(0),outDegree(0),status(UNDISCOVERED),dTime(-1),fTime(-1),parent(-1),priority(INT_MAX){}
};
//边对象
template<typename Te>
struct Edge{
Te data;
int weight;
EType type;
Edge(Te const& d,int w):data(d),weight(w),type(UNDETERMINED){}
};
//邻接矩阵
template<typename Tv,typename Te>
class GraphMatrix:public Graph<Tv,Te>{
private:
Vector<Vertex<Tv>>V;//顶点集(向量)
Vector<Vector<Edge<Te>*>>E;//边集(邻接矩阵)
public:
GraphMatrix(){n=e=0;}
~GraphMatrix(){
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
delete E[j][k];
}
//顶点基本操作:查询第i个顶点
virtual Tv& vertex(int i){return V[i].data;}
virtual int inDegree(int i){return V[i].inDegree;}
virtual int outDegree(int i){return V[i].outDegree;}
virtual int firstNbr(int i){return nextNbr(i,n);}
virtual int nextNbr(int i,int j)
{
while((-1<j)&&(!exist(i,--j)));
return j;
}
virtual VStatus& status(int i){return V[i].status;}
virtual int& dTime(int i){return V[i].dTime;}
virtual int& fTime(int i){return V[i].fTime;}
virtual int& parent(int i){return V[i].parent;}
virtual int& priority(int i){return V[i].priority;}
//顶点动态操作
virtual int insert(Tv const& vertex)
{
for(int j=0;j<n;j++)//各顶点预留潜在边
E[j].insert(NULL);
n++;
E.insert(Vector<Edge<Te>*>(n,n,(Edge<Te>*)NULL));//创建顶点对应边向量
return V.insert(Vertex<Tv>(vertex));//顶点向量增加顶点
}
virtual Tv remove(int i)
{
for(int j=0;j<n;j++)//出边
if(exists(i,j))
{
delete E[i][j];
V[j].inDegree--;
}
E.remove(i);
n--;
Tv vBak=vertex(i);
V.remove(i);
for(int j=0;j<n;j++)//入边
if(Edge<Te> * e=E[j].remove(i))
{
delete e;
V[j].outDegree--;
}
return vBak;
}
//边的确认操作
virtual bool exists(int i,int j)
{
return (0<=i)&&(i<n)&&(0<=j)&&(j<n)&&E[i][j]!=NULL;
}
//查询i,j联边
virtual EType& type(int i,int j){return E[i][j]->type;}
virtual Te& edge(int i,int j){return E[i][j]->data;}
virtual int& weight(int i,int j){return E[i][j]->weight;}
//边的动态操作
virtual void insert(Te const& edge,int w,int i,int j)
{
if(exists(i,j)) return;
E[i][j]=new Edge<Te>(edge,w);
e++;
V[i].outDegree++;
V[j].inDegree++;
}
virtual Te remove(int i,int j)
{
Te eBak=edge(i,j);
delete E[i][j];
E[i][j]=NULL;
e--;
V[i].outDegree--;
V[j].inDegree--;
return eBak;
}
};
//广度优先搜索
template<typename Tv,typename Te>
void Graph<Tv,Te>::BFS(int v,int& clock)
{
Queue<int> Q;
status(v)=DISCOVERED;
Q.enqueue(v);
while(!Q.empty())//不断取出队首,考察邻居
{
int v=Q.dequeue();
dTime(v)=++colok;
for(int u=firstNbr(v);-1<u;u=nextNbr(v,u))
if(UNDISCOVERED==status(u))
{//若未发现
status(u)=DISCOVERED;
Q.enqueue(u);
type(v,u)=Tree;
parent(u)=v;
}
else
type(v,u)=CROSS;
status(v)=VISITED;
}
}
#endif
Vector.h
#ifndef __Vector_H__
#define __Vector_H__
#include <iostream>
using namespace std;
#include <ctime>
#include<stdlib.h>
typedef int Rank; //秩
#define DEFAULT_CAPACITY 3 //默认的初始容量(实际应用中可设置为更大)
template <typename T>
class Vector
{
protected:
Rank _size;int _capacity;T* _elem;
void expand();
void shrink();
public:
Vector(int c=DEFAULT_CAPACITY,int s=0,T v=0)//构造
{_elem=new T[_capacity=c];for(_size=0;_size<s;_elem[_size++]=v);}
~Vector(){delete []_elem;}//析构
T& operator[] (Rank r);
Rank size() const{return _size;};
bool empty(){return !size();}
Rank insert(Rank r,T const& e);
Rank insert(T const& e){return insert(_size,e);}
void show();
T remove(Rank r);
int remove(Rank lo,Rank hi);
Rank find (T const& e){return find(e,0,_size);}
Rank find (T const &e,Rank lo,Rank hi);
void swap(T &a,T &b);
void BubbleSort_down(T A[],int n);
void BubbleSort_up(T A[],int n);
void mergeSort(Rank lo,Rank hi);
void merge(Rank lo,Rank mi,Rank hi);
};
//扩容
template <typename T>
void Vector<T>::expand()
{
if(_capacity<DEFAULT_CAPACITY)
_capacity=DEFAULT_CAPACITY;
if(_size<_capacity)
return;
T* _OldElem=_elem;
_elem=new T[_capacity<<=1];
for(int i=0;i<_size;i++)
_elem[i]=_OldElem[i];
delete [] _OldElem;
}
//缩容
template <typename T>
void Vector<T>::shrink()
{
if(_capacity<DEFAULT_CAPACITY<<1)
return;
if(_size>_capacity>>2)
return;
T* _OldElem=_elem;
_elem=new T[_capacity>>=1];
for(int i=0;i<_size;i++)
_elem[i]=_OldElem[i];
delete [] _OldElem;
}
template <typename T>
T& Vector<T>::operator[] (Rank r) //重载下标操作符
{
return _elem[r];
} // assert: 0 <= r < _size
//展示
template<typename T>
void Vector<T>::show()
{
for(int i=0;i<_size;i++)
cout<<_elem[i]<<" ";
cout<<endl;
}
//插入
template<typename T>
Rank Vector<T>::insert(Rank r,T const& e)
{
expand();
if(r<0||r>_size)
{cout<<"ERROR!"<<endl;return -1;}
for(int i=_size;i>r;i--)
_elem[i]=_elem[i-1];
_elem[r]=e;
_size++;
return r;
}
//区间删除
template<typename T>
int Vector<T>::remove(Rank lo,Rank hi)
{
if(hi==lo)
return 0;
while(hi<_size)
_elem[lo++]=_elem[hi++];
_size=lo;
shrink();
return hi-lo;
}
//单个删除
template<typename T>
T Vector<T>::remove(Rank r)
{
T e=_elem[r];
remove(r,r+1);
return e;
}
//区间查找
template<typename T>
Rank Vector<T>::find (T const &e,Rank lo,Rank hi)
{
while((lo<hi--)&&(e!=_elem[hi]));
return hi;
}
//交换
template<typename T>
void Vector<T>::swap(T &a,T &b)
{
T c;
c=a;
a=b;
b=c;
}
//冒泡降序
template <typename T>
void Vector<T>::BubbleSort_down(T A[],int n)
{
bool sorted=false;
while(!sorted)
{
sorted=true;
for(int i=0;i<n-1;i++)
{
if(A[i]<A[i+1])
{
swap(A[i],A[i+1]);
sorted=false;
}
}
n--;
}
}
//冒泡升序
template <typename T>
void Vector<T>::BubbleSort_up(T A[],int n)
{
bool sorted=false;
while(!sorted)
{
sorted=true;
for(int i=0;i<n-1;i++)
{
if(A[i]>A[i+1])
{
swap(A[i],A[i+1]);
sorted=false;
}
}
n--;
}
}
//归并排序
template <typename T>
void Vector<T>::mergeSort(Rank lo,Rank hi)
{
if(hi-lo<2)return;
Rank mi=(hi+lo)>>1;
mergeSort(lo,mi);
mergeSort(mi,hi);
merge(lo,mi,hi);
}
//归并
template <typename T>
void Vector<T>::merge(Rank lo,Rank mi,Rank hi)
{
T* A=_elem+lo;
int lb=mi-lo;
T* B=new T[lb];
for(Rank i=0;i<lb;i++)
B[i]=A[i];
int lc=hi-mi;
T* C=_elem+mi;
for(Rank i=0,j=0,k=0;(j<lb)||(k<lc);)
{
//cout<<A[i]<<" "<<B[j]<<" "<<C[k]<<" ";
if((j<lb)&&(!(k<lc)||B[j]<=C[k]))
A[i++]=B[j++];
if((k<lc)&&(!(j<lb)||C[k]<B[j]))
A[i++]=C[k++];
//cout<<A[i]<<" "<<B[j]<<" "<<C[k]<<" ";
}
delete [] B;
}
#endif
ListNode.h
#ifndef __ListNode_H__
#define __ListNode_H__
#include <iostream>
using namespace std;
#define Posi(T) ListNode<T>*
typedef int Rank;
//结点
template <typename T>
struct ListNode{
T data;
Posi(T) pred;
Posi(T) succ;
ListNode() {};
ListNode (T e,Posi(T) p=NULL,Posi(T) s=NULL)
{
data=e;pred=p;succ=s;
}
Posi(T) insertAsSucc(T const &e);
Posi(T) insertAsPred(T const &e);
};
//后插入
template <typename T>
Posi(T) ListNode<T>::insertAsSucc(T const &e)
{
Posi(T) x=new ListNode(e,this,succ);
succ->pred=x;succ=x;
return x;
}
//前插入
template <typename T>
Posi(T) ListNode<T>::insertAsPred(T const &e)
{
Posi(T) x=new ListNode(e,pred,this);
pred->succ=x;pred=x;
return x;
}
#endif
List.h
#ifndef __List_H__
#define __List_H__
#include"ListNode.h"
template<typename T>
class List{
private:
int _size;
Posi(T) header;
Posi(T) trailer;
public:
List(){Init();}
~List(){};
void Init();
Rank size(){return _size;}
bool empty(){return _size<=0;}
int clear();
T Data(Posi(T) p){return p->data;}
Posi(T) first() const{return header->succ;}
Posi(T) last() const{return trailer->pred;}
Posi(T) insertA(Posi(T) p,T const &e);
Posi(T) insertB(Posi(T) p,T const &e);
Posi(T) insertAsFist(T const &e);
Posi(T) insertAsLast(T const &e);
void show();
T remove(Posi(T) p);
Posi(T) find(T const &e);
Posi(T) search(T const &e,int n, Posi(T) p);
void insertSort(Posi(T) p,int n);
T Search(T const &e);
int Place(int place){return place;}
};
//初始化
template<typename T>
void List<T>::Init()
{
header=new ListNode<T>;
trailer=new ListNode<T>;
header->succ=trailer;header->pred=NULL;
trailer->pred=header;trailer->succ=NULL;
_size=0;
}
//首节点插入
template<typename T>
Posi(T) List<T>::insertAsFist(T const &e)
{
_size++;
return header->insertAsSucc(e);
}
//末节点插入
template<typename T>
Posi(T) List<T>::insertAsLast(T const &e)
{
_size++;
return trailer->insertAsPred(e);
}
//后插入
template<typename T>
Posi(T) List<T>::insertA(Posi(T) p,T const &e)
{
_size++;
return p->insertAsSucc(e);
}
//前插入
template<typename T>
Posi(T) List<T>::insertB(Posi(T) p,T const &e)
{
_size++;
return p->insertAsPred(e);
}
//展示
template<typename T>
void List<T>::show()
{
Posi(T) p=trailer->pred;;
while(p->pred)
{
cout<<p->data<<" ";
p=p->pred;
}
cout<<endl;
}
//查找
template<typename T>
Posi(T) List<T>::find(T const &e)
{
Posi(T) p=header->succ;
while(p->succ)
{
if(p->data==e)
return p;
p=p->succ;
}
return NULL;
}
//删除
template<typename T>
T List<T>::remove(Posi(T) p)
{
T e=p->data;
p->pred->succ=p->succ;
p->succ->pred=p->pred;
delete p;
_size--;
return e;
}
//清空
template<typename T>
int List<T>::clear()
{
int _oldSize=_size;
while(0<_size)
remove(header->succ);
return _oldSize;
}
//查找不大于e最后一个元素
template<typename T>
Posi(T) List<T>::search(T const &e,int n, Posi(T) p)
{
while(0<=n--)
{
p=p->pred;
if(p->data<=e)
break;
}
return p;
}
//插入排序
template<typename T>
void List<T>::insertSort(Posi(T) p,int n)
{
for(int r=0;r<n;r++)
{
insertA(search(p->data,r,p),p->data);
p=p->succ;
remove(p->pred);
}
}
//查找大于e第一个元素
template<typename T>
T List<T>::Search(T const &e)
{
Posi(T) p=header->succ;
while(p->succ)
{
if(p->data>e)
return p->data;
p=p->succ;
}
return NULL;
}
#endif
Queue.h
#ifndef __Queue_H__
#define __Queue_H__
#include"List.h"
template <typename T>
class Queue:public List<T>{
public:
void enqueue(T const &e)//尾入队
{
insertAsLast(e);
}
T dequeue()//首出队
{
return remove(first());
}
T& front()
{
return first()->data;
}
T& final()
{
return last()->data;
}
};
#endif