校园导游图.cpp

一个用最短距离法来实现的校园导游算法

        return 0;
}

KMPstrmatcher::~KMPstrmatcher()
{
	
}

//************************************************vector

template<class T>class vector
{
public:
     //构造函数
	vector(unsigned num);                            //向量长度
	vector(unsigned num,T initvalue);                //初始值
	vector(const vector<T>& s);
	virtual ~vector();
	//通过下标访问元素
	T & operator[](unsigned index)const;
	//赋值
	vector<T>& operator=(const vector<T>&);
	unsigned length()const;
	//扩充向量长度
	unsigned setsize(unsigned num);
	unsigned setsize(unsigned num,T initvalue);
private:
	T * data; 
	unsigned size;
};
//----------------------------------------
template<class T> vector<T>::vector(unsigned num):size(num)
{
    data=new T[size];
	//检查分配是否成功
	assert(data!=0);
}
//-------------------------------------------
template<class T> vector<T>::vector(unsigned mun,T v):size(num)
{
    data=new T[size];
	assert(data!=0);
    //初始赋值
    for(int i=0;i<size;i++)
		data[i]=v;
}
//-------------------------------------------
template<class T> vector<T>::vector(const vector<T> & s):size(s.size)
{
    data=new T[size];
	assert(data!=0);
	//元素赋值
    for(int i=0;i<size;i++)
		data[i]=s.data[i];
}
//-------------------------------------------
template<class T> vector<T>::~vector()
{
	delete[]data;
	data=0;
	size=0;
}
//-------------------------------------------
template<class T>T & vector<T>::operator [](unsigned index)const
{
	assert(index<size);
	return data[index];
}
//----------------------------------------------
template<class T>unsigned vector<T>::length()const
{
	return size;
}
//---------------------------------------------
template<class T>unsigned vector<T>::setsize(unsigned num)
{
	if(size!=num)
	{//分配新存储区
		T * np=new T[num];
		assert(np!=0);
		//确定需复制元素个数，复制元素
		unsigned n=num<=size?num:size;
		for(int i=0;i<n;i++)
			np[i]=data[i];
		delete[]data;
		size=num;
		data=np;
	}
	return size;
}
//---------------------------------------------
template<class T>unsigned vector<T>::setsize(unsigned num,T initvalue)
{
	if(size!=num)
	{//分配新存储区
		T * np=new T[num];
		assert(np!=0);
		//确定需复制元素个数，复制元素
		unsigned n=num<=size?num:size;
		for(int i=0;i<n;i++)
			np[i]=data[i];
		if(num>size)
			for(;k<num;k++)
				np[k]=initvalue;
		delete[]data;
		size=num;
		data=np;
	}
	return size;
}
//---------------------------------------------
template<class T>vector<T> & vector<T>::operator =(const vector<T> &r)
{
	if(size!=r.size)
	{//如果大小不匹配
		T * np=new T[r.size];
		assert(np!=0);
		delete[]data;
		size=r.size;
		data=np;
	}
	for(int i=0;i<size;i++)
		data[i]=r.data[i];
	return *this;
}

//----------------------------------------------------------iterator类定义
template<class T>
class iterator{
public:
	//对循环做初始化
	virtual int init()=0;
	//检查是否还有元素
	virtual int operator!()=0;
	//访问当前元素
	virtual T operator()()=0;
	//访问下一个元素
	virtual int operator++()=0;
	//改变当前元素
	virtual void operator=(T newvalue)=0;
};

//---------------------vectoriterator类定义
template<class T>
class vectoriterator:public iterator<T>
{
public:
	//构造函数
    vectoriterator(vector<T>&);
    vectoriterator(const vectoriterator &);
	//实现遍历器原型操作
	virtual int init();                   //到达第一个遍历位置
	virtual T operator()();                 //取当前位置上的元素
	virtual int operator!();                //测试遍历是否结束
	virtual int operator++();                //到下一个遍历位置
	virtual void operator=(T newvalue);        //赋值给当前位置上的元素
	//向量遍历器自己的新操作
	int operator--();                          //游标反向移动
	int key();                                   //返回当前访问元素的下标
protected:
	//数据成分
	unsigned currentkey;                         //游标，当前停在哪个元素上
    vector<T>& data;
};

