vector.cpp

包含字符串处理

#include<iostream.h>
#include<assert.h>
#include<cmath>
#include <stdlib.h>
#include<time.h>
char nothing;
unsigned j=0;


unsigned cstrLen(const char str[])
{
	unsigned i=0;
	while(str[i]!='\0')i++;
	return i;
}
template<class  t>class  link;
template<class  t>class  listiterator;
class substring;
class string
{
public:
	string();
	string(char);
	string(unsigned);
	string(const char *);
	string(const string &);
	~string();
    friend class substring;
	void operator = (const string & right);
	void operator += (const string &v);
	friend string operator+(const string &left,const string &right);
	friend string operator*(const string &left,const int right);
	friend void operator-(const string &left,const string &right);
	/////////////////////////////////////////////////////////////////////
	friend int operator>(const string &left,const string &right);
	friend int operator>=(const string &left,const string &right);
	friend int operator==(const string &left,const string &right);
	friend int operator<(const string &left,const string &right);
	friend int operator<=(const string &left,const string &right);
	friend int operator!=(const string &left,const string &right);
	//////////////////////////////////////////////////////////////////
	void replace(string &base,string pattern,string rp);
	int compare(const string & val)const;
	friend int change(const string &str);
	substring operator()(unsigned start,unsigned len);
	istream & getline(istream &);
	friend istream &operator>>(istream& cin,string& s);

	unsigned length()const;
	char & operator[](unsigned index)const;
	operator	const char *()const
	{
		return buffer;
	}
private:
	unsigned buflen;
	char *buffer;
};
//////////////////////////////////////////////////////
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 char *inittext)
{
	buflen=1+cstrLen(inittext);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;inittext[i]!='\0';i++)
		buffer[i]=inittext[i];
	
	buffer[i]='\0';
}
string::string(const string &initstr)
{
	buflen=1+cstrLen(initstr.buffer);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;initstr.buffer[i]!='\0';i++)
		buffer[i]=initstr.buffer[i];
	
	buffer[i]='\0';
}
string::string(char c)
{
	buflen=2;
	buffer=new char[buflen];
	assert(buffer!=0);
	buffer[0]=c;
	buffer[1]='\0';
}
string::string()
{
	buflen=1;
	buffer=new char[buflen];
	assert(buffer!=0);
	buffer[0]='\0';
}
string::~string()
{
	delete[]buffer;
	buffer=0;
}
/*void getCommand()
{
int i;
string prompt="command>";
double x;

}*/
unsigned string::length()const
{
	return cstrLen(buffer);
}
int string::compare(const string & val)const
{
	char *p=buffer;
	char *q=val.buffer;
	for(;(*p!='\0')&&(*p==*q);p++,q++)
		;
	return *p-*q;
}///////////////////////////////////////////////对运算的定义
void string::operator = (const string & right)
{
	const unsigned rightLength=right.length();
	if(right.length()>=buflen)
	{
		delete[]buffer;
		buflen=1+rightLength;
		buffer=new char[buflen];
		assert(buffer!=0);
	}
	for(unsigned i=0;right.buffer[i]!='\0';i++)
		buffer[i]=right.buffer[i];
	buffer[i]='\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';
	
}
string operator+(const string &left,const string &right)
{
	string result(left);
	result+=right;
	return result;
}
string operator*(const string &left,const int right)
{
	string result(left);
	for(int j=0;j<right;j++)
		result+=left;
	return result;
	
}

void operator-(const string &left,const string &right)
{
	unsigned i;
	bool flag=false;
	for(unsigned j=0;j<left.buflen;j++)
	{
		for(i=0;(right[i]!=left[j])||(right[i]='\0');j++,i++)
		{
			if(i=right.buflen-1)flag=true;
		}
	}
	if(flag)
	{
		for(unsigned k=i-right.buflen+unsigned(2);k<j;k++)
		{
			left[k]='\0';
		}
	}
}

///////////////////////////////////////////////////
char & string::operator[](unsigned index)const
{
	if(index>=cstrLen(buffer))
	{
		nothing='\0';
		return nothing;
	}
	return buffer[index];
}
////////////////////////////////////////////////////////
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;
}
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;
}
//////////////////////////////////////////////////
istream &operator>>(istream& cin,string& s)
{
	for(unsigned i=0;i<s.buflen;i++)
		cin>>s.buffer[i];
	return cin;
}
//////////////////////////////////////////////////

