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

字符串( String) 字符串是n(≥0)个字符的有限序列, 记作S:“c;c2cs 99 ●●● 其中,S是串名字 23°° 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 i int curlen /的当前长度 char *cha /的存储数组 public: String( const String &e ob ) String( const char x init ) String o; aString delete l ch; j

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; 3 /当前串*this的实际长度 String &operator((int pos, int len ) /取thi从p开始len个字符组成的子串 int operator =- const String &ob) R return strcmp(ch, ob. ch)==0;) /判当前串*this与对象串ob是否相等 int operator! = const String &ob const i return strcmp(ch, ob.ch)!=0;) /判当前串*thi与对象串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; j /判当前串*thi是否空串 String &operator=(String &ob); /将串ob赋给当前串*this String &operator +=(String &ob); /将串ob连接到当前串*th之后 char &operator [(int i ); /取当前串this的第i个字符 int Find( String& 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)i /复制构造函数:从已有串ob复制 ch= new charmaxLen+1};/建串数组 if (ch== nULL) cerr<<“ 存储分配错!m”; eXI curlen= ob. curLen;/复制串长度 strcpy(ch,obch);/复制串值

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 charlmaxLen+1l;/创建串数组 if (ch== NULL cerr<“存储分配错!in”; exit(1); curLen= strlen(init);/复制串长度 strcpy( ch, 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 (i /构造函数:创建一个空串 ch= new charmaxLen+1l1;/创建串数组 if ( ch== NULL cerr<“存储分配错!m” exit(1) curlen=0 ch0]=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 nfinity infinity 超 posten -1 posten -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 String;动态分配 if(pos=maxLen lencurLen=0 /返回空串 temp->ch[0]=0; se 提是取子串 if( postlen-1>=curLen len=curlLen-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=chjl;m传送串数组 temp-> ch[len=“07;/子串结束 return temp 例:串st=“ university”,pos=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