//------------------------------------
template<class T>
vectoriterator<T>::vectoriterator(vector<T>& v):data(v)
{//建立和初始化向量遍历器
	init();
}
//--------------------------------------
template<class T>
vectoriterator<T>::vectoriterator(const vectoriterator & x):
    data(x.data),currentkey(x.currentkey){}
//-----------------------------------------
template<class T>
int vectoriterator<T>::init()
{
    currentkey=0;
	return operator!();
}
//-------------------------------------
template<class T>
T vectoriterator<T>::operator()()
{
	//返回当前项的值
	return data[currentkey];
}
//----------------------------------------
template<class T>
int vectoriterator<T>::operator !()
{
	return currentkey<data.length();
}
//--------------------------------------
template<class T>
int vectoriterator<T>::operator ++()
{
	//将游标值加1
    currentkey++;
	return operator!();
}
//-----------------------------------------
template<class T>
void vectoriterator<T>::operator =(T newvalue)
{
	//改变当前项的值
	data[currentkey]=newvalue;
}
//------------------------------------------
template<class T>
int vectoriterator<T>::operator --()
{
	//将游标反向移动一个位置
	if(currentkey>0)currentkey--;
	return operator!();
}
//-----------------------------------------
template<class T>
int vectoriterator<T>::key()
{
	return currentkey;
}

//*****************************************************matrix
template<class T>class matrix
{
public:
   matrix(unsigned numberrows,unsigned numberofcolumns);   
   matrix(unsigned numberrows,unsigned numbercolumns,T init);
   ~matrix();
   vector<T>& operator[](unsigned index)const;
   int numberrows()const;   
   int numbercolumns()const;
private:
	vector<vector<T>*>rows;
};

template<class T>matrix<T>::matrix(unsigned numberrows,unsigned numbercolumns):rows(numberrows)
{
	for(unsigned i=0;i<numberrows;i++)
	{
		rows[i]=new vector<T>(numbercolumns);
		assert(rows[i]!=0);
	}
}

template<class T>matrix<T>::matrix(unsigned numberrows,unsigned numbercolumns,T init)
:rows(numberrows)
{
	for(unsigned i=0;i<numberrows;i++)
	{
		rows[i]=new vector<T>(numbercolumns,init);
		assert(rows[i]!=0);
	}
}

template<class T>matrix<T>::~matrix()
{
	unsigned max=rows.length(),i;
    vector<T>*p;
	for(i=0;i<max;i++)
	{
		p=rows[i];
		rows[i]=0;
		delete p;
	}
}

template<class T>int matrix<T>::numberrows()const
{
	return rows.length();
}

template<class T>int matrix<T>::numbercolumns()const
{
	return rows[0]->length();
}

template<class T>vector<T>& matrix<T>::operator [](unsigned index)const
{
	return * rows[index];
}

//***************************************************************
template<class T>
class list;
template<class T>
class listiterator;

//*************************************************************link
template<class T>
class link
{
public:
	//插入一个新结点
	link<T>*insert(T val);
	//构造函数
	link(T linkvalue,link<T>* np);
	link(const link<T>& s);
	//复制
    link<T>* duplicate()const;
    friend class list<T>;
    friend class listiterator<T>;
//private:	
    T value;
	link<T>* ptrtonextlink;
};
//--------------------------------------------------------------------
template<class T>
link<T>*link<T>::insert(T val)
{
    ptrtonextlink=new link<T>(val,ptrtonextlink);
    assert(ptrtonextlink!=0);
    return ptrtonextlink;
}

//------------------------------
template<class T>
link<T>::link(T val,link<T>* nxt)
:value(val),ptrtonextlink(nxt){}

