《数据结构》课程教学资源（教案设计）05 串

编号：006 课程 章节 课程讲 数据结构 第四章串、数组和广义表 名称 4,3串的模式匹配算法 授学时 45分钟 名称 学习要求 知识点 识记理解 熟练 课堂 应用 分析 掌握 综合 教学 串的模式匹配算法 TN 目的 态度积极主动学习 使用C语言提供的串操作函数构造与串相关的算法，解决简单的应 能力 用问题 教学内容（教学过程设计） 敦学安排 提出问题并导入新课：很多软件中，若有"编辑”菜单项的话，则其 5分钟 中必有“查找”子菜单项。如何实现查找算法？ 4.3串的模式匹配算法 15分钟 给出BF算法的基本思想，运行实例，写出BF算法 15分钟 分析BF算法的时间复杂度 再次运行实例，分析BF算法效率低的原因，引出KMP算法（在此之前 可以先引入首尾匹配算法：先比较模式串的第一个字符，再比较模式串 10分钟 的最后一个字符，最后比较模式串中从第二个到第-1个字符)】 根据部分匹配的特征，得出失效数组next的求解方法，通过具体实例进 一步理解net数组的求解方法 给出KMP算法，粗略分析KMP算法的时间性能 教学提示： 对于串的基本操作，只要求理解，但要强调串的基本操作的实现是训练 程序设计能力与技巧的一个很好的内容 首尾匹配法在教材上没有，引导学生对算法进行改进 ,KMP算法的技巧性很强，学生如果能真正学懂这个算法，将会极大地增 强学习兴趣，同时对教师的思维能力和表达能力也是一个挑战 重点 重点 与 串的模式匹配算法」 雅点： 难点 模式匹配KMP算法. 对策 教学策略：

编号：006 课程 名称 数据结构 章节 名称 第四章 串、数组和广义表 4.3 串的模式匹配算法 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 串的模式匹配算法 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 使用 C 语言提供的串操作函数构造与串相关的算法，解决简单的应 用问题 教学内容（教学过程设计） 教学安排 提出问题并导入新课：很多软件中，若有“编辑”菜单项的话，则其 中必有“查找”子菜单项。如何实现查找算法？ ↓ 4.3 串的模式匹配算法 ↓ 给出 BF 算法的基本思想，运行实例，写出 BF 算法 分析 BF 算法的时间复杂度 再次运行实例，分析 BF 算法效率低的原因，引出 KMP 算法（在此之前 可以先引入首尾匹配算法：先比较模式串的第一个字符，再比较模式串 的最后一个字符，最后比较模式串中从第二个到第 n-1 个字符） ↓ 根据部分匹配的特征，得出失效数组 next 的求解方法，通过具体实例进 一步理解 next 数组的求解方法 给出 KMP 算法，粗略分析 KMP 算法的时间性能 教学提示： ➢ 对于串的基本操作，只要求理解，但要强调串的基本操作的实现是训练 程序设计能力与技巧的一个很好的内容 ➢ 首尾匹配法在教材上没有，引导学生对算法进行改进 ➢ KMP 算法的技巧性很强，学生如果能真正学懂这个算法，将会极大地增 强学习兴趣，同时对教师的思维能力和表达能力也是一个挑战 5 分钟 15 分钟 15 分钟 10 分钟 重点 与 难点 对策 重点： 串的模式匹配算法。 难点： 模式匹配 KMP 算法。 教学策略：

在授课过程中采用多媒体教学，首先还原问题的本来面目一提出问题，引导学生 积极参与一—一尝试解决问题，在讨论的基础上给出结论一一 讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 手段 作幽： (1)已知模式串t='abcaabbabcab'写出用KMP法求得的每个字符对应的 作业 next和nextval函数值。 及 (2)设目标为t=“abcaabbabcabaacbacba”,模式为p="abcabaa” 课外 ①计算模式p的naxtval函数值； 推荐 ②不写出算法只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 资源 课后导读： KMP算法非常巧妙，求匹配失效数组next的算法更是巧上加巧，更深入的内 容请参见《算法设计与分析》（王红梅编著清华大学出版社） 教学 后记

在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）已知模式串 t=‘abcaabbabcab’写出用 KMP 法求得的每个字符对应的 next 和 nextval 函数值。 （2）设目标为 t=“abcaabbabcabaacbacba”,模式为 p=“abcabaa” ① 计算模式 p 的 naxtval 函数值； ② 不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。 课后导读： ➢ KMP 算法非常巧妙，求匹配失效数组 next 的算法更是巧上加巧，更深入的内 容请参见《算法设计与分析》（王红梅编著 清华大学出版社） 教 学 后记