《数据结构题集》参考答案 串.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(i=j) { temp=s[i]; s[i]=s[j]; s[j]=temp; i++;j--; } } 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。若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 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,Su