字符串 (String) 字符串是 n (  0 ) 个字符的有限序列， 记作 S = “c1c2c3…cn” 其中，S 是串名字

Presentation on theme: "字符串 (String) 字符串是 n (  0 ) 个字符的有限序列， 记作 S = “c1c2c3…cn” 其中，S 是串名字"— Presentation transcript:

1 字符串 (String) 字符串是 n (  0 ) 个字符的有限序列， 记作 S = “c1c2c3…cn” 其中，S 是串名字
ci 是串中字符 n 是串的长度。 例如, S = “Tsinghua University”

2 字符串抽象数据类型和类定义 const int maxLen = 128; class String { int curLen; //串的当前长度 char *ch; //串的存储数组 public: String ( const String& ob ); String ( const char * init ); String ( ); ~String ( ) { delete [ ] ch; }

3 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是否不等

4 const { return curLen == 0; } String &operator = (String &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; }

5 int Index(String S, String T, int pos){
if(pos>0){ n=StrLength(S);m=StrLength(T);i=pos; while(i<=n-m+1){ SubString(sub,S,i,m); if(StrCompare(sub,T)!=0) ++i; else return i; } return 0;

6 字符串部分操作的实现 //复制构造函数：从已有串ob复制 ch = new char[maxLen+1]; //创建串数组
String :: String ( const String& ob ) { //复制构造函数：从已有串ob复制 ch = new char[maxLen+1]; //创建串数组 if ( ch == NULL ) { cont << “存储分配错! ”<<endl; exit(1); } curLen = ob.curLen; //复制串长度 strcpy ( ch, ob.ch ); //复制串值

7 String :: String ( const char *init ) {
ch = new char[maxLen+1]; //创建串数组 if ( ch == NULL ){ cout<< “存储分配错 !”<<endl; exit(1); } curLen = strlen ( init ); //复制串长度 strcpy ( ch, init ); //复制串值

8 ch = new char[maxLen+1]; //创建串数组 if ( ch == NULL ) {
String :: String ( ) { //构造函数：创建一个空串 ch = new char[maxLen+1]; //创建串数组 if ( ch == NULL ) { cout<< “存储分配错!”<<endl; exit(1); } curLen = 0; ch[0] = ‘\0’;

9 提取子串的算法示例 pos+len -1 pos+len -1  curLen-1  curLen pos = 2, len = 3
i n f i n i t y i n f i n i t y 超出 f i n i t y pos+len pos+len -1  curLen  curLen

10 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 )

11 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”

12 String& String :: operator = ( String& ob ) { if ( &ob != this ) {
delete [ ] ch; ch = new char [maxLen+1]; //重新分配 if ( ch == NULL ) { cout<< “内存不足! ”<<endl; exit (1);} curLen = ob.curLen; //串复制 strcpy ( ch, ob.ch ); } else cout << “字符串自身赋值出错!”<<endl; return *this;

13 使用示例 newSt = st；newChar = st[1]; 数组赋值 newSt = “university”
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’

14 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; }

15 例：串 st1 = “beijing ”, st2 = “university”, 使用示例 st1 += st2; 连接结果 st1 = “beijing university” st2 = “university”

16 串的模式匹配 定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 4

17 第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 

18 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扫描完, 匹配成功 }