文档介绍：1
数据结构课程的内容
2
第4章串(String)
串的表示和实现
串的模式匹配算法
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
串类型的定义
3
记为: s =‘ a1 , a2 , …….. , an’(n≥0 )
串名
串值(用‘’括起来)
串中字符个数(n≥0). n=0 时称为空串。
由一个或多个空格符组成的串。
串s中任意个连续的字符序列叫s的子串; S叫主串。
子串的第一个字符的序号。
字符在串中的序号。
串长度相等,且对应位置上字符相等。
串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。
串类型的定义
若干术语:
串长:
空白串:
子串:
子串位置:
字符位置:
串相等:
隐含结束符‘/0’,即ASCII码NUL
4
练1:串是由字符组成的序列,一般记为。
练2:现有以下4个字符串:
a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’
问:①他们各自的长度?
② a是哪个串的子串?在主串中的位置是多少?
a =3,b =4,c = 7,d=8
a是c和d的子串,在c和d中的位置都是1
练3:空串和空白串有无区别?
答:有区别。空串(Null String)是指长度为零的串;而空白串(Blank String),是指包含一个或多个空白字符‘’(空格键)的字符串.
0个或多个
S=’a1a2……an’
5
ADT String{
Objects: D={ai | ai∈CharacterSet, i=1, 2,…,n, n≥0}
Relations: R1={<ai-1,ai> | ai-1,ai ∈D, i=2, …,n}
functions: // 有13种之多
StrAssign(&T, chars) // 串赋值,生成值为chars的串T
pare(S,T) // 串比较,若S>T,返回值大于0…
StrLength(S) // 求串长,即返回S的元素个数
Concat(&T, S1, S2) // 串连接,用T返回S1+S2的新串
SubString(&Sub, S, pos, len) // 求S中pos起长度为len的子串
……
Index(S, T, pos) // 返回子串T在pos之后的位置
Replace(&S, T,V) // 用子串V替换子串T
}ADT String
串的抽象数据类型定义(参见教材P71)
最小操作子集
6
设 s =’I AM A STUDENT’, t =’GOOD’, q=’WORKER’。求:
练习:
StrLength(s) =
StrLength(t) =
SubString(s, 8, 7)=
SubString(t, 2, 1)=
Index(s, ‘A’)=
Index(s, t)=
Replace(s, ‘STUDENT’,q)=
14
4
‘STUDENT’
‘O’
3
0 ( s中没有t!)
’I AM A WORKER’
再问:Concat(SubString(s,6,2), Concat(t,SubString(s,7,8))) =?
见本章自测题, ①
7
串的表示和实现
定长顺序存储表示
——用一组地址连续的存储单元存储串值的字符序列
堆分配存储表示
——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。
串的块链存储表示
——链式方式存储
串有三种机内表示方法:
顺序存储
链式存储
A 
B 
C 
I NULL
head
8
定长顺序存储特点:用一组连续的存储单元来存放串,直接使用定长的字符数组来定义,数组的上界预先给出,故称为静态存储分配。
例如:
#define Maxstrlen 255 //用户可用的最大串长
typedef unsigned char SString[ Maxstrlen+1 ];
SString s; //s是一个可容纳255个字符的顺序串。
注:
一般用SString[0]来存放串长信息;
C语言约定在串尾加结束符‘\0’,以利操作加速,但不计入串长;
若字符串超过Maxstrlen 则自动截断(因为静态数组存不进去)。
讨论:想存放超长字符串怎么办?——静态数组有缺陷!
实现方式:参见教材P73编程两例,两串连接和求子串
改用动态分配的一维数组——
“堆”!
9
例:顺序存储方式下获得子串的函数SubString(&Sub, S, pos,