String(字符串 )
string is composed of n（? 0 ）
characters in an orderly sequence.
recorded as S,,c1c2c3…c n”
S is string name
,c1c2c3…c n” is value
ci is a character
n is string length。
Such as,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; }
ADT and class definition of string
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 ); //复制串值
}
Implementation of string?s basic operation
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?;
}
Algorithm of extracting substring
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;
}
example,st =,university”,pos = 3,len = 4
use case,subSt = st (3,4)
substring extraction,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];
}
example,string st =,university”,
use case,newSt = st； newChar = st[1];
array assignment,newSt =,university”
substring extraction,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;
}
For example,string st1 =,beijing,,
st2 =,university”,
Then st1 += st2;
Results of connection:
st1 =,beijing university”
st2 =,university”
String?s pattern matching
Definition,search the position(the first
charater) of substring in the string.
Terminology,in the pattern matching,
substring is called pattern,and string is
called objective.
For example,objective T,,Beijing”
pattern P,,jin”
matching result= 3
First T a b b a b a Exhaustive pattern
P a b a matching process
Second T a b b a b a
P a b a
Third T a b b a b a
P a b a
Fourth 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扫描完,匹配成功
}