中国药科大学：《数据结构》课程PPT教学课件（讲稿）第5章 串和数组 5.1 串的定义 5.2 串的表示和实现 5.3 正文模式匹配

a 第5章串和数组 2( 计算机教研宦 第1页 2021/2/19

Data Structure 数据结构— 第5章串和数组 胡建华 2021/2/19 计算机教研室 第 1 页 第 5 章 串和数组

@51串的定义 串:由0或多个字符组成的序列 “a1a2a3…,an” 串的长度n 空串和空格串 子串及子串的位置 两个串相等 计算机教研宦 第2页 2021/2/19

Data Structure 数据结构— 第5章串和数组 胡建华 2021/2/19 计算机教研室 第 2 页 5.1 串的定义 • 串：由0或多个字符组成的序列 s=“a 1 a 2 a 3…a n ” • 串的长度 n • 空串和空格串 • 子串及子串的位置 • 两个串相等

@2串的抽象数据类型定义 ADT String t 数据对象:D={aa1∈ chari=1,2,…,n,n20} 编数据关系R={a1,a1∈D,=1,2,,n,n≥0} 基本操作 参见后面介绍 计算机教研宦 第3页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第3页 2.串的抽象数据类型定义 ADT String { 数据对象:D={ai |ai∈char,i=1,2,…,n,n≥0} 数据关系:R={|ai-1 ,ai ∈D,i=1,2,…,n,n≥0} 基本操作: 参见后面介绍 }

@串的基本操作(1) s StrAssign(&T, chars) 初始条件: chars是字符串常量。 操作结果生成一个其值等于 chars的串T R StrCopy(&T,s) 初始条件:字符串S已经存在。 操作结果:由串S复制得串T s StrEmpty(s) 意初始条件:字符串S已经存在。 串操作结果:若S为空串,则返回TRUE否则返回 FALSE。 计算机教研宦 第4页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第4页 StrAssign(&T,chars) 初始条件: chars是字符串常量。 操作结果: 生成一个其值等于chars的串T。 StrCopy(&T,S) 初始条件: 字符串S已经存在。 操作结果: 由串S复制得串T。 StrEmpty (S) 初始条件: 字符串S已经存在。 操作结果: 若S为空串，则返回TRUE,否则返回FALSE。 串的基本操作（1）

@串的基本操作(2) 9 StrCompare(s,T) 初始条件:字符串S和T存在。 操作结果:若S>T则返回值>0;若S=T则返回值=0否则 返回值<0 StrEngth(s) 初始条件:字符串S已经存在 操作结果:返回串S元素个数,称为串的长度 ClearString(&s) 初始条件:字符串S已经存在 操作结果:将串S清为空串 计算机教研宦 第5页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第5页 StrCompare(S,T) 初始条件: 字符串S和T存在。 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;否则 返回值<0。 StrLength(S) 初始条件:字符串S已经存在。 操作结果:返回串S元素个数，称为串的长度。 ClearString(&S) 初始条件:字符串S已经存在。 操作结果:将串S清为空串。 串的基本操作（2）

@串的基本操作(3) 8 Concat(&T,S1, S2) 初始条件:字符串S1,S2已经存在 操作结果/用T返回由串S1和s2联结而成的新串。 Substring(&Sub, S, pos, len) 初始条件:串S存在,1<=pos<=S的长度, 0<|en<=S的长度pos+1。 操作结果:用Sub返回串S的第pos个字符起长度为en的子串。 Index(S, T, pos) 初始条件:串S和T存在,T是非空串1=pos<=S的长度 操作结果:若主串S中存在和串T相同的子串,则返回它 在主串S中第pos个字符之后第一次出现的位置;否则返回 计算机教研室 第6页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第6页 串的基本操作（3） Concat(&T,S1,S2) 初始条件:字符串S1,S2已经存在。 操作结果:用T返回由串S1和S2联结而成的新串。 Substring(&Sub,S,pos,len) 初始条件:串S存在,1<=pos<=S的长度, 0<=len<=S的长度-pos+1。 操作结果:用Sub返回串S的第pos个字符起长度为len的子串。 Index(S,T,pos) 初始条件:串S和T存在,T是非空串,1<=pos<=S的长度。 操作结果:若主串S中存在和串T相同的子串，则返回它 在主串S中第pos个字符之后第一次出现的位置；否则返回 ０

串的基本操作(4) e Replace(S, T,V 初始条件:字符串STV已经存在,T是非空串 操作结果:用V替换主串S中出现的所有与T相等的不重叠的 子串。 StrInsert(&S, pos,T) 编初始条件:字符串ST存在1=pos<=S的长度+1。 操作结果:在串S的第pos个字符之前插入串T e StrDelete(&S, pos, len) 初始条件:串S存在1=05=8的长度mn+1 操作结果:从串S中删除第pos个字符起长度为en的子串 2 DestroyString(8s:把存在的串S销毁 计算机教研宦 第7页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第7页 串的基本操作（4） Replace(&S,T,V) 初始条件:字符串S,T,V已经存在，T是非空串。 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的 子串。 StrInsert(&S,pos,T) 初始条件:字符串S,T存在,1<=pos<=S的长度+1。 操作结果:在串S的第pos个字符之前插入串T。 StrDelete(&S,pos,len) 初始条件:串S存在,1<=pos<=S的长度-len+1。 操作结果:从串S中删除第pos个字符起长度为len的子串. DestroyString(&S):把存在的串S销毁

@串类型的最小操作子集 8上述13种基本操作中,下面5种操作构成最小操作子集: 串赋值 StrAssign 串比较 StrCompare 求串长 StrEngth; 串联结 Concat 求子串 Substring; 其它操作可以用其实现 计算机教研宦 第8页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第8页 上述13种基本操作中,下面5种操作构成最小操作子集: 串赋值 StrAssign; 串比较 StrCompare; 求串长 StrLength; 串联结 Concat; 求子串 Substring; 其它操作可以用其实现 串类型的最小操作子集

@C语言函数库中提供下列串处理函数: gets(str)输入一个串 puts(str)输出一个串 strati(strl,str2)串联接函数; strcpy(str,str2,k)串复制函数; strcmp(str1,st2)串比较函数; 钟 strlen(st)求串长函数 计算机教研宦 第9页 2021/2/19

Data Structure 数 据 结 构 — 第 5 章 串 和 数 组 胡建华 2021/2/19 计算机教研室 第9页 C语言函数库中提供下列串处理函数： gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；

a 52串的表示和实现 计算机教研宦 第10页 2021/2/19

Data Structure 数据结构— 第5章串和数组 胡建华 2021/2/19 计算机教研室 第10 页 5.2 串的表示和实现