//-------------------------------
template<class T>
link<T>::link(const link<T>& s)
:value(s.value),ptrtonextlink(s.ptrtonextlink){}

//------------------------------------
template<class T>
link<T>*link<T>::duplicate()const
{
    link<T>* newlink;
    if(ptrtonextlink!=0)             //当还有下一个结点时递归调用复制函数
    newlink=new link<T>(value,ptrtonextlink->duplicate());
    else
    newlink=new link<T>(value,0);
    assert(newlink!=0);              //检查动态分配是否成功
    return newlink;
}

//*********************************************************list
template<class T>
class list
{
public:
    list();
    list(const list<T> &);
    virtual  ~list();
    virtual  void  add(T );              //在第一个结点前插入一个新结点
    virtual  void  deleteallvalues();    //删除所有结点
    T  firstelement( )const;             //返回第一个结点值
    virtual  int  includes(T)const;      //查找某一个结点
    int  isempty()const;                 //判断表空
    virtual  void  removefirst();        //删除第一个结点
    list<T> *duplicate()const;           //复制整个表
	friend class listiterator<T>; 
//protected:
    link<T>* ptrtofirstlink;             //指向第一个结点的地址
};

//-------------------------------------------------------
template<class T>list<T>::list():ptrtofirstlink(0){}

//--------------------------------------------------
template<class T> list<T>::list(const list<T>&source)
{  
	if(source.isempty())
      ptrtofirstlink=0;
    else
	{
		link<T>*firstlink=source.ptrtofirstlink;
        ptrtofirstlink=firstlink->duplicate();
	}
}

//--------------------------------------------
template<class T> list<T>::~list()
{
	deleteallvalues();
}

//---------------------------------------------------------
template<class T>void list<T>::add(T val)
{
	ptrtofirstlink=new link<T>(val,ptrtofirstlink);
    assert(ptrtofirstlink!=0);
}

//-----------------------------------------------------
template<class T>void list<T>::deleteallvalues()
{
	link<T>*next;
    for(link<T>*p=ptrtofirstlink;p!=0;p=next)
	{
		next=p->ptrtonextlink;
        p->ptrtonextlink=0;
        delete p;
	}
    ptrtofirstlink=0;
}

//---------------------------------------------------------
template<class T>T list<T>::firstelement()const
{
	assert(ptrtofirstlink!=0);
	return ptrtofirstlink->value;
}

//-------------------------------------------------------
template<class T>int list<T>::includes(T v)const
{
	for(link<T>*p=ptrtofirstlink;p;p=p->ptrtonextlink)
       if(v==p->value)
		   return 1;
               return 0;
}

//-------------------------------------------------------
template<class T>int list<T>::isempty()const
{
	return ptrtofirstlink==0;
}

//-------------------------------------------------------
template<class T>void list<T>::removefirst()
{	
	assert(ptrtofirstlink!=0);
    link<T>*p=ptrtofirstlink;
    ptrtofirstlink=p->ptrtonextlink;
    delete p;
}

//------------------------------------------------------
template<class T>list<T>* list<T>::duplicate()const
{
	list<T>*newlist=new list<T>;
    assert(newlist!=0);
    if(ptrtofirstlink)
      newlist->ptrtofirstlink=ptrtofirstlink->duplicate();
    return newlist;
}

//***************************************
template<class T> class stack
{
public:
	virtual void deleteallvalues()=0;
    virtual int isempty()const=0;
    virtual T pop()=0;
    virtual void push(T value)=0;
    virtual T top()const=0;
};

//**************************************************************stacklist
template<class T> class stacklist:public stack<T>
{
public:
    //构造函数
    stacklist();
    stacklist(const stacklist & v);
    //栈操作
    virtual void deleteallvalues();
    virtual int isempty()const;
    virtual T pop();
    virtual void push(T value);
    virtual T top()const;
protected:
	//数据域
    list<T> data;
};

template<class T> 
stacklist<T>::stacklist():data(){}