清华大学：《数据结构》课程电子教案（PPT课件讲稿）Chapter9 String

String (字符串) string is composed ofn(20) characters in an orderly sequence recorded as s:“c1c 1-2 S is string name 12-3·· C )y is value is a character n is string length。 Such as,S=“ Tsinghua University

String(字符串) string is composed of n（  0 ） characters in an orderly sequence. recorded as S : “c1 c2 c3…cn ” S is string name “ c1 c2 c3…cn” is value ci is a character n is string length。 Such as, S = “Tsinghua University

ADT and class definition of string 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; } ADT and class definition of string

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

Implementation of strings basic operation 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 ); //复制串值 } Implementation of string’s basic operation

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

Algorithm of extracting substring pos=2, len=3 pos=5, len=4 in ty in finity 超出 posten -1 pos+ -1 curLen-l ≥ curlen

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 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; example:st=“ university”,pos=3,len=4 use case: subSt=st (3, 4 substring extraction: subst=“vers

temp->curLen = len; //子串长度 for ( int i = 0, j = pos; i 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