校园导游图.cpp

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

#include <iostream.h>
#include <stdio.h>  //C输出
#include<fstream.h>  //文件读入读出
#include<assert.h>
#include<math.h>


//----------------------------------------string主串类
class string{
public:
	//构造函数
	string();
    string(char);    //一个字符
    string(unsigned);           //存储空间大小
	string(const char *);       //一个字符串
    string(const string &);     //函数参数值返回
	~string();                  //析构函数    
	friend class substring;     //子串
	//串赋值
	void operator=(const string &r);        
	void operator=(const char right);
	void operator=(const char *r1);
	string operator+(const string & right);
	string operator+(const char right);
	friend string operator+(const char left,const string & right);
	void operator*(const int);
	//比较
    friend int operator ==(const string &,const string &);
    friend int operator !=(const string &,const string &);
    friend int operator >(const string &,const string &);
    friend int operator <(const string &,const string &);
    friend int operator >=(const string &,const string &);
    friend int operator <=(const string &,const string &);
    //串连接
	void operator+=(const string &v);
	//串输出输入
    friend ostream & operator<<(ostream & out,const string & s);
    istream & getline(istream &);
	//取子串
    substring operator()(unsigned start,unsigned len);
	//字符串长度
	unsigned length()const;
	//访问单个字符
	char &operator[](unsigned index)const;
	//字符串比较
    int compare(const string &)const;
	//转换
	operator const char *()const;
private:
	unsigned buflen;          //堆空间长度
	char * buffer;            
};

//----------------------------------串长度
unsigned cstrlen(const char str[])
{
	unsigned i=0;
	while(str[i]!='\0')i++;
	return i;
}

//---------------------------构造函数定义
string::string()
{
	buflen=1;
	buffer=new char[buflen];
	assert(buffer!=0);
    buffer[0]='\0';
}
string::string(char c){
    buflen=2;
	buffer=new char[buflen];
	assert(buffer!=0);
    buffer[0]=c;
	buffer[1]='\0';
}
string::string(unsigned size)
{
	assert(size>=0);
	buflen=1+size;
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;i<buflen;i++)
		buffer[i]='\0';
}
string::string(const string & str){
 	buflen=1+cstrlen(str.buffer);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;str.buffer[i]!='\0';i++)
		buffer[i]=str.buffer[i];
	buffer[i]='\0';
}  
string::string(const char * text)
{
	buflen=1+cstrlen(text);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;text[i]!='\0';i++)
	buffer[i]=text[i];
	buffer[i]='\0';
}
//----------------------------------------析构函数定义
string::~string()
	{
	delete[]buffer;
	buffer=0;
}
//------------------------------------------大小写转换
int isbig(char c)
{
	return (c>='A')&&(c<='Z');
}
void tosmall(string & word)
{
	for(unsigned i=0;word[i]!='\0';i++)
       if(isbig(word[i]))
		   word[i]=(word[i]-'A')+'a';
}
//---------------------------------------整数与字符串相乘
void string::operator*(const int k){
   for(int j=0;j<k;j++){
	for(unsigned i=0;buffer[i]!='\0';i++)
		cout<<buffer[i];}
}

//----------------------------------下标运算符重载
char nothing;
char & string::operator [](unsigned index)const
{
	if(index>=cstrlen(buffer))
	{
		nothing='\0';
		return nothing;
	}
	return buffer[index];
}
//串长度
unsigned string::length()const
{
	return cstrlen(buffer);
}
//-----------------------------------------运算符重载
void string::operator=(const string &r){
	string temp(r);
	const unsigned rlength=r.length();
	if(r.length()>=buflen)
	{   
		delete[]buffer;
		buflen=1+rlength;
		buffer=new char[buflen];
		assert(buffer!=0);
	}
	for(unsigned i=0;temp.buffer[i]!='\0';i++)
		buffer[i]=temp.buffer[i];
	buffer[i]='\0';
}

void string::operator=(const char right){
	buffer[0]=right;
	buffer[1]='\0';
}

void string::operator=(const char *r1){
	const unsigned rlength=cstrlen(r1);
	if(cstrlen(r1)>=buflen)
	{
		delete[]buffer;
		buflen=1+rlength;
		buffer=new char[buflen];
		assert(buffer!=0);
	}
	for(unsigned i=0;r1[i]!='\0';i++)
		buffer[i]=r1[i];
	buffer[i]='\0';
}

string string::operator+(const string & right){
	string left;
	left+=right;
	return left;
}
string string::operator+(const char right){
	string left;
	left=*this+right;
	return left;
}

string operator+(const char left,const string & right){
	string result(left);
	result+=right;
	return result;
}

string::operator const char *()const{
	return buffer;
}

int operator==(const string & left,const string & right){
	int result=left.compare(right);
	if(result==0)return 1;
	else return 0;
}
int operator!=(const string & left,const string & right){
	int result=left.compare(right);
	if(result!=0)return 1;
	else return 0;
}
int operator >(const string & left,const string & right){
	return left.compare(right)>0;
}
int operator <(const string & left,const string & right){
	return left.compare(right)<0;
}
int operator >=(const string & left,const string & right){
	return left.compare(right)>=0;
}
int operator <=(const string & left,const string & right){
	return left.compare(right)<=0;
}
//---------------------------------------------串连接
void string::operator+=(const string &v){
    unsigned i;
	unsigned conlen=length()+v.length();
	if(conlen>=buflen)
	{
		char *newbuf=new char[1+conlen];
		assert(newbuf!=0);
		for(i=0;buffer[i]!='\0';i++)
			newbuf[i]=buffer[i];
		delete[]buffer;
		buflen=1+conlen;
		buffer=newbuf;
	}
	else
		i=cstrlen(buffer);
	for(unsigned j=0;v.buffer[j]!='\0';i++,j++)
		buffer[i]=v.buffer[j];
	buffer[i]='\0';
}
//----------------------------------------------串比较
int string::compare(const string & val)const
{
	char *p=buffer;
	char *q=val.buffer;
	for(;(*p!='\0')&&(*p==*q);p++,q++)
		;
	return *p-*q;
}
//--------------------------------------------串输入输出
istream & operator>>(istream & in,string & str)
{
	char inbuffer[1000];
	if(in>>inbuffer)
		str=inbuffer;
	else 
		str="";
	return in;
}

