算法与数据结构 第3章 字符串

《算法与数据结构 第3章 字符串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章字符串首先介绍字符串的相关概念，引入字符串的抽象数据类型，然后具体给出两种字符串的表示方法：顺序表示和链接表示，分别给出它们的存储结构和主要操作的实现算法。本章的重点在第3节，详细讨论了无回溯的模式匹配算法。目录3.1字符串及其抽象数据类型3.1.1基本概念3.1.2抽象数据类型3.2字符串的实现3.2.1顺序表示3.2.2链接表示3.3模式匹配3.3.1朴素的模式匹配3.3.2无回溯的模式匹配3.1字符串及其抽象数据类型3.1.1基本概念字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。一个串可以记作s="s0s1…sn

2、-1"（n≥0），其中s是串的名字，双引号括起来的字符序列s0s1…sn-是串的值。例如：A="123"B="ABBABBC"C="BB"D="BB"E=""一个串中包括的字符个数称作这个串的长度。长度为零的串称为空串，它不包括任何字符，写作s=“”。空字符也是一个字符，由一个或多个空字符构成的字符串“”不是空串。字符串s1中任意个连续的字符组成的子序列s2被称为是s1的子串，而称s1是s2的主串。特别地，空串是任意串的子串。任意串s都是s本身的子串。除s本身之外，s的其它子串称为s的真子串。子串在主串中的位置指的是该子串的第一个字符在主串中的位

3、置。3.1.2抽象数据类型ADTStringisoperationsStringcreateNullStr(void)创建一个空串。intIsNullStr(Strings)判断串s是否为空串，若为空串，则返回1，否则返回0。intlength(Strings)返回串s的长度。Stringconcat(Strings1,Stings2)返回将串s1和s2拼接在一起构成的一个新串。StringsubStr(Strings,inti,intj)在串s中，求从串的第i个字符开始连续j个字符所构成的子串。intindex(Strings1,Strings2)如果

4、串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。endADTString3.2字符串的实现顺序表示链接表示3.2.1顺序表示字符串的顺序表示，就是把串中的字符，顺序地存储在一组地址连续的存储单元中。其类型定义为：structSeqString{/*顺序串的类型*/intMAXNUM;/*串允许的最大字符个数*/intn;/*串的长度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;例如：串s=“abcdef”，用顺序表示方式，假设s是structSeqString类型的变量，那么它的元

5、素在数组中的存放方式如下图所示：字符串运算1：创建空顺序串创建空串的方法与创建空顺序表类似，可有如下程序实现：PSeqStringcreateNullStr_seq(intm)字符串运算2：求顺序表示的串的子串PSeqStringsubStr_seq(PSeqStrings,inti,intj)求从s所指的顺序串中第i(i>0)个字符开始连续取j个字符所构成的子串。首先要创建一个空串，给子串分配空间（这由算法3.1实现）。然后判断所给参数i，j的值是否合理，i，j的取值应满足1≤i≤s->n，j>0。但可能会出现这种情况：j的值太大，从i开始在s中取不到

6、j个字符，这时可根据串的长度算出串s中从i开始到串尾的字符个数，并修改j的值，从而将串s中从i开始到串尾的j个字符都拷到子串中。程序实现3.2.2链接表示在串的链接表示中，每个结点包含两个字段：字符和指针，分别用于存放字符和指向下一个结点的指针。这样一个串就可用一个单链表来表示，其类型定义为：structStrNode;/*链串的结点*/typedefstructStrNode*PStrNode;/*结点指针类型*/structStrNode{/*链串的结点结构*/charc;PStrNodelink;};typedefstructStrNode*Lin

7、kString;/*链串的类型*/例如：串s="abcdef"，按单链表存储时，假设s是LinkString类型的变量，那么它的存储结构如图3.2(a)所示。同样为了方便处理，可在第一个结点之前增加一个头结点，如图3.2(b)所示。也可以采用循环表的形式存储串，具体形式请看图3.2(c)。字符串运算1：创建带头结点的空链串创建空串的方法与创建空链表类似，可有如下程序实现：LinkStringcreateNullStr_link(void)字符串运算2：求单链表示的串的子串LinkStringsubStr_link(LinkStrings,inti,int

8、j)求从s所指的带头结点的链串中第i(i>0)个字符开始连续取j个字符所构成的子