第三节 双向链表与循环.ppt

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