《数据结构》课件第4章 串.ppt

（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.lenjt.len)if(s.ch[i]==t.ch[j]){i++;j++;}/*当前对应字符相等时推进*/else{start++;/*当前对应字符不等时回溯*/i=start;j=0;/*主串从start+1开始，模式串从头（0）开始*/}if(j=t.len)return(start);/*匹配成功时，返回匹配起始位置*/elsereturn(-1);/*匹配不成功时，返回-1*/}顺序串的简单模式匹配（定位）函数算法4.2.2堆串字符串包括串名与串值两部分，而串值采用堆串存储方法存储，串名用符号表存储。堆串存储方法：仍以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。堆串存储表示：在C语言中，已经有一个称为“堆”的自由存储空间，并可用函数malloc（）和函数free（）完成动态存储管理。因此，我们可以直接利用C语言中的“堆”来实现堆串。此时堆串可定义如下：typedefstruct{char*ch；intlen；}HString；其中len域指示串的长度，ch域指示串的起始地址。串名符号表：所有串名的存储映像构成一个符号表。借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映像。堆串：heap[MAXSIZE]free=23堆串：heap[MAXSIZE]free=23符号表aprogramstringprocess符号名lenstarta90b79c716堆串的存储映象示例a=aprogram，b=string，c=process，free=23。堆串的基本操作(1)堆串赋值函数StrAssign(HString*s,char*tval)/*将字符常量tval的值赋给串s*/{intlen，i=0;if(s-ch!=NULL)free(s-ch);while(tval[i]!=\0)i++;len=i;if(len){s-ch=(char*)malloc(len);if(s-ch==NULL)return(0);for(i=0;