《数据结构[Python语言描述]》教案第8课串（4.1-4.3）.docx

《《数据结构[Python语言描述]》教案第8课串（4.1-4.3）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第8课串（4.1-4.3）.docx（6页珍藏版）》请在优知文库上搜索。

1、课题第8课串(4.1-4.3)课时2课时(90min)教学目标知识目标：(1)理解串的定义。(2)掌握串的基本操作。(3)掌握串的顺序和链式两种存储结构。(4)掌握串的模式匹配算法技能目标：(1)能使用串解决实际问题(2)能使用串的模式匹配算法定位串素质目标：加强实践练习，自觉提升专业技能和职业素养教学重难点教学重点：串的基本操作、串的顺序和链式两种存储结构、串的模式匹配算法教学难点：串的顺序和链式两种存储结构、串的模式匹配算法教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题

2、导入【教师】提出以下问题：如何理解串？【学生】举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍串的定义和基本操作、串的存储结构、串的模式匹配算法4.1 串概述串是一种数据元素受限的线性表，即要求组成线性表的所有数据元素都是字符.4.1.1 串的定义串是由若干字符组成的有限序列，通常记作Slr=ZMG.为/或slr=aM42.;其中，Slr是串名；用单引号或双引号括起来的字符序列是串值，它可以是字母、数字或其他字符；n(n0)是串中字符的个数，也称为串的长度，当n=0时称为空串。通常将仅由一个或多个空格组成的串称为空白串。空串和空白串是不同的。【提示】如果单引号本身是串中的一个字符，那

3、么串可以用双引号括起来；反之，如果双引号本身是串中的一个字符，那么串可以用单引号括起来.(详见教材)串中任意连续的字符组成的子序列称为该串的子串，包含子串的串称为主串.子串在主串中第一次出现时第一个字符的位置(即该字符在串中的序号，串中首字符的序号为0,以此类推)称为该子串在主串中的下标或索引。当两个串的长度相等，并且各个对应位置的字符都相等时，称两个串是相等的。4.1.2 串的基本操作【教师】用多媒体展示“串基本操作的定义”表(详见教材)，并介绍基本操作4.2 串的存储结构与线性表相同，串也有两种存储结构，一种是三序存储结构，即顺序串；另一种是链式存储结构,即链串。4.2.1 串的顺序存储一

4、顺序串【教师】随机邀请学生回答以下问题什么是串的顺序存储？【学生】聆听、思考、回答串的顺序存储是指用一组地址连续的存储单元依次存放串的字符序列。在这种存储结构中,按照预定义的大小为每个串分配一个固定长度的存储区，且这个存储区在程序运行期间不再改变，故串的顺序存储也称为串的静态存储。采用顺序存储结构的串称为顺序串。【教师】用多媒体展示“串的顺序存储结构”图片，并介绍构造方法串旧yItIhIOTTl下标012345#定义顺序串类#初始化串#构造空串#串中的数据元素#串长#以字符串构造串顺序串的构造方法如下。classSqString:def_init_(self,obj):ifobjisNone:

5、self.data=self.length=0elifisinstance(obj,str):遍历串 为串赋值 以列表构造串遍历列表 为串赋值self.length=Ien(obj)self.data=None*self.lengthforiinrange(self.length):self.datai=objielifisinstance(obj,list):self.length=Ien(obj)self.data=None*self.lengthforiinrange(self.length):self.datai=obji【教师】随机邀请学生回答以下问题顺序串的基本操作有哪些？【学生】

6、聆听、思考、回答顺序串的基本操作包括串插入、串删除、串定位和求子串等，其中最常用的操作是串定位和求子串。求子串是指返回串中从指定下标begin开始，长度为Ien的子串序列，其具体步骤如下。(1)判断参数begin和Ien是否满足条件Obegin串长和。Ien串长-begin。(2)若满足条件，则返回子串序列。【算法描述】defsubstring(self,begin,len):#求子串ifbegin=self.lengthorIenself.length-begin:raiseEXeePtiOn(参数不满足条件，)tmp=None*Ien#初始化子串foriinrange（begin,begi

7、n+len）:tmpi-begin=self.datai#复制子串returnSqString（tmp）.data#返回子串【教师】讲解实例41【实例4-1现有两个串Strl和str2均采用顺序存储结构，设计算法按照字典顺序（字典顺序即按字母顺序排列的方法。对于两个串来说，当其第一个字母相同时，则继续按照第二个字母在字典中的先后顺序进行比较，以此类推，直到其中一个串的字符全部比较完毕）比较两个串的大小。【问题分析】要比较strl和str2的大小，可以先比较Strl和str2共同长度范围内的对应字符；如果strl和str2共同长度范围内的对应字符均相等，则比较它们的长度。【代码实现】详见教材。4

8、.2.2 串的鞋式存储一链串+【教师】随机邀请学生回答以下问题什么是串的链式存储？【学生】聆听、思考、回答串的链式存储是指用单链表存储串值。采用链式存储结构的串称为链串。当采用链式存储结构时，链串中每个结点的数据域既可以存放一个字符，也可以存放多个字符（称为块）通常将结点数据域中存放字符的个数称为结点大小。【教师】用多媒体展示“结点大小为1的链串”和“结点大小为5的链串“表（详见教材），并介绍该结构当结点大小大于1时，由于串长不一定是结点大小的整数倍，也就是说链表的尾结点不一定总能被字符占满，此时就须在未占满的数据域中填充特殊符号或其硼F串值字符。在设计链串时，结点大小直接影响串处理的效率。结

