《数据结构》 第四章串
第四章 串 《数据结构》
第四章串 主要内容 1.串的逻辑结构 2.串的基本操作 3.串的链式存储结构 4.串的堆存出结构 5.串的顺序存储结构 6.静态结构存储串时的操作 第2页
第四章 串 第2页 主要内容 1. 串的逻辑结构 2. 串的基本操作 3. 串的链式存储结构 4. 串的堆存出结构 5. 串的顺序存储结构 6. 静态结构存储串时的操作
第四章串 主要内容 7模式匹配(重点) ·静态结构存储串时的操作(ndex函数) 朴素的模式匹配算法(BF算法) 改进的模式匹配算法(KMP算法) 求模式串next函数值的算法 求模式串next函数值的修正算法 °next函数的性质 示例与模式匹配 第3页
第四章 串 第3页 主要内容 • 静态结构存储串时的操作（Index函数） • 朴素的模式匹配算法（BF算法） • 改进的模式匹配算法（KMP算法） • 求模式串next函数值的算法 • 求模式串next函数值的修正算法 • next函数的性质 • 示例与模式匹配 7.模式匹配（重点）
第四章串 第四章串 串(又称字符串)是一种特殊的线 性表,它的每个结点仅由一个字符组成 本章将讨论串的有关概念、结构、 存储方法和串的基本运算及其实现。 第4页
第四章 串 第4页 第四章 串 串（又称字符串）是一种特殊的线 性表，它的每个结点仅由一个字符组成 。 本章将讨论串的有关概念、结构、 存储方法和串的基本运算及其实现
0.的逻结构 第四章串 定义:串( String)是零个或多个字符组成的 有限序列。 般记为:S=a1a2an(n≥0) 术语 1)串名:S 2)串值:a1a2a",a(1≤i-n) 3)串的长度:串中所包含的字符个数,如串 abcde的长度为5 第5页
第四章 串 第5页 定义：串（String）是零个或多个字符组成的 有限序列。 一般记为： S=‘a1a2···an ’ (n≥0). 术语 1）串名：S. 2）串值： 'a1a2···an ' ，ai (1≤i≤n). 3）串的长度：串中所包含的字符个数，如串 'abcde'的长度为5. ⚫ 串的逻辑结构
第四章串 0的逻结构 4)空:长度为0m=0)的串,它不包含任何字 符,记作S=“(或S=q) 5)空格:由空格符(ASCH值32)组成的串, 如S 注意S=与S="不同,前者 是长度为1的非空串,它含有一个空格字 符,而后者是长度为0的空串 6)子:串中任意个连续的字符组成的子序列 。比如 abcde中的"bcd. 第6页
第四章 串 第6页 4）空串：长度为0(n=0)的串，它不包含任何字 符，记作S=''(或S=φ). 5）空格串：由空格符(ASCII值32)组成的串， 如S=‘ ’.注意S= ' '与S=''不同，前者 是长度为1的非空串，它含有一个空格字 符，而后者是长度为0的空串。 6）子串：串中任意个连续的字符组成的子序列 。比如'abcde'中的'bcd'. ⚫ 串的逻辑结构
0.的逻结构 第四章串 一用二元组的形式来定义:串是一个二元组, string=(D,R) 其中 D={a|a∈字符集=1,2;…,n,n20} R={N} 有序偶的集合N=[a11a斗a1,a1∈D,j=2,3,…n} 故串的逻辑结构和线性表极为相似。区别仅在D 的定义上。线性表的数据对象可以是任意数据类型, 而串的数据对象是字符集 串是几种最简单的数据结构之 第7页
第四章 串 第7页 用二元组的形式来定义串：串是一个二元组, string = ( D, R ) 其中 D={ai |ai∈字符集,i=1,2,···,n,n≥0} R={N} 有序偶的集合N={| ai-1 ,ai ∈D, i=2,3,···n} 故串的逻辑结构和线性表极为相似。区别仅在D 的定义上。线性表的数据对象可以是任意数据类型， 而串的数据对象是字符集。 串是几种最简单的数据结构之一。 ⚫ 串的逻辑结构
0.的基本操作 第四章串 串虽然是一种特殊的线性表,但由于存储结构有所不同,故其 基本操作也不同 1、基本操作子集不同,比如串包含有联接、求子串等操作 2、操作对象不同,线性表的操作通常以数据元素或结点为操 作对象,而串的操作主要以串的整体为操作对象。 1)值操作 Assign(st)s为串名,t为字符串变量 Create(ssss为串名,S为字符序列 2)判等函数 Equal(st)返回布尔值true或 false.s.可为非空串或空串 3)求长历数 Length(s)返回串s字符的个数 4)联接函数 Concat(st)返回由串St相联接而成的新串。联接运算不满足 交换律,但满足结合律 第8页
第四章 串 第8页 串虽然是一种特殊的线性表，但由于存储结构有所不同，故其 基本操作也不同。 1、基本操作子集不同，比如串包含有联接、求子串等操作 2、操作对象不同，线性表的操作通常以数据元素或结点为操 作对象，而串的操作主要以串的整体为操作对象。 1）赋值操作 Assign(s,t) s为串名，t为字符串变量。 Create(s,ss) s为串名，ss为字符序列。 2）判等函数 Equal(s,t) 返回布尔值true或false.s,t可为非空串或空串。 3）求串长函数 Length(s) 返回串s字符的个数。 4）联接函数 Concat(s,t) 返回由串s,t相联接而成的新串。联接运算不满足 交换律，但满足结合律。 ⚫ 串的基本操作
0.的基本操作 第四章串 5)求子函数 Substr(S, start len)返回从串S中第 start个字符起,长度为 en的字符序列。 一要求1tngn+1, Oslens Length(s)-start+1 6)定位所数一 Index(s, t) 返回串t在串s中第一次出现时的串首位置,若未出现,则返回 值0,要求t不能是空串 7)置换操作 Replace(s, t, v) 以串v换所有在串s中出现的和非空串相等的子串。 第9页
第四章 串 第9页 5）求子串函数 Substr(S,start,len) 返回从串S中第start个字符起，长度为 len的字符序列。 要求 1≤start≤Length(s)+1, 0≤len≤ Length(s)-start+1. 6）定位函数 Index(s,t) 返回串t在串s中第一次出现时的串首位置，若未出现，则返回 值0，要求t不能是空串。 7）置换操作 Replace(s,t,v) 以串v替换所有在串s中出现的和非空串t相等的子串。 ⚫ 串的基本操作
0.的基本操作 第四章串 8)插入(就)操作一 Insert(s, pos, t) 在串s的第pos个字符之前插入串t.要求1 possLength(s)+1。 注. Insert(s, Length(s)+1,)与 Concat((s,功能相同, 即当pos= Length(s)+1时,t将插入至s的尾部之后。 9)坳除操作 Delete(s, pos, len 一从串s中删去从第pos个字符起,长度为en的子串。要求 1spossLength(s 1slensLength()-poS+ 说明:可将1)至5)定义为串的基本操作,6)至9)可由基本操作加 一以实现 第10页
第四章 串 第10页 ⚫ 串的基本操作 8）插入（前插）操作 Insert(s,pos,t) 在串s的第pos个字符之前插入串t. 要求1≤pos≤Length(s)+1。 注. Insert(S,Length(s)+1,t) 与 Concat(s,t)功能相同， 即当pos= Length(s)+1时，t将插入至s的尾部之后。 9）删除操作 Delete(s,pos,len) 从串s中删去从第pos个字符起，长度为len的子串。要求 1≤pos≤Length(s)， 且1≤len≤Length(s)-pos+1。 说明：可将1)至5)定义为串的基本操作，6)至9)可由基本操作加 以实现