天津大学：《数据结构 Data Structures》课程教学资源（PPT课件）第四章 字符串（String）

字串( String 字符串是n(≥0)个字符的有限序列 记作S:“c1c2C3 ●●● 其中,S是串名字 123° cn”是串值 c1是串中字符 n是串的长度。 例如,S=“ Tsinghua University

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

字符串抽象数据类型和类定义 const int maxLen=128: class string 3 int curlen: /的当前长度 char sch 的存储数组 public: String( const String ob ) String( const char x init ) String o; Strigoi delete[ ch; 3

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 i return curLen; f /求当前串this的实际长度 String &operator(( int pos, int len ) /取thi从pos开始len个字符组成的子串 int operator =- const String &ob) ireturn strcmp(ch, ob.ch)=0;3 /判当前串*this与对象串ob是否相等 int operator !=( const String &ob const return strcmp(ch, ob.ch)!=0; 3 /判当前串ths与对象串ob是否不等

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 ! o const i return curLen ==0; 5 /判当前串“this是否空串 String &operator =(String &ob); /将串ob赋给当前串*this String &operator +=(String &ob); /将串ob连接到当前串“ths之后 char &operator [ int 1); /取当前串“th的第i个字符 int Find( string &e pat ) const;

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)t 复制构造函数:从已有串ob复制 ch= new charImaxLen+11;创刨建串数组 if ch==NULL cer<<“存储分配错!Ⅷm”; exit(1); curlen= ob. curlen;1复制串长度 Cpy(ch,obch);/复制串值 sti

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 )i 复制构造函数:从已有字符数组init复制 ch= new char maxLen+1];//创建串数组 if(ch== NULL cer<<“存储分配错!Ⅷm”; exit(D) curlen= strlen(init);//复制串长度 strcpy(cl , Init ); //复制串值

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)t cer<<“存储分配错!n” exit(1); curlen =u ch|0]=“0

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

提取子串的算法示例 pos=2, len=3 pos=5, len=4 in ty in finity 超出 posten -1 pos+ -1 curLen-l ≥ curlen

提取子串的算法示例 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 Strings;动态分配 if(pos≤0‖ posten-1>= maxlen‖lencurLen=0; /返回空串 temp->ch 0=0; eise /提是取子串 if( postlen-1>=curLen) len=curLen- pos;

String& String :: operator ( ) (int pos, int len) { //从串中第 pos 个位置起连续提取 len 个字符 //形成子串返回 String * temp = new String; //动态分配 if (pos= maxLen || lencurLen = 0; //返回空串 temp->ch[0] = '\0'; } else { //提取子串 if ( pos+len -1 >= curLen ) len = curLen - pos;

temp-> curlen=len;/子串长度 for (int i=0,j=pos; ichi=chj];传送串数组 temp-> chen]=“0,;子串结束 return x temp; 例:串st=“ university”,p0s=3,len=4 使用示例 subst=st(3,4) 提取子串 subst=“vers

temp->curLen = len; //子串长度 for ( int i = 0, j = pos; i ch[i] = ch[j]; //传送串数组 temp->ch[len] = ‘\0’; //子串结束 } return * temp; } 例：串 st = “university”, pos = 3, len = 4 使用示例 subSt = st (3, 4) 提取子串 subSt = “vers