难得爱浓师小札妈妈网:数据结构的题 谁会做的帮帮忙
来源:百度文库 编辑:查人人中国名人网 时间:2024/10/04 18:57:58
分析:本算法的实现分三部:
①链串中的匹配;
②匹配成功后将子串逆置;
③将逆置后的子串连到原串中。
主要说明串逆置的过程。若t是所找到的子串,则prior指向子串t的第一个结点的直接前趋,p指针指向子串t最后一个结点的直接后继,如图(a)所示。为了对串t逆置,从子串t第一个结点开始设置三个指针q,r,u,再依次将r所指向结点的next域指向它的前一个结点,即将r->next=q,再将q,r,u右移而q=r;r=u;u=r->next直到p=r时逆置完毕,逆置后的结果如图(b)所示。而逆置后t1结点的直接后继是*p,*prior的直接后继是tn
解答:
int invert substr(LinkString s,t)
{ /*s,t均带头结点*/
prior=s;p=prior->next; /*prior为p的前驱*/
tl=t->next;
if((p==NULL) || (tl==NULL)
{printf(“不匹配”); return(0); }
while((p !=NULL)&&(tl !=NULL))
if(p->data==tl->data) {p=p->next;tl=tl->next;}
else{ prior=prior->next; /*匹配不成功,向后移*/
p=prior->next; tl=t->next; }
if(tl !=NULL){printf(“不匹配”);return(0);}
else{ q=prior->next;r=q->next; /*匹配成功,开始逆置*/
while(r!=p) {u=r->next;r->next=q; q=r;r=u; }
prior->next->next=p; /*将逆置后的子串连到原串中*/
prior->next=q; } }
用双链表最好了。