4.20.c

数据结构习题及答案

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 */
Status DelSub(SString &s, SString t)
/* 从串s中删除所有和串t匹配的子串。     */
/* 若有与t匹配的子串被删除，则返回TRUE；*/
/* 否则返回FALSE                        */
{int i,j,k,exist=0;
 for(i=1;i<=s[0]-t[0]+1;i++)
    {
     for(j=1;s[i+j-1]==t[j]&&j<=t[0];j++);
     if(j>t[0])                                //找到模式串
        {
         exist=1;
         for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]];  
         s[0]-=t[0];
         i--;                                 //i保持在原来位置，但由于for中i++,用i--与之相抵消
        }
    }
 if(exist==1) return TRUE;
 else return FALSE;

}