Question

数据结构的题 谁会做的帮帮忙

设s和t是用结点大小为1的单链表存储的两个串。试设计一个算法，将s串中首次与串t匹配的子串逆置。

Answer 1

分析：本算法的实现分三部：

①链串中的匹配；

②匹配成功后将子串逆置；

③将逆置后的子串连到原串中。

主要说明串逆置的过程。若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; } }

Answer 2

用双链表最好了。