第5章字符串和广义表
字符串
* 广义表
字符串
字符串ADT
字符串(string,简称为串)是由n(n≥0)个字符组成的有限序列,记为
s="a0 a1 … an-1"
其中,s是串名,双引号括起来的字符序列是串s的值,n是串中字符的个数,又称为串长度。n=0的串称为空串。要注意区分空串和空白串:空串不包括任何字符,空白串包括空格符。
串中任意连续个字符组成的子序列称为该串的子串(substring),包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。
与数组的情况类似,许多程序设计语言引入了串的概念,在不同程度上提供了字符串的处理能力。FORTRAN语言中的串是直接量,标准PASCAL、C/C++语言中是将字符串作为字符数组来处理的。但是许多语言的编译器通过库函数的方式,向用户提供了丰富的字符串函数。
。SNOBOL语言是一种专门面向字符串处理的程序设计语言,它有丰富的串运算函数。因此,我们可以认为字符串是许多程序设计语言已经实现的数据结构。作为一种数据结构,字符串是一种线性数据结构,但它不同于线性表,因为组成字符串的元素是字符,在存储表示上有其特殊性。线性表上的运算大都是针对单个元素的,而字符串运算往往是以子串为单位进行的(见ADT 5-1),因此,将字符串作为单独的数据结构进行研究是有必要的。我们同样可以将字符串定义为一个抽象数据类型。ADT 5-1中定义了一组常用的字符串运算,当然,我们还可以定义其他运算,以提供更多的字符串操作功能。
ADT 5-1 String{
数据:
零个或多个字符的有限序列,其最大允许长度为MaxString。
运算:
void CreateString(String *s, int maxsize);
后置条件: 构造一个空串。
int Length(String s)
后置条件: 函数值返回字符串s的长度。
void Clear(String *s)
后置条件: 字符串*s 成为空串。
void Copy(String p,String *s)
后置条件: 字符串*s 有串p的值。
BOOL Insert(String *s, String p, int pos)
后置条件:若0≤pos≤Length(*s),且Length(*s)+Length(p)≤maxsize,则串*s为在位置pos-1和pos之间插入串p后得到的串,其长度为Length(*s)+Length(p),并且函数返回TRUE,否则函数返回FALSE。
BOOL Remove(String *s, int pos,int len)
后置条件:若0≤pos<Length(*s),且Length(*s)-pos>len,则串*s为从位置pos开始删除了长度为len的子串后所得到的串,其长度为Length(*s)-len,并且函数返回TRUE,否则函数返回FALSE。
String SubString(String s, int pos,int len)
后置条件:若0≤pos<Length(*s),且Length(*s)-pos>len,则返回串*s中从位置pos开始,长度为len的子串,否则返回空串。
int Index(String s, String p, int pos)
后置条件:若0≤pos<Length(*s),则函数值是大于等于pos的最小整数k,使得串p与串s中从位置k开始,长度为Length(p)的子串相等,并且函数返回k,否则函数返回-1。
}
字符串的存储表示
1. 串的顺序表示
串的顺序表示是指把串中的字符顺序地存储在一片连续的空间中。在按字节编址的机器中,每个字符占一个字节。在按字编址的机器中,可采用压缩形式来存放。所谓压缩形式,就是根据各机器字的长度,尽可能将多个字符存放在一个字中。而非压缩形式则是不论机器字的长短,每个字只放一个字符。显然压缩形式节省了空间,但却不易实现字符串运算,非压缩形式的特点正相反。
一般来讲,字符串有定义长度,这是该字符串运算中的最大允许长度。一个字符串还有它当前的实际长度。指示一个串的实际长度可以有不同的做法。PASCAL语言在字符数组的位置为0的字节中直接存放该字符串的长度,C语言则以“\0”指示字符串结束,见图5-1。
图5-1 字符串的顺序表示(字节编址)
(a) PASCAL字符串存储方式;(b) C语言字符串存储方式
2. 串的链接表示
串也可以用单链表存储,每个结点可以存放一个字符,见图5-2(a)。这种方法处理简便,但存储空间利用率不高。每个结
中国人民共和国澳门特别行政区基本法 来自淘豆网www.taodocs.com转载请标明出处.