高校问答nike近期篮球鞋评测:数据结构的题 谁会做的帮帮忙
来源：百度文库 编辑：高校问答 时间：2024/04/29 07:09:10
分析：本算法的实现分三部：
①链串中的匹配；
②匹配成功后将子串逆置；
③将逆置后的子串连到原串中。
主要说明串逆置的过程。若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; } }
用双链表最好了。