数据结构(严蔚敏)第4章

.第四章串、【课前思考】、从数据结构的观点出发，串是特殊的线性表，但对于数据类型，字符串不是线性表。 希望带着这个问题开始学习这篇文章，学习这篇文章的内容能得出正确的结论。【学习目标】、1 .理解“串”类型定义中各基本操作的特征，正确利用它们进行串的其他操作。 2 .了解字符串类型的各种记忆表示方法。 3 .了解串匹配的各种算法。对于其他各个知识点，【重点和难点】本章不是课程整体的要点，而是系列已经用很多高级语言实现的数据类型，因此本章理解了系列类型定义中各个基本操作的定义和系列的实现方法，利用这些基本操作来实现系列的其他操作本章的难点是理解实现串匹配的KMP算法的思想，这不是本章学习的基本要求，也不是重要的学习内容。 【知识点】、字符串的类型定义、字符串的记忆表现、字符串匹配、KMP算法、【学习指南】现在用一般的高级语言实现了字符串类型，但是由于是通过软件实现的，因此作为软件相关人员应该知道字符串的实现方法。 没有必须在本章中完成的算法设计问题，如果有兴趣，请尝试以下几个问题：4.10、4.11、4.13、4.17、4.18、4.23、4.28和4.30。 其中前6个是练习列的基本操作的应用，以下2个是关于KMP算法的练习。4.1字符串类型的定义，4.2字符串的表现和实现，4.3字符串的模式匹配算法，4.1字符串的类型定义，一、基本概念，1 .字符串的定义字符串(string )是由零字符或者多个字符构成的有限排列，记述为s=a1a2an。 在这里，s是字符串的名称，用成对的单引号包围的字符串是字符串的值，但是两侧的引号不是字符串的值，不包含在字符串中。 ai(1in )可以是字母、数字或其他字符。 n是字符串中的字符数，称为字符串长度。 2 .空白字符串中不包含字符的字符串称为空白字符串，其长度n=0，s=。3 .空白字符串中包含一个或多个空白字符的字符串称为空白字符串，其长度n是空白字符的个数，通常用符号“”表示空白字符串。 字符串是有限长度的字符串，astring，4 .子字符串，主字符串通常将字符串中的字符序号称为字符串中的位置。 主字符串中部分字符串的位置由主字符串中部分字符串的第一个字符的位置表示。 如果一个字符串是另一个字符串的连续段，则该字符串称为另一个字符串的部分字符串，而另一个字符串称为该字符串的主字符串。 例如，在串s1=“abcdefg”、s2=“fabcdefghxyz”中，s1是s2的子串，s2是相对于s1的主串。 另外，空列是任意列的部分列，任意列是自己的部分列。 假设一列的长度为n，则该部分列的数量为1，真部分列的数量为(除列本身以外的部分列称为真部分列)。 仅在两个字符串的值相等时，两个字符串称为相等，仅在两个字符串的长度相等且对应位置的字符相等时相等。 抽象数据类型的定义包括： ADTString，数据对象：D=ai|aiCharacterSet，I=1，2，n0，数据关系：R1=|ai-1，aiD，i=2，基本操作：str assign i=pos； while (I=n-m1) 辅助(辅助，s，I，m )； if(StrCompare(sub，t )！=0) i； elsereturni； /while/ifreturn0； /S上不存在等于t的部分列/Index，此外列的替换函数： Replace(/0号单元格存储列的长度，或： typedefstruct/*列结构定义*/卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡intlen； 347； ssstring；在用这样的字符串的表现方法实现的字符串的运算的情况下，其基本操作是“字符串的复制”。 字符串的实际长度可以在此定义的长度范围内自由设置，超出定义长度的字符串值将被截断，称为截断。另外，在特征点：StatusConcat(SStringS1，SStringS2，SString/Concat，例如，串连接算法中，T1.S10=S11.S10； t S1 01. S1 0 S2 0 =S2 1. S2 0 ； T0=S10 S20； uncut=TRUE；if(S10 S20=MAXSTRLEN)/不截断，elseif(S10len)return(0) /*错误的插入位置*/1222222222222222222652 I=t.len pos； i-； s-chi=s-chi-t.len； 347； for(i=0； ichi pos=t.chi； 347； s-len=s-lent.len； 咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔咔i-)s-chi=s-chi-t.len； 347； for(i=0； ichi pos=t.chi； 347； s-len=maxlen； 卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡653 ichi pos=t.chi； 347； s-len=maxstrlen； 锃锃锃锃锃锃的锃锃222222222222锃锃653 57348； strdelete(s，pos，len)/*序列号pos到len文字*/可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可intpos，len； 两卡卡卡卡卡卡卡卡卡卡卡卡6 347； if (pos (s-len-len ) ) return (0)347； for(i=poslen； ilen； I )？s-ch I-len =s-ch I ； 347； s-len=s-len-len； 347； return(1) 222222222卡卡卡卡卡卡卡卡卡卡卡卡卡； StrCopy(s，t)/*将字符串t的值复制到字符串*/可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可for(i=0； ichi=t.chi； 347； s-len=t.len； ，【算法列复制函数】，(4)判定空函数。 57348； strempty(s)/*字符串s为空时(即字符串长度为0时)返回1，否则返回0*/可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可elsereturn(0) ，【算法判定空函数】，(5)串联比较函数。 57348； strcompare(s，t)/*字符串s和t相等时为0； 如果是st，则返回1的slent.len； ilen t.len； I)953348； s-chi=t.chi-s-len； 347； s-len=t.len； flag=1； 两卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡347； s-len=maxstrlen； flag=0； 2卡卡卡卡卡卡卡卡卡卡卡6 /*串s的长度等于MAXLEN，并且串t未连接*/111222222222222226 ，【算法连接函数】，(9)求子串函数。 卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡347； intpos，len； 卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡347； sub-len=len； return (1)22222222222222222652o； stringindex(s，pos，t)/*串s内串t的位置*/可可可可可可可可可可可可可可可可可可可可可可653 347； intpos； 二卡卡卡卡卡卡卡卡卡卡卡卡卡卡347； if(t.len=0)return(0) 347； I=pos； j=0； 347； while (I=t.len ) return (I-t.len )347； elsereturn(0) 57347； 算法定位函数，typedefstructchar*ch； /如果不是空字符串，则按字符串长度分配bank，/否则为NULLintlength； /字符串长度HString； 二、列堆分配存储器的特征：还在一系列地址连续的存储单元中存储列字符串，其存储空间在程序的执行中被动态分配。 c语言提供的字符串类型通常以这种存储方式实现。 系统使用函数malloc ()和free ()动态管理串空间，为每个新生成的串分配存储，并且将串值共享的存储称为“堆”。 c语言字符串以空字符结尾，字符串长度为默认值。 的双曲馀弦值。 这些字符串操作实现了一种算法，将存储空间分配给新生成的字符串，然后复制字符串值。StatusConcat(HString/Concat，status substring (hstring )/substring，sub.ch=(char * ) malloc (len * sizeof (char ) ) sub.ch 0. len-1 =s pos-1 . poslen-2 ； Sub.length=len； 块链存储表示、三、列也可以使用链表存储字符串值。 由于字符串的数据元素是一个字符，而且只有8位二进制文件，因此使用链表存储时，通常存储在一个节点上的是一个子字符串，而不是一个字符串。 存储密度=，数据要素所占的存储位，实际分配的存储位，#defineCHUNKSIZE80/用户可定义的块大小typedefstructChunk/节点结构charchCHUNKSIZE； structChunk*next； Chunk； typedefstruct/列的链表结构Chunk*head、*tail； /字符串开头和结尾的指针intcurlen； /字符串的当前长度LString； 例如，在编辑系统中，可以将整个文本编辑区域看作一列，每行由一部分列构成一个节点。也就是说，同一行的列为固定长度结构(80个字符)，行与行之间用指针连接。 实际上，可以根据问题的需要设置节点的大小。这是字符串的重要操作，许多软件都有“编辑”菜单项，其中包括“查找”子菜单项。 4.3序列模式匹配算法，子序列定位操作通常称为序列模式匹配，是各种序列处理系统中最重要的操作之一。初始条件：字符串s和t存在，t不是空字符串，而是1posStrLength(S )。 操作结果：如果主字符串s具有与字符串t相同值的部分字符串，则函数值为0，除非它返回在主字符串s的pos字符后出现的第一个位置。 首先，考虑了串匹配(搜索)的定义：索引(s、t、pos )，以及在利用特定次序结构来表示串的情况中的一些算法。 另一方面，简单算法、二、首尾匹配算法、三、KMP(D.E.Knuth、V.R.Pratt、J.H.Morris )算法、一、简单算法如目标串s=“cddcdc”、模式s的长度为n(n=6)，t的长度为m(m=3)。 用指针I表示目标列s的当前比较文字位置，用指针j表示图案列t的当前比较文字位置。 BF模式匹配的步骤如下所示。该算法简单易懂，但是效率差的主要原因是在：个主要字符串指针I相对等于一些字符串之后，如果一个字符相对不相等则必须倒推(即i=i-j 1)。 在最佳情况下，该算法的时间复杂度为O(m )，即，主串中的前m个字符恰好等于模式串中的m个字符。 最坏的情况下时间复杂度是O(n*m )。intindex(SqStrings，SqStringt)inti=0，j=0，k； while(i=t.len)k=i-t.len； /*返回匹配的第一个字符的下标*/elsek=-1模式匹配失败*/returnk； ，比较模式列中的第一个字符，然后比较模式列中的最后一个字符，最后比较模式列中的第二个到第n-1个