// 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t);
// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s // 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。 StringType SubString(StringType s, int start, int len); // 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 \的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!! void Replace(StringType &S, StringType T, StringType V) /* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ { int i; StringType head,tail; //InitStr(head);InitStr(tail); for(i=1;i<=StrLength(S)-StrLength(T)+1;i++) if(!StrCompare(SubString(S,i,StrLength(T)),T)) { StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+StrLength(T),StrLength(S)-i-StrLength(T)+1)); StrAssign(S,Concat(head,V)); Concat(S,tail); i=i+StrLength(V)-1; } } 4.13③ 编写算法，从串s中删除所有和串t相同的子串。 要求实现以下函数： void DelSubString(StringType &scrStr, StringType subStr); /* Remove all substring matching 'subStr' from 'scrStr'. */ StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。 void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t); // 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s // 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。 StringType SubString(StringType s, int start, int len); // 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 \的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!! void DelSubString(StringType &scrStr, StringType subStr) /* Remove all substring matching 'subStr' from 'scrStr'. */ { StringType head,tail,S; int i; InitStr(head); InitStr(tail); for(i=1;i<=StrLength(scrStr)-StrLength(subStr)+1;i++) if(!StrCompare(SubString(scrStr,i,StrLength(subStr)),subStr)) { StrAssign(head,SubString(scrStr,1,i-1)); StrAssign(tail,SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1)); StrAssign(scrStr,Concat(head,tail)); i--; /*向后退一位*/ } } 4.17③ 编写算法，实现串的基本操作Replace(&S,T,V)。要求采用教科书4.2.1节中所定义的定长顺序存储表示，但不允许调用串的基本操作。 要求实现以下函数： Status Replace(SString& s, SString t, SString v); /* 用串v替换串s中所有和串t匹配的子串。 */ /* 若有与t匹配的子串被替换，则返回TRUE；*/ /* 否则返回FALSE */ 定长顺序串SString的类型定义： typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string's length */ int Index(SString s, SString t,int pos ) { int i = pos; int j = 1; while( i<= s[0]&&j<=t[0]) { if( s[i] == t[j] ){ ++i; ++j; } else{i= i-j+2;j=1;} } if( j > t[0] ) return i - t[0]; else return 0; } Status Replace(SString& s, SString t, SString v)/* 用串v替换串s中所有和串t匹配的子串。 */ /* 若有与t匹配的子串被替换，则返回TRUE；*/ /* 否则返回FALSE */ { int flag = 0;//是否替换的标志 int i,j,w,r; //i是s1的标志，j是s的标志， SString s1; for( i = 0; i <= s[0]; i++ ) s1[i] = s[i]; for( i = 1, j = 1; i <= s1[0]; ) { w = Index( s1, t, i); //返回t的起始位置 if( !w ) { while( i <= s1[0] ) s[j++] = s1[i++]; } else { while( i < w ) s[j++] = s1[i++]; for( r = 1; r <= v[0]; r++ ) s[j++] = v[r]; flag++; i += t[0]; } } s[0] = --j; if( flag ) return TRUE; return FALSE; } /*int i,j,k,l; for(i=1;i<=s[0]-t[0]+1;i++) { for(j=i,k=1;t[k]&&s[j]==t[k];j++,k++) if(k>t[0]) { if(t[0]==v[0]) for(l=1;i<=t[0];l++) s[i+l-1]=v[l]; else if(t[0] for(l=s[0];l>i+t[0];l--) s[l+v[0]-t[0]]=s[l]; for(l=1;l<=v[0];l++) s[i+l-1]=v[l]; } else { for(l=i+v[0];l<=s[0]+v[0]-t[0];l++) s[l]=s[l-v[0]+t[0]]; for(l=1;l<=v[0];l++) s[i+l-1]=v[l]; } s[0]=s[0]-t[0]+v[0]; i=i+v[0]; } } return TRUE; */ 4.20③ 编写算法，从串s中删除所有和串t相同的子串。 要求实现以下函数： Status DelSub(SString &s, SString t); /* 从串s中删除所有和串t匹配的子串。 */ /* 若有与t匹配的子串被删除，则返回TRUE；*/ /* 否则返回FALSE */ 定长顺序串SString的类型定义： typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string's length */ int Index(SString s, SString t,int pos ) { int i = pos; int j = 1; while( i<= s[0]&&j<=t[0]) { if( s[i] == t[j] ){ ++i; ++j; } else{i= i-j+2;j=1;} } if( j > t[0] ) return i - t[0]; else return 0; } Status DelSub(SString &s, SString t) /* 从串s中删除所有和串t匹配的子串。 */ /* 若有与t匹配的子串被删除，则返回TRUE；*/ /* 否则返回FALSE */ { int flag = 0;//是否替换的标志 int i,j,w; //i是s1的标志，j是s的标志， for( i = 1, j = 1; i <= s[0]; ) { w = Index( s, t, i); //返回t的起始位置 if( !w ) { while( i <= s[0] ) s[j++] = s[i++]; } else { while( i < w ) s[j++] = s[i++]; flag++; i += t[0]; } } s[0] = --j; if( flag ) return TRUE; return FALSE; } 4.24③ 采用教科书4.2.2节中所定义的堆分配存储表示。试写一算法，在串的堆存储结构上实现串基本操作Concat(&T, s1, s2)。 要求实现以下函数： Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ 堆串HString的类型定义： typedef struct { char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度 } HString; Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ { int i, j; if( !(S.ch=(char*)realloc(S.ch,(S1.length+S2.length)*sizeof(char)))) exit(OVERFLOW); for(i=0;i S.length=S1.length+S2.length; } 4.30⑤ 假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一个最长重复子串及其位置，并分析你的算法的时间复杂度。 要求实现以下函数： void CommonStr(SString s, SString &sub, int &loc); /* 求串s中出现的第一个最长重复子串sub及其位置loc */ 定长顺序串SString的类型定义： typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string's length */ void CommonStr(SString s, SString &sub, int &loc) /* 求串s中出现的第一个最长重复子串sub及其位置loc */ { int index=0,length=0,length1,i=0,j,k; while(i j=i+1;