算法与数据结构：第2章 串讲解）

第二章第二章串串【课前思考课前思考】1.串就是线性表串就是线性表的结论是否正确？的结论是否正确？从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。2.串和线性表的主要差别是什么？串和线性表的主要差别是什么？希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。2.1 串类型的定义串类型的定义2.2 串的表示和实现串的表示和实现2.3 串的模式匹配算法串的模式匹配算法2.1串的类型定义串的类型定义一、一、基本概念基本概念 1串的定义串的定义串串(string)是是由由零零个个或或多多个个字字符符组组成成的的有有限限序序列列，记记作作s=“a1a2an”，ai(1in)可可以以是是字字母母、数数字字或或其其它它字字符。符。n为串中字符的个数，称为为串中字符的个数，称为串的长度串的长度。2空串空串不含任何字符的串称为不含任何字符的串称为空串空串，它的长度，它的长度n=0，记为记为s=“”。一般用符号一般用符号“”表示空串表示空串3空格串空格串含含有有一一个个或或多多个个空空格格的的串串，称称为为空空格格串串，它它的的长长度度n为为空格的个数。空格的个数。4子串、主串子串、主串若若一一个个串串是是另另一一个个串串中中连连续续的的一一段段，则则这这个个串串称称为为另另一一个串的个串的子串子串，而另一个串相对于该串称为，而另一个串相对于该串称为主串主串。例如例如,串串s1=“abcdefg”，s2=“fabcdefghxyz”通常将字符在串中的序号称为通常将字符在串中的序号称为该字符在串中的位置该字符在串中的位置。子子串串在在主主串串中中的的位位置置则则以以子子串串的的第第一一个个字字符符在在主主串串中中的的位置来表示。位置来表示。空串是任意串的子串，任意串是自身的子串。空串是任意串的子串，任意串是自身的子串。若若一一个个串串的的长长度度为为n，则则它它的的子子串串数数目目为为?真真子子串串个个数数为为?(除串本身以外的子串都称为真子串除串本身以外的子串都称为真子串)。两个串相等两个串相等：当且仅当两个串的值相等时：当且仅当两个串的值相等时二、串的抽象数据类型的定义如下：二、串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 基本操作基本操作：StrAssign(s,chars)StrCopy(s,t)DestroyString(s)StrEmpty(s)StrCompare(s,t)StrLength(s)StrConcat(l,s,t)SubString(t,s,i,len)Str Index(s,t)Str Replace(s,t,v)StrInsert(s,i,t)StrDelete(s,i,len)ClearString(s)ADT String StrAssign(s,chars)初始条件：chars 是字符串常量。操作结果：把 chars 赋为串变量s 的值。StrCopy(s,t)初始条件：串 s 存在。操作结果：将串 t 的值复制给 s。DestroyString(s)初始条件：串 s 存在。操作结果：串 s 被销毁。StrEmpty(s)初始条件：串s存在。操作结果：若 s 为空串，则返回1，否则返回 0。表示空串，空串的长度为零。StrCompare(s,t)初始条件：初始条件：串 s 和 t 存在。操作结果：操作结果：若s t，则返回值 0；若s t，则返回值 0；若s t，则返回值 0。例如：例如：StrCompare(“data”,“state”)0StrLength(s)初始条件：串 s 存在。操作结果：返回 s 的元素个数，称为串的长度。StrConcat(l,s,t)初始条件：串 s 和 t 存在。操作结果：用 l 返回由 s 和 t 联接而成的新串。例如例如：StrConcate(l,“man”,“kind”)求得 l=“mankind”SubString(t,s,i,len)初始条件：串 s 存在，1iStrLength(s)且0lenStrLength(s)-i+1。操作结果：用 t 返回串 s的第 i 个字符起 长度为 len 的子串。例如：例如：SubString(t,“commander”,4,3)求得 t=“man”；SubString(t,“commander”,1,9)求得 t=“commander”；SubString(t,“commander”,9,1)求得 t=“r”；子串为子串为“串串”中的一个字符子序列中的一个字符子序列SubString(t,“commander”,4,7)t=?SubString(t,“beijing”,7,2)=?t=?SubString(“student”,5,0)=“”起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串 StrIndex(s,t)初始初始条件：条件：串s和t存在，t是非空串，操作结果：操作结果：若主串 s 中存在和串 t值相同 的子串,则返回它在主串 s 中第一次出现的位置；否则函数值为-1。(此处串的第一个字符放在下标为0的位置)假设 s=“abcaabcaaabc”,t=“bca”StrIndex(s,t)=2；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。StrReplace(s,t,v)初始条件：串s,t和 v 均已存在，且 t 是非空串。操作结果：用v替换主串s中出现 的所有与（模式串）t 相等的不重叠的子串。例如：假设 s=“abcaabcaaabca”，t=“bca”若 v=“x”，则经置换后得到 s=“axaxaax”若 v=“bc”，则经置换后得到 s=“abcabcaabc”StrInsert(s,i,t)初始条件：串s和t存在，1iStrLength(s)1。操作结果：在串s的第i个字符之前 插入串t。例如：例如：s=“chater”，t=“rac”，则执行 StrInsert(s,4,t)之后得到 s=“character”StrDelete(s,i,len)初始条件：串s存在 1iStrLength(s)-len+1。操作结果：从串s中删除第i个字符 起长度为len的子串。ClearString(s)初始条件：串s存在。操作结果：将s清为空串。对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：在上述抽象数据类型定义的13种操作中，串赋值串赋值StrAssign、串复制串复制Strcopy、串比较串比较StrCompare、求串长求串长StrLength、串联接串联接StrConcat以及求子串以及求子串SubString 等六种操作构成串类型的最小操作子集等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。例如，实现定位函数StrIndex(s,t)可利用串比较、求串长和求子串等操作。StrCompare(SubString(s,i,StrLength(t),t)?0 s 串 t 串 t串in-m+1算法的基本思想为：算法的基本思想为：int StrIndex(String S,String T)/T为非空串。若主串S中存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回-1 n=StrLength(S);m=StrLength(T);i=1;while(i t返返回回值值0，若若s=t返返回回值值=0，否否则则返返回回值值chi=t-chi)&(s-chi!=0)&(t-chi!=0)i+;return s-chi-t-chi;2.求串长（1）int StrLength(SString*s)/*求求串串长长即即串串s中中字字符的个数符的个数*/return s-len;/*直接返回串长域的值直接返回串长域的值2.求串长（2）C语言中是没有设串长int StrLength(SString*s)int i=0;/*初始化数组下标和串长域初始化数组下标和串长域len*/s-len=0;while(s-chi!=0)s-len+；i+;return s-len；3.串联接void StrConcat(SString*l,SString*s,SString*t)int i,j;if(s-len+t-lenSTRINGLEN)printf(“结果串结果串L的长度超过串的定长的长度超过串的定长STRINGLEN!n”);else for(i=0;s-chi!=0;i+)l-chi=s-chi;for(j=0;t-chj!=0;j+)l-chi+j=t-cht;li+j=0;l-len=s-len+t-len;4.求子串void SubString(SString*t,SString*s,int i,int len)/*i下下标标从从0开始开始*/int j;if(i=s-len)printf(“子串的开始位置子串的开始位置i越界错误越界错误n”);else if(lens-len-i)printf(“子串的长度子串的长度len越过主串错误越过主串错误n”);else for(j=0;jchj=s-chi /*将所求子串存入将所求子串存入t串中串中*/t-chj=0;/*为子串为子串t添加结束标志添加结束标志*/t-len=len;/*设置子串长度设置子串长度*/二、串的堆分配存储表示二、串的堆分配存储表示(课本课本)特点：仍用一组地址连续的存储单元存储串的字符序列，但其存储空间是在程序执行过程中动态分配而得。char storemaxsize：堆空间，其中maxsize表示这片连续存储空间的最大容量。free：整型变量，该空间中尚未分配区间的开始地址（初始值为0）。length：串值序列的长度，start:串值序列在store中的开始地址。串的存储映像映像表：反映了堆中串名与串值之间的一一对应关系堆中的串不以0结尾堆式动态存储的串的类型说明#define MAXSIZE 10000 /*MAXSIZE为堆的最大容量*/typedef struct string /*定义串为结构体*/int length;/*串长度*/int start;/*串在堆中的开始位置*HString;/*定义串类型标识符为HString*/char storeMAXSIZE;/*定义堆为一维数组store*/int free;/*堆store中尚未分配区间的开始地址指示器变量*/堆式动态存储的串赋值算法void StrAssign(HString*s,char chars)int i,len;i=0;/*为统计字符串常量中的字符个数初始化*while(charsi!=0)/*统计chars中字符个数*/i+;len=i;if(lenMAXSIZE)/free初值为0 printf(“串常量为空串或堆的尚未分配区间空间不足n”)；else for(i=0;istart=free;/*建立存储映像*/s-length=len;free=free+len;/*修改堆中的指示器变量free的值*/堆式动态存储的串复制算法void StrCopy(HString*s,HString*t)int i;if(free+t-lengthMAXSIZE)/