《数据结构题集》参考答案4 串.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。若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 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。若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,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,SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1));
StrAssign(scrStr,Concat(head,tail));
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 SString[MAXSTRLEN+1];
/* s[0] is the string's length */

注：这题在Status Replace(SString& s, SString t, SString v)函数前要写一个int Index(SString s, SString t,int pos )的函数。如下：

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, 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, 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++;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}

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)函数前要写一个int Index(SString s, SString t,int pos )的函数。如下：

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 DelSub(SString &s, SString t)
/* 从串s中删除所有和串t匹配的子串。 */
/* 若有与t匹配的子串被删除，则返回TRUE；*/
/* 否则返回FALSE */
{
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 )
s[j++] = s[i++];
flag++;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}

4.30⑤ 假设以定长顺序存储结构表示串，试设计
一个算法，求串s中出现的第一个最长重复子串及
其位置，并分析你的算法的时间复杂度。

要求实现以下函数：
void CommonStr(SString s, SString &sub, int &loc);
/* 求串s中出现的第一个最长重复子串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中出现的第一个最长重复子串sub及其位置loc */
{
int index=0,length=0,length1,i=0,j,k;
while(i<s[0])
{
j=i+1;
while(j<=s[0])
{
if(s[i]==s[j])
{
length1=1;
for(k=1;s[i+k]==s[j+k];k++)
length1++;
if(length1>=length)
{
index=i;
length=length1;
}
j=j+length1;
}
else j++;
}
i++;
}
loc=index;
sub[0]=length;
}