《数据结构》课程PPT教学课件（2012）第4章 串 String（1/2）

第4章串(String) 4.1串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

1 第4章 串（String） 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

4.1串类型的定义 串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。 记为： S=‘a1a2.an (n≥0 串名串值（用”括起来） 隐含结束符八0'， 即ASCII码NUL 为何要单独讨论“串”类型？ 1)字符串操作比其他数据类型更复杂（如拷贝、 连接操作) 2)程序设计中，处理对象很多都是串类型

2 记为： s =‘ a1 a2 . an’ (n≥0 ) 串名 串值（用‘’ 括起来） 串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。 4.1 串类型的定义 隐含结束符‘\0’ ， 即ASCII码NUL 为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型

若干术语： 串长：串中字符的个数(n≥0).n=0时称为空串⑦ 空白串：由一个或多个空格符组成的串。 问：空串和空白串有无区别？ 答： 有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串. 3

3 若干术语： 串长：串中字符的个数（n≥0）. n=0 时称为空串  。 空白串：由一个或多个空格符组成的串。 问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符 ‘ ’(空格键)的字符串

子串：串S中任意个连续的字符序列叫S的子串；S叫主串。 子串位置：子串的第一个字符在主串中的序号。 字符位置：字符在串中的序号。 串相等：串长度相等，且对应位置上字符相等。 例1：现有以下4个字符串： a =BEP b=JING'c=BEIJING' d=BEI JING' 问：①他们各自的长度？ a=3,b=4,c卡7，d=8 ②a是哪个串的子串？在主串中的位置是多少？ a是c和d的子串，在c和d中的位置都是1 ③空串是哪个串的子串？a是不是自己的子串？ “空串是任意串的子串；任意串S都是S本身的子串，除S本身 外，S的其他子串称为S的真子串。 《数据结构与算法》中山大学出版社

4 子串： 子串位置： 字符位置： 串相等： 例1：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ a是c和d的子串，在c和d中的位置都是1 串S中任意个连续的字符序列叫S的子串; S叫主串。 子串的第一个字符在主串中的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 “空串是任意串的子串；任意串S都是S本身的子串，除S本身 外，S的其他子串称为S的真子串。 ” ——《数据结构与算法》中山大学出版社 ③ 空串是哪个串的子串？a是不是自己的子串？

串的抽象数据类型定义（参见教材P71) ADT String{ Objects: D=fai aiE CharacterSet,i=1,2,.,n,n20} Relations:R1={ai-1,ai ED,i=2,., n, functions: /至少有13种基本操作 StrAssign(&T,chars) /串赋值，生成值为chars的串T StrCompare(S,T) /串比较，若5>工，返回值大于0. 最 StrLength(S) /求串长，即返回串S中的元素个数 操 Concat(&T,S1,S2) /串连接，用T返回S1+S2的新串 SubString(&Sub,S,pos,len)/求S中pos起长度为len的子串 子集 Index(S,T,pos) 仔串定位函数（模式匹配），返回位置 Replace(&S,T,V) 用孓串V替换子串T }ADT String C语言中已有类似串运算函数！