int isLowerCase(char c)
{
	return (c>='a')&&(c<='z');
}
///////////////////////
int isDigit(char c)
{
	return (c>='0')&&(c<='9');
}
//////////////////////////////
int isAlphabetic(char c)
{
	return((c>='a')&&(c<='z'))||((c>='A')&&(c<='Z'));
}
//////////////////////////
int isAlphnumber(char c)
{
	return((c>='a')&&(c<='z'))||((c>='A')&&(c<='Z'))||((c>='0')&&(c<='9'));	
}
//////////////////////////
void toUpper(string &word)
{
	for(unsigned i=0;word[i]!='\0';i++)
		if(isLowerCase(word[i]))
			word[i]=(word[i]-'a')+'A';
}
int change(const string &str)
{		
	int a[10];
	int r=0;
	for(unsigned j=0,i=0;str[i]!='\0';i++)
	{
		if((str.buffer[i]>'0')&&(str.buffer[i]<'9'))
		{
			a[j]=str.buffer[i];
			j++;
		}
	}
	if(j==0)return 0;
	else for(unsigned i=0;i<j;i++)
    {
		a[i]=a[i]-48;
		int k=j;
		for(;j>1+i;j--)
		{
			a[i]=a[i]*10;
		}
		j=k;
	}
	for(i=0;i<j;i++)
		r+=a[i];
	return r;
}
/////////////////////////////////////////////////////////////////////////
void string::replace(string &base,string pattern,string rp)
{
	unsigned len=base.buflen,f=0;
	base.buflen=(base.buflen+rp.buflen-pattern.buflen);
	base=new char[base.buflen];
	for(unsigned i=0;i<base.buflen;i++)
	{
		for(unsigned j=0;(base[i]=pattern[j])&&(j<pattern.buflen);i++,j++)
			;
		
	}
}
///////////////////////////////////////////////////////////////////////子串类
class substring
{
public:
	substring(string& b,unsigned s,unsigned l):base(b),start(s),len(l){}
	substring(const substring & source):base(source.base),start(source.start),len(source.len){}
	operator string()const;
	void operator =(const string&);
private:
	string& base;
	const unsigned start,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::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;
}
/////////////////////////////////////////////////////////
void substring::operator =(const string& str)
{
	unsigned slen = str.length(),i,j;
	if (slen == len)
		for(i = 0;i < len;i++)
			base[start+i] = str[i];
		else
		{
			unsigned blen = base.length();
			int newbuflen = blen + slen - len + 1;
			char* newbuffer = new char[newbuflen];
			for(i = 0;i < start;i++)
				newbuffer[i] = base[i];
			for(i = 0;i < slen;i++)
				newbuffer[start+i] = str[i];
			for(j = start+len;base[j]!='\0';i++,j++)
				newbuffer[start+i] = base[j];
			newbuffer[start+i] = '\0';
			base.buflen = newbuflen;
			delete[] base.buffer;
			base.buffer = newbuffer;
			
		}
}
/////////////////////////////////////////////////////////////////////////向量类的定义及其成员函数的定义

template<class t>class vector
{
public:
	vector()
	{size=(unsigned)0;data=NULL;}
	vector(unsigned numelements);
	vector(unsigned numelements,t initvalue);
	vector(const vector<t>&source);
	virtual~vector();

	t& operator[](unsigned index)const;

	vector<t>&  operator=(const vector<t>&);
	unsigned length()const;
	void grow(unsigned len)
	{size=size+len;}
	void shrink(unsigned len)
	{size=size-len;}
	friend ostream& operator<<(ostream &cout,vector<t>& v);
	unsigned setsize(unsigned unmofelements);
	unsigned setsize(unsigned numofelements,t initvalue);
	
protected:
	t*data;
	unsigned size;
};
template<class t>ostream& operator <<(ostream &cout,vector<t>& v)
{
	for(unsigned i=0;i<v.length()-1;i++)
		cout<<v[i]<<" ";
	cout<<v[v.length()-1]<<endl;
	return cout;
}

template<class t>vector<t>::vector(unsigned num):size(num)
{
	data=new t[size];
	assert(data!=0);
}

