安徽理工大学：《数据结构》课程教学资源（课件讲稿，C语言版）第4章 串

前课回顾 Q.front 链队列 O.rear Q.rear. M-1 0 循环队列 1 Q.front -1 1945

— 1— — 1— 前课回顾 链队列 Q.front Q.rear ∧ 循环队列 0 M-1 1 Q.front Q.rear

学习要求 第四章串 ■掌握串的基本操作 ■掌握串操作在不同存储结构下的实现 -2 1945

— 2— — 2— 学习要求  掌握串的基本操作  掌握串操作在不同存储结构下的实现 第四章 串

目录页 Contents Page 串类型的定义 第四章串 串的表示和实现 串的模式匹配算法 一3 1945

— 3— — 3— Contents Page 目录页 串的表示和实现 串的模式匹配算法 串类型的定义

4.1串类型的定义 4.1.1串的基本概念 串的定义 串(string)是由零个或多个字符组成的有限序列， 般记作S=‘a1a2a3…an’(>=0)。a(1≤i)可以是字 母、数字或其它字符。 串中字符的个数n称为串的长度。 空串 长度为零的串称为空串。由一个或多个空格组成 的串称为空白串。 -4 1945

— 4— 4.1  串类型的定义  串的定义 串( string) 是由零个或多个字符组成的有限序列， 一般记作S=‘a1a2a3…an’ (n>=0) 。ai(1≤i≤n)可以是字 母、数字或其它字符。 串中字符的个数n称为串的长度。  空串 长度为零的串称为空串。由一个或多个空格组成 的串称为空白串。 4.1.1 串的基本概念

4.1串类型的定义 4.1.1串的基本概念 ■子串、主串 串中任意连续字符组成的子序列称为该串的子串。 而包含子串的串相应地称为主串。通常将子串的第 一个字符在主串的位置称为子串在主串中的位置。 如：串s1=is”,s2=This is a string”,则s1为s2 的子串，s2相对于s1为主串。s1在s2中出现了两次， 其中首次出现所对应的主串位置是3。因此，称s1在 s2中的位置为3。 1945

— 5— 4.1  串类型的定义  子串、主串 串中任意连续字符组成的子序列称为该串的子串。 而包含子串的串相应地称为主串。通常将子串的第 一个字符在主串的位置称为子串在主串中的位置。 如：串s1 =“is”，s2 =“This is a string”，则s1为s2 的子串， s2相对于s1为主串。 s1在s2中出现了两次， 其中首次出现所对应的主串位置是3。因此，称s1在 s2中的位置为3。 4.1.1 串的基本概念

4.1串类型的定义 4.1.2串的抽象数据类型的定义 ADT String 数据对象： D={a:la:∈CharacterSet,i=l,2,,n,n≥0} 数据关系： R1={|a-1wa;∈D,i=2,,n} 基本操作： ADT String -6 145

— 6— 4.1  串类型的定义 ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ | ai-1, ai ∈D, i=2,...,n } 4.1.2 串的抽象数据类型的定义 基本操作： } ADT String

4.1串类型的定义 4.1.2串的抽象数据类型的定义 串的基本操作 串赋值 串复制 串判空 串比较 求串长 串联接 求子串 串定位 串替换 串插入 串删除 串销毁 1945

— 7— 4.1  串类型的定义 串赋值  串的基本操作 串复制 串判空 串比较 求串长 串联接 求子串 串定位 串替换 串插入 串删除 串销毁 4.1.2 串的抽象数据类型的定义

4.1串类型的定义 4.1.2串的抽象数据类型的定义 StrAssign (&T,chars) 初始条件：chars是字符串常量。 操作结果：把chars赋为T的值。 例如：StrAssign(T,'datastru) 得T='datastru' -8- 145

— 8— 4.1  串类型的定义 StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 例如：StrAssign( T, datastru) 得 T = datastru 4.1.2 串的抽象数据类型的定义

4.1串类型的定义 4.1.2串的抽象数据类型的定义 StrCopy (&T,S) 初始条件：串S存在。 操作结果：由串S复制得串T。 例如：S='datastru',StrCopy(T,S) 得T='datastru' Q -9- 145

— 9— 4.1  串类型的定义 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。 例如：S= datastru, StrCopy( T, S) 得 T = datastru 4.1.2 串的抽象数据类型的定义

4.1串类型的定义 4.1.2串的抽象数据类型的定义 StrEmpty(S) 初始条件：串S存在。 操作结果：若S为空串， 则返回TRUE, 否则返回FALSE。 "表示空串，空串的长度为零。 -10- 145

— 10 — 4.1  串类型的定义 StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。  表示空串，空串的长度为零。 4.1.2 串的抽象数据类型的定义