文档介绍：数据结构课程的内容
1
第4章串(String)
串的表示和实现
串的模式匹配算法
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
串类型的定义
2
记为: s =‘ a1 , a2 , …….. , an’(n≥0 )
串名
串值(用‘’括起来)
串中字符个数(n≥0). n=0 时称为空串。
由一个或多个空格符组成的串。
串s中任意个连续的字符序列叫s的子串; S叫主串。
子串的第一个字符的序号。
字符在串中的序号。
串长度相等,且对应位置上字符相等。
串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。
串类型的定义
若干术语:
串长:
空白串:
子串:
子串位置:
字符位置:
串相等:
隐含结束符‘/0’,即ASCII码NUL
3
练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’
4
ADT Sting{
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 Sting
串的抽象数据类型定义(参见教材P71)
最小操作子集
5
设 s =’I AM A STUDENT’, t =’GOOD’, q=’WORKER’。求:
练****br/>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))) =?
见本章自测题, ①
6
例:用顺序存储方式实现求子串函数SubString(&Sub, S, pos, len)
Status SubString(SString &sub, SString S, int pos, int len )
{ if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
return ERROR; //pos不合法则告警
Sub[1……len]=S[pos……pos+len-1];
Sub[0]=len; return OK;
}
将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中(注:串Sub的预留长度与S一样)
s =‘ a1 , a2 , …….. , an’
n=串长
pos
len
9
思路:利用malloc函数合理预设串长空间。
特点: 若在操作中串值改变,还可以利用realloc函数按新串长度增加(堆砌)空间。
Typedef struct {
char *ch; // 若非空串,按串长分配空间; 否则 ch = NULL
int length; //串长度
}HString
堆分配存储特点:仍用一组连续的存储单元来存放串,但存储空间是在程序执行过程中动态分配而得。
约定:所有按堆存储的串,其关键信息放置在:
10