第4章 串电子课件

第4章串本章讲解字符串。要求理解字符串的概念；掌握顺序串和链串的存储结构和基本操作；掌握BF和KMP模式匹配算法；灵活应用字符串。四川的腊肉还是很有名的。春节前，各种腊肉一串一串被挂起卖，品类也多，如香肠、三线肉、排骨、香舌、猪肝等等，它们都可以被称为串，但品类不同串的类型也就不同，好比其它串就是其它串，香肠串看作字符串吧。提纲4.1串基本概念4.2顺序串4.3链串4.4串的模式匹配4.5串应用4.6串学习总结4.1串基本概念

4.1串基本概念串的抽象数据接口IString描述4.2顺序串以顺序存储结构进行存储的串称为顺序串。4.2.1顺序串存储结构顺序串存储结构采用顺序存储方式，同顺序表存储结构，故顺序串也可以用一维数组存储，不同的是顺序串中的元素是字符或者字符串，前者用字符数组char[]存储，后者用字符串数组str[]存储，我们主要探讨的是前者。如图4.1所示。4.2.1顺序串存储结构举例：肉联厂有台猪肉识别机器，如果是猪肉就传送过去做成火腿肠，如果是牛肉、羊肉、兔肉等就打回。在这个例子中，火腿肠严格要求是猪肉，好比字符数组或字符串数组严格要求其内的元素是字符或字符串一样的道理。4.2.2顺序串基本操作顺序串类SqString描述4.2.2顺序串基本操作读取第i个元素顺序串读取第i个元素操作是指获得字符串中位置序号为i的字符。4.2.2顺序串基本操作【算法4.1】读取顺序串第i个元素。思路:利用数组的随机访问特点，在i合法情况下直接返回第i个位置的字符。代码见算法4.14.2.2顺序串基本操作2.求子串顺序串求子串操作是指求字符串中1个指定区间的字符串。4.2.2顺序串基本操作【算法4.2】求字符串中从指定开始位置begin到结束位置end-1的子串。思路:（1）判断begin和end参数的合法性，若不合法返回异常否则执行（2）；

（2）从begin位置开始遍历，读取的字符放入1个字符数组temp[]中；

（3）重复（2），直到遍历完end-1位置处的字符；

（4）将用temp[]构造1个字符串，并返回该字符串。代码见算法4.24.2.2顺序串基本操作【思考与练习4.1】利用算法4.1是否可以实现算法4.2，若可以请写出实现算法。答：可以。将算法4.2中for循环中的语句改成：tmp[i-begin]=new算法4_1().algorithm4_1(i);调用4.1算法即可。4.2.2顺序串基本操作3.插入子串顺序串插入子串操作是指在指定位置之前插入指定字符串。4.2.2顺序串基本操作【算法4.3】在字符串的第i个字符之前插入子串str。思路:（1）判断i的合法性，若不合法返回异常，否则执行（2）；

（2）扩容子串的长度；

（3）从i位置的字符开始到最后1个字符，向后移动子串长度个位置；

（4）将子串str插入到i位置；

（5）字符串长度增加子串长度。代码见算法4.34.2.2顺序串基本操作4.删除子串顺序串删除子串操作是指将字符串中指定区间的字符串删掉。4.2.2顺序串基本操作

4.2.2顺序串基本操作5.比较字符串大小顺序串比较字符串大小操作是指依次比较2个字符串中的字符ASCII编码大小，直到比较完而返回相应结果。4.2.2顺序串基本操作

4.2.2顺序串基本操作【思考与练习4.2】下面的算法也是比较2个字符串大小（当前字符串与str字符串比较），请指出算法的不完整性在哪里？答：假设str1=“abc”，str2=“abcdefg”，执行上面的算法，返回0说明2字符串相等，与实际不符。4.3链串以链式存储结构进行存储的串称为链串。4.3.1链串存储结构链串存储结构采用链式存储方式，同链表存储结构。链串中的元素既可以是字符也可以是字符串，前者结点大小为1但存储密度较小，后者结点大小大于1且存储密度大，但是删除、增加、替换操作时可能会带来大量字符移动，所以我们主要探讨的是前者。用带头结点的单链表表示链串如图4.2所示。4.3.2链串基本操作链串结点类LinkNode描述链串类LinkString描述4.3.2链串基本操作插入子串链串插入子串操作是指在串指定位置插入子串，构成新的字符串。4.3.2链串基本操作【算法4.6】在链串i位置处插入子串。思路:（1）建1空链串s；

（2）遍历原串，每次将结点尾插到s，直到i位置结点结束插入；

（3）将待插入串尾插到s；

（4）将原串余下结点尾插到s；

（5）返回s。代码见算法4.64.3.2链串基本操作

