中国人民共和国澳门特别行政区基本法.pdf


文档分类:法律/法学 | 页数:约44页 举报非法文档有奖
1/44
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/44
文档列表 文档介绍
第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转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数44
  • 收藏数0 收藏
  • 顶次数0
  • 上传人Q+1243595614
  • 文件大小141 KB
  • 时间2018-05-06