2.cpp

来自「（1）构造一个空的串算法实现 (2) 利用C++串构造堆串算法 (3) 堆串」· C++ 代码 · 共 233 行

#include<iostream.h>
#include<iomanip>
#include<cstring>


template<class T>
class String
{
public:
	String();   // 构造一个空的字符串
	String(T *str);   //用C++串构造字符串
	String(String &ob);  //用串对象构造字符串
	int Length();   //求字符串的长度
	friend int Stringcmp(String<T> &s1,String<T> &s2);  //两个字符串的比较
	String<T> Substring(int i,int len);    //求子串
	String<T> Strconcat(String<T> &s1);  // 两个字符串的连接
	String<T> Destring(int i,int len);   //串的删除
	friend ostream &operator<<(ostream &stream,String<T> &ob);   //串的输出
	friend istream &operator>>(istream &stream,String<T> &ob);   //串的输入
	void Clearstring();    //清空串
	int bf_index(const String<T> &T,int pos);
	int kmp_index(const String<T> &T,int pos);
	void getnext(const String<T> &T,int *next);
private:
	int length;
	T *s;
};
template<class T>
String<T>::String()
{
	length=1;
	s=new T[length];
	if(s==NULL)
	{
		cerr<<"分配错误 !"<<endl;
		exit(1);
	}
	*s='\0';
}
template<class T>
String<T>::String(T *str)
{
	int i=0;
	while(str[i]!='\0')
		i++;
	length=i;
	s=new T[length+1];
	if(s==NULL)
	{
		cerr<<"分配错误!"<<endl;
		exit(1);
	}
	for(i=0;i<=length;i++)    //一种实现
		s[i]=str[i];
}
template<class T>
String<T>::String(String &ob)
{
	length=ob.length;
	s=new T[length+1];
	if(s==NULL)
	{
		cerr<<"分配错误!"<<endl;
		exit(1);
	}
	strcpy(s,ob.s);  //另外一种实现,需引入#include<cstring>
}
template<class T>
int String<T>::Length()
{
	if(!s) throw "字符串不存在!";
	return length;
}
template<class T>
int Stringcmp(String<T> &s1,String<T> &s2)
{
	for(int i=0;i<s1.length && i<s2.length;i++)
		if(s1.s[i]!=s2.s[i])  
			return s1.s[i]-s2.s[i];
		return s1.length-s2.length;
}
template<class T>
String<T> String<T>::Substring(int i,int len) //将串s从i位开始，连续取len位的子串。
{
    if(i<1 || i>length || len<=0 || len> length-i+1)
	  throw "i不合法！"; 
    String<T> ob;
      ob.length=len;
      ob.s=new T[len+1];
      for(int j=i;j<=i+len-1;j++)
	       ob.s[j-i]=s[j-1];
      ob.s[ob.length]='\0';
      return ob;
}
template<class T>
String<T> String<T>::Strconcat(String<T> &s1)
{
  int L;T *s3;
  L=length+s1.length;
  s3=new T[L+1];
  for(int i=0;i<length;i++)
	  s3[i]=s[i];
  for(i=0;i<=s1.length;i++)
	  s3[length+i]=s1.s[i];
  delete []s;
  s=s3; length=L;
  return s3;
}
template<class T>
String<T> String<T>::Destring(int i,int len)
{
    if (i<1 || i>length||len<=0 || len> length-i+1)
	  throw "i或length不合法！";
	String<T> ob;
    ob.length=length-len;
    ob.s=new T[ob.length+1];
    for(int k=0;k<=i-2;k++)
	  ob.s[k]=s[k];
    for(int j=i+len-1;j<=length;j++,k++)//从第i+len位开始，到串尾复制到s1串中
	  ob.s[k]=s[j];
	delete []s; 
    return ob;
}
template <class T>
ostream &operator<<(ostream &stream,String<T> &ob) //字符串输出流重载
{
	 stream<<ob.s;
	 return stream;
}
template <class T>
istream &operator>>(istream &stream,String<T> &ob)//把输入流赋给串对象ob
{
	  char c[255];
	  int len;
	for(len=0;len<254;len++)
	  { 
		stream.get(c[len]);
	      if(c[len]=='\n')break;
		 if(c[len]=='\b') 
		if(len!=0)  
		{
			len--;		
			cout<<"'\b'";
		}
	  }
	c[len]='\0';
	if(ob.length)
	 {
		 delete ob.s;
	 }
	ob.s=new char[len+1];
	if (ob.s==NULL)
	{
		cout<<"分配失败！"<<endl;
		exit(1);
	}
	ob.length=len;
	for(int i=0;i<=len;i++)
		 ob.s[i]=c[i]; 
	 return stream;
}
template <class T>
void String<T>::Clearstring() //清空串  
{
    if(s) {delete [] s;}
    length=0;
}
template <class T>
int String<T>::bf_index(const String<T> &T,int pos)
{ 
    if (pos<1||pos>length) throw "pos不合法！";
    int i=pos,j=1;   
    while (i<=length && j<=T.length)
    {
         if (s[i-1]==T.s[j-1]) 
		 {
             i++;   j++;
         }  
         else 
		 {
             i=i-j+2;    j=1;//回溯
         }   
     }
     if(j>T.length) return(i-j+1);   
     else return 0;
}
template<class T> 
int String<T>::kmp_index(const String<T> &T,int pos)
{
	int *next=new int[T.length];
	getnext(T,next);
	int i=pos-1,j=0;
	while(i<length && j<T.length) 
	{
          if (j==-1 || s[i]==T.s[j] ) {++i;++j;} 
          else {j=next[j];}     
    }
     if(j>=T.length) 
         return i-T.length+1; 
     else return 0;
}
template <class T>
void String<T>::getnext(const String<T> &T,int *next)
{	
	int i=0,j=-1;
	next[i]=-1;
	while(i<T.length)
	{
         if(j==-1||T.s[i]==T.s[j])
 		  {
			  i++;
			  j++;
			  next[i]=j;
		  }
		  else j=next[j];
	}
}

int main()
{
	String<char> s1("Hello world!"),s2("eeeewre Hello world!fdf"),s3("I have a dream!"),s4(s2);	
	cout<<s2.bf_index(s1,1)<<endl;
	cout<<s2.kmp_index(s1,1)<<endl;
	cout<<"字符串长度为："<<s1.Length()<<endl;
	cout<<"两字符比较后:"<<Stringcmp(s1,s2)<<endl;
	cout<<"s1从第7位开始，连续取5位的子串为:"<<s1.Substring(7,5)<<endl;
	cout<<s1.Strconcat(s3)<<endl;
	cout<<"s4从第4位开始，删除3位后为:"<<s4.Destring(4,3)<<endl;
	s1.Clearstring();
	return 0;
}