串的基本概念

串的基本概念第1页，共26页，2023年，2月20日，星期三串的抽象数据定义：P71对于串的基本操作集可以有不同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。定位算法（P72）——Index（S，T，pos）第2页，共26页，2023年，2月20日，星期三4.2串的表示和实现对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。串的3种机内表示方式：定长顺序存储表示堆分配存储表示串的块链存储表示第3页，共26页，2023年，2月20日，星期三4.2.1定长顺序存储表示实现：用一组地址连续的存储单元存储串值的字符序列。存储表示#defineMAXSTRLEN255TypedefunsignedcharString[MAXSTRLEN+1]截断——超过与定义长度的串值被舍去。串长的两种表示：下标为0的分量存放串的实际长度，如：pascal在串尾加一个不计入串长的结束标记符。如：C中的‘\0’第4页，共26页，2023年，2月20日，星期三串连接算法Concat（&T，S1，S2）StatusConcat(SString&T,SStringS1,SStringS2){//用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。S[0]//保存串的长度,有三种情况(1)S1[0]+S2[0]<=MAXSTRLEN;(2)S1[0]<MAXSTRLEN//&&S1[0]+S2[0]>MAXSTRLEN;(3)S1[0]=MAXSTRLENIf(S1[0]+S2[0]<=MAXSTRLEN{//未截断T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){//截断T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{//截断，仅取S1T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}第5页，共26页，2023年，2月20日，星期三求子串算法SubString（&Sub，S，pos，len）串操作特点：原操作为——字符序列的复制操作的时间复杂度基于复制序列的长度截断处理StatusSubString(SString&Sub,SStringS,intpos,intlen){//用Sub返回串的第pos个字符起长度为len的子串，其中//1<=pos<=StrLength(s)&&0<=len<=StrLength(s)-pos+1if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}第6页，共26页，2023年，2月20日，星期三串的动态存储结构串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。串的动态存储方式采用堆存储结构和链式存储结构两种形式：4.2.2堆存储结构特点仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。存储结构：typedefstruct{char*ch; //若是非空串，按串长分配空间，否则ch为NULLintlength; //串长}HString;第7页，共26页，2023年，2月20日，星期三基本算法（P76-77）举例：串插入操作StatusStrAssign(HString&T,char*chars);//生成一个值等于串常量chars的串TIntStrLength(HStringS);//返回串S的元素个数，称为串的长度IntStrCompare(HStringS,HStringT);//若S>T，返回值>0,若S=T，返回值=0，若S<T，返回值<0StatusClearString(HString&S);//将S清为空串，并释放S所占空间StatusConcat(HString&T,HStringS1,HStringH2);//用T返回S1和S2联接成的新串HStringSubString(HStringS,intpos,intlen);//返回串S的第Pos个字符起长度为len的子串//1<=pos<=StrLength(S)&&0<=len<=StrLength(S)-pos+1;串的堆分配存储结构基本操作第8页，共26页，2023年，2月20日，星期三4.2.3链式存储结构串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。用单链表存放串，每个结点仅存储一个字符，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构。#defineCHUNKSIZE80//用户定义块的大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstructChunk{Chunk*head，*tail;//串的头尾指针，tail联接2个串使用

intcurlen; //串的当前长度}Chunk;用块链表存放字符串时，其结构用C语言定义如下：第9页，共26页，2023年，2月20日，星期三存储密度小（如节点大小为1时），运算处理方便，但存储占用量大。因此，串的链式存储结构对如联接操作方便，但总体不如定长顺序存储和堆分配存储灵活，占用存储量大且操作复杂。第10页，共26页，2023年，2月20日，星期三4.3串的模式匹配算法4.3.1求子串位置的定位函数Index(S,T,pos)如S=“ASTRINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT”T=“STING”结果：Index=37，while循环次数执行41次，（Index+T[0]-1）+4，算法复杂度O(n+m)对于S=“0000000…0001”,T=“00000001”结果：Index=S[0]-T[0]+1,while循环次数Index*m,时间复杂度O(n*m)第11页，共26页，2023年，2月20日，星期三4.3.2首尾匹配算法先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。第12页，共26页，2023年，2月20日，星期三4.3.3KMP算法（D.E.Knuth,V.R.Pratt,J.H.Morris）

↓i=3第一趟匹配ababcabcacbababcac↑j=3↓i=3↓i=7第二趟匹配ababcabcacbababcac↑j=1↑j=5↓i=7↓i=11第三趟匹配ababcabcacbababcac↑j=2j=6第13页，共26页，2023年，2月20日，星期三设主串为”s1s2…sn”,模式串为”p1p2…pm”，当主串中第i个字符与模式串中第j个字符失配时，主串中第i个字符（不回退）应与模式串中哪个字符比较？存在k且不存在k‘>k满足“p1p2…pk-1”=“si-k+1si-k+2…si-1”已经得到的“部分匹配”结果是“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”所以“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”第14页，共26页，2023年，2月20日，星期三模式串的next函数Next[j]表示当模式串中第j个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的字符位置第15页，共26页，2023年，2月20日，星期三J12345678模式串abaabcacNext[j]01122312如何求Next[j]?第16页，共26页，2023年，2月20日，星期三求next函数值的过程是一个递推过程，已知：next[1]=0；假设：next[j]=k；即“p1…pk-1”=“pj-k+1…pj-1”若pj=pk则：next[j+1]=k+1=next[k]+1若：pj

pk则需往前回朔，检查pj=p?，这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串第17页，共26页，2023年，2月20日，星期三将模式串向右滑动至第next[k]个字符与主串中第j个字符比较。若next[k]=k’且pj=pk’，则next[j+1]=k’+1=next[k’]+1若pj

pk’，则以此类推第18页，共26页，2023年，2月20日，星期三J12345678模式abaabcacNext[j]01122312第19页，共26页，2023年，2月20日，星期三next函数的改进例如：

S=aaabaaabaaabaaabaaabT=aaaabnext[j]=01234Next[j]=k,且模式中pj=pk时，当主串中si

pj时，不需要再和pk比较，直接和pnext[k]比较nextval[j]=00004第20页，共26页，2023年，2月20日，星期三4.4文本编辑文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。例如有下列一段源程序：main(){floata,b,max;scanf(〃%f,%f〃,&a,&b);ifa>bmax=a;elsemax=b;}我们把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，如表4-7所示（图中↙表回车符）。第21页，共26页，2023年，2月20日，星期三第22页，共26页，2023年，2月20日，星期三在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行表.第23页，共26页，2023年，2月20日，星期三下面我们就来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。（2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述。第24页，共26页，2023年，2月20日，星期三本章小结本章主要介绍了如下一些基本概念：串：串（或字符串）（String）是由零个或多个字符组成的有限序列。主串和子串：一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。串的静态存储结构：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。堆存储结构：用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储