用数组实现串.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

class String
{
public:
	//构造函数		
	String(char *s="");
	String(const String& s);
	//析构函数
	~String();
	//赋值运算
	String& operator=(const String& s);
	//关系运算
	bool operator==(const String& s) const;
	//串长运算
	int Length() const;
	//串接运算
	String operator+(const String& s) const;
	void operator+=(const String& s);
	//查找字符运算
	int Find(char c,int start) const;
	//子串运算
	String SubStr(int index,int count) const;
	//插入运算
	void Insert(const String& s,int index);
	//删除运算
	void Delete(int index, int xount);
	//读入字符串
    int ReadString(istream& is=cin,char delimiter='\n');
    //其他串运算
	void Prefix();
	void ModifiedPrefix();
	int Match(String& t);
private:
	char *str;//串数组
	int *pre;//前缀函数数组
	int size;//串长
};

String::String(char *s)
{
	//串尾有一个空字符
	size=strlen(s)+1;
	str=new char[size];
	if(str==0) out<<"it is wrong";
	strcpy(str,s);
	pre=new int[size];
	if(pre==0) out<<"it is wrong";
}

String::String(const String& s)
{
	//复制构造函数
	size=s.size;
	str=new char[size];
	if(str==0) out<<"it is wrong";
	strcpy(str,s.str);
	pre=new int[size];
	if(pre==0) out<<"it is wrong";
}

String::~String()
{
	delete[] str;
	delete[] pre;
}

bool String::operator==(const String& s) const
{
	return strcmp(str,s.str)==0;
}

int String::Length() const
{
	return size-1;
}

String String::operator+(const String& s) const
{
	String temp;
	int n;
	delete[] temp.str;
	n=size+s.size-1;
	temp.str=new char[n];
	if(temp.str==0) out<<"it is wrong";
	temp.size=n;
	strcpy(temp.str,str);
	strcat(temp.str,s.str);
	return temp;
}

void String::operator+=(const String& s)
{
	char *tempstr;
	int n;
	n=size+s.size-1;
	tempstr=new char[n];
	if(tempstr==0) out<<"it is wrong";
	strcpy(tempstr,str);
	strcat(tempstr,s.str);
	delete[] str;
	str=tempstr;
	size=n;
}

int String::Find(char c,int start) const
{
	int ret;
	char *p;
	p=strchr(&str[start],c);
	if(p!=0) ret=int(p-str);
	else ret=-1;
	return ret;
}

String String::SubStr(int index,int count) const
{
	int Left=size-index-1,i;
	String temp;
	char *p,*q;
	if(index>=size-1) return temp;
	if(count>Left) count=Left;
	delete[] temp.str;
	temp.str=new char[count+1];
	if(temp.str==0) out<<"it is wrong";
	for(i=0,p=temp.str,q=&str[index];i<count;i++)
		*p++=*q++;
	*p=0;
	temp.size=count+1;
	return temp;
}

void String::Insert(const String& s,int index)
{
	int n,m=s.size-1,i;
	char *newstr,*p,*q;
	n=size+m;
	newstr=new char[n];
	if(newstr==0) out<<"it is wrong";
	for(i=0,p=newstr,q=str;i<=index-1;i++)
		*p++=*q++;
	strcpy(p,s.str);
	p+=m;
	strcpy(p,&str[index]);
	delete [] str;
	size=n;
	str=newstr;
}

void String::Delete(int index, int count)
{
	int Left=size-index-1,n,i;
	char *newstr,*p,*q;
	if(index>=size-1) return ;
	if(count>Left) count=Left;
	n=size-count;
	newstr=new char[n];
	if(newstr==0) out<<"it is wrong";
	for(i=0,p=newstr,q=str;i<=index-1;i++)
		*p++=*q++;
	q+=count;
	strcpy(p,q);
	delete[] str;
	size=n;
	str=newstr;
}
int String::ReadString(istream& is,char delimiter)
{
	char tmp[256];
	if(is.getline(tmp,256,delimiter))
	{
		delete[]str;
		size=strlen(tmp)+1;
		str=new char[size];
		if(str==0) out<<"it is wrong";
		strcpy(str,tmp);
		return size-1;
	}
	else return -1;
}
void String::Prefix()
{
	int m=Length();
	delete [] pre;
	pre=new int [m+1];
	if(pre==0) out<<"it is wrong";
	pre[1]=0;
	int k=0;
	for(int i=2;i<=m;i++)
	{
		while((*(str+i-1)!=*(str+k))&&(k>0)) k=pre[k];
		if(*(str+i-1)==*(str+k)) pre[i]=++k;
		else pre[i]=0;
	}
}


int String::Match(String& t)
{
	int i=0,j=0;
	int n=Length(),m=t.Length();
	t.Prefix();
	while((i<n)&&(j<m))
		if(str[i]==t.str[j])
		{
			i++;
			j++;
		}
		else
			if(j==0) i++;
			else j=t.pre[j];
		if(j<m) return j;
		else return i-m+1;
}

int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		out<<"the input.txt is not exist";
		exit(1);
	}
	ofstream out("output.txt");
}