第三节 双向链表与循环

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三节 双向链表与循环链表,什么是双向链表？,前面我们学习了线性链表，也称单链表，其每个结点只有一个指针域，由这个指针只能找到结点的后继或前驱，也就是说只能顺着指针单方向进行扫描，这对于某些问题的处理会带来不便。为了弥补单链表的这个缺点，在某些应用中，每个结点设置两个指针，分别指向前驱和后继。如下图所示：,这种结点用,C,语言结构体定义如下：,struct dou_node,数据成员表；,struct dou_node *prev;,struct dou_node *next;,0,0,head,双向链表的删除运算,p.prev.next=p.next;,p.next.prev=p.prev;,a,b,c,p,双向链表的插入运算,s,.prev=p.prev;,p,.prev.next=s;,s,.next=p;,p.prev=s;,a,x,b,p,思考：,之间的顺序是否唯一呢？,答案：并非唯一,原理：只要满足下列条件即可：,设,A,是含指针符号的任意项,那么，,A,出现在左边的式子必须在含,A,式子的后面。,实例说明,在上述例子四个式子中，,A,可以是,s,.prev、,p,.prev、,p,.prev.next、,s,.next。,而且先后都出现在式子的左边；,下面一个一个分析，分析中发现只有,p,.prev,重复出现。因此只要判断这一个即可。,p,.prev,出现在左边是式子是,，,含,p,.prev,的式子有,，所以根据以上原理可推出：,式必须在 式后面。,满足这一点的所有序列均可。,循环链表,循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。,因此，从表中任一结点出发均可找到表中其他结点。,上述两种形式的链表结合就是循环双向链表。,第四章 字符串模式匹配算法,什么是模式匹配,在一般的编辑软件中，经常要遇到在一个给定的文本中检测一个特定的字符串的问题，这就是字符串匹配，也称模式匹配。,设,P,是一个模式字符串(简称模式)，其长度为,m；s,是一个正文字符串(简称正文,)，,其长度为,n。,通常认为,nm。（,示例）,简单算法,算法描述：,从正文,s,和模式,p,的第一个字符出发，将,s,和,p,的字符依次逐个进行比较，如果,p,中的所有字符均与,s,中的对应字符匹配，则说明匹配成功；如果在比较过程中发现了一个字符不匹配，则将模式,p,沿正文,s,向后移动一个字符的位置，然后再从,p,的第一个字符开始与中的对应字符逐个进行比较。以此类推，直到匹配成功或到达的末段为止。,算法实现,PROCEDURE ZFQPP(s,p,n,m,flag,i),i=1;j=1;,While(i=n-m and jm)return(i-m)else return(0),end,模式匹配的,KMP,算法,基本思想：,当模式,p,与正文,s,进行比较的过程中发现不匹配时，找到一种模式,p,沿正文,s,向后移动的规则，以便使得,正文,s,中失去匹配的字符以前的字符不再参与比较,，,即只从当前失去匹配的字符开始与模式,p,中的字符继续依次进行比较，并且又不错过模式被发现的机会。,示例：,算法分析,假设正文为,s,1,s,2,s,n,，,模式为,p,1,p,2,p,n,，,要实现改进算法，也就是要解决下述问题：当匹配过程中产生失配时(即,s,i,!=p,j,)，,模式“向右滑动”可行的距离有多远，换句话说，当正文中第,i,个字符与模式中第,j,个字符“失配”时，正文中第,i,个字符应与模式中哪个字符相比较？,假设此时应与模式中第,k,个字符继续比较，其中,k,应具有以下两个性质：,1、,kj，,因为当失配时必然使模式,p,向后移，从而导致,kj。,移的幅度越小，,k,与,j,相差越小。,2、,k,应取所有,可能值,中的最大值，因为取最大值就意味着移的幅度越小，也就避免错过成功匹配的机会。,根据这个假设,，必然使得下式成立：,p,1,p,2,p,k-1,=s,i-k+1,s,i-k+2,s,i-1,(1),而,已经得到,的“部分匹配”的结果是：,p,j-k+1,p,j-k+2,p,j-1,=s,i-k+1,s,i-k+2,s,i-1,(2),(2)式的由来是：,当初正文中的第,i,个字符与模式中的第,j,个字符失配时，说明两者之前的(,j-1),个字符肯定是一样的，而,kj，,所以前,k,个字符也是相同的。这就得出(2)式。,由(1)(2)两式便可得：,p,1,p,2,p,k-1,=,p,j-k+1,p,j-k+2,p,j-1,(3),(3)式的结论可如下描述：,在模式,p,中，前,k-1,个字符与第,j,个字符之前的,k-1,个字符相同。,设,nextj,表示：当模式中第,j,个字符与正文中相应字符“失配”时，在模式中重新和正文中该字符进行比较的字符的位置。,并令,nextj=k。,Next,数组的完整定义如下：,Max k|1kk,满足上式，那么,nextj+1=,k,+1,式1,也就是：,nextj+1=nextj+1,2、,若,p,k,!=p,j,，,则表明,p,1,p,2,p,k,!=,p,j-k+1,p,j-k+2,p,j,这时如何求,nextj+1,呢,？,有两种可能情况,转化法,式1,的,结论,可这样描述：何时的,k,使得,p,k,=p,j,，,就用此时的,k,代入式1。,而现在的,k,是,p,k,!=p,j，,因此必须要换成另外一个“,k”，,并设它为,k,2，,以使得,p,k2,=p,j。,问题又出来了：,k,2,如何得来？,如图：,要使得,k,转为,k,2，,实际上就是将,p,往右移，移动后,p,的,j,对应,p,的,k,2,。,1,1,j,j,j-k+1,k,P,P,k,2,，,到底是多少首先取决于另一个,前提条件,：,p,1,p,2,p,k2-1,=,p,j-k2+1,p,j-k2+2,p,j-1,如图：,实际上，,k,2,=nextk,1,1,1,j,j,j,j-k+1,k,k,k,2,k-k,2,+1,p1,p2,p3,那么，满足了这个前提条件，是否就满足,p,k2,=p,j,了呢？,显然两者互不相干。也就是说，仅移动一次不一定满足,p,k2,=p,j,。,如果移动一次后得到,k,2,仍然不满足,p,k2,=p,j,，就要按照前提条件再移动一次。,依次类推，直到,p,kn,=p,j,或,k,n,=0,为止。,此时有：,nextj+1=,k,n,+1,而,k,n,=next,k,n-1,k,1,=k=next,j,由于，,k,n,k,n-1,k,1,=km0,输出：,p,中第1个字符在,s,中的位置,。,PROCEDURE KMP(s,p,n,m,flag,i),int nextm;,1:,构造,p,的,next,数组,Next1=0;j=1;k=0;,While(j=m)do,if(k=0 or pk=pj ),j=j+1;k=k+1;nextj=k;,Else k=nextk;,2:,字符串匹配,i=1;j=1;,While(i=n and jm)return(i-m)else return(0),end,