4.13.c

数据结构习题及答案

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<t，返回值<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;
  int i;
  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--;                  //i的位置应该保持不变，但由于for中i++，故用i--与之抵消
         }
     }

}