【数据结构课件】串.ppt

《【数据结构课件】串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构NorthChinaElectricPowerUniversityDataStructure华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第五章串★串的基本概念★串的基本操作★串的存储结构NorthChinaElectricPowerUniversity★关于串的几个算法★串的基本概念NorthChinaElectricPowerUniversity华电计算机系例如:

2、S1=´abc´S2=´FORTRAN_77´S3=´´=(空串)S4=´´由4个空格组成的空格串串是由n0个字符组成的有限序列,通常记为S=´a1a2a3…an-1an´其中,S表示串名(也称串变量),一对引号括起来的字符序列称为串值,ai可以是字母、数字或其他允许的字符。n为串的长度,长度为0的串称为空串。一.串的定义NorthChinaElectricPowerUniversity华电计算机系1.串值须用一对引号括起来，但引号不属于串值。说明2.要区分空串与由空格字符组成的串的不同。S

3、tring=´String´NorthChinaElectricPowerUniversity华电计算机系1.子串：串中若干个连续的字符组成的子序列。例如:S=´Beijing&Shanghai´T=´jing´2.主串:包含子串的串。3.位置：(2).子串在主串中的位置被定义为该字符在串中的序号。例如:S=´Beijing&Nanjing&Shanghai´T=´jing´位置为4二.几个名词概念(1).单个字符在主串中的位置被定义为主串中首次出现的该子串的第一个字符在主串中的位置。North

4、ChinaElectricPowerUniversity华电计算机系的充分必要条件为两个字符串的长度相等，并且对应位置上的字符相同。4.两个字符串相等´abcd´´bacd´´abcd´=´abcd´NorthChinaElectricPowerUniversity华电计算机系6.2串的基本操作1.给串变量赋值ASSIGN(S1,S2)strcpy(S2,S1)2.判断两个串是否相等EQUAL(S1,S2)strcmp(S1,S2)3.两个字符串连接CONCAT(S1,S2)strcat(S1

5、,S2)4.求字符串的长度LEN(S)strlen(S)5.求子串SUBSTR(S,i,k)6.求子串在主串中的位置INDEX(S1,S2)strstr(S1,S2)7.串的替换REPLACE(S,S1,S2)8.串的复制COPY(S1,S2)strcpy(S2,S1)9.串的插入INSERTS(S1,i,S2)C函数NorthChinaElectricPowerUniversity华电计算机系1.非紧缩格式(设每个字有4个字节)例如:S=´DATASTRUCTURE´DASTRUCTATU

6、RE@DATASTRUCTURE@2.紧缩格式3.单字节方式6.3串的存储结构一.串的顺序存储结构ATSATRUUTCDRE@NorthChinaElectricPowerUniversitySDATE^……说明：所谓链结点大小是指每个链结点的数据域中存放的字符的个数。DATASTRURE@@……S^二.串的链式存储结构结点大小为4的链表结点大小为1的链表NorthChinaElectricPowerUniversity6.4串的几个算法一.串的定义Typestring=recordcurlen

7、:integer;ch:array[1..maxlen]ofchar;end;二.串的连接假设r,s,t都是上面定义的string型变量，且r是s与t连接后得到的串，则连接运算concat(r,s,t)是将s与t的串值分别传送到r相应的位置上。NorthChinaElectricPowerUniversity华电计算机系1)s.curlen+t.curlen≤maxlen，这时得到的串r是连接所要求的正确结果；2)s.curlen+t.curlen>maxlen，需要将t的一部分截断，得到的串r

8、只包含s和t的一个子串；3)s.curlen>maxlen，这时需要对s进行截断，得到的串r仅是s的一个子串；Procedureconcat(varr,s,t:string;varp:boolean);Begincases.curlen+t.curlen<=maxlen:[p:=false;movch(r,s,1,1,s.curlen);movch(r,t,s.curlen+1,1,t.curlen);r.curlen:=s.curlen+t.curlen;]s.curlen+t.curlen>