第四章+串.ppt

第四章串
[内容提要]
⒋1 串的概念
⒋2 串的存储结构
⒋3 串基本操作的实现
⒋4 串的应用举例----文本编辑
1
1、对象:串的数据对象约束为字符集。
2、操作:
在线性表的基本操作中,大多以“单个元素”作为操作对象。
在串的基本操作中,通常以“串的整体”作为操作对象。
串与线性表的区别
2
串的定义
串是一组由字符组成的有限序列,一般记为:
S='c1 c2 ...cn ' (n≥0)
3
串的值:用成对的单引号括起来的字符序列是串的值。(成对的单引号本身仅是串值的标记,不包含在串值中。在C语言中,s1='a'与s2=〃a〃两者是不同的,s1表示字符,而s2表示字符串。
串的长度:串中字符的数目n称为串的长度。零个字符的串为空串,它的长度为零.
例如: s1=‘I have a dog’; s2=‘have’;s3=‘dog’
则它们的长度分别为12、4、3
串的概念
4
子串和主串:串中任意个连续的字符组成的序列称为该串的子串。包含子串的串相应地称为主串。
例如:
s1=’I have a dog’;s2=’have’;s3=’dog’
则:串s3是s1的子串, s1是s3的主串;串s2不是s1的子串
串的概念
5
串的位置:字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。特别地,空串是任意串的子串,任意串是其自身的子串。
例如: s1=’I have a dog’; s3=’dog’
则:子串s3在s1中的位置为10
串的概念
6
两个串相等:当两个串的长度相等,并且各个对应位置的字符都相等时才相等。
例如:
s1=’I have a dog’;s2=’have’;s3=’dog’; s4=’dog’
则:串s1,s2,s3都是互不相等,但s3与s4相等。
串的概念
7
空格串:由一个或多个空格组成的串称为空格串(请注意:此处不是空串)它的长度不为0。如‘’是空格串长度为2。
空串:不含任何字符的串,它的长度为0,为了清楚起见,以后我们用符号''来表示空串。
串的概念
8
假设本节中的s,t,v,a,b,c和d都是串名, 并且a,b,c和d的值分别为‘BEI’、‘JING’、‘’和'BEIJING'.
⑴赋值操作:Assign(s,t)和Create(s,ss)
其中t为串名,ss为字符序列。Create(s,ss)的操作结果为设定了一个串s,其值为字符序列ss;Assign(s,t)的操作结果是将t的值赋给s。例如, 执行Assign(s,d)的操作之后, s的值为'BEIJING'
串的基本操作定义
9
⑵判等函数:Equal(s,t)
若s和t相等, 则返回函数值(即运算结果)1, 否则返回函数值 0。s和t可以是非空串,也可以是空串。
例如, 执行Equal (a,b) 后, 值为0。
执行Equal (‘abc’,‘abc’) 后, 值为1。
串的基本操作定义
10