第4章--串.ppt

4.1串的基本概念串的基本概念串串(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记为：一般记为：S=a1a2an(n0)子串子串：串中任意个：串中任意个连续的字符连续的字符组成的子序列称为该串的子串。组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，为串名，用单引号括起来的为串值，n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串：n=0时的串为空串时的串为空串返回主目录第1页/共37页串的抽象数据类型定义：串的抽象数据类型定义：ADTString数据对象数据对象:D=ai|aiCharacterSet,i=1,2,n;n0数据关系数据关系:R=|ai-1,aiD,i=2,n;n0基本操作：基本操作：（1）StrAsign(S,chars)初始条件初始条件:chars是字符串常量是字符串常量操作结果操作结果:生成一个值等于生成一个值等于chars的串的串S返回主目录第2页/共37页（2）StrInsert(S,pos,T)初始条件初始条件:串串S和和T存在存在,1posStrLength(S)+1操作结果操作结果:在串在串S的第的第pos个字符之前插入串个字符之前插入串T（3）StrDelete(S,pos,len)初始条件初始条件:串串S存在存在,1posStrLength(S)-len+1操作结果操作结果:从串从串S中删除第中删除第pos个字符起长度为个字符起长度为len的子串的子串（4）StrCopy(S,T)初始条件初始条件:串串S存在存在操作结果操作结果:由串由串T复制得串复制得串S返回主目录第3页/共37页（5）StrEmpty(S)初始条件初始条件:串串S存在存在操作结果操作结果:若串若串S为空串为空串,则返回则返回TRUE,否则返回否则返回FALSE（6）StrCompare(S,T)初始条件初始条件:串串S和和T存在存在操作结果操作结果:若若ST,则返回值则返回值0;若若S=T,则返回值则返回值=0;若若ST,则返回值则返回值MAXLEN且且pos+LCMAXLEN且且pos+LCMAXLEN，则，则B的全部字符被舍弃（不需后移）的全部字符被舍弃（不需后移），并且，并且C在插入时也有在插入时也有部分字符被舍弃。部分字符被舍弃。第9页/共37页StrInsert(SString*s,intpos,SStringt)/*在串在串s中下标为中下标为pos的字符之前插入串的字符之前插入串t*/inti;if(poss-len)return(0);/*插入位置不合法插入位置不合法*/if(s-len+t.lenlen+t.len-1;i=t.len+pos;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=s-len+t.len;elseif(pos+t.lenMAXLEN,但串但串t字符序列可以全部插入字符序列可以全部插入*/for(i=MAXLEN-1;it.len+pos-1;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=MAXLEN;else/*插入后串插入后串长长MAXLEN,并且串并且串t的部分字符也要舍弃的部分字符也要舍弃for(i=0;ichi+pos=t.chi;s-len=MAXLEN;return(1);顺序串插入函数算法顺序串插入函数算法 第10页/共37页（2）串删除函数）串删除函数StrDelete(SString*s,intpos,intlen)/*在串在串s中删除从下标中删除从下标pos起起len个字符个字符*/inti;if(pos(s-len-len)return(0);/*删删除参数不合法除参数不合法*/for(i=pos+len;ilen;i+)s-chi-len=s-chi;/*从从pos+len开始至串尾依次向前移开始至串尾依次向前移动动，实现删实现删除除len个字符个字符*/s-len=s-len-len;/*s串串长长减减len*/return(1);第11页/共37页（3）串复制函数）串复制函数StrCopy(SString*s,SStringt)/*将串将串t的值复制到串的值复制到串s中中*/inti;for(i=0;ichi=t.chi;s-len=t.len;第12页/共37页（4）判空函数）判空函数StrEmpty(SStrings)/*若串若串s为空则返回为空则返回1，否则返回，否则返回0*/if(s.len=0)return(1);elsereturn(0);返回主目录第13页/共37页（5）串比较函数）串比较函数StrCompare(SStrings,SStringt)/*若若串串s和和t相相等等则则返返回回0；若若st则则返返回回正正数数；若若st则则返返回负数回负数*/inti;for(i=0;is.len&ilen=0;返回主目录第17页/共37页（8）连接函数）连接函数(3)连接后串长连接后串长MAXLEN且且LA=MAXLEN，则，则B的全部字符被舍弃（不需连接）。的全部字符被舍弃（不需连接）。(1)连接后串长连接后串长MAXLEN，则直接将，则直接将B加在加在A的的后面。后面。(2)连接后串长连接后串长MAXLEN且且LAlen+t.lenlen;ilen+t.len;i+)s-chi=t.chi-s-len;s-len+=t.len;flag=1;elseif(s-lenlen;ichi=t.chi-s-len;s-len=MAXLEN;flag=0;elseflag=0;/*串串s的长度等于的长度等于MAXLEN,串串t不被连接不被连接*/return(flag);串连接函数算法串连接函数算法第19页/共37页（9）求子串函数）求子串函数SubString(SString*sub,SStrings,intpos,intlen)/*将串将串s中下标中下标pos起起len个字符复制到个字符复制到sub中中*/inti;if(poss.len|lens.len-pos)sub-len=0;return(0);/*不合法不合法*/elsefor(i=0;ichi=s.chi+pos;sub-len=len;return(1);第20页/共37页（10）定位函数）定位函数T为为目目标标串串（主主串串），S为为模模式式串串(子子串串)，在在主主串串 T中中 找找 子子 串串 S的的 过过 程程 为为 模模 式式 匹匹 配配（patternmatching）。用用定定位位函函数数实实现现求求子子串串T在在主主串串S中中从从pos的的位位置置开开始始第第一一次次出出现现的的位位置置序序号号，定定位位函函数也叫串的模式匹配。数也叫串的模式匹配。【问题分析问题分析】第21页/共37页3.串的简单模式匹配串的简单模式匹配Brute-Force（布鲁特（布鲁特-福斯）算法福斯）算法 简单的模式匹配算法是一种带简单的模式匹配算法是一种带回溯回溯的匹配算法，算法的匹配算法，算法的基本思想是：从主串的基本思想是：从主串S的第的第pos个字符开始，和模式串个字符开始，和模式串T的的第一个字符开始比较，如果相等，就继续比较后续字符，如第一个字符开始比较，如果相等，就继续比较后续字符，如果不等，则从（回溯到）主串果不等，则从（回溯到）主串S的第的第pos+1个字符开始重新和个字符开始重新和模式串模式串T比较，直到模式串比较，直到模式串T中的每一个字符和主串中的每一个字符和主串S中的一中的一个连续字符子序列全部相等，则称匹配成功，返回和个连续字符子序列全部相等，则称匹配成功，返回和T中第中第一个字符相等的字符在主串一个字符相等的字符在主串T中的位置；或者主串中没有和中的位置；或者主串中没有和模式串相等的字符序列，则称匹配不成功。模式串相等的字符序列，则称匹配不成功。【算法思想算法思想】第22页/共37页实现时设实现时设i、j、start三个指示器：三个指示器：i指指向向主主串串T中中当当前前比比较较的的字字符符，起起始始指指向向T的的首首字字符符，此此后后，每每比比较较一一步步，后后移移一一步步，一一趟趟匹匹配配失失败败时时，回溯到该趟比较起点的下一位置。回溯到该趟比较起点的下一位置。j指指向向子子串串S中中当当前前比比较较的的字字符符，起起始始指指向向S的的首首字字符符，此此后后，每每比比较较一一步步，后后移移一一步步，一一趟趟匹匹配配失失败败时时，回溯到回溯到S的首字符处。的首字符处。start记录每趟比较时在主串记录每趟比较时在主串T中的起点，每趟比较后，中的起点，每趟比较后，后移一步，以便确定下一趟的起始位置。后移一步，以便确定下一趟的起始位置。【算法描述】第23页/共37页StrIndex(SStrings,intpos,SStringt)/*求求从从主主串串s的的下下标标pos起起，串串t第第一一次次出出现现的的位位置置，成成功功返返回回位位置置序序号号，不不成功返回成功返回-1*/inti,j,start;if(t.len=0)return(0);/*模式串模式串t为空串时，是任意串的匹配串为空串时，是任意串的匹配串*/start=pos;i=start;j=0;/*主串从主串从pos开始，模式串从头（开始，模式串从头（0）开始）开始*/while(is.len&j=t.len)return(start);/*匹配成功时，返回匹配起始位置匹配成功时，返回匹配起始位置*/elsereturn(-1);/*匹配不成功时，返回匹配不成功时，返回-1*/顺序串的简单模式匹配（定位）函数算法顺序串的简单模式匹配（定位）函数算法 第24页/共37页4.2.2堆串堆串字字符符串串包包括括串串名名与与串串值值两两部部分分，而而串串值值采采用用堆堆串串存存储储方法存储，串名用符号表存储。方法存储，串名用符号表存储。堆串存储方法：堆串存储方法：仍以一组地址连续的存储单元存放串仍以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执行过程中的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。的空间存储新串的串值。第25页/共37页 假设以一维数组heapMAXSIZE表示可供字符串进行动态分配的存储空间，并设 int free 指向heap 中未分配区域的开始地址(初始化时free=0)。在程序执行过程中，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。第26页/共37页堆堆串串存存储储表表示示：在在C语语言言中中，已已经经有有一一个个称称为为“堆堆”的的自自由由存存储储空空间间，并并可可用用函函数数malloc（）和和函函数数free（）完完成成动动态态存存储储管管理理。因因此此，我我们们可可以以直直接接利利用用C语言中的语言中的“堆堆”来实现堆串。此时堆串可定义如下：来实现堆串。此时堆串可定义如下：typedefstructchar*ch；intlen；HString；其中其中len域指示串的长度，域指示串的长度，ch域指示串的起始地址。域指示串的起始地址。第27页/共37页串名符号表：串名符号表：所有串名的存储映像构成一个符号表。所有串名的存储映像构成一个符号表。借助此结构可以在串名和串值之间建立一个对应关借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映像。系，称为串名的存储映像。堆串：堆串：heapMAXSIZEfree=23堆串：堆串：heapMAXSIZEfree=23符号表符号表ap r o g r a m s tr in gp ro c e s s符号名符号名lenstarta90b79c716堆串的存储映象示例堆串的存储映象示例a=aprogram，b=string，c=process，free=23。第28页/共37页堆串的基本操作堆串的基本操作(1)堆串赋值函数堆串赋值函数StrAssign(HString*s,char*tval)/*将字符常量将字符常量tval的值赋给串的值赋给串s*/intlen，i=0;if(s-ch!=NULL)free(s-ch);while(tvali!=0)i+;/*统计字符串统计字符串tval的字符个数或字符串长度的字符个数或字符串长度*/len=i;if(len)s-ch=(char*)malloc(len);if(s-ch=NULL)return(0);for(i=0;ichi=tvali;elses-ch=NULL;s-len=len;return(1);第29页/共37页(2)堆串插入函数堆串插入函数StrInsert(HString*s，intpos，HString*t)/*在串在串s中下标为中下标为pos的字符之前插入串的字符之前插入串t*/inti;char*temp;if(poss-len|s-len=0)return(0);/*插入位置不正确插入位置不正确*/temp=(char*)malloc(s-len+t-len);if(temp=NULL)return(0);for(i=0;ichi;for(i=0;ilen;i+)tempi+pos=t-chi;for(i=pos;ilen;i+)tempi+t.-len=s-chi;s-len+=t-len;free(s-ch);s-ch=temp;return(1);第30页/共37页(3)堆串删除函数堆串删除函数StrDelete(HString*s，intpos，intlen)/*在串在串s中删除从下标中删除从下标pos起起len个字符个字符*/inti;char*temp;if(pos(s-len-len)return(0);/*删除位置不正确删除位置不正确*/temp=(char*)malloc(s-len-len);if(temp=NULL)return(0);for(i=0;ichi;for(i=pos;ilen-len;i+)tempi=s-chi+len;s-len=s-len-len;free(s-ch);s-ch=temp;return(1);第31页/共37页4.2.3块链串块链串#defineBLOCK_SIZE4/*每结点存放字符个数每结点存放字符个数*/typedefstructBlockcharchBLOCK_SIZE;structBlock*next;Block;typedefstructBlock*head;Block*tail;intlength;BLString;块链结构的定义块链结构的定义第32页/共37页4.3串的应用举例串的应用举例:文本编辑文本编辑文本编辑程序用于源程序的输入和修改，公文书信、报刊和文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有书籍的编辑排版等。常用的文本编辑程序有Edit，WPS，Word等等。为为了了编编辑辑方方便便，可可以以用用分分页页符符和和换换行行符符将将文文本本分分为为若若干干页页，每每页页有有若若干干行行。我我们们把把文文本本当当作作一一个个字字符符串串，称称为为文文本本串串，页是文本串的子串，行是页的子串。页是文本串的子串，行是页的子串。我们采用堆存储结构来存储文本，同时设立页指针、行指我们采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。建立页表和行表存储每一页、每一行的起始位置和长度。第33页/共37页假设有如下假设有如下Pascal源程序：源程序：FUNCmax(x，y：integer)：integer;VARz：integer;BEGINIFxyTHENz:=x;ELSEz:=y;RETURN(z);END;页号起始位置长度10107行号 起始位置 长度 103123115346645221573146871471015FUNCmax(x，y:integer):integer;VARz:integer;BEGIN IFxlen=0)return s-head-next;if(t-len=0)return s-head-next;/*/*空串是任意串的子串空串是任意串的子串*/start=s-head-next;start=s-head-next;/*/*记录主串的起始比较位置记录主串的起始比较位置*/sp=start;sp=start;/*/*主串从主串从startstart开始开始*/tp=t-head-next;tp=t-head-next;/*/*模式串从第一个结点开始模式串从第一个结点开始*/while(sp!=NULL&tp!=NULL)while(sp!=NULL&tp!=NULL)if(sp-ch=tp-ch)if(sp-ch=tp-ch)/*/*若当前对应字符相同，则继续比较若当前对应字符相同，则继续比较*/sp=sp-next;tp=tp-next;sp=sp-next;tp=tp-next;else else/*/*发现失配字符，则返回到主串当前起始位置的下一个结点继续比较发现失配字符，则返回到主串当前起始位置的下一个结点继续比较*/start=start-next;start=start-next;/*/*更新主串的起始位置更新主串的起始位置*/sp=start;sp=start;tp=t-head-next;tp=t-head-next;/*/*模式串从第一个结点重新开始模式串从第一个结点重新开始*/if(tp=NULL)return start;if(tp=NULL)return start;/*/*匹配成功，返回主串当前起始位置指针匹配成功，返回主串当前起始位置指针*/else return NULL;else return NULL;/*/*匹配不成功，返回空指针匹配不成功，返回空指针*/第37页/共37页