4.3.2链串基本操作2.字符串相等比较链串字符串相等比较操作是指判断2个链串是否一样。4.3.2链串基本操作【算法4.7】比较2个链串s和t是否相等，若相等返回true，否则返回false。思路:（1）比较s和t长度，若不相等则返回false，否则执行（2）；

（2）依次遍历s和t，一旦遇到不相等则返回false；

（3）遍历过程中若没有返回false，遍历结束之后返回true。代码见算法4.74.4串的模式匹配串的模式匹配，又称串匹配，是指子串的定位运算。假设有2个串s和t，s为主串也称正文串，t为子串也称模式串。在主串s中查找与模式串t相匹配的子串，如果查找成功，返回匹配的子串第1个字符在主串中的位置。串的模式匹配算法最常见的有2种：BF算法和KMP算法。4.4.1BF算法BF(BruteForce)算法属蛮力、暴力、穷举算法，就是穷举主串s中的所有子串，与模式串t进行比较，判断是否存在相等。例如，设主串s="aaaaab"，模式串t="aaab"，比较过程如图4.3所示。也可以这样理解：将t看作s的“移动窗口”，若失配则继续移动，直到匹配或超出范围。4.4.1BF算法【算法4.8】顺序串的BF模式匹配算法。思路:（1）从主串s="s0s1…sn-1"的第1个字符开始和模式串t="t0t1…tm-1"中的第1个字符比较，若相等则继续逐个比较后续字符，否则执行（2）；

（2）从主串s的第2个字符开始重新与模式串t的第1个字符进行比较；

（3）依此类推；

（4）若从主串s的第i个字符开始，每个字符依次和模式串t中的对应字符相等，则匹配成功，返回i；否则返回-1。代码见算法4.84.4.1BF算法【算法4.9】链串的BF模式匹配算法。思路:（1）返回值i置为0，p指向s首结点，p1指向p结点，q指向t首结点；

（2）p1和q结点字符相等时同步后移，若q为null则返回i，否则执行（3）；

（3）p移向s下1个结点，p1指向p结点，q指向t首结点，i增1；

（4）重复（2）、（3），直到遍历完s；

（5）若没有匹配则返回-1。代码见算法4.94.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法3.求next[]数组在求next[]数组前，先来理解2个概念：字符串的前缀和后缀。前缀：从第1个字符开始求连续的字符串但不包含本身，这些字符串构成了前缀，显然前缀不包含最后1个字符；后缀：从最后1个字符开始求连续的字符串但不包含本身，这些字符串构成了后缀，显然后缀不包含第1个字符。4.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法4.4.2KMP算法设主串s="ababcabcacbab"，模式串t="abcac"。给出KMP进行模式匹配的过程。答：KMP模式匹配只需3趟完成，其过程如图4.6所示。4.4.2KMP算法

4.5串应用串尤其字符串的应用十分广泛，几乎项目中都要用到Java语言中的字符串类：String类，可见一斑。下面举些典型例子加深学习。4.5串应用【例4.1】病毒检测。疫情爆发，有种病毒其DNA序列呈环形，而人类的DNA序列呈线性，例如病毒DNA序列为“aabb”，患者DNA序列为“eabbacab”，该患者感染了病毒，因为环形的“aabb”可以分解为“aabb”、“abba”、“bbaa”、“baab”，患者DNA序列中含有“abba”，故患者为感染者。设计1个算法来检测患者是否为感染者。4.5串应用思路：（1）用1个循环队列存储病毒DNA序列；（2）通过出队入队和遍历操作循环队列，求出病毒所有DNA序列；（3）用KMP模式匹配算法，检测每1种病毒DNA序列是否存在于患者DNA序列中；（4）若检测到有1个病毒序列存在于患者中，则输出true，否则输出false。代码见应用4.14.5串应用【进一步思考】例4.1算法中求环形病毒DNA所有序列还可以用到哪些数据结构？答：循环单链表；数组（模运算）；栈（入栈顺序不变，出栈顺序考虑），等。4.5串应用【例4.2】顺序串s由数字和小写字母组成，设计1个算法将所有数字放在前面，所有字母放在后面。思路：（1）双指针i和j设置，初始值分别指向s的首字符和尾字符；（2）i从前向后找小写字母，j从后向前找数字字符；（3）它们都找到之后，交换字符；（4）重复（2）、（3），直到i大于等于j。代码见

应用4.24.5串应用【进一步思考】例4.2算法如果用单指针实现，其思路是什么？答：指针从头开始遍历：若遇数字则继续移动，若遇字母则将其插入到s末尾后继续移动。重复上述过程，直到遍历了s的n个长度。4.5串应用【例4.3】求1个字符串s中第1个最长平台，所谓平台是指连续相同的字符。思路：（1）双指针设置：i和j初始位置分别指向s首字符和第2个字符；（2）比较i和j所指向的字符，若不等则i指针移动特定距离，j指针仍为其后继指针，