串的定义及基本运算.ppt

2019年5月25日,1,4.1 串的定义及基本运算 4.2 串的存储结构 4.3 模式匹配算法的实现 4.4 小结与习题,第四章 串,2019年5月25日,2,串（字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成，计算机非数值处理的对象经常是字符串数据，在事物处理程序中，一般也是作为字符串处理的。,4.1 串的定义及基本运算,一、串和基本概念 串(String)是零个或多个字符组成的有限序列。 一般记作：S=“a1a2a3an” 其中S是串名，双引号括起来的字符序列是串值； ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。,2019年5月25日,3,通常将仅由一个或多个空格组成的串称为空白串(Blank String) 。 注意：空串和空白串的不同。,二、串的术语 1.主串和子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。,2019年5月25日,4,2.子串的位置：子串的第一个字符在主串中的序号称为子串的位置。 B在A中出现了两次，首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。,特别地，空串是任意串的子串，任意串是其自身的子串。,3.串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。,2019年5月25日,5,三、串的基本运算,1.求串长StrLength(s)： 操作条件：串s存在；操作结果：求出串s的长度。,2.串赋值StrAssign(s1,s2) 操作条件： s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝）。 操作结果：将s2的串值赋值给s1， s1原来的值被覆盖掉。,2019年5月25日,6,3.连接操作 ：StrConcat (s1,s2,s) 或StrConcat (s1,s2) 操作条件：串s1,s2存在。 操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变; 后者是在s1的后面联接s2的串值，s1改变， s2不改变。,4.求子串SubStr (s,i,len)： 操作条件：串s存在，1iStrLength(s)，0lenStrLength(s)-i+1。 操作结果：返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。,2019年5月25日,7,5.串比较 StrCmp(s1,s2) 操作条件：串s1,s2存在。操作结果：若s1= =s2，操作返回值为0；若s1s2, 返回值0。,6.子串定位 StrIndex(s,t)：找子串t在主串s中首次出现的位置 操作条件：串s,t存在。操作结果：若ts，则操作返回t在s中首次出现的位置，否则返回值为-1。,2019年5月25日,8,8.串删除 StrDelete(s,i,len) 操作条件：串s存在，1iStrLength(s)， 0lenStrLength(s)-i+1。 操作结果：删除串s 中从第i个字符开始的长度为 len的子串，s的串值改变。,7.插入 StrInsert(s,i,t) 操作条件：串s,t存在，1iStrLength(s)+1。 操作结果：将串t插入到串s 的第i个字符位置上。,9.串替换 StrRep(s,t,r) 操作条件：串s,t,r存在，t不为空。 操作结果：用串r 替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。,2019年5月25日,9,4.2 串的存储结构,4.2.1 串的定长顺序存储 类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：,1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下： typedef struct char dataMAXSIZE; int curlen; SeqString;,2019年5月25日,10,2.在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用0来表示串的结束。,3. 设定长串存储空间：char sMAXSIZE+1; 用s0存放串的实际长度，串值存放在s1sMAXSIZE，字符的序号和存储位置一致，应用更为方便。,2019年5月25日,11,4.2.2 定长顺序串的基本运算,1.串联接：把两个串s1和s2首尾连接成一个新串s 。 int StrConcat1(s1,s2,s) int i=0 , j, len1, len2; len1= StrLength(s1); len2= StrLength(s2) if (len1+ len2MAXSIZE-1) return 0 ; j=0; while(s1j!=0) si=s1j;i+; j+; j=0; while(s2j!=0) si=s2j;i+; j+; si=0; return 1; ,2019年5月25日,12,2. 求子串 int StrSub (char *t, char *s, int i, int len) int slen; slen=StrLength(s); if ( islen | lenslen-i+1) printf(参数不对); return 0; for (j=0; jlen; j+) tj=si+j-1; tj=0; return 1;,2019年5月25日,13,3.串比较:若s1= =s2，操作返回值为0；若s1s2, 返回值0。,int StrComp(char *s1, char *s2) int i=0; while (s1i= =s2i ,2019年5月25日,14,4.2.3 串的块链存储表示,顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。,typedef struct node char data; struct node *next; lstring;,一个链串由头指针唯一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。,2019年5月25日,15,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符#(#不属于串的字符集)来填充最后一个结点，以表示串的终结。,存储密度的概念：,2019年5月25日,16,4.3 模式匹配算法的实现,4.3.1 求子串位置的定位函数StrIndex(s,t),串的模式匹配（即子串定位）是一种重要的串运算。 设 s 和 t 是给定的两个串，在串 s 中查找串 t 的位置, 在此过程中称 s 为主串, t 为子串。 在主串 s 中查找子串 t 的过程称为模式匹配，如果查找成功，则称匹配成功，函数返回 t 在 s 中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t 也称为模式。,2019年5月25日,17,算法思想如下： 首先将主串中的第一个字符s1与子串中的第一个字符t1进行比较，若相同，继续比较两个串中的第二个字符，即s2和t2进行比较， 若这样的比较对于子串的每个字符都成立，则该趟比较的开始位置就是子串在主串中的位置（查找成功） 若上面的比较在某个位置上出现对应位置字符不相同的情况，即此趟比较不成功，将主串的指针指向本趟比较开始位置的下一个字符（i=i-j+2） ，同时将子串的位置返回到第一个位置。 进行下次比较，直到匹配成功或者主串已经结束。,简单的模式匹配算法BF-穷举的模式,2019年5月25日,18,算法举例,第2趟 S a b b a b a (i=3-j+2=2开始) T a b a (j=1开始),第4趟 S a b b a b a T a b a (查找成功）,第1趟 S a b b a b a (i=3,j=3) T a b a,第3趟 S a b b a b a (i=2-j+2=3)开始 T a b a (j=1开始),主 串 S a b b a b a (初始位置i=1,j=1) 子 串 T a b a,2019年5月25日,19,算法程序实现如下 int StrIndex_BF(char *s,char *t) int i=1,j=1; while (it0) return (i-t0); /* 成功，返回存储位置 */ else return (1);,2019年5月25日,20,算法分析-时间复杂度,（i)在最好情况下，每趟不成功的匹配都发生在第一对字符比较时例如：s=aaaaaaaaaabc t=bc 即最好情况下的时间复杂度是O(n+m)。,(ii)在最坏的情况下，如果不成功的匹配都发生在子串（t）的最后一个字符的位置，即每趟比较都要进行 m 次，这样比较的趟数要 n 趟，因此，此情况下的时间复杂度为 O(n*m)。 例如：s=aaaaaaaaaab t=aaaab,2019年5月25日,21,算法分析 优点：算法简单 实现容易 缺点：算法复杂度高； 重复比较次数比较，只要不匹配的情况，要从新开始；回溯次数比较多。,2019年5月25日,22,算法思路：如上所述，希望某趟在si和tj匹配失败后，主串指针i不回溯，模式串t向右“滑动”至某个适当位置上，使得tk对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，关键的问题是确定滑动的位置。,KMP算法 算法引入：分析BF算法的执行过程, 造成BF算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于s串要回到本趟开始字符的下一个字符，t串要回到第一个字符。而这些回溯并不是必要的。,2019年5月25日,23,KMP算法中NEXT函数的介绍 next函数的性质： nextj是一个整数，且0nextjj 为了使t的右移不丢失任何匹配成功的可能，当存在多个 满足上面(4)式的 k 值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个。 如果在tj前不存在满足(4)式的子串，此时若t1tj，则 k=1; 若t1=tj，则k=0; 这时“滑动”的最远，为j-1个字符，即用t1 和sj+1继续比较。,2019年5月25日,24,NEXT函数的表示 Next函数的定义： 设有模式串：t=“abcaababc”，则它的next函数值为：,0 当j=1 max k | 1kj 且t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 1 其它情况,nextj=,2019年5月25日,25,KMP算法程序实现如下： int StrIndex_KMP(char *s,char *t,int pos) /* 从串 s 的第 pos 个字符开始找首次与串 t 相等的子串 */ int i=pos, j=1, slen, tlen; while (it0) return i-t0; /* 匹配成功，返回位置 */ else return 1; /* 匹配不成功，返回信息*/ ,2019年5月25日,26,Next函数的求法： 据前述，可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有上面的(5)式成立，则当tk tj 时应将模式向右滑动，使得第nextk个字符和“主串” 中的第j个字符相比较。若nextk=k，且t ktj，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得 t1 t2 t k =tj-k+1 tj- k+2 tj (6) 因此： nextj+1=nextk+1 (7),2019年5月25日,27,同理若t k tj，则将模式继续向右滑动至使第nextk个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k(1 kk j)满足(4.10)，此时若t1tj+1 ， 则有：nextj+1=1 (8) 否则若 t1=tj+1 ， 则有：nextj+1=0 (9),2019年5月25日,28,求Next函数的程序实现： void GetNext(char *t,int next ) int i=1,j=0; next1=0; while (i0 ,2019年5月25日,29,