资源描述：
《《严蔚敏数据结构》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章串（String）4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法1记为：s=‘a1a2……..an’(n≥0)串名串值（用‘’括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。4.1串类型的定义隐含结束符‘ ’，即ASCII码NULL为何要单独讨论“串”类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。2若干术语：串长：串中字符的个数（n≥0）.n=0时称为空串。空白串：由一个或多个空格符组成的串。问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；
2、而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.3子串：子串位置：字符位置：串相等：例1：现有以下4个字符串：a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’问：①他们各自的长度？a是c和d的子串，在c和d中的位置都是1串S中任意个连续的字符序列叫S的子串;S叫主串。子串的第一个字符在主串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。②a是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”——《数据结构与算法
3、》中山大学出版社③空串是哪个串的子串？a是不是自己的子串？4C语言中已有类似串运算函数！ADTString{Objects:D={ai
4、ai∈CharacterSet,i=1,2,…，n,n≥0}Relations:R1={
5、ai-1,ai∈D,i=2,…，n}functions://至少有13种基本操作StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若S>T，返回值大于0…StrLength(S)//求串长，即返回串S中的元素个数Concat(&T,S1,S2)//串连接，用T返回S1＋S2的新串SubS
6、tring(&Sub,S,pos,len)//求S中pos起长度为len的子串……Index(S,T,pos)//子串定位函数（模式匹配），返回位置Replace(&S,T,V)//用子串V替换子串T}ADTString串的抽象数据类型定义（参见教材P71）最小操作子集5注：Concat操作＝concatenation，把多个短字符串合并为长字符串复习：C语言中常用的串运算C串比较：intstrcmp(char*s1,char*s2);求串长：intstrlen(char*s);串连接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,
7、char*c);……注：用C处理字符串时，要调用标准库函数#include类CStrCompare(S,T)StrLength(S)Concat(&T,S1,S2)Index(S,T,pos)6Replace(&S,T,V)//用子串V替换子串T设s=’IAMASTUDENT’,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//参见
8、P714‘STUDENT’‘O’30（s中没有t=’GOOD’！）Index(S,T,pos)//返回子串T在pos之后的位置’IAMAWORKER’7提问：当s=’IAMASTUDENT’时,INDEX（s,’A’，pos）=3，若想搜索后面那个‘A’怎么办？答:根据教材P71倒1行的函数说明，INDEX（s,’A’）返回的只是“第一次”出现的位置。如果还要搜索后面的A，则pos变量要跟着变才行。也就是说，要把得到的“第一次”位置再代入INDEX（s,’A’，pos）函数中循环操作才行。8解：因为SubString(s,6,2)＝‘A’；SubString(s,7,8)＝‘STUDENT’
9、Concat(,t,SubString(s,7,8))＝’GOODSTUDENT’所以：Concat(,SubString(s,6,2),Concat(t,SubString(s,7,8)))＝‘AGOODSTUDENT’例2：设s=’IAMASTUDENT’,t=’GOOD’,求：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？94.2串的表示和实现
