严蔚敏版数据结构C语言版参考答案第五章(3)

{

for(l=S.length-1;l>=i+T.length;l--) S.ch[l+V.length-T.length]=S.ch[l]; for(l=0;l

else //新子串长度小于原子串时:先将后部左移 {

for(l=i+V.length;l

S.length+=V.length-T.length; i+=V.length;n++; }//if }//for return n;

}//HString_Replace 4.26

Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前 {

if(pos<1) return ERROR;

if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾 S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char)); for(i=S.length-1;i>=pos-1;i--)

S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置 for(i=0;i

S.ch[pos+i-1]=T.ch[pos]; //插入串T S.length+=T.length; return OK;

}//HString_Insert 4.27

int Index_New(Stringtype s,Stringtype t)//改进的定位算法 {

i=1;j=1;

while(i<=s[0]&&j<=t[0]) {

if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])) { //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个 i=i+j-2; j=1; } else

{

i++;j++; }

}//while

if(j>t[0]) return i-t[0]; }//Index_New 4.28

void LGet_next(LString &T)//链串上的get_next算法 {

p=T->succ;p->next=T;q=T; while(p->succ) {

if(q==T||p->data==q->data) {

p=p->succ;q=q->succ; p->next=q; }

else q=q->next; }//while

}//LGet_next 4.29

LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针 {

p=pos;q=T->succ; while(p&&q) {

if(q==T||p->chdata==q->chdata) {

p=p->succ; q=q->succ; }

else q=q->next; }//while if(!q) {

for(i=1;i<=Strlen(T);i++) p=p->next; return p;

} //发现匹配后,要往回找子串的头 return NULL; }//LIndex_KMP 4.30