数据结构——串学生讲解反转课堂课件.pptxVIP

数据结构与算法第4章串王磊代文远网络1701SPOC3刘晨光麻治翁世杰赵宗旭

目录content01串及其运算02串的存储结构及实现串的模式匹配03实例分析04

串的应用程序设计中的源程序、目标程序事物处理程序中，顾客姓名、地址、货物的产地、名称软件系统方面的字符编辑、情报检索、词法分析等多入侵检测系统DNA序列检测……

串的定义由零个或多个字符组成的有限序列，一般记作：S=‘aaa…a’特殊的线性表，数据元素限制为字符集123n(1)S为串的名字(2)单引号括起来的字符序列为串的值将串值括起来的单引号本身不属于串，它的作用是避免串与常数或与标识符混淆‘123’123‘La’La(3)a(1≤i≤n)可以是字母、数字或其他字符i(4)n为串中字符的个数，称为串的长度

D=‘structure‘’’是长度为0的空串‘’长度为1的空白串A=‘data’B=‘datastructure’C=‘datastructure’(1)空串长度为0的串，不包含任何字符(2)空白串仅由一个或多个空格组成的串，长度≥1(3)子串串中任意个连续字符组成的子序列(4)主串包含子串的串空串？自身？‘d‘’da‘’dat‘’data’(5)前缀子串、真前缀子串(6)后缀子串、真后缀子串‘ata’‘a‘’ta’‘data’子串B在主串中，从第1个位置开始的位置是：2(7)位置字符在串中的序号子串在主串中的位置？主串：A=‘abcaabcaaabc’子串：B=‘bca’子串B在主串中，从第2个位置开始的位置是：6(8)相等串两个串的长度相等每个对应位置字符相等子串从主串的某一位置开始，其在主串中首次出现的位置(9)模式匹配

串的基本运算串的抽象数据类型定义：ADTString{数据对象：D={a|a∈CharacterSet，i=1,2,…,n,n≥0}ii数据关系：基本操作：R={a,a|a,a∈D，i=2,3,…,n}i-1ii-1iStrAssign(S,chars)StrCopy(S,T)StrLength(S)StrInsert(S,pos,T)StrDelete(S,pos,len)StrCompare(S,T)StrCat(S,T)SubString(T,S,pos,len)StrIndex(S,pos,T)StrReplace(S,T,V)StrEmpty(S)StrClear(S)StrDestory(S)……这些串的基本操作通常以“串的整体”“串的一部分”作为操作对象}ADTString

串的基本运算对于以上串的基本操作，C语言的函数库文件string.h包括其中几个字符串操作函数：gets(S)输入字符串puts(S)输出字符串strlen(S)求字符串S的有效长度strcmp(S,S)比较字符串S和S1212strcpy(S,S)复制字符串S至S1221strcat(S,S)连接字符串S至S后1221

串的基本运算StrInsert(S,pos,T)初始条件：串S和串T存在，1≤pos≤StrLength(S)+1操作结果：在字符串S的第pos个字符之前插入字符串T例:S=‘chater’,T=‘rac’,运行StrInsert(S,4,T)结果：S=‘character’

串的基本运算StrDelete(S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1操作结果：从串S中删除从第pos个字符开始连续len个字符后形成的子串例:S=‘chapter’,运行StrDelete(S,5,3)结果：S=‘chap’

串的基本运算StrCat(S,T)初始条件：串S和串T存在操作结果：将字符串T的值连接在串S的后面例:S=‘man’,运行StrCat(S,‘kind’)结果：S=‘mankind’

串的基本运算SubString(T,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1操作结果：截取字符串S中从第pos个字符开始连续len个字符形成的子串，并赋值给串T例:S=‘commander’,运行SubString(T1,S,4,3)结果：T1=‘man’运行SubString(T2,S,5,0)结果：T2=‘’运行SubString(T3,S,4,7)结果T3无结果，函数返回错误

串的基本运算StrIndex(S,pos,T)初始条件：串S和串T存在，1≤pos≤StrLength(S)操作结果：若字符串S从第pos个字符后存在与字符串T相等的子串，则返回字符串T在串