数据结构串

4.1串的抽象数据类型定义4.2串的表示和实现4.3串的匹配算法第四章串串的基本概念串是由零个或多个任意字符组成的字符序列。一般记作：s=‘a1a2…an’。其中s是串名；在本书中，用单引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1=i=n)是一个任意字符，可以是字母、数字或其它字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。注意：空串和空白串（通常将仅由一个或多个空格组成的串称为空白串(BlankString))。串中任意个连续字符组成的子序列称为该串的子串；包含子串的串相应地称为主串；通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的位置。例如，设A和B分别为A=‘Thisisastring’B=‘is’则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。特别地，空串是任意串的子串，任意串是其自身的子串。串的类型定义串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量或数的常量混淆而已。如x=‘123’；表明x是一个串变量名，赋予它的值是字符序列123，而x=123，则表明x是一个整型变量，赋予它的值为整数123。同样在aString=‘aString’;中，左边的aString是一个串变量名，而右边的字符序列‘aString’是赋给它的值。串的类型定义通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。串的类型定义ADTString｛数据对象：D=｛ai|aiCharacterSet，i=1，2，…，n，n0｝数据关系：R=｛ai-1，ai|ai-1，aiD，i=2，…，n｝基本操作：1.｛结构初始化｝StrAssign(&T,chars)初始条件：chars是串常量。操作结果：生成一个其值等于chars的串T。串的抽象数据类型定义串的抽象数据类型定义StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。2.｛销毁结构｝DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。串的抽象数据类型定义3.｛引用型操作｝StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。StrLength(S)初始条件：串S存在。操作结果：返回串S序列中的字符个数，即串的长度。串的抽象数据类型定义SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在,T是非空串，1≤pos≤StrLength(S)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。串的抽象数据类型定义4.｛加工型操作｝ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。Replace(&S,T,V)初始条件：串S，T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。串的抽象数据类型定义StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。｝ADTString串的抽象数据类型定义在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等5种操作构成串类型的最小操作子集。即这些操作不可能利用其它操作来实现，而其它操作均可在这个最小操作子集上实现。例如，可利用判等、求串长和求子串等操作实现串的定位函数Index(S,T,pos)。串的抽象数据类型定义Index(S,T,pos)算法的基本思想：从主串S中取“第i个字符起、长度和串T相等的子串”和串T比较，若相等，则求得函数值为i，否则i值增1直至找到和串T相等的子串或者串S中不存在和T相等的子串为止。即求使下列等式StrCompare(SubString(S,i,StrLength(T)),T)==0成立的i值。i的初值应为pos，在找不到的情况下，i的终值应该是n-m+1，其中，n为S串的长度，m为T串的长度。串的抽象数据类型定义intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，//则返回第一个这样的子串在S中的位置，否则返回0。if(pos0){n=StrLength(S);m=StrLength(T);//求得串长i=pos;while(i=n-m+1){SubString(sub,S,i,m);//取得从第i个字符起长度为m的子串if(StrCompare(sub,T)!=0)++i;elsereturni;//找到和T相等的子串}//while}//ifreturn0;//S中不存在满足条件的子串}//Index如果在程序设计语言中，串只是作为输入/输出的常量出现，则只需要存储这个串常量值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。则需要根据串操作的特点，合理地选择和设计串值的存储结构及其维护方式。串有三种机内表示方法，下面分别介绍。串的表示和实现串的表示和实现一、定长顺序存储表示；二、串的堆分配存储表示；三、串的块链存储表示；定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出。#defineMAXSTRLEN255//用户可在255内定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];//零号单元存放串的长度串的实际长度可在预定义长度的范围内随意，超过预定义的串值则被舍去，称之为“截断”。定长顺序存储表示串长有两种表示方法：1.如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中采用的串类型采用这种表示方法；2.在串值后面加一个不计入串长的的结束标记字符。如，C语言中以字符‵\0′表示串值的终结。此时的串长为隐含值，显然不便于进行某些操作。定长顺序存储表示例如C语言中串不是预定义的数据类型，而是以字符数组来表示串。如声明charstr[10]；表明str是一个串变量。C语言中还规定了一个串的结束标志'\0'，即数组中在该结束标志之前的字符是串变量的有效字符，但结束标志本身要占一个字符的空间，因此串变量str的值（字符序列）的实际长度可在这个定义范围内随意，但最大不能超过9。定长顺序存储表示StatusConcat(SString&T，SStringS1，SStringS2){//以T返回由S1和S2联接而成的新串if(S1[0]+S2[0]=MAXSTRLEN){//未截断T[1...S1[0]]=S1[1..S2[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){//截断……}else{//截断(仅取S1)……}}//Concat串联接操作StatusSubString(SString&Sub，SStringS，intpos，intlen){//若参数合法(即1≤pos≤StrLength(S)且//0≤len≤StrLength(S)-pos+1),则以Sub带回串S中第pos个//字符起长度为len的子串，并返回TRUE，否则返回FALSEif(pos1||posslen||len0||lenslen-pos+1)returnFALSE;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnTRUE;}//SubString求子串操作堆分配存储表示仍属于顺序存储表示，它的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。堆分配存储表示假设以一维数组heap[MAXSIZE]表示可供字符串进行动态分配的存储空间，并设intfree指向heap中未分配区域的开始地址(初始化时free=0)。在程序执行过程中，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。此时，堆串可定义如下：typedefstruct{intstart;//串的起始位置intlength;//串长度}HeapSring;堆分配存储表示下图是一个堆存储及符号表，其中a=‘aprogram’，b=‘string’，c=‘process’，free=24：堆分配存储表示在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”，实现堆串。此时，堆串可定义如下：typedefstruct{char*ch;//若是非空串，则按串长分配存储区,//否则ch为NULL;intlength;//串长度}HeapSring;这类操作的实现算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。串的堆分配存储表示以上两种存储表示通常为高级程序设计语言所采用。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。堆分配存储表示和线性表的链式存储结构类似，也可用链表来存储串值。但由于串的结构的特殊性，即串的数据元素是一个字符，它只有8位二进制数，因此用链表存储串值时通常采用的办法是在一个结点中存放多个字符，因此称它为块链存储表示。串的链式存储结构由于在一般情况下，串的操作都是从前往后进行的，因此串的链表通常不设双链，也不设头结点，但为了便于进行诸如串的联接等操作，链表中还附设有尾指针，并且由于串的长度不一定是结点大小的整数倍（链表中最后一个结点中的字符非都是有效字符），因此还需要一个指示串长的域。称如此定义的存储结构为串的块链存储结构，其定义如下：串的块链存储表示#defineCHUNKSIZE=80;//可由用户定义的块大小typedefstructChunk{//结点结构charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{//串的链表结构Chunk*head,*tail;//串的头指针和尾指针intcurlen;//串的当前长度}LString;串的块链存储表示在链式存储方式中，结点大小的选择和顺序存