if(pos>=0) { n=StrLength(S); m=StrLength(T); i=pos; while ( i<=n-m ) { SubString( sub,S,i,m );//返回S中从i起长度为m的子串 if( SubCompare (sub,T)!= 0 ) i++; else return i; } // while
StrCompare(S, T) : 若S>T 返回>0;若S=T 返回=0;若
S<T 返回<0;
StrLength( S ) :串S存在，返回S中元素的个数，称为串
的长度
more
串的基本操作
Concat( &T, S1,S2 ) : 用T返回S1和S2联接而成的新串 SubString( &Sub,S,pos,len ) : 用Sub返回串S的第pos个
▪ 两个串之间可以进行比较。 ▪ 称两个串相等，当且仅当这两个串的值相等，包括
两个串的长度相等，并且各个对应位置的字符都相 等。
▪ 当两个串不相等时，可按“字典顺序”分大小。令
s= “s0s1…sm-1” (m>0) t= “t0t1…tn-1” (n>0) ▪ 假设，两者最大有前k个子序列相等（最大相等前缀子
▪ 串中任意个连续的字符组成的子序列称为该串的子串。包含 子串的的串相应地称为主串。通常称字符在序列中的序列号 为该字符在串中的位置。子串在主串中的位置则以子串第0 个字符在主串的位置来表示。
4.1 串的定义和操作
▪ 例如：下面a，b，c，d都是串
▪ a=“BEI”
长度为3
▪ b=“JING”
长度为4
44
第4章 串
▪ 字符串数据是计算机非数值处理的主要对象之一。在早 期字符串字符串作为输入输出的常量出现，现已发展成 为字符串类型，可以进行一系列的操作。
▪ 字符串一般简称为串。在汇编和编译程序中，源程序是 字符串数据。在事务处理程序中，顾客的姓名和地址及 货物的名称、产地等也是字符串。此外，如信息检索系 统、文字编辑程序、自然语言翻译系统等都是以字符串 为处理对象。
串），s和t的大小由sk和tk的大小来决定。在C语言中字 符的大小按ASCII码的大小为准
4.1 串的定义和操作
▪ 串值必须用一对双引号括起来，但双引号不属于串， 它的作用只是为了避免与变量或常量混淆。例如：
▪ x = “123”;
▪ 其中，X是一个串变量名，赋给它的值是字符序列123, 而不是整数123。之间可以进行比较。
S = “a0a1…an-1” (n ≥ 0 ) ▪ 其中，S是串的名称，用双号括起来的字符序列是串的值；
ai (0≤i≤n-1)可以是字母、数字或其它字符（字符的序号从 0开始，与C、C++、JAVA等语言的习惯一致）；串中字符 的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。
} ADT String
4.1 串的定义和操作
▪ 对于串的基本操作集可以有不同的定义方法，各种 版本的C语言都定义了自己的串操作函数，使用时 应以语言参考为准。
▪ 在前面的基本操作中：串赋值(StrAssing)、串 比较(StrCompare)、求串长(StrLength)、串 联接(StrCompare)、求子串(SubString)等五
▪ 然而，目前的计算机硬件结构主要是面向数值计算的需 要，基本上没有提供处理字符串数据操作的指令，需要 用软件来实现字符串类型。由于各种应用具有不同的特 点，要有效的实现字处理，必须根据具体情况使用合适 的存储结构。
4.1 串的定义和操作
▪ 串(String),或称字符串是由零个或多个字符组成的有限序 列。一般记为：
数 据 结 构（Data Structure ）
第四章 串（String）
主讲：李耀国
第4章 串
▪ 4.1 串的定义和操作 ▪ 4.2 串的表示和实现
▪ 4.2.1 定长顺序存储表示 ▪ 4.2.2 堆分配存储表示 ▪ 4.2.3 块链存储表示
▪ 4.3 正文模式匹配** ▪ 4.4 正文编辑-串操作应用举例
字符起长度为len的子串 Index( S, T, pos ) : 如果在主串S中存在和串T值相同的
子串，则返回它在主串S中第pos个字符之后第一次出现 的位置，否则返回0 Replace( &S,T,V ) : 用V替换主串S中出现的所有与T相等 的不重叠的子串 StrInsert( &S,pos,T ) : 在串S的第pos个字符之前插入串 T StrDelete( &S,pos,len ) : 在串S中删除第pos个字符起长 度为len的子串 DestroyString( &S ) : 串S被摧毁
串的基本操作（1）
ADT String{
数据对象: D={ai| ai∈CharacterSet,i=1,2,...,n,n≥0} 数据关系: R1={<ai-1, ai> | ai-1,ai∈D,i=2,...,n} 基本操作：
StrAssing( &T, chars ) : chars是字符串常量，生成一个 值等于chars的串T StrCopy( &T, S ) :串S存在，由串S复制得串T StrEmpty( S ) :如果串S为空，返回TRUE，否则返回 FALSE
▪ aString=“aString”;
▪ 左边的aString是一个串变量名，而右边的字符序列 aString是赋给它的值
▪ 在各种应用中，空格通常是串的字符集合中的一个
元素，可以出现在其它字符之间，由一个或多个空
格组成的串称为空格串
▪ “ ”； 和 “
”；都是空格串。
为了清楚起见我们以后用Φ来表示空串
▪ c=“BEIJING”
长度为7
▪ d=“BEI JING”
长度为8
▪ 串的逻辑结构和线性表极为相似，区别仅仅在于串 的数据对象约束为字符集。但是串的基本操作和线 性表有很大的差别。
▪ 在线性表的操作中大多数以“单个元素”为操作对 象，而在串的操作中大多数以“串的整体”为操作 对象。
4.1 串的定义和操作
种操作构成串类型的最小操作子集。其他操作可由 这些最小操作子集来实现。
▪ 例如可用串比较、求串长和求子串等操作实现定位
函数(Index)
4.1 串的定义和操作
▪ 算法4.1（用最小操作子集来实现定位函数(Index) int Index( String S, String T, int pos ) {//T非空、如果主串S中pos之后存在与T相等的子串， //则返回第一个这样的子串在S中的位置，否则返回-1
