《数据结构题集》参考答案4 串.doc

4.10 编写对串求逆的递推算法。要求实现以下函数：void Reverse(StringType &s);/* Reverse s by iteration. */StringType是串的一个抽象数据类型，它包含以下6种基本操作：void InitStr(StringType &s); / 初始化s为空串。void StrAssign(StringType &t, StringType s); / 将s的值赋给t。s的实际参数是串变量。int StrCompare(StringType s, StringType t); / 比较s和t。若st，返回值0；若s=t，返回值=0；若st，返回值0。int StrLength(StringType 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的子串，否则返回空串。/ 注意,不要使用 s = 的形式为 StringType 类型的变量赋值 ,/ 而要使用 StrAssign 函数!void Reverse(StringType &s)/* Reverse s by iteration. */ int i=0,j=StrLength(s)-1; char temp; while(it，返回值0；若s=t，返回值=0；若st，返回值0。int StrLength(StringType 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的子串，否则返回空串。/ 注意,不要使用 s = 的形式为 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 SStringMAXSTRLEN+1; /* s0 is the strings length */注：这题在Status Replace(SString& s, SString t, SString v)函数前要写一个int Index(SString s, SString t,int pos )的函数。如下：int Index(SString s, SString t,int pos ) int i = pos; int j = 1; while( i= s0&j t0 ) return i - t0; 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; SString s1; for( i = 0; i = s0; i+ ) s1i = si; for( i = 1, j = 1; i = s10; ) w = Index( s1, t, i); if( !w ) while( i = s10 ) sj+ = s1i+; else while( i w ) sj+ = s1i+; for( r = 1; r = v0; r+ ) sj+ = vr; flag+; i += t0; s0 = -j; if( flag ) return TRUE; return FALSE;4.20 编写算法，从串s中删除所有和串t相同的子串。要求实现以下函数：Status DelSub(SString &s, SString t);/* 从串s中删除所有和串t匹配的子串。 */* 若有与t匹配的子串被删除，则返回TRUE；*/* 否则返回FALSE */定长顺序串SString的类型定义：typedef unsigned char SStringMAXSTRLEN+1; /* s0 is the strings length */注：这题在Status DelSub(SString &s, SString t)函数前要写一个int Index(SString s, SString t,int pos )的函数。如下：int Index(SString s, SString t,int pos ) int i = pos; int j = 1; while( i= s0&j t0 ) return i - t0; else return 0;Status DelSub(SString &s, SString t)/* 从串s中删除所有和串t匹配的子串。 */* 若有与t匹配的子串被删除，则返回TRUE；*/* 否则返回FALSE */ int flag = 0; int i,j,w; for( i = 1, j = 1; i = s0; ) w = Index( s, t, i); if( !w ) while( i = s0 ) sj+ = si+; else while( i w ) sj+ = si+; flag+; i += t0; s0 = -j; if( flag ) return TRUE; return FALSE;4.30 假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一个最长重复子串及其位置，并分析你的算法的时间复杂度。要求实现以下函数：void CommonStr(SString s, SString &sub, int &loc);/* 求串s中出现的第一个最长重复子串sub及其位置loc */定长顺序串SString的类型定义：typedef unsigned char SStringMAXSTRLEN+1; /* s0 is the strings length */void CommonStr(SString s, SString &sub, int &loc)/* 求串s中出现的第一个最长重复子串sub及其位置loc */ int index=0,length=0,length1,i=0,j,k; while(is0) j=i+1; while(j=length) index=i; length=length1; j=j+length1; else j+; i+; loc=index; sub0=length;