数据基础结构 4

教案纸（首页）第1页第次课学时授课时间___________教学主题串的基本概念，串的存储结构教学要求1、掌握串的逻辑结构特性和串抽象数据类型的描述方法。2、掌握串的两类存储结构设计方法以及各自的优缺点。3、掌握顺序串算法设计方法。4、掌握链串算法设计方法。。4、掌握栈在实际求解问题中的应用方法。教学重点串的顺序存储结构和链式存储结构的优缺点；顺序串运算算法设计；链串运算算法设计。教学难点串的顺序存储结构和链式存储结构的优缺点；顺序串运算算法设计；链串运算算法设计。教学方法讲授教学手段多媒体、板书讲授要点1、串的概念。2、串抽象数据类型的描述方法。3、串的顺序存储结构及顺序串算法设计方法。4、串的链式存储结构及链串算法设计方法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记4.1串1、串的定义串（或字符串）是由零个或多个字符组成的有限序列。串线性表关于串的几个概念：串中所含字符的个数称为该串的长度（或串长）。含零个字符的串称为空串，用Ф表示。非空串：通常用“a1a2…an”表示。其中，双引号不是串的内容，起标识作用，ai（1≤i≤n）代表一个字符。串相等：两个串的长度相等并且各个对应位置上的字符都相同时字串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串主串：是指包含子串的串举实例说明，加深学生对串的理解和认识。4.2串的存储结构1、串的存储结构顺序存储——顺序串链式存储——链串2、串的基本运算StrAssign(&s，cstr)：将字符串常量cstr赋给串s，即生成其值等于cstr的串s。StrCopy(&s，t)：串复制。将串t复制给串s。StrEqual(s，t)：判串相等。若两个串s与t相等则返回真；否则返回假。StrLength(s)：求串长。返回串s中字符个数。Concat(s，t)：串连接:返回由两个串s和t连接在一起形成的新串。SubStr(s，i，j)：求子串。返回串s中从第i（1≤i≤n）个字符开始的、由连续j个字符组成的子串。InsStr(s1，i，s2)：插入。将串s2插入到串s1的第i（1≤i≤n+1）个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。DelStr(s，i，j)：删除。从串s中删去从第i（1≤i≤n）个字符开始的长度为j的子串，并返回产生的新串。RepStr(s，i，j，t)：替换。在串s中，将第i（1≤i≤n）个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。DispStr(s)：串输出。输出串s的所有元素值。3、顺序串的基本操作实现非紧缩格式#defineMaxSize100typedefstruct{chardata[MaxSize];intlength;}SqString;例4-1。4、链串的基本操作实现typedefstructsnode{chardata;structsnode*next;}LinkStrNode;例4-3。教学总结：本章节给大家介绍了串的基本定义，串的顺序存储结构和链式存储结构及其基本操作的实现。

第次课学时授课时间__________教学主题串的模式匹配算法教学要求1、掌握串的模式匹配算法设计方法教学重点简单模式匹配算法设计，KMP算法设计，KMP算法是如何提高串匹配效率的。教学难点KMP算法设计，KMP算法是如何提高串匹配效率的。教学方法讲授+练习教学手段多媒体、上机操作讲授要点1、串的模式匹配的概念。2、串的简单模式匹配算法。3、KMP算法及其提高串匹配效率的特点。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记4.3串的模式匹配1、简单匹配算法Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举的思路。BF算法思路：从s的第一个字符开始和t的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从s的第二个字符开始和t的第一个字符进行比较，重复上述过程，直到t中的字符全部比较完毕，则说明匹配成功；如果s中的字符全部比较完，则说明匹配失败。B－F算法实现及分析。2、KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。KMP算法思路：基于BF算法，采用空间换时间的方式，提取保存有利于匹配的信息。S串不回溯，模式串t