istream & string::getline(istream & in)
{
	in.getline(buffer,buflen,'\n');
	return in;
}

ostream & operator<<(ostream & out,const string & s){
	out<<s.buffer<<endl;
	return out;
}


//--------------------------------------------------子串类定义substring
class substring{
public:
	substring(string & base,unsigned start,unsigned len);
	substring(const substring & source);
	void operator=(const string &)const;
	operator string()const;
private:
	string & base;
	const unsigned start;
	const unsigned len;
};

//---------------------------------------------------划分一个子串
substring string::operator()(unsigned start,unsigned len){
    if(start>=length()){
		start=0;
		len=0;
	}
	unsigned maxlen=length()-start;
	if(len>maxlen)len=maxlen;
	return substring(*this,start,len);
}
//--------------------------------------------------子串构造函数定义
substring::substring(string & str,unsigned s,unsigned l)
:base(str),start(s),len(l){}

substring::substring(const substring & source)
:base(source.base),start(source.start),len(source.len){}

//-------------------------------------------------子串赋值
void substring::operator=(const string & rstr)const
{
	unsigned i;
	if(len==rstr.length())
	{
		for(i=0;i<len;i++)
			base[start+i]=rstr[i];
		return;
	}
	unsigned newlen=rstr.length()+base.length()-len;
	char *newdata=new char[newlen+1];
	for(i=0;i<start;i++)
		newdata[i]=base[i];
	for(unsigned j=0;rstr[j]!='\0';j++)
		newdata[i++]=base[j];
	newdata[i]='\0';
	delete[] base.buffer;
	base.buflen=newlen;
	base.buffer=newdata;
	return;
}

substring::operator string()const{
	char *buf=new char[len+1];
	assert(buf !=0);
	for(unsigned i=0;i<len;i++)
		buf[i]=base[start+i];
	buf[len]='\0';
	string result(buf);
	delete[] buf;
	return result;
}


//------------------------------------------模式匹配类
class stringmatcher{
public:
	stringmatcher(string &t);
	virtual int init();
	int operator!()const;
    int operator++();
    substring operator()();
    unsigned position()const;
    unsigned position(unsigned p);
    unsigned length();
    friend ostream & operator<<(ostream & out,const stringmatcher & st);
protected:
	string &text;
	unsigned pos;
	unsigned patlen;
};

stringmatcher::stringmatcher(string &t):text(t)
{
	pos=0;
}

int stringmatcher::init()
{
	pos=-1;
	return operator++();
}

int stringmatcher::operator !()const
{
	return(pos>=0)&&(pos<text.length());
}

substring stringmatcher::operator ()()
{
	return text(position(),length());
}

int stringmatcher::operator++()
{
    return pos;
}

unsigned stringmatcher::position()const
{
	return pos;
}

unsigned stringmatcher::position(unsigned p)
{
	unsigned pos=p;
    return operator++();
}

unsigned stringmatcher::length()
{
	return patlen;
}

ostream & operator<<(ostream & out,const stringmatcher & st){
	out<<st.text<<endl;
	return out;
}

//简单匹配
class simplestrmatcher : public stringmatcher
{
public:
    simplestrmatcher(const string & pat,string & text);
	virtual int operator++();
private:
	const string & pattern;
};

simplestrmatcher::simplestrmatcher(const string & p,string & t):
    stringmatcher(t),pattern(p){
	patlen=p.length();
}

int simplestrmatcher::operator++(){
	unsigned last=text.length()-patlen;
	for(pos++;pos<=last;pos++)
		if((string)text(pos,patlen)==pattern)
			return 1;
		pos=-1;
		return 0;
}

//----------------------------------------KMP匹配
class KMPstrmatcher:public stringmatcher
{
public:
	KMPstrmatcher(const string &,string &);
	~KMPstrmatcher();
    virtual unsigned operator ++();
protected:
	const string & pattern;
	int * prefix;
};


KMPstrmatcher::KMPstrmatcher(const string & p,string &t)
			 :stringmatcher(t),pattern(p)
{   unsigned i=1;
    unsigned k;
	patlen=p.length();
	assert(patlen>0);
	prefix=new int[patlen];
	assert(prefix!=0);
    prefix[0]=0;
	for(;i<patlen;i++)
	{
	    k=prefix[i-1];
		while(pattern[i]!=pattern[k] && k!=0)
			k=prefix[k-1];
		if(pattern[i]==pattern[k])
			prefix[i]=k+1;
	    else	
		    prefix[i]=0;
	}
}

unsigned KMPstrmatcher::operator ++()
{
	unsigned end=text.length();
	unsigned cur=pos+1;
	unsigned patp=0;
	for(;cur<end;cur++){
		while(patp>0&&pattern[patp]!=text[cur])
			patp=prefix[patp-1];
		if(pattern[patp]==text[cur])
			if(++patp==patlen){
				pos=1+cur-patlen;
				return 1;
			}
}
        pos=-1;