数据结构 课件 第4章 串

第四章串1串是字符串的简称，它是一种特殊的线性表，因为它仅由一系列字符构成，这些字符之间的关系是一种线性关系。串的处理在信息检索、文字编辑等领域都有广泛的应用，例如office办公软件中关键词查找与替换的功能，百度搜索中根据关键词语进行网页查找的功能，网络文章当中的特殊词语的识别、处理功能等等，都需要串的处理技术。24.1串的基本概念及抽象数据类型基本运算4.1.1串的基本概念串（用s来表示）是由零个或多个任意字符组成的字符序列，可表示为：s=＂C1C2...Ci...Cn＂其中s是串名，在C和C++语言中，串用双引号引起来，但引号本身不属于串的内容；Ci(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的逻辑序号;n为串的长度，表示串中所包含的字符个数。当串中没有任何字符时，我们称此串为空串。34.1串的基本概念及抽象数据类型基本运算而串中任意连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串，另外子串的第一个字符在主串中的序号称为子串在主串中的位置。我们规定，空串是任意串的子串。如果两个串的长度相等且对应字符也都相等，

我们称这两个串相等。例如串s=”abc”,则s的子串有”a”,”ab”,”abc”,”b”,”bc”,”c”和空串。44.1.2串的抽象数据类型基本运算串有许多的操作，下面只选择较常用的一些进行介绍。StrInitial(s,str[]):使用字符串数组给串s初始化或赋值StrLen(s):求串长，返回串s中字符的个数StrCopy(s,p):将串p的值赋值拷贝给串s，此时两串相等StrCat(s,p):串连接，返回s，它表示串p连接到串s后的新串StrSub(s,i,len):返回s中从i（1≤i≤n）开始的len个字符组成的串StrCmp(s,p):字符串比较，若s与p相等，返回0；若s>p，返回1；否则返回-1StrInsert(s,i,p):将串p插入到串s中第i个（1≤i≤n+1）位置，返回新的结果串StrDelete(s,i,len):删除串s中第i个（1≤i≤n）位置开始的串长为len的子串，返回新串StrReplace(s,i,len,p):用串p替换s中第i个字符开始的长度为len的子串，返回新串StrDisplay(s):在屏幕上打印串sStrFree(s):销毁串s，回收内存空间54.2串的存储结构及基本运算串是特殊的线性表，而线性表在计算机系统中可以有不同的存储形式所以串也和线性表一样在内存当中有顺序存储形式和链式存储形式64.2串的存储结构及基本运算使用顺序存储结构的串简称顺序串。在顺序表知识基础上，用一组地址连续的存储单元存储串值中的字符序列，我们为每一个字符分配一个固定长度的存储单元，并定义一个整型变量length存储串中的实际字符数。#defineMaxNum100typedefstruct{chardata[MaxNum];intlength;}SqString;在上述数据存储结构的基础上，我们设计顺序串的基本运算。74.2串的存储结构及基本运算使用顺序存储结构的串简称顺序串。在顺序表知识基础上，用一组地址连续的存储单元存储串值中的字符序列，我们为每一个字符分配一个固定长度的存储单元，并定义一个整型变量length存储串中的实际字符数。#defineMaxNum100typedefstruct{chardata[MaxNum];intlength;}SqString;在上述数据存储结构的基础上，我们设计顺序串的基本运算。8顺序串代码举例下面简单介绍几个典型顺序串的算法。StrInitial(s,str[]):使用字符数组给串s初始化或赋值voidStrInitial(SqString&s,charstr[]){ inti; for(i=0;str[i]!='\0';i++) s.data[i]=str[i]; s.length=i;}9StrLen(s):求串长，返回串s中字符的个数intStrLen(SqString&s){ returns.length;}StrCopy(s,p):将串p的值赋值拷贝给串s，此时两串相等voidStrCopy(SqString&s,SqString&p){ inti; for(i=0;i<p.length;i++) s.data[i]=p.data[i]; s.length=p.length; }顺序串代码举例10使用链式存储结构的串简称链串。在链表知识基础上，我们使用带头结点的单链表来实现串的存储和基本运算，并且每个链表结点只存储一个字符。链串的结点类型定义如下：typedefstructcharnode{ chardata;structcharnode*next;}LinkStringNode;在上述数据存储结构的基础上，我们设计链串的基本运算实现代码4.2.2串的链式存储结构及基本运算11链串存储结构代码举例下面简单介绍几个典型链串的算法。StrInitial(s,str[]):使用字符数组给串s初始化或赋值voidStrInitial(LinkStringNode*&s,charstr[]){ inti; LinkStringNode*rear,*ptr; rear=s=(LinkStringNode*)malloc(sizeof(LinkStringNode)); for(i=0;str[i]!='\0';i++){ ptr=(LinkStringNode*)malloc(sizeof(LinkStringNode)); ptr->data=str[i]; rear->next=ptr; rear=ptr; } rear->next=NULL;}12StrLen(s):求串长，返回串s中字符的个数intStrLen(LinkStringNode*s){ intlen=0; LinkStringNode*ptr=s->next; while(ptr!=NULL) { len++; ptr=ptr->next; } returnlen;}链串存储结构代码举例13思政感悟：每个人的人生就像文中所提到的模式串，都需要在社会这个大的目标串中寻找自己的定位不管自己的人生是什么样的存在形式，都可以为社会做出自己的贡献，实现自己的人生价值。作为当代大学生，我们应该深刻认识到努力学习知识，就是让自己有能力为社会为家庭付出努力、做出贡献，就是实现自己人生价值的过程。144.3串的模式匹配串的模式匹配在拼写检查、语言翻译、搜索引擎、病毒查找领域都有重要应用。模式匹配运算就是在主串中对子串进行定位的过程。设s是给定的主串（也称为目标串），而t是给定的子串（也称为模式串），而在主串s中查找等于子串t的串的过程称为模式匹配。如果在s中找到t子串，则称匹配成功，并返回t在s中首次出现的存储位置;否则匹配失败，返回0。本节内容的串采用顺序存储结构，串值从下标0开始存放。154.3.1BruteForce算法串的暴力搜索算法，即BF（Brute-Force）算法，是一种简单的字符串匹配算法，也称为朴素的模式匹配算法或穷举搜索算法。BF算法的基本思想是通过穷举所有可能的解决方案来解决问题：一般是从目标串s的第一个字符开始，逐一与模式串t的每个字符比较，如果匹配失败则将s的位置后移一位，重新开始下一趟匹配BF算法的具体步骤如下：1）从s的第一个字符开始，与t的第一个字符进行比较；2）如果相同，则继续比较s和t的下一个字符；如果不同（此时我们将模式匹配过程中这种字符比较不相同的情况称为“失配”），则将s的位置后移一位，重新开始与t的比较；3）若s的位置已经到达s.length-t.length+1则匹配失败，返回0；若模式串已经匹配完毕，则匹配成功，返回此次开始比较的目标串的起始位置。16intBFindex(SqStrings,SqStringt){ inti=0,j=0; while(i<s.length&&j<t.length) { if(s.data[i]==t.data[j]) //对应字符相同，则继续比较下一个字符 { i++;j++; //目标串和模式串指针后移

} else //对应字符不同，则目标串指针回溯进行下一次匹配 { i=i-j+1; //目标串从下一个位置开始与模式串比较 j=0; //目标串从头开始匹配 } } if(j>=t.length) //若模式串已经匹配完毕，则匹配成功 return(i-t.length); //返回目标串中匹配的第一个字符的下标 else //若s的位置已经到达s.length-t.length+1则匹配失败 return(-1); //返回-1}假设字符串使用顺序存储，则BF算法的代码如下：17如图所示第1趟模式匹配从s[0]与t[0]开始，直到s[7]与t[7]失配，匹配失败；第2趟模式匹配从s[1]与t[0]开始，s[1]与t[0]失配，匹配失败；第3趟模式匹配从s[2]与t[0]开始，s[2]与t[0]失配，匹配失败；第4趟模式匹配从s[3]与t[0]开始，s[3]与t[0]失配，匹配失败；第5趟模式匹配从s[4]与t[0]开始，直到s[11]与t[7]均匹配成功，标志着此次模式匹配成功，推导出目标串下标为11-7=4为模式串的起始位置。18BF算法的时间复杂度为O(m*n)，其中m和n分别为模式串和目标串的长度。BF算法的优点是简单直接、可靠它通过穷举所有可能的解决方案，能够找到确切的答案，且实现起来相对简单，不需要复杂的数据结构或算法；而缺点是效率低、不适用于大规模问题，因为在问题空间较大的情况下，时间复杂度可能非常高，运行时间长，并且随着问题规模的增加，穷举所有可能的解决方案的计算量呈指数级增长。194.3.2KMP算法KMP算法，全称Knuth-Morris-Pratt算法，是根据三位作者DonaldKnuth、JamesMorris、VaughanPratt的姓氏的首字母来命名的KMP算法是BF算法的改进算法，其主要特点是消除了目标串指针的回溯的过程，使算法效率有了很大的提升。20BF算法与KMP算法的对比BF算法的运行示意图KMP算法的运行示意图从两图的对比看出KMP算法的优势：当第1趟s[7]与t[7]失配后，第2趟直接让s[7]与t[3]进行比较，成功后，再让两串的指针（下标）依次加1来进一步比较。此时，目标串的指针（下标）没有像BF算法一样回退到i-j+1的位置，这就是“消除了目标串指针的回溯”的实际意义，显然也就使算法的效率有了提升。21如图所示第1趟模式匹配从s[0]与t[0]开始，直到s[7]与t[7]失配，匹配失败；第2趟模式匹配从s[1]与t[0]开始，s[1]与t[0]失配，匹配失败；第3趟模式匹配从s[2]与t[0]开始，s[2]与t[0]失配，匹配失败；第4趟模式匹配从s[3]与t[0]开始，s[3]与t[0]失配，匹配失败；第5趟模式匹配从s[4]与t[0]开始，直到s[11]与t[7]均匹配成功，标志着此次模式匹配成功，推导出目标串下标为11-7=4为模式串的起始位置。22BF算法的时间复杂度为O(m*n)，其中m和n分别为模式串和目标串的长度。BF算法的优点是简单直接、可靠它通过穷举所有可能的解决方案，能够找到确切的答案，且实现起来相对简单，不需要复杂的数据结构或算法；而缺点是效率低、不适用于大规模问题，因为在问题空间较大的情况下，时间复杂度可能非常高，运行时间长，并且随着问题规模的增加，穷举所有可能的解决方案的计算量呈指数级增长。23那KMP算法如何知道目标串中的某字符失配的情况下，在下一趟应该与模式串中的哪个位置的字符进行比较来提高效率呢？这就需要研究模式串自身的特点和建立一个被称作next的数组。对于模式串“abcdabce”，如上图所示，设j表示其下标，其相应的next[]数组的定义如下：.next[j]=-1，当j=0时；.Next[j]=max(k),当串“t[0]...t[k-1]”=串“t[j-k]...t[j-1]”,且0<k<j时；.Next[j]=0,其他情况。按照上述定义，可以得出下表所示的包含next数组的表格。24对表格中的信息解读如下：1）当j=0时出现失配，查表可知，next[0]=-1，则理论上下一趟比较应由元素t[-1]与目标串中出现失配的s[i]进行，而实际上表示下一趟要由s[i+1]与t[0]开始进行比较；2）当j=1时出现失配，查表可知，next[1]=0，则下一趟应由元素t[next[1]]即t[0]与目标串中出现失配的s[i]进行下一趟比较；3）当j=2时出现失配，查表可知，next[2]=0，则下一趟应由元素t[next[2]]即t[0]与目标串中出现失配的s[i]进行下一趟比较；4）当j=3时出现失配，查表可知，next[3]=0，则下一趟应由元素t[next[3]]即t[0]与目标串中出现失配的s[i]进行下一趟比较；5）当j=4时出现失配，查表可知，next[4]=0，则下一趟应由元素t[next[4]]即t[0]与目标串中出现失配的s[i]进行下一趟比较；25对表格中的信息解读如下：6）当j=5时出现失配，查表可知，