第四章_串.ppt

文档介绍：第4章串
【教学目的】掌握串的定义、逻辑结构、存储结构及操作实现以及串的应用
【教学重点】串的顺序、链式、堆存储结构及串的操作的实现
【教学难点】串的模式匹配算法工作原理、经典的模式匹配端法、KMP算法和改进的KMP算法
本章主要内容




――串操作应用
串及其基本运算
一、串的基本概念
串是由零个或多个任意字符组成的字符序列。
一般记作:s=’s1 s2 … sn’
其中s 是串名;’引号引起来的字符序列为串值,引号本身不属于串的内容;串中的任一个字符ai,称为串的元素,是构成串的基本单位,i是它在整个串中的序号; n为串的长度,表示串中所包含的字符个数,当n=0时,称为空串,通常记为Ф。
子串与主串:串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
子串的位置:子串的第一个字符在主串中的序号称为子串的位置。
串相等:称两个串是相等的,是指两个串的长度相等且对应字符都相等。
串及其基本运算
二、串的基本操作
:Init_String(s)
操作条件:串s不存在
操作结果:构造一个串
:Destroy_String(s)
操作条件: 串s存在
操作结果:销毁一个已存在的串
串及其基本运算
二、串的基本操作
(s)
操作条件:串s存在
操作结果:求出串s中的字符的个数。
(s1,s2)
操作条件: s1是一个串变量,s2或者是一个串常量,或者是一个串变量。
操作结果:将s2的串值赋值给s1, s1原来的值被覆盖掉。
:StrConcat (s1,s2,s) 或StrConcat (s1,s2)
操作条件:串s1,s2存在。
操作结果:两个串的联接就是将一个串的串值紧接着放在另一个串的后面,连接成一个串。
串及其基本运算
二、串的基本操作
(t,s,i,len):
操作条件:串s存在
操作结果:产生一个新串t。
StrCmp(s1,s2)
操作条件:串s1,s2存在。
操作结果:若s1==s2,操作返回值为1;否则返回值为0。
StrIndex(s,t):
操作条件:串s,t存在。
操作结果:若t∈s,则操作返回t在s中首次出现的位置,否则返回值为-1。
串及其基本运算
三、串的高级操作
StrInsert(s,i,t)
操作条件:串s,t存在,1≤i≤StrLength(s)+1。
操作结果:将串t插入到串s 的第i个字符位置上
:StrDelete(s,i,len)
操作条件:串s存在。
操作结果:删除串s 中从第i个字符开始的长度为len的子串。
11、串替换 StrRep(s,t,r)
操作条件:串s,t,r存在,t不为空。
操作结果:用串r 替换串s中出现的所有与串t相等的不重叠的子串。
串的顺序存储与操作
一、串的定长顺序存储
类似于顺序表,用一组地址连续的存储单元存储串值中的字符序列,所谓定长是指按预定义的大小,为每一个串变量分配一个固定长度的存储区,如:
#define MAXSIZE 256
char s[MAXSIZE];
则串的最大长度不能超过256。
如何标识实际长度?
1. 类似顺序表,串描述如下:
typedef struct
{ char data[MAXSIZE];
int Length; /*串的长度*/
} SeqString;
定义一个串变量:SeqString s;
串的顺序存储与操作
一、串的定长顺序存储

2、在串尾存储一个不会在串中出现的特殊字符作为串的终结符,以此表示串的结尾。比如C语言中处理定长串的方法就是这样的,它是用’\0’来表示串的结束。这种存储方法不能直接得到串的长度,是用判断当前字符是否是’\0’来确定串是否结束,从而求得串的长度。
 char s[MAXSIZE];
0
1
2
3
4
5
6
7
8
9
10
...
MAXSIZE-1
a
b
c
d
e
f
g
h
i
j
k
\0
串的顺序存储与操作
一、串的定长顺序存储

3、在串首存储串长。比如Pascal语言中处理定长串的方法。
  char s[MAXSIZE+1];
0
1
2
3
4
5
6
7
8
9
10
...
MAXSIZE
9
a
b
c
d
e
f
g
h
i
...