文档介绍：第4章串(String)
串的基本概念
串的表示和实现
1
第4章串(String)
字符串(简称串)对大家来说并不陌生。在解决实际问题时,经常会用到串操作。
一般地说,不同问题中所遇到的字符串具有不同特点。例如,在某些问题中,字符串都是100来个字符,比较均匀;而在有些问题中,一部分字符串很长,另一部分字符串很短,起伏较大。
显而易见,在处理不同特点的字符串时,应采用不同的存储结构,只有这样,才能获得较高的效率。
在本章中,我们将讨论串的几种存储结构和一些基本操作。
2
第4章串(String)
串类型的定义
一、串的定义
串是由n(n≥0)个字符组成的序列,常记为
s='a1a2…an'
其中,
⑴ s为串的名字。
⑵ a1a2…an称为串的值。为了不至于与变量名或常量混淆,串的值一定要用单引号括起来,但单引号本身不属于串。
⑶串中字符的数目n称为串的长度。长度为0的串称为空串,记为φ。
⑷串中任意个连续的字符组成的子序列称为该串的子串,原串称为主串.
⑸通常把字符在序列中的序号称为该字符在串中的位置(从1开始)。
⑹子串在主串中的位置指的是子串的第一个字符在主串中的位置。
⑺称两个串相等当且仅当串的值相等,即串的长度相等,而且对应位置上的字符相等。
3
一、串的定义
可以看出,串和线性表都是有限的序列,逻辑结构很相似。但是,他们有两点区别:
⑴串的每个数据元素为单个字符,数据对象是某个字符集。
⑵串的基本操作和线性表的基本操作差别较大。
线性表的基本操作大多以“单个元素”为操作对象,例如,获取一个数据元素、插入一个元素以及删除一个元素等。
串的基本操作很少以单个字符为操作对象,而大多以“串的整体”为操作对象,例如,在串中取一个子串、在串中插入/删除一个子串等。
4
二、串的抽象数据类型
P71用抽象数据类型 String 描述了串及其基本操作。
ADT String {
数据对象:D={ai|ai∈CharacterSet, i=1, …,n, n≥0}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D, i=2, …,n}
基本操作:
StrAssign(&T, chars)
初始条件:chars是字符串常量
操作结果:生成一个值为chars的串T。
StrCopy(&T, S)
初始条件:串S已经存在。
操作结果:由串S复制得到串T。
…………
}ADT String
5
三、串的基本操作
StrAssign(&S, chars)
初始条件: chars是字符串常量
操作结果:生成一个值为chars的串S。
StrCopy(&T, S)
初始条件:串S已经存在。
操作结果:由串S复制得到串T。
StrEmpty(S)
初始条件:串S已存在。
操作结果:若S为空串,则返回TRUE,否则FALSE。
6
三、串的基本操作
pare(S, T)
初始条件:串S、T已存在。
操作结果:若S>T,则返回值>0;
若S=T,则返回值=0;
若S<T,则返回值<0。
Concat(&T, S1, S2)
初始条件:串S1、S2已存在。
操作结果:用T返回由S1与S2连接而成的新串。
StrLength(S)
初始条件:串S已存在。
操作结果:返回串S中的字符个数。
7
三、串的基本操作
SubString(&Sub, S, pos, len)
初始条件:串S已存在,且1≤pos≤StrLength(S),
0≤ len ≤ StrLength(S)-pos+1
操作结果:用Sub返回S中从第pos个字符起长度为len
的子串。
Index(S, T, pos)
初始条件:串S、T已存在,且1≤pos≤StrLength(S)。
操作结果:返回S中从第pos个字符起子串T首次出现的
位置。
StrInsert(&S, pos, T)
初始条件:串S、T已存在,1≤pos≤StrLength(S)+1.
操作结果:在S的第pos个字符前插入串T。
8
三、串的基本操作
StrDelete(&S, pos, len)
初始条件:串S已存在,1≤pos≤StrLength(S)-len+1.
操作结果:删除S中从第pos个字符起长度为len的子串.
应当注意,在不同的高级语言中,对串操作的定义可能有差异。
9
四、串的基本操作举例
例一、若执行以下程序,会输出怎样的结果?
v