9、点大小越小，存储密度越小，串的相关操作越方便，但存储量占用较大.相反，结点大小越大，存储密度越大，串的相关操作（如插入、删除等）越复杂，但存储量占用较小在实际应用中为便于操作，通常将链串的结点大小设置为【提示】当结点大小为1时，链串中基本操作的实现与单链表类似，此处不再赘述。总体而言，相较于顺序串，链串不够灵活，存储量占用大且操作复杂，但对于串的某些基本操作（如连接）来说较方便。在实际应用中，用户可根据具体情况选择合适的存储结构。4.3 串的模式匹配算法【教师】随机邀请学生回答以下问题什么是串的模式匹配？【学生】聆听、思考、回答串的模式匹配又称为串定位.若有两个串S和t,其中串S称为目标串，串

10、t称为模式串。如果在目标串S中杳找到模式串I,则称模式匹配成功，并返回模式串t的第一个字符在目标串S中的位置。如果在目标串S中未查找到模式串I,则称模式匹配失败，并返回-1。串的模式匹配算法有多种，本节介绍最常用的BF算法和KMP算法。4.3.1 BF算法BF（brute-force）算法是最简单且直观的模式匹配算法，其基本思想是从目标串的指定字符起和模式串的首字符进行比较，若相等，则继续逐个比较下一个字符，否则从目标串的下一个字符起重新和模式串的首字符进行比较。以此类推，直到模式串的每个字符依次和目标串的一个连续的字符序列相等，则匹配成功，并返回和模式串的第一个字符相等的字符在目标串中的位置

11、，否则返回-1。例如，目标串s=acabaabaabcacbc,模式串=,abaabc,分别使用变量/和J(初始均为O)遍历S和/,使用BF算法判断模式串z与目标串S是否匹配的过程如下。【教师】用多媒体展示“匹配过程”图，并介绍匹配算法(1)第1趟从i=o、j=0开始依次匹配。当i=kj=l时，匹配失败。此时，须将i从1=1开始，将j回溯到j=。重新进行匹配。(2)第2趟从i=1、尸0开始依次匹配，可以发现匹配失败。此时，须将，从i=2开始，将,回溯到J=O重新进行匹配。*目标串SaCabaabaabcacbTl下标0123456789IOH121314X模式串/IaIblalalblC下标X

12、I2345(3)-(6),【算法描述】【算法分析】详见教材4.3.2 KMP算法KMP(Knuth-Morris-Pratt)算法是在BF算法的基础上改进而来的，其目的是消除某次匹配失败时目标串开始比较位置的回溯，从而提高匹配效率。KMP算法的基本思想是每当一趟匹配过程中出现字符不相等时，指向目标串的指针无须回溯，而是利用已经得到的部分匹配”结果将模式串向右移动一段距离后继续比较。因此，KMP算法要解决的关键问题是，当某次匹配不成功时，如何确定模式串向右移动的距离。也就是说，当目标串的第i个字符与模式串的第j个字符不相等时，目标串的第i个字符应该重新与模式串的哪个字符继续比较。这时，可借助前缀

13、数组next,其定义如下。MAX伙I0V&V/,且血i於尸幻办1r1(此集合非空)next-0(其他情况)IT(7=0)其中，Ml.JZ”为模式串的前缀,UM-EU7”为模式串的后缀，k为前缀和后缀最长共有元素的长度，也就是当目标串的第，个字符与模式串的第/个字符不相等时，模式串中下一次与目标串的第/个字符进行比较的字符的位置。【提示】前缀是除了最后一个字符外，一个串的全部头部集合。后缀是除了第一个字符外，一个串的全部尾部集合。需要注意的是,从中间位置截取的串不属于前缀或后缀。例如,串good的前缀为g,go,goo,后缀为WocToodI借助前缀数组next,KMP算法的具体步骤如下。(1)

14、从目标串的第pos个字符开始，与模式串的字符逐个进行匹配，变量i和j分别指向目标串和模式串中当前进行匹配的字符.(2)当目标串的第i个字符与模式串的第j个字符相等时，变量i和j同时加1,继续匹配下一个字符；当目标串的第i个字符与模式串的第j个字符不相等时，变量i不变，模式串向右移动，直到变量j回溯到nexlj所指示的位置，并与目标串的第i个字符重新进行匹配；当变量j=1时，变量i和j须同时加I,即从目标串的第i+1个、模式串的第j+1个字符起重新进行匹配。(3)重复上述过程，直到模式串与目标串匹配结束，返回匹配结果。例如，目标串.S-acabaabaabcacbc,模式串r=,abaabc,分

15、别使用变量，和/(初始均为O)遍历S和t,使用KMP算法判断模式串/与目标串S是否匹配的过程如下.【教师】用多媒体展示“匹配过程”图(详见教材)，并介绍匹配过程(1)求解模式串=abaabc，对应的前缀数组next.(2)借助前缀数组next进行模式串/与目标串S的匹配。(详见教材)【学生】聆听、思考、理解、记录任务实施任务一编辑文本文件【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频”编辑文本文件“(详见教材)，要求学生设计算法【问题描述】设计一个算法，在指定目录下创建一个文本文件，并在该文件中写入串，然后输出指定串在该文件中的行号及位置。【问题分析】首先在目录D:下创建一个名为iesifile.ixi的文件，并写入串，然后计算指定串在lesifile.ixi文件中的行号，最后使用BF算法进行模式匹配，以确定指定串在具体行中的位置。【学生