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