数据结构——C语言描述(共10章)第4章-串

第第4章章串串4.1串的基本概念串的基本概念4.2串的存储实现串的存储实现4.2.1定长顺序串定长顺序串4.2.2堆串堆串4.2.3块链串块链串4.3串的应用举例：简单的行编辑器串的应用举例：简单的行编辑器4.4总结与提高总结与提高返回主目录4.1串的基本概念串的基本概念串串(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记为：一般记为：S=a1a2an(n0)子串子串：串中任意个：串中任意个连续的字符连续的字符组成的子序列称为该串的子串。组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，为串名，用单引号括起来的为串值，n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串：n=0时的串为空串时的串为空串返回主目录4.1串的定义串的定义串串(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记为：一般记为：S=a1a2an(n0)子串子串：串中任意个：串中任意个连续的字符连续的字符组成的子序列称为该串的子串。组成的子序列称为该串的子串。主串主串：包含子串的串相应地称为主串。：包含子串的串相应地称为主串。其中其中S为串名，用单引号括起来的为串值，为串名，用单引号括起来的为串值，n为串的长度。为串的长度。通常将字符在串中的序号称为该字符在串中的位置。通常将字符在串中的序号称为该字符在串中的位置。空格串空格串：由一个或多个称为空格的特殊字符组成的串。：由一个或多个称为空格的特殊字符组成的串。空串空串：n=0时的串为空串时的串为空串串相等串相等：当且仅当两个串的值相等时当且仅当两个串的值相等时,称这两个串是相等的称这两个串是相等的 串的抽象数据类型定义：串的抽象数据类型定义：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）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返回主目录（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在插入时也有在插入时也有部分字符被舍弃。部分字符被舍弃。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);顺序串插入函数算法顺序串插入函数算法（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);（3）串复制函数）串复制函数StrCopy(SString*s,SStringt)/*将串将串t的值复制到串的值复制到串s中中*/inti;for(i=0;ichi=t.chi;s-len=t.len;（4）判空函数）判空函数StrEmpty(SStrings)/*若串若串s为空则返回为空则返回1，否则返回，否则返回0*/if(s.len=0)return(1);elsereturn(0);返回主目录（5）串比较函数）串比较函数StrCompare(SStrings,SStringt)/*若若串串s和和t相相等等则则返返回回0；若若st则则返返回回正正数数；若若st则则返返回回负负数数*/inti;for(i=0;is.len&ilen=0;返回主目录（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);串连接函数算法串连接函数算法（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);（10）定位函数）定位函数T为为目目标标串串（主主串串），S为为模模式式串串(子子串串)，在在主主串串T中中找找子子串串S的的过过程程为为模模式式匹匹配配（patternmatching）。用用定定位位函函数数实实现现求求子子串串T在在主主串串S中中从从pos的的位位置置开开始始第第一一次次出出现现的的位位置置序序号号，定定位位函数也叫串的模式匹配。函数也叫串的模式匹配。【问题分析问题分析】3.串的简单模式匹配串的简单模式匹配Brute-Force（布鲁特（布鲁特-福斯）算法福斯）算法 简单的模式匹配算法是一种带回溯的匹配算法，算法的基简单的模式匹配算法是一种带回溯的匹配算法，算法的基本思想是：从主串本思想是：从主串S的第的第pos个字符开始，和模式串个字符开始，和模式串T的第一个的第一个字符开始比较，如果相等，就继续比较后续字符，如果不等，字符开始比较，如果相等，就继续比较后续字符，如果不等，则从（回溯到）主串则从（回溯到）主串S的第的第pos+1个字符开始重新和模式串个字符开始重新和模式串T比比较，直到模式串较，直到模式串T中的每一个字符和主串中的每一个字符和主串S中的一个连续字符子中的一个连续字符子序列全部相等，则称匹配成功，返回和序列全部相等，则称匹配成功，返回和T中第一个字符相等的中第一个字符相等的字符在主串字符在主串T中的位置；或者主串中没有和模式串相等的字符中的位置；或者主串中没有和模式串相等的字符序列，则称匹配不成功。序列，则称匹配不成功。【算法思想】【算法思想】实现时设实现时设i、j、start三个指示器：三个指示器：i指指向向主主串串T中中当当前前比比较较的的字字符符，起起始始指指向向T的的首首字字符符，此此后后，每每比比较较一一步步，后后移移一一步步，一一趟趟匹匹配配失失败败时时，回溯到该趟比较起点的下一位置。回溯到该趟比较起点的下一位置。j指指向向子子串串S中中当当前前比比较较的的字字符符，起起始始指指向向S的的首首字字符符，此此后后，每每比比较较一一步步，后后移移一一步步，一一趟趟匹匹配配失失败败时时，回溯到回溯到S的首字符处。的首字符处。start记录每趟比较时在主串记录每趟比较时在主串T中的起点，每趟比较后，中的起点，每趟比较后，后移一步，以便确定下一趟的起始位置。后移一步，以便确定下一趟的起始位置。【算法描述】StrIndex(SStrings,intpos,SStringt)/*求求从从主主串串s的的下下标标pos起起，串串t第第一一次次出出现现的的位位置置，成成功功返返回回位位置置序序号号，不不成成功返回功返回-1*/inti,j,start;if(t.len=0)return(0);/*模式串为空串时，是任意串的匹配串模式串为空串时，是任意串的匹配串*/start=pos;i=start;j=0;/*主串从主串从pos开始，模式串从头（开始，模式串从头（0）开始）开始*/while(is.len&j=t.len)return(start);/*匹配成功时，返回匹配起始位置匹配成功时，返回匹配起始位置*/elsereturn(-1);/*匹配不成功时，返回匹配不成功时，返回-1*/顺序串的简单模式匹配（定位）函数算法顺序串的简单模式匹配（定位）函数算法 4.2.2堆串堆串字字符符串串包包括括串串名名与与串串值值两两部部分分，而而串串值值采采用用堆堆串存储方法存储，串名用符号表存储。串存储方法存储，串名用符号表存储。堆串存储方法：堆串存储方法：仍以一组地址连续的存储单元仍以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程存放串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储中分配一个大小和字符串长度相同的空间存储新串的串值。新串的串值。堆堆串串存存储储表表示示：在在C语语言言中中，已已经经有有一一个个称称为为“堆堆”的的自自由由存存储储空空间间，并并可可用用函函数数malloc（）和和函函数数free（）完完成成动动态态存存储储管管理理。因因此此，我我们们可可以以直直接接利利用用C语语言言中中的的“堆堆”来实现堆串。