教科版 （2019）高二选择性必修1信息技术第2单元第3课《字符串应用》课件

2.3字符串应用 高中信息技术/教科版/选择性必修1 目录 1.案例导入 2.体验探究 3.编程实现 4.课堂小结 1.案例导入 前两节我们学习了线性表及其应用，如果需要处理的数据类型不是数值，而是文本，我们需要选择哪种数据结构呢？ 字符串 我们日常生活中和学习中有哪些应用字符串的例子？ 邮件里面的查找功能 文本编辑软件中的“查找”“替换”功能 上网搜索查找功能 字符串使用案例 在文本编辑软件中利用“查找”命令，可以在指定的文本信息中查找特定形式的字符串；在邮件过滤器中，根据事先定义的字符串属性特征，通过获取电子邮箱地址、标题及正文来识别垃圾邮件。另外，在文本挖掘、机器翻译、信息检索、问答系统和对话系统等自然语言处理技术中，也随处可见字符串的身影。 2.新课讲授 学习任务 本节围绕“破译恺撒密码”项目展开学习，通过项目活动熟悉字符串的基本操作，理解字符串抽象数据类型的定义，并利用字符串的基本方法编程实现破译恺撒密码的操作。本节主要包含“体验手动破译恺撒密码”和“编程实现破译恺撒密码”两个任务。 解密“恺撒密码” 密码技术作为信息安全的核心技术，不仅可以保证信息的机密性、完整性和可用性，还可以防止信息被篡改和伪造。 “恺撒密码”的历史故事 任务一 体验手动破译恺撒密码 活动1体验恺撒加密 恺撒加密作为一种最为古老的加密技术，在古罗马的时候就已经很流行。它通过把字母移动一定的位数来实现加密。明文中的所有字母都在字母表上向左 (或向右) 按照某个位数进行偏移后被替换成密文，其中的位数就是恺撒密码加密和解密的密钥。 明文: Imagination is more important than knowledge. 密钥:3 当密钥为3时，所有字符向左偏移3位，加密时明文里所有的字母A将被替换成X，B变成Y，以此类推，X将变成U，Y变成V，Z变成W，如下图所示。 任务一 体验手动破译恺撒密码 活动1体验恺撒加密 明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 密码表 请补全加密后的密文: fp jlob fjmloqxkq . 明文: Imagination is more important than knowledge. 密钥:3 FJxdfkxqflk qexk hkltibadb 任务一 体验手动破译恺撒密码 活动2体验恺撒解密 明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 密码表 请补全解密后的明文: great was ever without . 密文: Fglzafy yjwsl osk wnwj suzawnwv oalzgml wflzmkaske 密钥:8 当密钥是8的时候，解密时密文里所有的字母A将被替换成I，B变成J，以此类推，X将变成F，Y变成G，乙变成H，如图所示。 Nothing achieved enthusiasm 字符串及其概念 字符串:是一种由字符构成的线性结构。上面活动中的明文和密文均是字符串，字符串中的每个字符从左到右依次排列，且有确定的位置。字符串中第一个字符的位置下标是0，可以根据字符在字符串中的位置下标来访问字符。 任务一 体验手动破译恺撒密码 活动2体验恺撒解密 字符串长度:字符串所含字符的总数称为字符串的长度，长度为0的字符串称作空字符串或空串。 子串:字符串中某一连续的片段称为字符串的子串。任何字符串都是自己的子串。 任务一 体验手动破译恺撒密码 活动2体验恺撒解密 字符串s="Data Structure”由14个字符构成，因此字符串长度为14，其中位置下标为5的字符是“S“ata”是字符串s的个子串。 D a t a S t r u c t u r e 0 1 2 3 4 5 6 7 8 9 10 11 12 13 S S[0] S[5] S[13] 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 密文:pqrabkqzxoapqrxoq 线索:信息中包含了Stuar，不区分大小写，共有17个字符。 恺撒加密技术的密钥是有限的，只有1~25，所以可以用穷举的方法来破译密文。可分三步操作来破译密文。 (1)对“stuart”加密，选代循环，密匙从1到25； (2)在任务给的密文里面查找“stuart”的密文； (3)如果存在即可以知道密钥，进而破译密文； 否则密钥增加1，继续进行操作(1)。 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 ”stuart”的密文为“rstzqs“。手动的字符串查找当密钥为1时，过程如下: 字符串“pqrabkqzxoapqrxoq”为目标串T，字符串“rstzqs”为模式串P。分别写在等间距格子的纸带上，字符串T的纸带固定不动，字符串P的纸带的首字符与字符串T的首字符对齐，如图所示。 目标串T p q r a b k q z x o a p q r x o q 模式串P r s t z q s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 第1轮匹配:从目标串T的第一个字符开始，将T和P对应的字符逐个依次比对。如图所示，第一个字符“p”和“r”不相同，此轮匹配失败。 目标串T p q r a b k q z x o a p q r x o q 模式串P r s t z q s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 第2轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的字符对不相同，此轮匹配失败。 目标串T p q r a b k q z x o a p q r x o q 模式串P r s t z q s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 第3轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的首字符相同，但下一个字符对“a”和“s”不相同，此轮匹配也失败。 目标串T p q r a b k q z x o a p q r x o q 模式串P r s t z q s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 = ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 第4轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的首字符不相同，此轮匹配也失败。 目标串T p q r a b k q z x o a p q r x o q 模式串P r s t z q s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码 第5~17轮匹配:每轮匹配均失败。 “stuart”的密文为“qrsypr”，手动查找字符的结果密钥为2时，字符匹配失败。 当密钥为2时，stuart”的密文为“qrsypr”，手动查找字符的结果是字符匹配失败。 当密钥为3时，“stuart”的密文为“pqrxoq”，手动查找字符的结果是在第12轮字符匹配成功。 经过解密，密文对应的明文是 。 studentcardstuart 通过体验手动破译恺撒密码，你能总结出字符串匹配的方法吗 字符串匹配的方法 (1) 字符串匹配检测需要进行多轮，首轮匹配检测的起始端从目标串T的第一个字符开始。 (2)将目标串T和模式串P的对应字符逐个依次比对，如果所有字符都相同，匹配成功，操作结束;否则只要有任一个字符不同，本轮匹配失败，执行 (3)，进行下一轮匹配检测。 (3)若T和P的右边界已对齐，整个匹配检测过程失败;否则，将匹配检测的起始端在T中后移一位，执行(2)。 字符串匹配 在字符串中检测查找特定形式的字符串的这类操作都属于字符串匹配(string matching)。即给定目标串T和模式串P之后，判定T中是否存在某一子串与P相同，如果存在则匹配成功。 字符串匹配的应用非常广泛，比如垃圾邮件的检测、搜索引擎关键字的查询、网络热搜排行榜的更新等都会用到字符串匹配操作。 字符串抽象数据类型的定义 ADT接口定义 说明 String(value) 建立一个字符串对象，value是字符序列或者其他类型对象。 isEmpty（） 判断字符串是否是空串 size（） 获取字符串的长度 split(sep) 根据分隔符sep将字符串进行分隔，并返回分隔后字符串的列表。 strip（） 返回去掉前后空格之后的字符串。 find(sub) 返回sub在字符串中第一次出现的位置，如果没有则返回-1。 字符串抽象数据类型的定义 ADT接口定义 说明 replace(old,new) 返回将所有old子串替换为new后的字符串 count(sub) 返回sub在字符串中出现的次数 concat(another) 返回与another连接后的字符串。 substring(start,end) 返回起始位置为start，结束位置为end的子字符串 getItem(index) 返回位置为index的字符。 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作 Python内置的字符串类型str是字符串抽象数据类型的一种具体实现，对于抽象数据类型中定义的每个接口，Python的字符串类型都有对应的实现，可以根据需要直接调用。 若字符串s="imagination is more important than knowledge"，如图所示，请完成下表。 i m a g i n a t i o n . . i m p o r t a n t . . s 0 1 2 3 4 5 6 7 8 9 10 20 21 22 23 24 25 26 27 28 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作 ADT String 操作 输出 String(value) s=str("imagination is moreimportant than knowledge")或s="imagination is moreimportant than knowledge" "imagination is moreimportant than knowledge" isEmpty（） s==”“ False size（） len（） 44 split(sep) s.split ["imagination","is"more","important","than""knowledge"] getItem(index) s[20] “i” 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作 ADT String 操作 输出 strip（） s.strip（） "imagination is moreimportant than knowledge” find(sub) s.find("import") 20 replace(old,new) s.replace("more","less") count(sub) s.count("import") 1 concat(another) s+"Data Structure" substring(start,end) s[3:10] “Imagination is more important than knowledge” “Imagination is more important than knowledge data Structure” “gination” 3.编程实现 任务二 编程实现破译恺撒密码 活动1建立数据结构 密文: sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog。 线索:明文中包含有“programmer“ 根据字符串的抽象数据类型的定义，首先创建两个字符串对象分别来保存已知密文目标串T和线索模式串P。 01.#密文目标串初始化 02.tStr="sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog”03.pStr="programmer" #线索模式串初始化 任务二 编程实现破译恺撒密码 活动2算法设计与实现 密文: sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog。 线索:明文中包含有“programmer“ 根据字符串的抽象数据类型的定义，首先创建两个字符串对象分别来保存已知密文目标串T和线索模式串P。 01.#密文目标串初始化 02.tStr="sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog”03.pStr="programmer" #线索模式串初始化 任务二 编程实现破译恺撒密码 活动2算法设计与实现 如前所述，利用字符串的基本操作实现破译恺撒密码的算法描述 如下。 (1)对已知线索字符串加密，密钥初始值为1。 (2) 在任务二给出的密文里面查找线索字符串的密文。 (3)如果存在即可以知道密钥，进而破译密；;否则密钥增加1，继续进行操作(1)。 根据以上算法，定义加密函数enCrypt(message,key)，参数key是密钥，message是明文，根据密钥key对明文message进行加密。若左移后的位置大于0则直接左移，否则需要回到字母表末尾继续计算移动位置，这里用对26求余得出移动位置。请补全下面的代码。 任务二 编程实现破译恺撒密码 活动2算法设计与实现 04.#加密函数 05. def enCrypt(message, key) : #用key对message加密 06.alphabet='abcdefghijklmnopqrstuvwxyz' #字母表 07.encrypted=' ’ #加密后的密文 08.for char in message: #对明文字符依次加密 09.if char not in alphabet: #非字符不变 10.encrypted=encrypted+char 11.else: #字符加密 12.rotatedIndex=alphabet.index(char)-key #左移位数 任务二 编程实现破译恺撒密码 活动2算法设计与实现 13.#位数对26求余 14.encrypted=encrypted+ . 15.return encrypted alphabet[rotatedIndex%26] 任务二 编程实现破译恺撒密码 活动2算法设计与实现 在任务二给出的密文里面查找线索字符串的密文可以通过字符串匹配算法来实现，具体描述如下。 (1) 字符串匹配检测需要进行多轮，首轮匹配检测的起始端从目标串T的第一个字符开始。 (2)将目标串T和模式串P的对应字符逐个依次比对，如果所有字符都相同，匹配成功，算法结束;否则只要有任一个字符不同，本轮匹配失败，执行(3)，进行下一轮匹配检测。 (3)若T和P的右边界已对齐，整个匹配检测过程失败;否则，将匹配检测的起始端在T中后移一位，执行(2)。 任务二 编程实现破译恺撒密码 活动2算法设计与实现 以上算法可以用嵌套的for循环实现字符串匹配过程，外层的for循环实现每轮匹配检测向右移动，内层的for循环实现依次比对字符。以下代码是通过函数stringMatch(t,p)实现字符串匹配的过程。请补全下面的代码。 16. #字符串匹配函数 17. def stringMatch(t,p): 18. n=len(t) #目标串长度 19.m=len(p) #模式串长度 20.for i in range(n-m+1): #字符串匹配过程 21. for j in range(m): #字符比对过程 任务二 编程实现破译恺撒密码 活动2算法设计与实现 以上算法可以用嵌套的for循环实现字符串匹配过程，外层的for循环实现每轮匹配检测向右移动，内层的for循环实现依次比对字符。以下代码是通过函数stringMatch(t,p)实现字符串匹配的过程。请补全下面的代码。 16. #字符串匹配函数 17. def stringMatch(t,p): 18. n=len(t) #目标串长度 19.m=len(p) #模式串长度 20.for i in range(n-m+1): #字符串匹配过程 21. for j in range(m): #字符比对过程 22.if #字符不同 23.break 24.else: #匹配成功 25.return i 26.return -1 #匹配失败 t[i+j]!=p[j]: 任务二 编程实现破译恺撒密码 活动2算法设计与实现 最后还需要定义解密函数deCrypt(message,key)，参数key是密钥，message是密文，依据密钥key对密文message进行解密。若右移后的位置小于26则直接右移，否则需要回到字母表首位继续计算移动位置，这里用对26求余得出移动位置。请补全下面的代码。 27.#解密函数 28.def deCrypt(message, key) : #用key对message进行解密29.alphabet='abcdefghijklmnopqrstuvwxyz’ #字母表 29.decrypted=' ’ #解密后的明文 31.for char in message: #对密文字符依次解密 任务二 编程实现破译恺撒密码 活动2算法设计与实现 32.if char not in alphabet: #非字符不变 33. decrypted=decrypted+charelse: #字符右移 34.else： 35.rotatedIndex= .##右移位数 36.#位数对26求余 37.decrypted=decrypted+alphabet[rotatedIndex % 26] 38.return decrypted 输出破译后的明文的程序代码如下所示。 alphabet.index(char)+key 任务二 编程实现破译恺撒密码 活动2算法设计与实现 39.#输出明文 40. for key in range(1,26): #密钥依次递增 41.#密文字符串匹配 42.if stringMatch(tStr.lower(),enCrypt(pStr,key))!=-1: 43. print(deCrypt(tStr.lower(),key)) #解密密文 44.break 4.else: 46.print("can not find it") 线性表和字符串都是线性结构，元素之间有先后关系，但字符串中每个元素只能存储字符，而线性表则可以存储任意类型的数据元素。 4.课堂小结 本节可我们学习了一种特殊的线性数据结构——字符串。通过活动熟悉了字符串的基本操作，总结·了字符串抽象数据类型的定义，并利用字符串的基本方法编程实现破译了恺撒密码的操作！ 请同学们认真完成教材中的拓展练习哦！ 下节课见！ $$