《[课件]数据结构第四章串》由会员分享，可在线阅读，更多相关《[课件]数据结构第四章串（25页珍藏版）》请在金锄头文库上搜索。
1、4.1 串类型的定义 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=a1a2an (n0) 其中：s为串名，用双引号括起来的字符序列是串的值；ai(0in)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；串中字符的数目n称为串的长度。 空串零个字符的串，通常以两个相邻的双引号来表示空串（Null string），如：s=，它的长度为零； 空格串仅由空格组成的的串，如：s=；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=Im a student的长度为13。,第四章 串的基本概念,串的抽象数据定义：P71,对于串的基本操作集可以有不
2、同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。,定位算法（P72） Index（S，T，pos）,4.2 串的表示和实现 对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。,串的3种机内表示方式： 定长顺序存储表示 堆分配存储表示 串的块链存储表示,4.2.1 定长顺序存储表示,实现：用一组地址连续的存储单元存储串值的字符序列。 存储表示,#define MAXSTRLEN 255 Typedef u
3、nsigned char StringMAXSTRLEN+1,截断超过与定义长度的串值被舍去。 串长的两种表示： 下标为0的分量存放串的实际长度，如：pascal 在串尾加一个不计入串长的结束标记符。如：C中的0,串连接算法Concat（&T，S1，S2）,Status Concat(SString ,else if(S10MAXSTRLEN)/截断 T1S10=S11S10; TS10+1MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN;uncut=FALSE;,else/截断，仅取S1 T0MAXSTRLEN=S10MAXSTRLEN;uncut=FALSE
4、; return uncut; ,求子串算法SubString（&Sub，S，pos，len）,串操作特点： 原操作为字符序列的复制 操作的时间复杂度基于复制序列的长度 截断处理,Status SubString(SString &Sub,SString S,int pos,int len) /用Sub返回串的第pos个字符起长度为len的子串，其中/1=pos=StrLength(s)&0=len=StrLength(s)-pos+1,if(posS0|lenS0-pos+1 return ERROR; Sub1len=Spospos+len-1; Sub0=len;return OK; ,
5、串的动态存储结构 串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。 串的动态存储方式采用堆存储结构和链式存储结构两种形式： 4.2.2堆存储结构 特点 仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。 在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc( )分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free( )释放串不再需要的空间。 存储结构：,typedef stru
6、ct char *ch; /若是非空串，按串长分配空间，否则ch为NULL int length; /串长 HString;,基本算法（P76-77） 举例：串插入操作,Status StrAssign(HString ,串的堆分配存储结构基本操作,4.2.3链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。 用单链表存放串，每个结点仅存储一个字符，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构。,#define CHUN
7、KSIZE 80 /用户定义块的大小 typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct Chunk Chunk *head，*tail;/串的头尾指针，tail联接2个串使用 int curlen; /串的当前长度 Chunk;,用块链表存放字符串时，其结构用C语言定义如下：,存储密度小（如节点大小为1时），运算处理方便，但存储占用量大。 因此，串的链式存储结构对如联接操作方便，但总体不如定长顺序存储和堆分配存储灵活，占用存储量大且操作复杂。,4.3 串的模式匹配算法 4.3.1求子
8、串位置的定位函数Index(S,T,pos),如S=“A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT” T=“STING” 结果：Index=37，while循环次数执行41次，（Index+T0-1）+4，算法复杂度O(n+m) 对于S=“00000000001”,T=“00000001” 结果：Index=S0-T0+1,while循环次数Index*m,时间复杂度O(n*m),4.3.2首尾匹配算法 先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。,4.3.3 KMP算法（D.E.K
9、nuth, V.R.Pratt, J.H.Morris ） i=3 第一趟匹配 a b a b c a b c a c b a b a b c a c j=3 i=3 i=7 第二趟匹配 a b a b c a b c a c b a b a b c a c j=1 j=5 i=7 i=11 第三趟匹配 a b a b c a b c a c b a b a b c a c j=2 j=6,设主串为”s1s2sn”,模式串为”p1p2pm”，当主串中第i个字符与模式串中第j个字符失配时，主串中第i个字符（不回退）应与模式串中哪个字符比较？ 存在k且不存在kk满足 “p1p2pk-1”=“si-
10、k+1si-k+2si-1” 已经得到的“部分匹配”结果是 “pj-k+1pj-k+2pj-1”=“si-k+1si-k+2si-1” 所以 “p1p2pk-1”=“pj-k+1pj-k+2pj-1”,模式串的next函数 Nextj表示当模式串中第j个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的字符位置,J 1 2 3 4 5 6 7 8 模式串 a b a a b c a c Nextj 0 1 1 2 2 3 1 2 如何求Nextj?,求next函数值的过程是一个递推过程， 已知：next1 = 0； 假设：nextj = k； 即 “p1pk-1”=“pj-
11、k+1pj-1” 若 pj = pk 则： nextj+1 = k+1=nextk+1 若： pj pk 则需往前回朔，检查 pj = p?，这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,将模式串向右滑动至第nextk个字符与主串中第j个字符比较。 若nextk=k且pj=pk，则nextj+1=k+1=nextk+1 若pj pk，则以此类推,J 1 2 3 4 5 6 7 8 模式 a b a a b c a c Nextj 0 1 1 2 2 3,1,2,next函数的改进 例如： S = aaabaaabaaabaaabaaab T = aaaab nextj=0123
12、4 Nextj=k,且模式中pj=pk时，当主串中si pj时，不需要再和pk比较，直接和pnextk比较 nextvalj=00004,4.4 文本编辑 文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。,例如有下列一段源程序： main() float a,b,max; scanf(%f,%f, 我们
13、把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，如表4-7所示（图中表回车符）。,在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行表.,下面我们就来讨论文本的编辑。 （1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中
14、行号从小到大的顺序。 （2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。 （3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。 对页表的维护与行表类似，在此不再叙述。,本章小结 本章主要介绍了如下一些基本概念： 串：串（或字符串）（String）是由零个或多个字符组成的有限序列。 主串和子串：一个串的任意个连续的
15、字符组成的子序列称为该串的子串，包含该子串的串称为主串。 串的静态存储结构：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。 堆存储结构：用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。 串的链式存储结构：类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构。 除上述基本概念以外，还应该了解串的基本运算（字符串拷贝（赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的静态存储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用C语言提供的串函数进行操作。,习 题 四 1简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别？ 2两个字符串相等的充要条件是什么？ 3串有哪几种存储结构？ 4已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 5已知：s1=Im a student，s2=student，s3=teacher，试求下列各运算的结果： Strlength(s1)； S
