数据结构考研分类复习真题 第四章 答案[15]

[题目分析]教材中介绍的串置换有两种形式第一种形式是replace（sijt）含义是将s串中从第i个字符开始的j个字符用t串替换第二种形式是replace(stv)含义是将s串中所有非重叠的t串用v代替我们先讨论第一种形式的替换因为已经给定顺序存储结构我们可将s串从第（i+j）到串尾（即scurlen）移动tcurlenj绝对值个位置（以便将t串插入）若j>tcurlen则向左移;若j<tcurlen则向右移动;若j=tcurlen则不必移动最后将t串复制到s串的合适位置上当然应考虑置换后的溢出问题

int replace(strtp stint ij)//s和t是用一维数组存储的串本算法将s串从第i个字符开始的连续j个字符用t串置换操作成功返回否则返回表示失败

{if(i< || j< || tcurlen+scurlenj>maxlen)

{printf(参数错误\n);exit();}//检查参数及置换后的长度的合法性

if(j<tcurlen)//若s串被替换的子串长度小于t串长度则s串部分右移

for(k=scurlen;k>=i+j;k) sch[k+tcurlenj]=sch[k];

else if (j>tcurlen)//s串中被替换子串的长度小于t串的长度

for(k=i+j;k<=scurlen;k++) sch[k(jtcurlen)]=sch[k];

for(k=;k<tcurlen;k++) sch[i+k]=tch[k]; //将t串复制到s串的适当位置

if(j>tcurlen) scurlen=scurlen(jtcurlen);else scurlen=scurlen+(tcurlenj);

}//算法结束

[算法讨论]若允许使用另一数组在检查合法性后可将s的第i个（不包括i）之前的子串复制到另一子串如s中再将t串接到s串后面然后将s的第i+j直到尾的部分加到s之后最后将s串复制到s主要语句有

for(k=;k<i;k++) sch[k]=sch[k]; //将s第i个字符前的子串复制到s这时k=i

for(k=;k<tcurlen;k++) sch[i+k]=tch[k]//将t串接到s的尾部

l=scurlen+tcurlenj;

for(k=scurlen;k>i+j;k);//将子串第i+j个字符以后的子串复制到s

sch[l]=sch[k]

for(k=;k<scurlen+tcurlenj;k++) sch[k]=sch[k];//将结果串放入s

下面讨论replace（stv）的算法该操作的意义是用串v替换所有在串s中出现的和非空串t相等的不重叠的子串本算法不指定存储结构只使用串的基本运算

void replace(string stv)//本算法是串的置换操作将串s中所有非空串t相等且不重复的子串用v代替

{i=index(st);//判断s是否有和t相等的子串

if(i!=)//串s中包含和t相等的子串

{creat(temp);//creat操作是将串常量（此处为空串）赋值给temp

m=length(t);n=length(s);//求串t和s的长度

while(i!=)

{assign(tempconcat(tempsubstr(si)v));//用串v替换t形成部分结果

assign(ssubstr(si+mnim+));//将串s中串后的部分形成新的s串

n=n(i)m;//求串s的长度

i=index(st);//在新s串中再找串t的位置

}

assign(scontact(temps)); //将串temp和剩余的串s连接后再赋值给s

}//if结束

}//算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []