6、, int len);
// 當1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1時，
// 返回s中第start個字符起長度為len的子串，否則返回空串。
// 注意,不要使用 " s = " 的形式為 StringType 類型的變量賦值 ,
// 而要使用 StrAssign 函數(shù)!!!
void DelSubString(StringType &scrStr, StringType subStr)
/* Remove all substring matching 'subStr' from 'scrS
7、tr'. */
{
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
8、,SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1));
StrAssign(scrStr,Concat(head,tail));
i--;
}
}
③ 編寫算法，實現(xiàn)串的基本操作Replace(&S,T,V)。
要求采用教科書節(jié)中所定義的定長順序存儲表示，
但不允許調(diào)用串的基本操作。
要求實現(xiàn)以下函數(shù)：
Status Replace(SString& s, SString t, SString v)
9、;
/* 用串v替換串s中所有和串t匹配的子串。 */
/* 若有與t匹配的子串被替換，則返回TRUE；*/
/* 否則返回FALSE */
定長順序串SString的類型定義：
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
注：這題在Status Replace(SString& s, SString t, SString v)函數(shù)前要寫一個int Index(SString s, SString t,int
10、pos )的函數(shù)。如下：
int Index(SString s, SString t,int pos )
{
int i = pos;
int j = 1;
while( i<= s[0]&&j<=t[0])
{
if( s[i] == t[j] ){ ++i; ++j; }
else{i= i-j+2;j=1;}
}
if( j > t[0] ) return i - t[0];
else return 0;
}
Status Replace(SString& s,
11、SString t, SString v)
/* 用串v替換串s中所有和串t匹配的子串。 */
/* 若有與t匹配的子串被替換，則返回TRUE；*/
/* 否則返回FALSE */
{
int flag = 0;
int i,j,w,r;
SString s1;
for( i = 0; i <= s[0]; i++ )
s1[i] = s[i];
for( i = 1, j = 1; i <= s1[0]; )
{
w = Index( s1
12、, t, i);
if( !w )
{
while( i <= s1[0] )
s[j++] = s1[i++];
}
else
{
while( i < w )
s[j++] = s1[i++];
for( r = 1; r <= v[0]; r++ )
s[j++] = v[r];
flag++
13、;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}
③ 編寫算法，從串s中刪除所有和串t相同的子串。
要求實現(xiàn)以下函數(shù)：
Status DelSub(SString &s, SString t);
/* 從串s中刪除所有和串t匹配的子串。 */
/* 若有與t匹配的子串被刪除，則返回TRUE；*/
/* 否則返回FALSE
14、 */
定長順序串SString的類型定義：
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
注：這題在Status DelSub(SString &s, SString t)函數(shù)前要寫一個int Index(SString s, SString t,int pos )的函數(shù)。如下：
int Index(SString s, SString t,int pos )
{
int i = pos;
int j = 1;
15、
while( i<= s[0]&&j<=t[0])
{
if( s[i] == t[j] ){ ++i; ++j; }
else{i= i-j+2;j=1;}
}
if( j > t[0] ) return i - t[0];
else return 0;
}
Status DelSub(SString &s, SString t)
/* 從串s中刪除所有和串t匹配的子串。 */
/* 若有與t匹配的子串被刪除，則返回TRUE；*/
/* 否則返回FALSE
16、 */
{
int flag = 0;
int i,j,w;
for( i = 1, j = 1; i <= s[0]; )
{
w = Index( s, t, i);
if( !w )
{
while( i <= s[0] )
s[j++] = s[i++];
}
else
{
while( i < w )
17、 s[j++] = s[i++];
flag++;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}
⑤ 假設以定長順序存儲結構表示串，試設計
一個算法，求串s中出現(xiàn)的第一個最長重復子串及
其位置，并分析你的算法的時間復雜度。
要求實現(xiàn)以下函數(shù)：
void CommonS
18、tr(SString s, SString &sub, int &loc);
/* 求串s中出現(xiàn)的第一個最長重復子串sub及其位置loc */
定長順序串SString的類型定義：
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
void CommonStr(SString s, SString &sub, int &loc)
/* 求串s中出現(xiàn)的第一個最長重復子串sub及其位置loc */
{
int index=0,length=0,lengt
19、h1,i=0,j,k;
while(i=length)
{
index=i;
length=length1;
}
j=j+length1;
}
else j++;
}
i++;
}
loc=index;
sub[0]=length;
}
《數(shù)據(jù)結構題集》參考答案4串
