- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
对于串的基本操作集可以有不同的定义方法， 对于串的基本操作集可以有不同的定义方法，在使用高级程 序设计语言中的串类型时，应以该语言的参考手册为准。 序设计语言中的串类型时，应以该语言的参考手册为准。 例如： 语言函数库中提供下列串处理函数： 例如：C语言函数库中提供下列串处理函数： 输入一个串； gets(str) 输入一个串； 输出一个串； puts(str) 输出一个串； 串联接函数； strcat(str1, str2) 串联接函数； 串复制函数； strcpy(str1, str2) 串复制函数； 串比较函数； strcmp(str1, str2) 串比较函数； 求串长函数； strlen(str) 求串长函数；
Replace (&S, T, V) 初始条件： T和 均已存在， 是非空串。 初始条件：串S, T和 V 均已存在，且 T 是非空串。 操作结果： 中出现的所有与（模式串） 操作结果：用 V 替换主串 S 中出现的所有与（模式串）T 相等的不重叠的子串。 不重叠的子串 相等的不重叠的子串。 abcaabcaaabca″ 例如： 例如：假设 S = ″abcaabcaaabca″, T = ″bca ″若 V = ″x ″, aax 则经置换后得到 S = ″axaxaax ″ bcabcaabc″ aabc 若 V = ″bc ″, 则经置换后得到 S = ″abcabcaabc″
StrInsert (&S, pos, T) 初始条件： 存在， 1≤pos≤StrLength(S)＋ 初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前插入串T pos个字符之前插入串 操作结果：在串S的第pos个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件： 存在，1≤pos≤StrLength(S)-len+1。 初始条件：串S存在，1≤pos≤StrLength(S)-len+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 pos个字符起长度为len的子串 操作结果：从串S中删除第pos个字符起长度为len的子串。 例如： 例如：S = ″chater ″，T = ″rac ″， charac racter 则执行 StrInsert(S, 4, T) 之后得到 S = ″character ″ ClearString (&S) 初始条件： 存在。 初始条件：串S存在。 操作结果： 清为空串。 操作结果：将S清为空串。
Index (S, T, pos) 初始条件 条件： 存在， 是非空串1≤pos≤StrLength(S) 1≤pos≤StrLength(S)。 初始条件：串S和T存在，T是非空串1≤pos≤StrLength(S)。 操作结果： 值相同的子串, 操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它 中第pos个字符之后第一次出现的位置;否则函数值为0 pos个字符之后第一次出现的位置 在主串 S 中第pos个字符之后第一次出现的位置;否则函数值为0。 子串在主串中的位置” “子串在主串中的位置”意指子串中的第一个字符在主串中的位 序。 假设 S = ″abcaabcaaabc ″, Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0; T = ″bca ″
4.1
串的抽象数据类型的定义
4.2
串的表示和实现
4.3
串的模式匹配算法
4.1
串的抽象数据类型的定义
字符串：简称串 是特殊的线性表， 字符串：简称串，是特殊的线性表，其特殊性主要在于表 中的每个元素是一个字符，以及由此而要求的一些特殊操 中的每个元素是一个字符， 作。 长度：一个串中包括的字符个数。长度为零的串称为空串。 长度：一个串中包括的字符个数。长度为零的串称为空串。 空串 子串：字符串s1中任意个连续的字符组成的子序列s2被称 子串：字符串s1中任意个连续的字符组成的子序列s2被称 s1中任意个连续的字符组成的子序列s2 为是s1 子串，而称s1 s2的主串。 s1的 s1是 为是s1的子串，而称s1是s2的主串。
串的抽象数据类型的定义如下： 串的抽象数据类型的定义如下： 抽象数据类型的定义如下 ADT String { 数据对象： 数据对象：
串是有限长的字符序列， 串是有限长的字符序列，由 一对双引号相括， 一对双引号相括，如: ″ a string ″
D＝{ ai |ai∈CharacterSet, i=1,2,...,n， n≥0 } 数据关系： 数据关系：
R1＝{ < ai-1, ai > | ai-1, ai ∈D,i=2,...,n }
基本操作： 基本操作： ……
基本操作： 基本操作：
StrAssign (&T, chars) DestroyString(&S) StrCopy (&T, S) StrLength(S) StrCompare (S, T) Concat (&T, S1, S2) StrEmpty (S)
if (pos > 0) { n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1) n{ SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) else return i ; } } return 0; }
nwhile ( pos <= n-m+1 && i) { i=Index(S, T, pos); if (i!=0) { SubString(sub sub, iSubString(sub, S, pos, i-pos); // 不置换子串 Concat(news, news, sub, V); Concat(news, news pos = i+m; }//if }//while SubString(sub, nSubString(sub, S, pos, n-pos+1); sub news, Concat( S, news, sub ); } // 剩余串
StrEmpty (S) 初始条件： 存在。 初始条件：串S存在。 操作结果： 为空串， true， false。 操作结果：若 S 为空串，则返回 true，否则返回 false。 StrCompare (S, T) 初始条件： 存在。 初始条件：串 S 和 T 存在。 操作结果： 操作结果：若S > T，则返回值 > 0； 若S = T，则返回值 = 0； 若S < T，则返回值 < 0。 StrLength (S) 初始条件： 存在。 初始条件：串 S 存在。 操作结果： 的元素个数，称为串的长度。 操作结果：返回 S 的元素个数，称为串的长度。
在上述抽象数据类型定义的13种操作中， 在上述抽象数据类型定义的13种操作中， 13种操作中 串赋值StrAssign、串复制Strcopy、 串赋值StrAssign、串复制Strcopy、 StrAssign Strcopy 串比较StrCompare 求串长StrLength StrCompare、 StrLength、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString Concat以及求子串 串联接Concat以及求子串SubString 最小操作子集。 等六种操作构成串类型的最小操作子集 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现，反之，其他串 这些操作不可能利用其他串操作来实现，反之， 操作（除串清除ClearString和串销毁DestroyString ClearString和串销毁DestroyString外 操作（除串清除ClearString和串销毁DestroyString外）可 在这个最小操作子集上实现。 在这个最小操作子集上实现。
Concat (&T, S1, S2) 。 初始条件： 存在。 初始条件：串 S1 和 S2 存在。 操作结果： 联接而成的新串。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 例如： man″ kind″ mankind″ 例如： Concaቤተ መጻሕፍቲ ባይዱe( T, ″man″, ″kind″)，得 T = ″mankind″ SubString (&Sub, S, pos, len) 初始条件： 存在， 初始条件：串 S 存在，1≤pos≤StrLength(S) ≤len≤StrLength(S)-pos+1。 且 0≤len≤StrLength(S)-pos+1。 操作结果： 操作结果： 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串 例如： 例如：SubString( sub, ″commander ″, 4, 3) 求得 sub = ″man ″ ;
4.2
串的表示和实现
在程序设计语言中， 在程序设计语言中，串只是作为输入或输出 的常量出现，则只需存储此串的串值， 的常量出现，则只需存储此串的串值，即字符序 列即可。但在多数非数值处理的程序中， 列即可。但在多数非数值处理的程序中， 串也以变量的形式出现。 串也以变量的形式出现。
T串
int Index (String S, String T, int pos) {
T为非空串 若主串S中第pos 为非空串。 pos个字符之后存在与 相等的子串， // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串， 位置，否则返回0 // 则返回第一个这样的子串在S中的 位置，否则返回0 则返回第一个这样的子串在S
位置：子串在主串中的位置是以子串的第一个 第一个字 第一个 符在主串中的字符序号(下标+1)。 相等：两个串的长度相等，并且对应位置上的字 符都 相等。
