数据结构作业系统_第四章答案.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=len0;i-) Concat(t,SubString(s,i,1); StrAssign(s,t); 4.12 编写一个实现串的置换操作Replace(&S,T,V)的算法。要求实现以下函数：void Replace(StringType &S, StringType T, StringType V);/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */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 Replace(StringType &S, StringType T, StringType V)/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ int i,flag; StringType str1,str2,str3; InitStr(str1);InitStr(str2);InitStr(str3); for(i=1;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. */ int i,flag; StringType str1,str2,str3; InitStr(str1);InitStr(str2);InitStr(str3); for(i=1;i=StrLength(scrStr)-StrLength(subStr)+1;i+) str1=SubString(scrStr,i,StrLength(subStr); flag=StrCompare(str1,subStr); if(flag=0) str2=SubString(scrStr,1,i-1); str3=SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1); StrAssign(scrStr,str2); Concat(scrStr,str3); 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)/* 用串v替换串s中所有和串t匹配的子串。 */* 若有与t匹配的子串被替换，则返回TRUE；*/* 否则返回FALSE */ int i=1,j=1; int k,c,flag=0; while(it0) if(v0t0) for(k=s0,c=v0-t0;k=i;k-)sk+c=sk; else if(v0t0) for(k=i,c=t0-v0;k=s0;k+)sk-c=sk; for(k=i-j+1,c=1;c=v0;k+,c+)sk=vc; s0=s0+v0-t0; i=i-t0+v0; j=1; flag=1; if(flag=1)return TRUE; else 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)/* 从串s中删除所有和串t匹配的子串。 */* 若有与t匹配的子串被删除，则返回TRUE；*/* 否则返回FALSE */ int i=1,j=1; int k,c,flag=0; while(it0) for(k=i,c=t0;k=s0;k+)sk-c=sk; s0=s0-t0; flag=1; i=i-t0; j=1; if(flag=1)return TRUE; else 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)free(S.ch); S.ch=(char *)malloc(S1.length+S2.length)*sizeof(char); for(i=0;iS1.length;i+) S.chi=S1.chi; for(i=S1.length,j=0;jS2.length;i+,j+) S.chi=S2.chj; S.length=S1.length+S2.length; return TRUE;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 i,j,k,len=0,count