数据结构（Java语言版）电子教案 6-1：串

授课题目第6章串授课时间授课学时22学时授课地点授课形式理论教学目标知识目标掌握串的存储方法；掌握BF算法和KMP算法。能力目标能够利用串的相关操作与模式匹配算法，解决相关问题。素质目标由字符串的应用案例可以拓展网络入侵检测问题，培养学生的家国情怀和科技报国的社会责任感。学情分析已经在程序设计语言课程中学习过字符数组的知识，用于字符串的处理。计算机上的非数值处理的对象大多数是字符串数据，串是内容受限（元素是字符）的线性表，其主要应用为文字编辑中的查找、替换，都涉及内容搜索即匹配。本次课学习串的概念及匹配。教学内容串的定义、存储及模式匹配算法教学重点串的存储模式匹配的BF算法解决方法存储采用顺序存储。BF算法是一种回溯算法，理解容易。教学难点模式匹配的KMP算法解决方法KMP算法是一种非回溯算法，理解并掌握模式串的next函数是关键。教学策略串是内容受限的线性表，其应用是文本的查找、替换，如何快速定位模式串位置（串匹配）是关键。从传统匹配算法（BF算法）开始引入，讲清楚回溯的关键节点；之后在此基础上推导出非回溯策略，进而掌握KMP算法。层层递进，带领学生理解关键环节，从而提高听课效率。学习方法课前：复习程序设计语言的字符数组的相关知识，理解字符串的存储表示。预习串的传统匹配算法。课中：认真听讲预习中有疑惑的内容，层层递进，理解BF算法中的关键节点；进而理解非回溯算法（KMP算法）的next函数的计算，从而掌握KMP算法。课后：复习和习题巩固掌握BF算法和KMP算法。教学资源

教学过程教学环节及时间教学内容教师活动学生活动设计意图课前复习：字符数组预习：BF算法布置复习内容布置预习任务：BF算法匹配不成功时如何回溯的预习相关内容。完成相关题目奠定基础；促使学生思考、发现问题。课中环节一（10分钟）复习字符数组：字符数组是内容受限的线性表。1、提问：字符数组的元素是什么类型？2、提问：你认为字符串匹配怎样进行？1、回答问题2、听讲并思考抛出问题、促进课堂听课效果。课中环节二（5分钟）引入：串的应用非常广泛，文本就是串，最常用的应用是查找、替换。1、讲解文本编辑中串的应用2、提问：串的应用还有哪些？1、听讲并思考2、回答问题：病毒检测、网络攻击检测1、通过案例引入，使学生理解并掌握串的常见应用。2、通过提问，明确串在网络安全方面的应用，提高学生学习兴趣。课中环节三（15分钟）串的类型定义串的存储结构：顺序存储结构链式存储结构1、讲解串的类型定义、存储结构。2、提问：顺序存储结构和链式存储结构哪种操作方便？存储密度怎样？1、听讲并思考2、回答问题：顺序存储结构存储密度高，插入、删除不方便；链式结构反之。1、通过讲解，使学生理解串的存储结构及特点。2、通过提问，使学生牢记串的特点及操作课中环节四（15分钟）串的模式匹配之BF算法：BF算法是回溯算法。当匹配不成功时，需要回溯。时间复杂度：O(m+n)1、讲解BF算法的匹配过程，匹配成功时匹配位置的计算及匹配不成功时回溯位置的计算。2、提问：匹配不成功时，主串回溯到什么位置？1、听讲并思考2、回答问题1、使学生沉浸式思考相关知识，促进听课效果。2、通过提问，促使学生牢记匹配不成功时回溯位置。课中环节五（5分钟）串的模式匹配之KMP算法：KMP算法为不回溯算法：BF缺陷：主串的指针i回溯，已经被检索过的部分主串被重复检索。同时，模式串的指针j也会回溯到起始位置。KMP特点：如何避免指针i回溯？在BF中，指针i回溯的目的？不回溯可能会错过一些匹配。指针i不动？子串向右滑动，即找到j移动的位置，使得新的指针j之前的字符能够自动匹配。1、启发学生发现BF算法的缺陷。2、提醒学生发现问题所在：怎样让主串位置不回溯、模式串从什么位置开始与主串比较。听讲并思考抛出问题，促使学生思考。课中环节六（35分钟）next函数计算：通过前后缀，构造next值。KMP算法：1、启发讲解前后缀计算next值的方法。2、互动式举例计算模式串的next值。3、讲解KMP算法4、提问：KMP算法与BF算法在何处不同？1、听讲并思考2、互动计算next值3、回答问题1、使学生沉浸式听讲，提高听课效果。2、通过回答问题，让学生参与其中，促使学生认真听讲，并思考。课中环节七（5分钟）总结归纳互动理解串的存储结构及操作