文档介绍：第四章串
串类型的定义
串的表示和实现
串的模式匹配算法
串操作应用举例
计算机上的非数值处理的对象基本上是字符串数据;
字符串一般简称为串;
现在我们使用的计算机硬件结构主要是反映数值计算的需要的,因此,在处理字符串数据时比处理整数和浮点数要复杂得多;
首要工作是根据具体情况使用更合适的存储结构。
串的特性
串的特性
串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。
然而,串的基本操作与线性表有很大差别。
在线性表的基本操作中,大多以“单个元素”作为操作对象,如:在线性表中查找某个元素、获取某个元素、在某个位置上插入一个元素和删除一个元素等;
而在串的基本操作中,通常以“串的整体”作为操作对象,如:在串中查找某个子串、获取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。
串类型的定义
串(String)是零个或多个字符组成的有限序列;
一般记作S=“a1a2a3…an”,其中S是串名,双引号括起来的字符序列是串值;
ai(1≦i≦n)可以是字母、数字或其它字符;
串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String),它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白串(Blank String);
注意:空串和空白串的不同,例如“”和“”分别表示长度为1的空白串和长度为0的空串。
串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。
通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号,定义为子串在主串中的序号(或位置)。
例如:设A和B分别为A=“This is a string” B=“is”则B是A的子串,A为主串。B在A中出现了两次,其中首次出现所对应的主串位置是3。因此,称B在A中的序号(或位置)为3。
特别地,空串是任意串的子串,任意串是其自身的子串。
通常在程序中使用的串可分为两种:串变量和串常量:
串常量和整常数、实常数一样,在程序中只能被引用但不能改变其值,即只能读不能写。
通常串常量是由直接量来表示的,例如语句Error(“overflow”)中“overflow”是直接量;
但有的语言允许对串常量命名,以使程序易读、易写。如C++中,可定义
const char path[]=“dir/bin/appl”;
这里path是一个串常量,对它只能读不能写。
串变量和其它类型的变量一样,其取值是可以改变的。
另外值得一提的是,串值必须用一对单引号括起来,但单引号本身不属于串,它的作用只是为了避免与变量名或数的常量混淆而已。
例如:程序设计语言中
x=‘123’;则表明x是一个串变量名,赋给它的值是字符序列123。
在各种应用中,空格常常是串的字符集合中的一个元素,因而可以出现在其它字符中间。由一个或多个空格组成的串一称为空格串(空白串,blank string),它的长度为串中空格字符的个数。
为了区别于空白串,用符号“ø”来表示“空串”。
串的抽象数据定义
串的抽象数据类型定义:
数据对象: D={ ai|ai∈ElemSet,i=1,2,……,n, n≥0 }
数据关系: R1={ <ai-1,ai>| ai-1, ai ∈D,i=2,……,n }
基本操作:
StrAssign(&T, chars)
初始条件:chars是字符串常量。操作结果:对一个空串T赋值。
StrCopy(&T, S)
     初始条件:串S存在。操作结果:由串S复制得串T。
StrEmpty(S)
    初始条件:串S存在。
操作结果:若S为空串,则返回TRUE, 否则返回FALSE。
pare(S, T)
    初始条件:串S和T存在。
操作结果:若S>T,则返回值>0;若S=T, 则返回值=0;若S<T,则返回值<0。
StrLength(S)
   初始条件:串S存在。
操作结果:返回S的元素个数,称为串的长度。
ClearString(&S)
     初始条件:串S存在。操作结果:将S清为空串。
Concat(&T, S1, S2)
  初始条件:串S1和S2存在。操作结果:用T返回由S1和S2联接而成的新串。
SubString(&Sub, S, pos, len)
    初始条件:串S存在,1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos-1。
操作结果:用Sub返回串S的第pos个字符起长度为len的子串。