template<class t>vector<t>::vector(unsigned num, t v):size(num)
{
	data=new t[size];
	assert(data!=0);

	for(unsigned 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(unsigned i=0;i<n;i++)
			np[i]=data[i];
		delete[]data;
		size=num;
		data=np;
	}
	return size;
}

template<class t>vector<t>&vector<t>::operator =(const vector<t>&right)
{
	if(size!=right.size)
	{
		t*np=new t[right.size];
		assert(np!=0);

		delete[]data;

		size=right.size;
		data=np;
	}
	for(int i=0;i<size;i++)
		data[i]=right.data[i];
	return *this;
}

///////////////////////对不同长度的单词做计数

void wordlengthfreq(vector<int>&counts)
{
	const int lengthmax=counts.length();
	int len;
	string word;

	while(cin>>word)
		if((len=word.length())<lengthmax)
			counts[len]++;
		else
			counts[0]++;
}

////////////////////////向量遍历器及其成员函数的定义

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;
};

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>int vectoriterator<t>::init()
{
	currentkey=0;
	return operator!();
}

template <class t>vectoriterator<t>::vectoriterator(const vectoriterator<t>& x):data(x.data),currentkey(x.currentkey){}

template<class t>int vectoriterator<t>::operator !(){return currentkey<data.length();}

template<class t>int vectoriterator<t>::operator ++()
{
	currentkey++;
	return operator!();
}

template<class t>t vectoriterator<t>::operator ()(){return data[currentkey];}

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;}
template<class t>class orderedvectoriterator:public vectoriterator<t>
{
public:
		orderedvectoriterator(vector<t>&x);

};
template<class t>orderedvectoriterator<t>::orderedvectoriterator(vector<t>&x):vectoriterator<t>(x.data){}
////////////////////////////////////////////////////////////////////有序向量及其成员函数的定义
template<class t>class orderedvector
{
public:
	orderedvector();
	orderedvector(unsigned len);
	orderedvector(const orderedvector<t>& v);
	t&operator[](unsigned int index)const;
	void add(t value);
	void deleteallvalue();
	int includes(t value)const;
	int isempty()const;
	void remove(t value);
	unsigned int binarysearch(t value);
	friend istream& operator>>(istream &cin,orderedvector<t>& v);
	friend ostream& operator<<(ostream &cout,orderedvector<t>& v);
private:
	vector<t> date;
};
template<class t>istream& operator >>(istream &cin,orderedvector<t>& v)
{
	for(unsigned i=0;i<v.date.length();i++)
		cin>>v[i];
	return cin;
}
template<class t>ostream& operator <<(ostream &cout,orderedvector<t>& v)
{
		assert(0<v.date.length());
	for(unsigned i=0;i<v.date.length();i++)
		cout<<v[i]<<" ";
	cout<<endl;
	return cout;
}
template<class t>t& orderedvector<t>::operator [](unsigned index)const
{
	assert(index<date.length());
	return date[index];
}
template<class t>
orderedvector<t>::orderedvector()
{
	date.setsize(0);
}
template<class t>
orderedvector<t>::orderedvector(unsigned len)
{
	date.setsize(len);
}
template<class t>
orderedvector<t>::orderedvector(const orderedvector<t>& v)
{
	date.setsize(v.length());
	for(unsigned i=0;i<v.length();i++)
		date[i]=v[i];
}
template<class t>
void orderedvector<t>::deleteallvalue()
{
	date.setsize(0);
}
template<class t>int orderedvector<t>::isempty()const
{
	return date.length()==0;
}
template<class t>
unsigned int orderedvector<t>::binarysearch(t)
{
	int a=0;
	unsigned int low=0;
	unsigned int high=date.length();
	while(low<high)
	{
		unsigned int mid=(high+low)/2;
		if(date[mid]==value)return mid;
		else if(date[mid]<value)
			low=mid+1;
		else high=mid;
		a++;
	}
	cout<<a<<endl;
	return low;
}
template<class t>
int orderedvector<t>::includes(t value)const
{
	unsigned int index=binarysearch(value);
	if((index<date.length())&&(value==date[index]))
		return 1;
	return 0;
}
template<class t>void orderedvector<t>::add(t value)