astring.cpp

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#include"AString.h"
#include<iostream>
using namespace std;


AString::AString(int sz) {
	//构造函数：创建一个空串
	maxSize = sz;
	ch = new char[maxSize+1];        //创建串数组
	if (ch == NULL) 
	{ cerr << "存储分配错!\n";  exit(1); }
	curLength = 0;       
	ch[0] = '\0';
};
;
AString::AString(const char *init) {
	//复制构造函数: 从已有字符数组*init复制
	int len = (int)strlen(init);
	maxSize = (len > defaultSize) ? len : defaultSize;
	ch = new char[maxSize+1];     //创建串数组
	if (ch == NULL)
	{ cerr << "存储分配错 ! \n";  exit(1); }
	curLength = len;	 	   //复制串长度
	strcpy(ch,init);	             //复制串值	
};
AString :: AString(const AString& ob) {
	//复制构造函数：从已有串ob复制
	maxSize = ob.maxSize;               //复制串最大长度
	ch = new char[ob.curLength+1];     //创建串数组
	if (ch == NULL) 
	{ cerr << "存储分配错! \n";  exit(1); }
	curLength = ob.curLength;          //复制串长度
	strcpy(ch, ob.ch);                         //复制串值
};	
AString  AString::operator () (int pos, int len) {
	//从串中第 pos 个位置起连续提取 len 个字符形成
	//子串返回 	
	AString  temp;                           //建立空串对象
	if (pos >= 0 && pos+len-1 < maxSize && len > 0)
	{                                                  //提取子串

		if (pos+len-1 >= curLength)  
			len = curLength - pos;     //调整提取字符数
		temp.curLength = len;           //子串长度
		for (int i = 0, j = pos; i < len; i++, j++) 
			temp.ch[i] = ch[j];        //传送串数组
		temp.ch[len] = '\0';           //子串结束
	}

	return  temp;
};	
AString& AString::operator = (const AString& ob) {
	if (&ob != this) {	//若两个串相等为自我赋值
		delete []ch; 
		ch = new char[maxSize+1];	//重新分配 
		if (ch == NULL) 
		{ cerr <<"存储分配失败!\n ";  exit(1); }
		curLength = ob.curLength;  strcpy(ch,ob.ch);
	}
	else cout << "字符串自身赋值出错!\n";	
	return *this;
}; 
char& AString::operator [ ] (int i) {
	//串重载操作：取当前串*this的第i个字符
	if (i < 0 && i >= curLength) 
	{ cout << "字符串下标超界!\n "; exit(1); } 
	return ch[i];
};
AString& AString::operator += (const AString& ob)
{
	char *temp = ch;		//暂存原串数组
	int n = curLength + ob.curLength;	      //串长度累加
	int m = (maxSize >= n) ? maxSize : n; //新空间大小
	ch = new char[m];
	if (ch == NULL) 
	{ cerr << "存储分配错!\n ";  exit(1); }
	maxSize = m;  curLength = n;
	strcpy(ch, temp);        	         //拷贝原串数组
	strcat(ch, ob.ch);	         //连接ob串数组  	
	delete []temp;  
	return *this;
};
int AString::Find(AString& pat, int k) const {
	//在当前串中从第 k 个字符开始寻找模式 pat 在当
	//前串中匹配的位置。若匹配成功, 则函数返回首
	//次匹配的位置, 否则返回-1。
	int i, j, n = curLength, m = pat.curLength;
	for (i = k; i <= n-m; i++) { 
		for (j = 0; j < m; j++)
			if (ch[i+j] != pat.ch[j]) break;   //本次失配
		if (j == m) return i;
		//pat扫描完, 匹配成功
	}	
	return -1;	 //pat为空或在*this中找不到它
};
int AString::fastFind(AString& pat, int k,  int next[]) const {
	//从 k 开始寻找 pat 在 this 串中匹配的位置。若找
	//到，函数返回 pat 在 this 串中开始位置，否则函
	//数返回-1。数组next[ ] 存放 pat 的next[j] 值。
	int posP = 0,  posT = k;	//两个串的扫描指针
	int lengthP = pat.curLength;         //模式串长度
	int lengthT = curLength;               //目标串长度
	while (posP < lengthP && posT < lengthT)	
		if (posP == -1 || pat.ch[posP] == ch[posT]) 
		{ posP++;  posT++; }          //对应字符匹配
		else posP = next[posP];   //求pat下趟比较位置
		if (posP < lengthP) return -1;	//匹配失败
		else return posT-lengthP;		//匹配成功
};
void AString::getNext(int next[]) {
	int j = 0, k = -1,  lengthP = curLength;
	next[0] = -1;
	while (j < lengthP) 		//计算next[j]
		if ( k == -1 || ch[j] == ch[k]) {
			j++;  k++;
			next[j] = k;
		}
		else k = next[k];
}; 

ostream& operator << (ostream& out, AString & str){
	out<<"The String is: "<<endl;
	out<<str.ch;
	out<<endl;
	return out;
}