数据结构—串及其基本运算

串(即字符串)是一种特殊的线性表,它的数据元素仅由一个字符组成,计算机非数值处理的对象经常是字符串数据,如在汇编和高级语言的编译程序中,源程序和目标程序都是字符串数据;在事物处理程序中,顾客的姓名、地址、货物的产地、名称等,一般也是作为字符串处理的。另外串还具有自身的特性,常常把一个串作为一个整体来处理,因此,在这一章我们把串作为独立结构的概念加以研究,介绍串的串的存储结构及基本运算。
 

4.1.1 串的基本概念


1.串的定义

串是由零个或多个任意字符组成的字符序列。一般记作:s="s1 s2 … sn""

其中s 是串名;在本书中,用双引号作为串的定界符,引号引起来的字符序列为串值,引号本身不属于串的内容;ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位,i 是它在整个串中的序号; n 为串的长度,表示串中所包含的字符个数,当n=0 时,称为空串,通常记为Ф。

2.几个术语

子串与主串:串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
子串的位置:子串的第一个字符在主串中的序号称为子串的位置。
串相等:称两个串是相等的,是指两个串的长度相等且对应字符都相等。

4.1.2 串的基本运算

串的运算有很多,下面介绍部分基本运算:

1.求串长StrLength(s)
操作条件:串s 存在
操作结果:求出串s 的长度。

2.串赋值StrAssign(s1,s2)
操作条件: s1 是一个串变量,s2 或者是一个串常量,或者是一个串变量(通常s2 是一个串常量时称为串赋值,是一个串变量称为串拷贝)。
操作结果:将s2 的串值赋值给s1, s1 原来的值被覆盖掉。

3.连接操作:StrConcat (s1,s2,s) 或StrConcat (s1,s2)
操作条件:串s1,s2 存在。
操作结果:两个串的联接就是将一个串的串值紧接着放在另一个串的后面,连接成一个串。前者是产生新串s,s1 和s2 不改变; 后者是在s1 的后面联接s2 的串值,s1 改变, s2不改变。
例如: s1="he",s2=" bei",前者操作结果是s="he bei";后者操作结果是s1="he bei"。

4.求子串SubStr (s,i,len):
操作条件:串s 存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:返回从串s 的第i 个字符开始的长度为len 的子串。len=0 得到的是空串。
例如:SubStr("abcdefghi",3,4)= "cdef"

5.串比较StrCmp(s1,s2)
操作条件:串s1,s2 存在。
操作结果:若s1==s2,操作返回值为0;若s1<s2, 返回值<0;若s1>s2, 返回值>0。

6.子串定位StrIndex(s,t):找子串t 在主串s 中首次出现的位置
操作条件:串s,t 存在。
操作结果:若t∈s,则操作返回t 在s 中首次出现的位置,否则返回值为-1。
如:StrIndex("abcdebda","bc")=2
StrIndex("abcdebda","ba")=-1

7.串插入StrInsert(s,i,t)
操作条件:串s,t 存在,1≤i≤StrLength(s)+1。
操作结果:将串t 插入到串s 的第i 个字符位置上,s 的串值发生改变。

8.串删除StrDelete(s,i,len)
操作条件:串s 存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:删除串s 中从第i 个字符开始的长度为len 的子串,s 的串值改变。

9.串替换StrRep(s,t,r)
操作条件:串s,t,r 存在,t 不为空。
操作结果:用串r 替换串s 中出现的所有与串t 相等的不重叠的子串,s 的串值改变。以上是串的几个基本操作。其中前5个操作是最为基本的,它们不能用其他的操作来合成,因此通常将这5个基本操作称为最小操作集。

如果引用本站的原创文章,请注明原文链接:,本站保留追究责任的权利!

发表评论