字符串 (String)
字符串 是 n (? 0 ) 个字符的有限序列，
记作 S,,c1c2c3…c n”
其中,S 是串名字
,c1c2c3…c n”是串值
ci 是串中字符
n 是串的长度。
例如,S =,Tsinghua University”
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String& ob );
String ( const char * init );
String ( );
~String ( ) { delete [ ] ch; }
字符串抽象数据类型和类定义
int Length ( ) const { return curLen; }
//求当前串 *this的实际长度
String &operator ( ) ( int pos,int len );
//取 *this从 pos开始 len个字符组成的子串
int operator == ( const String &ob )
{ return strcmp (ch,ob.ch) == 0; }
//判当前串 *this与对象串 ob是否相等
int operator != ( const String &ob )
const { return strcmp (ch,ob.ch) != 0; }
//判当前串 *this与对象串 ob是否不等
int operator ! ( )
const { return curLen == 0; }
//判当前串 *this是否空串
String &operator = (String &ob);
//将串 ob赋给当前串 *this
String &operator += (String &ob);
//将串 ob连接到当前串 *this之后
char &operator [ ] ( int i );
//取当前串 *this的第 i 个字符
int Find ( String& pat ) const;
}
String,,String ( const String& ob ) {
//复制构造函数：从已有串 ob复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = ob.curLen; //复制串长度
strcpy ( ch,ob.ch ); //复制串值
}
字符串部分操作的实现
String,,String ( const char *init ) {
//复制构造函数,从已有字符数组 *init复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ){
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = strlen ( init ); //复制串长度
strcpy ( ch,init ); //复制串值
}
String,,String ( ) {
//构造函数：创建一个空串
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 !\n”;
exit(1);
}
curLen = 0;
ch[0] =?\0?;
}
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
i n f i n i t y i n f i n i t y
pos = 2,len = 3 pos = 5,len = 4
f i n i t y
超出
String& String,,operator ( ) (int pos,int len) {
//从串中第 pos 个位置起连续提取 len 个字符
//形成子串返回
String * temp = new String; //动态分配
if (pos<0 || pos+len-1 >= maxLen || len<0) {
temp->curLen = 0; //返回空串
temp->ch[0] = '\0';
}
else { //提取子串
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串长度
for ( int i = 0,j = pos; i < len; i++,j++ )
temp->ch[i] = ch[j]; //传送串数组
temp->ch[len] =?\0?; //子串结束
}
return * temp;
}
例：串 st =,university”,pos = 3,len = 4
使用示例 subSt = st (3,4)
提取子串 subSt =,vers”
String& String,,operator = ( String& ob ) {
//串赋值：从已有串 ob复制
if ( &ob != this ) {
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ch == NULL )
{ cerr <<,内存不足 !\n,; exit (1);}
curLen = ob.curLen; //串复制
strcpy ( ch,ob.ch );
}
else cout <<,字符串自身赋值出错 ! \n”;
return *this;
}
char& String,,operator [ ] ( int i ) {
//按串名提取串中第 i 个字符
if ( i < 0 && i >= curLen )
{ cout <<,串下标超界 !\n,; exit (1); }
return ch[i];
}
例：串 st =,university”,
使用示例 newSt = st； newChar = st[1];
数组赋值 newSt =,university”
提取字符 newChar =?n?
String& String,,operator += ( String& ob ) {
//串连接
char * temp = ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ch == NULL )
{ cerr <<,存储分配错 !\n,; exit (1); }
strcpy ( ch,temp ); //拷贝原串数组
strcat ( ch,ob.ch ); //连接 ob串数组
delete [ ] temp; return *this;
}
例：串 st1 =,beijing,,
st2 =,university”,
使用示例 st1 += st2;
连接结果 st1 =,beijing university”
st2 =,university”
串的模式匹配
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为模式，串称为目标。
示例 目标 T,,Beijing”
模式 P,,jin”
匹配结果 = 3
第 1趟 T a b b a b a 穷举的模式
P a b a 匹配过程第 2趟 T a b b a b a
P a b a
第 3趟 T a b b a b a
P a b a
第 4趟 T a b b a b a
P a b a
int String,,Find ( String& pat ) const {
//穷举的模式匹配
for ( int i = 0; i <= curLen-pat.curLen;
i++ )
{ //逐趟比较
int j = 0; //从 ch[i]与模式 pat.ch比较
while ( j < pat.curLen )
if ( ch[i+j] == pat.ch[j] ) j++;
else break;
if ( j == pat.curLen ) return i;
//pat扫描完,匹配成功
}