4.1　串定义

4.1.1　串定义

串或字符串（String）是由数字、字母、下画线等组成一个有限的字符序列,它本质上就是数据元素类型为字符的线性表。字符串一般表示为如下形式。

S＝"a₁a₂…a_n"　　（n≥0）

其中,S为串名,双引号表示字符串的起止定界符,双引号括起来的字符序列为串的值；a_i（1≤i≤n）表示串中的第i个字符,n表示串中字符的个数,称为串的长度；当n＝0时,称为空串（null string）,即串中不含任何字符。

由一个或多个空格组成的串,如“”,“　”,“　　”称为空格串,其长度为串中空格的个数。为了与空串加以区别,通常用符号“Φ”表示空串。

串中任意连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串；空串是任意串的子串；任意串是它自身的子串。通常称字符在序列中的序号为该字符在串中的位置。子串在串中的位置以子串第一个字符在主串中的位置表示。例如,设A＝“This is a Student”,B＝“is”,B是A的子串,B在A中出现两次,其中首次出现的主串位置为3,因此称B在A中的位置为3。

当且仅当两个串的值相等时,称这两个串是相等的。即两个串长度相等且对应位置上的每个字符相同时,才可认为这两个串是相等的。

4.1.2　抽象数据类型定义

串本质上是数据元素类型为字符的线性表。但在操作上,线性表以“单个元素”作为操作对象,而串以“串的整体”作为操作对象。这些特点在串的多种操作中将得到体现。

串的抽象数据类型定义如下。