《算法与数据结构-C语言描述（第二版）：第3章 字符串》由会员分享，可在线阅读，更多相关《算法与数据结构-C语言描述（第二版）：第3章 字符串（35页珍藏版）》请在金锄头文库上搜索。
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 基本概念基本概念字符串字
2、符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。一个串可以记作s=s0s1sn-1（n0），其中s是串的名字，双引号括起来的字符序列s0s1sn-是串的值。例如：A=123B=ABBABBCC=BBD=BBE=一个串中包括的字符个数称作这个串的长度长度。长度为零的串称为空串空串，它不包括任何字符，写作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,Str
4、ings2)如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。end ADTString3.2 字符串的实现顺序表示链接表示3.2.1顺序表示字符串的顺序表示，就是把串中的字符，顺序地存储在一组地址连续的存储单元中。其类型定义为：structSeqString/*顺序串的类型*/intMAXNUM;/*串允许的最大字符个数*/intn;/*串的长度，nMAXNUM*/char*c;typedefstructSeqString*PSeqString;例如：串s=“abcdef”，用顺序表示方式，假设s是structSeqString类型的变量，那么它的元素在数组中的存放方式如下图所
5、示：字符串运算1：创建空顺序串 创建空串的方法与创建空顺序表类似，可有如下程序实现： PSeqStringcreateNullStr_seq(intm) 字符串运算2：求顺序表示的串的子串PSeqStringsubStr_seq(PSeqStrings,inti,intj)求从s所指的顺序串中第i(i0)个字符开始连续取j个字符所构成的子串。首先要创建一个空串，给子串分配空间（这由算法3.1实现）。然后判断所给参数i，j的值是否合理，i，j的取值应满足1is-n，j0。但可能会出现这种情况：j的值太大，从i开始在s中取不到j个字符，这时可根据串的长度算出串s中从i开始到串尾的字符个数，并修改j
6、的值，从而将串s中从i开始到串尾的j个字符都拷到子串中。程序实现3.2.2链接表示在串的链接表示中，每个结点包含两个字段：字符和指针，分别用于存放字符和指向下一个结点的指针。这样一个串就可用一个单链表来表示，其类型定义为：structStrNode;/*链串的结点*/typedefstructStrNode*PStrNode;/*结点指针类型*/structStrNode/*链串的结点结构*/charc;PStrNodelink;typedefstructStrNode*LinkString;/*链串的类型*/例如：串s=abcdef，按单链表存储时，假设s是LinkString类型的变量，那
7、么它的存储结构如图3.2(a)所示。同样为了方便处理，可在第一个结点之前增加一个头结点，如图3.2(b)所示。也可以采用循环表的形式存储串，具体形式请看图3.2(c)。字符串运算1：创建带头结点的空链串创建空串的方法与创建空链表类似，可有如下程序实现： LinkStringcreateNullStr_link(void)字符串运算2：求单链表示的串的子串LinkStringsubStr_link(LinkStrings,inti,intj)求从s所指的带头结点的链串中第i(i0)个字符开始连续取j个字符所构成的子串。这里首先要为链串结构和头结点申请空间，创建一个空链表，这由算法3.3实现。然后
8、判断所给参数i，j的值是否合理，i，j的取值应为i0，j0。接着从s-head开始找第i个结点，找到后，就从该结点开始，为子串中的结点申请空间，并将元素值拷过去。程序实现3.3 模式匹配设有两个串t和p：t=t0t1tn-1p=p0p1pm-1其中1mn（通常有mc0表示）开始比较。在最坏的情况下，每趟比较都在最后出现不等，最多比较nm1趟，总比较次数为m*(nm1)，由于在一般情况下mn，所以算法运行时间为O(m*n)。3.3.2无回溯的模式匹配为要找到一个无回溯的匹配算法，关键在于当匹配过程中，一旦pi和tj比较不等，即：subStr(p,1,i-1)subStr(t,j-i+1,i-1)
9、，pitj要能立即确定右移的位数和继续（无回溯的）比较的字符.把这个字符记为pk，显然有ki，并且对不同的i，k值也不相同。Knuth等人发现这个k值仅依赖于模式p本身前i个字符的组成，而与目标t无关。下面用nexti表示与pi对应的k值，其意义在于：一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符pnexti与tj进行比较。特别地，如果p中任何字符都不必再与tj进行比较（这个nexti下面用-1表示），可以直接从tj+1和p0开始比较。对任何模式p，只要我们能确定nexti（i0，1，m-1）的值，就可以如下加速匹配的过程：当pitj时，直接右移inexti个字符，如果ne
10、xti大于等于0，则从tj与pnexti继续比较，否则从tj1与p0继续比较下去。在已知next数组的前提下，无回溯的匹配算法可以实现为：intpMatch(PSeqStringt,PSeqStringp,int*next)仔细分析执行过程，j的值在循环中只增不减。由于j的初值为0，循环过程中保持jn（第7行），所以循环体中（第9行）j+的语句最多执行n次，从而与它相邻的（第9行）i+语句最多也不超过n次；另外i的初值（第6行）为0，循环中唯一能使i减少的语句是（第11行）i=nexti（每次执行至少减1），由于一旦执行i=nexti,而使i=-1,那么下步必定会执行（第9行）i+;j+，所以
11、循环中，执行（第11行）inexti的次数，不会超过i+的执行次数加1。根据上面分析可知：算法3.6的时间代价为O()。例子taabcbabcaabcaababcn18，p“abcaababc”,m9。next数组的存在性在p与任意的目标t匹配时，若发现pitj，则意味着p0，p1，pi-1已与t中对应的字符进行过比较，而且是相等的（见图3.5(a)），否则便轮不到pi与tj比较。因此，图3.5(a)与3.5(b)相同。然后，把p右移k位，希望用p与tj继续比较，这意味着，tj以前的比较工作（相当于用p0pi-1的一个前缀（p0pk-1）与它的一个长度相同的后缀（pi-kpi-1）进行比较）,
12、都已经全部相等（图3.6）。图3.5发现pitj时的状态图3.6p0p-1的前缀与后缀比较因此，我们可以在p0pi-1中，求出其相同的而且是最大的前缀与后缀的长度，设它是k（0ki1）。显然这个值不但存在，而且仅仅依赖于本身，与任何无关。当右移量为ik时，相同的前后缀恰好对齐，pk与tj对齐。我们用不着去比较这一对前后缀，因为已经知道它们是相等的。当右移量小于ik时，也用不着比较，因为根据k的意义，此时用长度大于k的前后缀对齐，比较结果必定不相等。当右移量大于ik时，又可能错过目前匹配成功的机会。由此可见，若在匹配时发现pitj，即可直接地把p右移ik位，并且只从pk与tj开始向右比较。这样做
13、，不但实现了没有回溯，同时并没有丢失任何匹配成功的机会。通过上述分析，可以知道求nexti的关键，就是求出p0pi-1中最大相同的前缀与后缀的长度。而求出p0pi-1中最大相同的前缀与后缀的问题，也就是需要判断：p0pi-2是否等于p1pi-1如果不等，继续判断p0pi-3是否等于p2pi-1等等。 作为一种特殊情况，对于任何而言，当i0时，都可以令next-1。因为如果p0与tj比较不等，只能用p0与tj+1去比较，也就是说不存在一个pnext0可以再与tj比较。另外根据前面的讨论，可以知道：对于任意的i（0im）有nextii；同时，如果p0pi-1中最大相同的前缀与后缀的长度k，那么p0
14、pi中最大相同的前缀与后缀的长度为k+1。加上有next-1作为基础，就可以依次计算出next，next，等值。在计算nexti+1时，充分利用已经求出的next0，next1，nexti的值，结果使得计算nexti+1的过程，有点类似于前面无回溯的模式匹配。程序实现算法改进按上述方法求出的next数组，已可用于无回溯的匹配，但是还可以进一步改善。试想，按上面算法求出k后，若pkpi，则当发现pitj时，用pk与tj比较，也必然不相等。应该再右移，用pnextk与tj比较。既然预先就知道这种结局，理应预先避免走这个弯路。这只要把第7行修改为：if(pk!=pi)nextik;elsenexti
15、nextk;这种改进是为了使nexti的值尽可能变得更小些，以便在匹配时更多地右移。程序实现以上算法从形式上来看，这是一个二重循环，每重循环最多执行m次，最大运行时间可能达到O(m2)。但是仔细分析一下，因为每执行一次外层（第4行）循环，i严格增1（第6行），所以外层循环正好执行m1次；另外k的值从（第2行）-1开始，k+恰好执行（第6行）m1次，并且只有在这一语句中k被增值。而在内层循环（第5行）中，语句knextk至少使k减少1，所以整个算法中，这个语句的执行次数累计起来不可能超过m1次（否则，k将小于-1，这是不可能的），所以内层循环总的执行次数最大为m1。因此算法的执行时间为O(m)。与算法3.6的执行时间合在一起，得到用长度为m的串p为模式与长度为n的目标串t进行匹配所需的总计算时间为O(mn)。 小结字符串是由字符作元素组成的线性表。但是作为一种抽象数据类型，有它自己的操作，在对串处理时，要抓住它的特殊性。串和线性表一样有顺序存储和链式存储两种方式。模式匹配是子串在主串中的定位操作，是一个比较常用的操作。朴素的模式匹配算法比较直观，易于理解；但是效率比较低。无回溯的模式匹配算法的技巧性很强，实现无回溯的模式匹配的基础是依靠next数组支持。计算next数组的算法，实质上还是一个无回溯的模式匹配算法。对于这个算法的改进是巧上加巧。
