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