5 C语言中已有类似串运算函数！ ADT String{ Objects: D={ai | ai∈CharacterSet, i=1, 2,.，n, n≥0} Relations: R1={ | ai-1,ai ∈D, i=2, .，n} functions: //至少有13种基本操作 StrAssign(&T, chars) // 串赋值，生成值为chars的串T StrCompare(S,T) // 串比较，若S>T，返回值大于0. StrLength(S) // 求串长，即返回串S中的元素个数 Concat(&T, S1, S2) // 串连接，用T返回S1＋S2的新串 SubString(&Sub, S, pos, len) // 求S中pos起长度为len的子串 . Index(S, T, pos) //子串定位函数（模式匹配），返回位置 Replace(&S, T,V) // 用子串V替换子串T }ADT String 串的抽象数据类型定义（参见教材P71） 最 小 操 作 子 集

复习：c语言中常用的串运算 注：用C处理字符串时，要调用标准库函数include 类C 串比较：int stremp(char*sl,char*s2); StrCompare(S,T) 求串长：int strlen(char*s; StrLength(S） 串连接：char strcat(char*to,char*from) Concat(&T,S1,S2) 子串T定位：char strchr(char*s,char*c)Index(S,T,pos) 注：Concat操作=concatenation,把 多个短字符串合并为长字符串 6

6 注：Concat操作＝concatenation，把 多个短字符串合并为长字符串 复习：C语言中常用的串运算 C 串比较：int strcmp(char *s1,char *s2); 求串长：int strlen(char *s); 串连接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c); . 注：用C处理字符串时，要调用标准库函数#include 类C StrCompare(S,T) StrLength(S) Concat(&T, S1, S2) Index(S, T, pos)

例1：设s=I AM A STUDENT’,t='GOOD, q=NORKER’。求： StrLength(s)= 141/参死R71 Index(S,T,pos) /返回子串T在pos StrLength(t) 之后的位置 SubString(&sub,s,8,7)=STUDENT' SubString(&sub,t,2,1)=O' Replace(&S,T,V) Index(s,‘A'斤 /用子串V替换子串T Index(s,t)= 中没有=GOOD!) Replace(&s,'STUDENT',q )='IAMA WORKER

7 Replace(&S, T,V) // 用子串V替换子串T 设 s =’I AM A STUDENT’ , t =’GOOD’ , q=’WORKER’。求： 例1： StrLength(s) ＝ StrLength(t) ＝ SubString(&sub,s, 8, 7)= SubString(&sub, t, 2, 1)= Index(s, ‘A’)= Index(s, t)= Replace( &s, ‘STUDENT’, q )= 14 //参见P71 4 ‘STUDENT’ ‘O’ 3 0 （ s中没有t=’GOOD’ ！） Index(S, T, pos) // 返回子串T在pos 之后的位置 ’I AM A WORKER’

提问：当s=IQM④STUDENT时， INDEX(s,A,pos)=3,若想搜索后面那个‘？ 怎么办？ 答：根据教材P71倒1行的函数说明，INDEX(s,A)返 回的只是“第一次”出现的位置。 如果还要搜索后面的A,则pos变量要跟着变才行。 也就是说，要把得到的”第一次”位置再代入 INDEX(s,'A',pos)函数中循环操作才行。 8

8 提问： 当s =’I AM A STUDENT’时, INDEX（s,’A’ ，pos）=3，若想搜索后面那个‘A’ 怎么办？ 答: 根据教材P71倒1行的函数说明， INDEX（s,’A’）返 回的只是“第一次”出现的位置。 如果还要搜索后面的A，则pos变量要跟着变才行。 也就是说，要把得到的“第一次”位置再代入 INDEX（ s,’A’ ，pos）函数中循环操作才行

例2：设s=I AM A STUDENT',t='GOOD',求： Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))=? 本章自测题 解：因为 SubString(s,6,2)=A'; SubString(s,7,8)=STUDENT' Concat(t,SubString(s,7,8))='GOOD STUDENT' 所以： Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) =‘A GOOD STUDENT' 9

9 （本章自测题） 解：因为 SubString(s,6,2)＝‘A’； SubString(s,7,8)＝‘ STUDENT’ Concat(t,SubString(s,7,8))＝’GOOD STUDENT’ 所以： Concat(SubString(s,6,2), Concat(t,SubString(s,7,8))) ＝‘AGOOD STUDENT’ 例2：设 s =’I AM A STUDENT’ , t =’GOOD’ ,求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ＝？

4.2串的表示和实现 首先强调：串与线性表的运算有所不同，是以“串的整体”作为 操作对像，例如查找某子串，在主串某位置上插入一个子串等。 串有三种机内表示方法： 定长顺序存储表示 顺序 用一组地址连续的存储单元存储串值的字符序列 存储 属静态存储方式。 堆分配存储表示 用一组地址连续的存储单元存储串值的字符序列， 但存储空间是在程序执行过程中动态分配而得。 链式 ●串的块链存储表示 存储 链式方式存储 10

10 4.2 串的表示和实现 定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列， 属静态存储方式。 堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列, 但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示 ——链式方式存储 首先强调：串与线性表的运算有所不同，是以“串的整体”作为 操作对象，例如查找某子串，在主串某位置上插入一个子串等。 串有三种机内表示方法： 顺序 存储 链式 存储