数据结构上机作业1-5章(8)

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 */

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; //i是s1的标志，j是s的标志， 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); //返回t的起始位置 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; }

/*int i,j,k,l;

for(i=1;i<=s[0]-t[0]+1;i++) {

for(j=i,k=1;t[k]&&s[j]==t[k];j++,k++) if(k>t[0]) {

if(t[0]==v[0])

for(l=1;i<=t[0];l++) s[i+l-1]=v[l]; else if(t[0]

for(l=s[0];l>i+t[0];l--) s[l+v[0]-t[0]]=s[l]; for(l=1;l<=v[0];l++) s[i+l-1]=v[l]; } else {

for(l=i+v[0];l<=s[0]+v[0]-t[0];l++) s[l]=s[l-v[0]+t[0]]; for(l=1;l<=v[0];l++)

s[i+l-1]=v[l]; }

s[0]=s[0]-t[0]+v[0]; i=i+v[0]; } }

return TRUE; */

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 */

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; //i是s1的标志，j是s的标志， for( i = 1, j = 1; i <= s[0]; ) {

w = Index( s, t, i); //返回t的起始位置 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.24③ 采用教科书4.2.2节中所定义的堆分配存储表示。试写一算法，在串的堆存储结构上实现串基本操作Concat(&T, s1, s2)。 要求实现以下函数：

Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ 堆串HString的类型定义： typedef struct {

char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度 } HString;

Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ {

int i, j;

if( !(S.ch=(char*)realloc(S.ch,(S1.length+S2.length)*sizeof(char)))) exit(OVERFLOW); for(i=0;i

S.length=S1.length+S2.length; }

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

j=i+1;