数据结构DS04-串

《数据结构DS04-串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基本概念串的存储结构串的基本操作串的模式匹配第四章串*4.1串的定义和基本操作串定义：串（String）是零个或多个字符组成的有限序列。它是字符串的简称，一般记为：S="a1a2……an"（n≥0）其中，S是串名；用双引号（“”）括起的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其它字符；串字符的数目n称为该串的长度。空串与空格串长度为零（n＝0）的串称为空串（NullString），它不包含任何字符。由空格字符组成的串，称为空格串（BlankString）。它的长度为串中空格字符的个数。子串与主串串中任意个连续

2、字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。子串的位置将子串在主串中首次出现时，该子串首字符对应的主串序列中的序号定义为子串在主串中的位置。串的比较当且仅当两个串的长度相等，并且各个对应位置的字符也都相同，称两个串相等；当两个串不相等时，可按“字典顺序”区分大小(在C语言中，按字符ASCII码的大小为准)。例如，有下列四个串s1，s2，s3，s4：s1="pro"，s2="Program"s3="program"，s4="program□"以上四个串彼此互不相等，且s4＞s3＞s1＞s2。串变量与串常量串

3、变量和其它类型的变量一样，其取值是可以改变的，它必须用名字来识别；串常量和整常数、实常数一样，具有固定的值，在程序中只能被引用但不能改变其值，即只能读不能写。例如，在C语言中，有下列语句：charx[]="456";/*x是一个串变量名，它的值为字符序列456，而不是整数456*/charstring1[]="string";/*string1是一个串变量名，字符序列string是赋给它的值*/串的基本操作求串长Strlen(s)：求串s的长度，Strlen(s)的值是一个非负整数。若s是一个空串，则Strlen(s)=0

4、。串赋值StringAssign(s,string_constant)：给串s赋值。其中string_constant可为串变量、串常量或经过适当运算所得到的串值。串复制Strcpy(s,t)：由串s复制得到串t。串联接Strcat(s,t)：将串t联接到串s的末尾形成新串s。串比较Strcmp(s,t)：比较s和t的大小，若s＜t，则返回值小于0；若s＞t，则返回值大于0；若s=t，则返回值为0。求子串Substr(s,pos,len,sub)：从串s中的第pos个字符开始取长度为len的子串构成串sub。子串的定位In

5、dex(s,t)：在串s中寻找串t第一次出现时，串t首字符在串s中的位置。若找到，则返回该位置，否则返回0。串插入StrInsert(s,pos,t)：将串t插入在串s的位置pos上。串删除StrDelete(s,pos,len)：从串s中位置pos开始，删除len个字符。子串替换操作Replace(s,t,v)：将串s中的子串t全部替换成串v。4.2串的表示和实现串的顺序存储结构，简称为顺序串。用一组地址连续的存储单元来依次存放串中的字符序列，串中相邻的字符顺序存放在相邻的的存储单元中。所谓定长，指按照预先定义的大小为每

6、一个串分配一个固定的存储区域。通常有两种实现方式：4.2.1串的定长顺序存储第一种使用定长的字符数组存放串，一般使用一个不会在串中出现的特殊字符（如‘’）放在串值的末尾（不记入串长）来表示串的结束。类型定义如下:#defineMaxStrSize256/*串可能的最大长度*/typedefcharSeqString[MaxStrSize];/*SeqString是顺序串类型*/SeqStringS;/*S是一个顺序串变量*/这种存储方法不能直接得到串的长度，而是判断字符是否为‘’来确定串是否结束，串长是隐含的。当串

7、空间最大值为MaxStrSize时，最多只能存放MaxStrSize-1个字符。第二种不使用终结符，用一个整数length来指示串的实际长度，length-1表示串中最后一个字符的存储位置。类型定义如下：#defineMaxStrSize256 /*串可能的最大长度*/typedefstruct{charch[MaxStrSize];intlength;/*指示串的当前长度*/}SeqString;/*SeqString是顺序串类型*/在这种方式中，字符串的串值由ch[0]开始存放。当然，也可以将串的实际长度存储在0号单元

8、中，实际串值从1号单元处开始存放。实际应用中究竟采用哪种结构，需要根据情况进行权衡。在C语言中是采用字符''作为串的终结符的方式。顺序串的基本操作的实现下面讨论串的部分基本操作的实现算法。串的数据类型说明如下：#defineMaxStrSize256typedefstruct{charch[MaxS