数据结构(C++)串.ppt
1,考题,算法题（本题12分）假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。称可以操作的序列为合法序列，否则称为非法序列。1.下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIOC.IIIOIOIO D.IIIOOIOO2.通过对问题1的分析，写出一个算法判定给所给的操作序列是否合法。若合法则返回true，否则返回false。（假定被判定的操作序列已存入一维数组中。）,2,#define m 100#define true 1#define false 0int JudgeS(char s)char Stackm;int top=-1,i=0;while(si!=#)if(si=I)top+;Stacktop=si+;else if(si=0)if(top=0)top-;i+;else return false;else return true;,3,Essential of Lecture Eight:,一、串的定义 二、串类的实现 三、串的模式匹配 四、一些应用,第八讲 串,难点,4,一、串的定义 string,串是零个或多个字符组成的有限序列。一般记作S=“a0a1a2an-1“(n=0)ai(0in-1)可以是字母、数字或其它字符；,串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。串可以看成字符类型的顺序表。,5,一、串的定义 string,例：（1）a=“This is a string”（2）b=“string”（3）c=“”（4）d=“”（5）e=“你好”说明：（1）串中包含的字符个数，称为串的长度。长度为0的串称为空串，它不包括任何字符;（2）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。,6,一、串的定义 string,空 串n=0的串子 串串中若干相邻字符组成的子序列主 串包含子串的串空格串仅含有空格字符的串(n不为0)串相等设 s1=a11,an1 s2=a12,an2 若 n1=n2且ai1=ai2（1in1)则 s1=s2,术语：,7,1void Copy(String©,const String&original)初始条件：串original已存在。操作结果：将串original复制得到一个串copy。2bool Empty()const初始条件：串已存在。操作结果：如串为空则返回true，否则返回false。3int Length()const初始条件：串已存在。操作结果：返回串的长度，即串中的字符个数。,串的基本操作,一、串的定义 string,8,4void Concat(String&addTo,const String&addOn)初始条件：串addTo和addOn已存在。操作结果：将串addOn联接到串addTo的后面。5String SubString(const String&s,int pos,int len)初始条件：串存在，且0poss.Length()，0 lens.Length()pos+1。操作结果：返回从第pos个字符开始长度为len的子串。,串的基本操作,一、串的定义 string,9,6int Index(const String&text,const String&target,int pos=0)初始条件：串text和串target都存在，串target非空，且0 pos text.Length()。操作结果：返回串text中第pos个字符后第一次出现的串target的位置。,串的基本操作,一、串的定义 string,10,原始的C风格的串，容易出问题。char*s;在C+在头文件string中已含了一种安全的字符串实现，但由于这个库没有包含在一些较老的C+编译器中，因此本节将设计自已的安全的String类，使用面向对象技术来克服C风格的串中存在的问题。,二、字符串的实现,11,class String protected:/串实现的数据成员:char*strVal;/串值int length;/串长public:/抽象数据类型方法声明及重载编译系统默认方法声明:String();/构造函数 virtual String();/析构函数String(const String/从C风格串转换的构造函数,串类的实现,12,String(LinkList,13,void Write(const String/求串s的第pos个字符开始的长度为len的子串,串相关操作,14,bool operator=(const String/重载关系运算符!=,15,串构造函数(1)String:String(const char*inString)/操作结果：从C风格串转换构造新串转换构造函数length=strlen(inString);/串长strVal=new charlength+1;/分配存储空间 strcpy(strVal,inString);/复制串值,16,串构造函数(2)String:String(LinkList/串值以0结束,17,将C+串转换为C语言串const char*String:CStr()const/操作结果：将串转换成C风格串return(const char*)strVal;/串值类型转换,18,串比较实现bool operator=(const String,19,进一步串操作示例void Concat(String/释放copy,20,模式匹配：在T中查找与P相同的子串第一次出现的位置的过程。Pattern matching主串也称为目标串Target子串也称为模式串Pattern应用：文本编辑中经常搜索某个子文本，又如分子生物学中，利用匹配算法从DNA序列中提取信息，获得其中的某种模式串。,三、串的模式匹配,21,三、串的模式匹配,简单模式匹配算法,22,Sub!=p,Sub!=p,Sub!=p,三、串的模式匹配,简单模式匹配算法,23,匹配成功,三、串的模式匹配,Sub!=p,Sub!=p,Sub=p,简单模式匹配算法,24,int SimpleIndex(const String,简单模式匹配算法,25,while(i T.Length()/匹配失败,26,简单模式匹配算法,假设:目标串T a a a a a a a a a a a a 模式串P a a a a a b,缺点：每次都在比较到模式串的最后一个字符时才发现不匹配。改进：首尾字符串模式匹配算法但若不匹配出现在模式串的中间位置，效率反而会降低。,27,三、串的模式匹配,首尾字符串模式匹配算法,int FrontRearIndex(const String while(startPos T.Length()-P.Length()+1),28,首尾字符串模式匹配算法,int front=0,rear=P.Length()-1while(front rear)return startPos;/匹配成功else+startPos;return-1;,29,匹配算法分析,三、串的模式匹配,设n=T.Length();m=P.Length();最好情况的复杂度为O(m),如P=“STING”T=“STING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT”最坏情况的复杂度为O(n*m),如P=“00000001”T=“0000000000000000000000000000001”,30,匹配算法分析与改进,三、串的模式匹配,在最坏情况下，第i 趟匹配成功，前面i-1趟的不成功的匹配中，每趟比较了m次，第i 趟成功时也比较了m次，所以共比较了i m次。因此在最坏情况下，平均比较次数是：,由于nm，故上述的时间复杂度为O(mn),31,简单匹配算法缺点在于每次不能匹配以后主串（目标串）指针和子串（模式串）指针都必须回溯，造成了这种算法的时间复杂度为O(m*n)。而KMP算法使得主串指针不必回溯而只需回溯模式串指针，并且模式串指针也不一定需要回溯到模式串的第一个字符，KMP算法的时间复杂度为O(m+n)。例如，当：T=“0000000000000000000000000000001”P=“000001”时，KMP算法比简单算法效率要高的多。,模式匹配的改进,32,改进算法是由D.E.Knuth,J.H.Morris,和V.R.Pratt同时发现的。,KMP字符串模式匹配算法,应该直接跳过第2趟，直接进行第3趟的t3和p1的比较。已知p1=t1，而p0p1那么p0t1由于p0=p2，所以t2=p0,33,改进算法是由D.E.Knuth,J.H.Morris,和V.R.Pratt同时发现的。,基本思想：,i,j,匹配失败!,KMP字符串模式匹配算法,34,比较到第i+1趟匹配时，如果比较到P中第j个字符时不匹配。即：,35,假设,ti+1ti+2.ti+j-1,由此，第i+2趟匹配可以跳过不做。,仅考察模式串,36,第i+3趟匹配是否需要进行呢？,假设模式串,假设,ti+2ti+3.ti+j-1,由此，第i+3趟匹配可以跳过不做。,37,依此类推，直到对于某值k，使得p0p1.pk pj-k-1pj-kpj-1而p0p1.pk-1=pj-kpj-k+1pj-1,38,假设主串为：t0t1.tn-1模式串为：p0p1.pm-1我们要解决的问题是：当“失配”(tipj)时，模式串“向右滑动”的可行距离有多远；或者说，下一步ti应该与模式串中的哪个字符比较?可以推断：答案将完全取决于模式串，而与主串无关因此：可以预先为模式串设定一个数组nextj，当“失配”(tipj)时，i不变，j改为nextj。,KMP字符串模式匹配算法,39,定义nextj如下：,例：,nextj=,Maxk|0kj且P0Pk-1=Pj-kPj-k+1Pj-1 当此集合不空时,0 其他情况,-1 当j=0时,KMP字符串模式匹配算法,40,KMP字符串模式匹配算法,41,42,设字符串S=aabaabaabaac，P=aabaac（1）给出S和P的next值；（2）若S作主串，P作模式串，试给出利用简单匹配算法和KMP算法的匹配过程。,实战:,P的next值为-1 0 1 0 1 2。,43,利用简单匹配算法的匹配过程：第一趟匹配：aabaabaabaac aabaac(i=5,j=5)第二趟匹配：aabaabaabaac aa(i=2,j=1)第三趟匹配：aabaabaabaac a(i=2,j=0)第四趟匹配：aabaabaabaac aabaac(i=8,j=5)第五趟匹配：aabaabaabaac aa(i=5,j=1)第六趟匹配：aabaabaabaac a(i=5,j=0)第七趟匹配：aabaabaabaac(成功)aabaac(i=12,j=6),44,利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac aabaac(i=5,j=5)nextj=next5=2第二趟匹配：aabaabaabaac(aa)baac(i=8,j=5)nextj=next5=2第三趟匹配：aabaabaabaac(成功)(aa)baac,45,S=“S0S1Sn-1”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：（1）将S的所有第奇数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第偶数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：S=ABCDEFGHIJKL则改造后的S为ACEGIKLJHFDB,实战1:,46,算法思路:对读入的字符串的第偶数个字符，直接放在数组前面，对第奇数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中,实战1:,47,48,如果字符串的一个串（其长度大于1）的各个字符均相等，则称之为等值子串。试设计一个算法：输入字符串S，以#作为结束标记，如果串S中不存在等值子串，则输出信息：“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：s=”xyz123xyz123#”，则输出：无等值子串；又如：若s=”xyzyyzxxxmmmmmzzzyy#”，则输出等值子串:mmmmm,实战2:,49,分析：此题主要考察字符串的查找操作。在查找过程中，对等值字符进行统计，由于字符串以#作为结束标记，则无须通过字符串的长度来判断字符是否遍历结束。求主串中最长的重复子串，该算法同样适用。,实战2:,50,51,实战3:,m个苹果放到n个盘子上(允许有空盘子)，问有多少种放法?,递归出口：没有苹果或者盘子剩下1个：1种,苹果数少于盘子数：去掉多余的盘子,苹果数多于盘子数:至少有一个盘子空着和 所有的盘子都有苹果(从每个盘子拿走一个苹果),52,实战3:,以下是该函数的程序段，请补充完整。intf(int m,int n)if(m=0|n=1)return;/没有苹果或者盘子剩下1个 if(mn)return;/苹果数少于盘子数，只需要相同的盘子数就足够了 return f(m,n-1)+f(m-n,);/苹果数多于盘子数,53,实战3:,以下是该函数的程序段，请补充完整。intf(int m,int n)if(m=0|n=1)return 1;/没有苹果或者盘子剩下1个 if(mn)return f(m,m);/苹果数少于盘子数，只需要相同的盘子数就足够了 return f(m,n-1)+f(m-n,n);/苹果数多于盘子数,54,本 讲 小 结,重点：1、串的基本概念 2、串类的实现 难点：1、串的模式匹配 2、串的应用,
