数据结构授课教案-第4章.doc

山东轻工业学院教师授课教案课程名称:数据结构(计科)课程代码:学分::必修开课单位:信息科学与技术学院授课班级:授课教师:杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第四章串第一节串类型的定义串、串长、子串、空格串等概念和串的基本运算。第二节串的表示和实现串的定长存储表示及实现,串的堆分配表示和块链存储表示。第三节串的模式匹配算法串的模式匹配算法(KMP算法)。目的要求目的:理解串的定义、基本运算和实现,理解模式匹配算法。基本要求:了解串的存储结构和基本操作、串的KMP模式匹配方法;理解串的概念和基本操作。重点串的基本概念和基本操作。难点KMP模式匹配方法。(C语言版),严蔚敏,清华大学出版社,2002。、算法与应用-C++语言描述,(美)SartajSahni著,汪诗林等译,***出版社,2002。课型理论课学时分配复****分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共2学时注:课型一栏填写理论课、实验课、、串的基本概念串(String)是零个或多个字符组成的有限序列。 一般记为:S=‘a1a2…an’(n≥0)其中S为串名,用单引号括起来的为串值,n为串的长度。空串(NullString):n=0时的串为空串空格串(Blankstring):由一个或多个称为空格的特殊字符组成的串。请注意空串(NullString)和空格串(Blankstring)的区别。子串:串中任意个连续的字符组成的子序列称为该串的子串。主串:包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。假如有串A=‘ChinaBeijing’,B=‘Beijing’,C=‘China’,则它们的长度分别为13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。当且仅当两个串的值相等时,称这两个串是相等的。即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。需要特别指出的是,串值必须用一对单引号括起来(C语言中是双引号),但单引号是界限符,它不属于串,其作用是避免与变量名或常量混淆。二、串的基本操作求串长StrLength(S)(2)复制StrCopy(S,T)(3)串联接ConCat(S,T)(4)pare(S,T)(5)求子串SubString(S,pos,len)。可用定长数组描述。#definemaxstrlen256typedefcharSString[maxstrlen];sstrings;//s是一个可容纳255个字符的顺序串。串长的表示方法:1、用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如,C语言中以字符‵\0′表示串值的终结。2、用s[0]存放串的实际长度,串值存放在s[1]~s[MAXSIZE]。3、类似顺序表,另设一个整数表示串长:typedefstruct{charch[maxstrlen];intlength;}sstring;例:串联接 sta