《数据结构与算法》_第4章 串-PPT.pptxVIP

【本章重点】;【本章难点】;【本章内容】;4.1串的概念及基本运算;（2）串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应的称为主串。子串在主串中的序号定义为子串在主串中首次出现的位置序号。例如，设S1和S2分别为：

S1=ThisisastringS2=is

则S2是S1的子串，S1是S2的主串。S2在S1中出现了两次，首次出现在主串的第3个位置上，因此S2在S1中的序号是3。

（3）串可以分为串变量和串常量。例如使用C语言可以有如下定义：

charstr[]=string;constcharstr_const[]=string;

str是串变量，而str_const是串符号常量。

（4）只含有空格的串称为空格串，例如凵凵凵是空格串，长度为3

;串的常用基本运算

（1）StrLength(S)求串长。计算并返回串的长度。

（2）StrCopy(S1,S2)串赋值。将S2赋给S1。S1是串变量，S2是串常量或者是串变量。

（3）StrCat(S1,S2)串连接。将S2连接在S1的后面。S1是串变量，S2是串常量或者是串变量。

例如，S1=ABCD，S2=1234，StrCat(S1,S2)运算的结果是S1=ABCD1234，而S2=1234。

（4）StrCmp(S1,S2)串比较。若S1=S2，则结果为0；若S1S2，则运算结果大于0；若S1S2，则结果小于0。

两个串的比较，实际上比较的是字符的ASCII码值。从第一个位置上的字符开始逐个字符进行比较，当第一次出现字符不等的情况，即可得到比较的结果。

例如abcd等于abcd，abc大于aBc，abc小于abcd。

;（5）StrIndex(S,T)子串定位。若串T是串S的子串，则结果为T在S中首次出现的位置，否则运算结果为0。例如StrIndex(DataStructures,ruct)的结果为8。

（6）SubStr(Sub,S,i,len)求子串。串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，运算结果是得到S串从第i个字符开始的长度为len的子串，并将其赋给T。如果len为0，则赋给Sub的是空串。例如SubStr(Sub,student,4,3)的结果是Sub=den。

（7）StrInsert(S,i,T)串插入。串S和T均为非空串，且1≤i≤StrLength(S)+1。结果是将串T插入到串S的第i个字符位置上，串S的值被改变。例如S=Youareastudent，T=rteacher，StrInsert(s,4,t)的运算结果是S=Yourteacherareastudent。

（8）StrDelete(S,i,len)串删除。串S非空，且1≤i≤StrLength(S)???0≤len≤StrLength(S)，运算结果是删除S串中从第i个字符开始的长度为len的子串，串S的值被改变。;（9）StrRep(S,T,R)串替换。串S、T、R均非空，运算结果是用串R替换串S中所有子串T，串S的值被改变。

以上是串的基本运算，其中前5个运算是最基本的，而其余的串运算一般可以由这些最基本的串运算组合而成。;4.2 串的顺序存储结构及基本运算的实现;（2）在串的末尾设置串结束符，例如C语言用转义字符\0作为串结束符。这种方式不能直接得到串的长度，而是通过判断当前字符是否为\0来确定串是否结束，从而求得串的长度。顺序串的定义如下：

#defineMAXSIZE256

typedefcharsstring[MAXSIZE];

sstrings;//s是一个可容纳255个字符的顺序串。

这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放\0字符作为串结束符。;（3）顺序串存储空间：chars[MAXSIZE+1];

用s[0]存放串的实际长度，而串值存放在s[1]~s[MAXSIZE]中。

优点：字符的序号与存储位置的下标一致;1、求串长;2、串赋值（串复制）;3、串比较;4、串连接;复习：常用的C语言字符串处理库函数。教材P79

【例4.1】利用C语言的库函数完成取子串运算。取主串s中pos起始的len个字符作为子串sub。

例如，主串s=“d:\\user\\wang\\”，pos=8，len=5，sub=“\\wang”;4.4串的模式匹配算法;18;朴素的模式匹配过程举例。模式串P=”abc”与目标串T=“abbabca”的简单模式匹配的匹配过程（pos=1）。;20