文档介绍：第四章串
1
本章目录
串的定义
串的存储结构
顺序串的实现
模式匹配
2
串的定义
1. 串的相关概念
2. 串的抽象数据类型定义
3. 串操作解析
3
微机上常用的字符集是标准ASCII码,由 7 位二进制数表示一个字符,总共可以表示 128 个字符。
扩展ASCII码由 8 位二进制数表示一个字符,总共可以表示 256 个字符,足够表示英语和一些特殊符号,但无法满足国际需要。
Unicode由 16 位二进制数表示一个字符,总共可以表示 216个字符,即6万5千多个字符,能够表示世界上所有语言的所有字符,包括亚洲国家的表意字符。为了保持兼容性,
Unicode字符集中的前256个字符与扩展ASCII码完全相同。
串的数据对象
串的数据对象约束为某个字符集
4
串的相关概念
串(string):是由零个或多个字符组成的有限连续序列,即串是一串字符。一个非空串记为: S=“s1s2...sn”
空串(null string) :由零个字符组成的串。
空格串:由一个或多个空格组成的串。
子串:字符串中任意个连续的字符构成的子序列称为字符串的子串。空串是任何串的子串。
主串:包含子串的字符串。
位置:一个字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
串的比较:见后页
5
串的比较:
例:“abcd”= = “abcd”
“abc”< “abcd”
“abcd”> “abc”
设有两个串:X=“x1x2...xm”、Y=“y1y2...yn”,
等于( = = ) :当m = = n,且xi= = yi 时,称X = = Y。
小于( < ) :当m < n,且xi= = yi (i=1,2,...,m ), 或存在某个k≤min(m,n),使得xi= = yi (i=1,2,...,k-1),xk < yk 时,称X < Y  
大于( > ) :当m > n,且xi= = yi (i=1,2,...,n), 或存在某个k≤min(m,n),使得xi= = yi (i=1,2,...,k-1),xk > yk 时,称X > Y
6
假设 S = abcaabcaaabc, T = bca
Index(S, T, 1) =
Index(S, T, 3) =
Index(S, T, 8) =
子串中的第一个字符在主串中的位序
2
6
0
子串在主串中的位置
7
串的抽象数据类型定义
ADT String {
Data:D={ ai | ai ∈CharaterSet, i=1, 2, …, n, n≥0}
Relation: R={ <ai-1, ai >| ai-1, ai∈D, i=2, …, n, }
Operation
StrAssign ( &S , T ) ;//串赋值
StrLength( S ) ; // 求串长
StrConcat( &S , T );// 串联接
StrSub ( S, i,len) ;// 求子串
StrCmp ( S , T) ;// 串比较
StrIndex ( S , T ) ;// 串匹配
StrInsert (&S,i,T) ;// 串插入
StrDelete (&S,i,len) ;// 串删除
StrRep (&S,T,R) ;// 串置换
} ADT
8
a b c d e f g e
i = 3, len = 3
i = 7, len = 4
c d e
a b c d e f g e
g e
空串
求子串
SubStr(s, i, len)
9
例如:
sub =SubString(“commander”, 4, 3)
sub = ?
sub =SubString(“commander”, 1, 9)
sub = ?
sub =SubString( “commander”, 9, 1)
sub =?
man
“commander”
“r”
求子串示例
10