数据结构(C++)串.ppt

《数据结构(C++)串.ppt》由会员分享，可在线阅读，更多相关《数据结构(C++)串.ppt（54页珍藏版）》请在优知文库上搜索。

1、 算法题（本题算法题（本题12分）分） 假设以假设以I和和O分别表示入栈和出栈操作，栈的初分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表态和终态均为空，入栈和出栈的操作序列可表示为仅由示为仅由I和和O组成的序列。称可以操作的序列组成的序列。称可以操作的序列为合法序列，否则称为非法序列。为合法序列，否则称为非法序列。 1.下面所示的序列中哪些是合法的？下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO 2.通过对问题通过对问题1的分析，写出一个算法判定给所给的操的分析，写出一个算法判定给所给的操作序列是否

2、合法。若合法则返回作序列是否合法。若合法则返回true，否则返回，否则返回false。（假定被判定的操作序列已存入一维数组中。）（假定被判定的操作序列已存入一维数组中。）#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、定义 二、串类的实现二、串类的实现 三、三、串的模式匹配串的模式匹配 四、一些应用四、一些应用难点难点 串是零个或多个字符组成的有限序列。串是零个或多个字符组成的有限序列。 一般记作一般记作S=“ a0a1a2an-1 “ (n=0) ai(0in-1)可以是字母、数字或其它字符；可以是字母、数字或其它字符； 串的应用非常广泛，许多高级语言中都把串的作为基串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的货物的名称、产地可作为字符串处理，文本文件中的每一行字符等

4、也可作为字符串处理。串可以看成字符每一行字符等也可作为字符串处理。串可以看成字符类型的顺序表。类型的顺序表。 例：例：（1）a = “This is a string”（2）b = “string” （3）c = “ ” （4）d = “”（5）e = “你好你好”说明：说明：（1）串中包含的字符个数，称为串的长度。）串中包含的字符个数，称为串的长度。 长度为长度为0的的串称为空串，它不包括任何字符串称为空串，它不包括任何字符;（2）串中所包含的字符可以是字母、数字或其他字符，）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。这依赖于具体计算机所允许的字符集。空空

5、 串串n=0的串的串子子 串串串中若干相邻字符组成的子序列串中若干相邻字符组成的子序列主主 串串包含子串的串包含子串的串空格串空格串仅含有空格字符的串仅含有空格字符的串(n不为不为0)串相等串相等设设 s1=a11,an1 s2=a12,an2 若若 n1=n2且且ai1=ai2（1in1) 则则 s1=s2 术语：术语：串的基本操作串的基本操作串的基本操作串的基本操作串的基本操作串的基本操作 原始的原始的C风格的串，容易出问题。风格的串，容易出问题。 char *s; 在在C+在头文件在头文件string中已含了一种安全的字中已含了一种安全的字符串实现，但由于这个库没有包含在一些较老符串实现

6、，但由于这个库没有包含在一些较老的的C+编译器中，因此本节将设计自已的安全编译器中，因此本节将设计自已的安全的的String类，使用面向对象技术来克服类，使用面向对象技术来克服C风格风格的串中存在的问题。的串中存在的问题。串类的实现串类的实现串相关操作串相关操作串构造函数串构造函数(1)(1)串构造函数串构造函数(2)(2)String:String(LinkList ©)/ 操作结果：从线性表转换构造新串操作结果：从线性表转换构造新串转换构造函数转换构造函数length = copy.Length();/ 串长串长strVal = new charlength + 1;/ 分配存储空

7、间分配存储空间 for (int i = 0; i m，故上述的时间复杂度为，故上述的时间复杂度为O(mn)2/ )2+(=)1+/(=)(1+1=1+1=mnmimnmmiPmnimnii简单匹配算法缺点在于每次不能匹配以后主串（目标简单匹配算法缺点在于每次不能匹配以后主串（目标串）指针和子串（模式串）指针都必须回溯，造成了串）指针和子串（模式串）指针都必须回溯，造成了这种算法的时间复杂度为这种算法的时间复杂度为O(m*n)。而而KMP算法使得主串指针不必回溯而只需回溯模式串算法使得主串指针不必回溯而只需回溯模式串指针，并且模式串指针也不一定需要回溯到模式串的指针，并且模式串指针也不一定需要

8、回溯到模式串的第一个字符，第一个字符，KMP算法的时间复杂度为算法的时间复杂度为O(m+n)。例如，当：例如，当：T=“0000000000000000000000000000001”P=“000001”时，时，KMP算法算法比简单算法效率要高的多。比简单算法效率要高的多。 改进算法是由改进算法是由D.E. Knuth, J.H.Morris, 和和V.R. Pratt同时发现的。同时发现的。KMP字符串模式匹配算法字符串模式匹配算法第第1趟匹配趟匹配 T a b a a b a b P a b a b | | |第第2趟匹配趟匹配 T a b a a b a b P a b a b |第第3

9、趟匹配趟匹配 T a b a a b a b P a b a b |应该直接跳过第应该直接跳过第2趟，趟，直接进行第直接进行第3趟的趟的t3和和p1的比较。的比较。已知已知p1=t1，而，而p0p1那么那么p0t1由于由于p0=p2，所以，所以t2=p0 改进算法是由改进算法是由D.E. Knuth, J.H.Morris, 和和V.R. Pratt同时发现的。同时发现的。基本思想：基本思想：abadabd?0taba0pdabcacbabapdabij匹配失败匹配失败! !KMP字符串模式匹配算法字符串模式匹配算法 比较到第比较到第i+1趟匹配时，如果比较到趟匹配时，如果比较到P中第中第j个

10、字个字符时不匹配。即：符时不匹配。即：tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpjtpti+1ti+2 . ti+j ti+mp0p1 . pj-1 pm-1第第i+2趟趟若匹配成功若匹配成功tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpjpp0p1 .pj-2p1p2 . pj-1p假设假设ti+1ti+2 .ti+j-1 由此，第由此，第i+2趟匹配可以跳过不做。趟匹配可以跳过不做。仅考察仅考察模式串模式串 第第i+3趟匹配是否需要进行呢？趟匹配是否需要进行呢？tpi+jtiti+1 . ti+j-1j

11、p0p1 . pj-1第第i+1趟趟ti+jpj假设假设模式串模式串pp0p1 .pj-3p2p3.pj-1p假设假设ti+2ti+3 .ti+j-1 由此，第由此，第i+3趟匹配可以跳过不做。趟匹配可以跳过不做。 依此类推，直到对于某值依此类推，直到对于某值k，使得，使得p0p1.pk pj-k-1pj-kpj-1 而而p0p1.pk-1 = pj-kpj-k+1pj-1ti+jtiti+1.ti+j-1pp0p1.pkk+1jpj-k-1pj-k.pj-1p0p1.pk-1pj-kpj-k+1.pj-1=pki+j假设主串为：假设主串为： t0t1.tn-1模式串为：模式串为： p0p1.

12、pm-1我们要解决的问题是：当我们要解决的问题是：当“失配失配”(ti pj)时，模式串时，模式串“向右滑动向右滑动”的可行距离有多远；或者说，下一步的可行距离有多远；或者说，下一步ti应应该与模式串中的哪个字符比较该与模式串中的哪个字符比较?可以推断：答案将完全取决于模式串，而与主串无关可以推断：答案将完全取决于模式串，而与主串无关因此：可以预先为模式串设定一个数组因此：可以预先为模式串设定一个数组nextj，当，当“失配失配”(ti pj)时，时，i不变，不变，j改为改为nextj。KMP字符串模式匹配算法字符串模式匹配算法j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6

13、 7 模式串模式串nextjnextj a b a a b c a c a b a a b c a c -1 0 0 1 1 2 0 1 -1 0 0 1 1 2 0 1nextj=Maxk|0kj且且P0Pk-1=Pj-kPj-k+1Pj-1 当此集合不空时当此集合不空时0 其他情况其他情况-1 当当j=0时时KMP字符串模式匹配算法字符串模式匹配算法int KMPIndexHelp(const String &T, const String &P, int pos, int next ) int i=pos, j=0; while( i T.Length() & j P.Length()

14、if ( j = -1 ) i+; j=0; else if( Pj = Ti ) i+; j+; else j = nextj; if ( js; /读入字符串读入字符串 i=0; j=0; k=0; while(si) /改造字符串改造字符串 if(i%2=1) stkk+=si; else sj+=si; i+; while(i0) sj+ = stk-k /将第偶数个字符填入原将第偶数个字符填入原字符数组字符数组如果字符串的一个串（其长度大于如果字符串的一个串（其长度大于1）的各个字符均）的各个字符均相等，则称之为等值子串。试设计一个算法：输入字符相等，则称之为等值子串。试设计一个算法

15、：输入字符串串S，以，以#作为结束标记，如果串作为结束标记，如果串S中不存在等值子串，中不存在等值子串，则输出信息：则输出信息：“无等值子串无等值子串”，否则求出（输出）一个，否则求出（输出）一个长度最大的等值子串。长度最大的等值子串。例如：例如：s=”xyz123xyz123#”，则输出：无等值子串；，则输出：无等值子串；又如：若又如：若s=”xyzyyzxxxmmmmmzzzyy#”，则输出，则输出等值子串等值子串:mmmmm实战实战2: 分析：此题主要考察字符串的查找操作。在查找分析：此题主要考察字符串的查找操作。在查找过程中，对等值字符进行统计，由于字符串以过程中，对等值字符进行统计，

16、由于字符串以#作为作为结束标记，则无须通过字符串的长度来判断字符是否遍结束标记，则无须通过字符串的长度来判断字符是否遍历结束。求主串中最长的重复子串，该算法同样适用。历结束。求主串中最长的重复子串，该算法同样适用。实战实战2:void MaxEqSubstr(String &s, String &t) int max=0,index=0; /index记最长的串在记最长的串在s串中的开串中的开始位置，始位置，max记其长度记其长度 int i=0,start=0, length=1; /length记局部重复子串长度记局部重复子串长度 int n=s.Length(); while(in-1)if( si = si+1 ) length+; i+; continue;else if(maxlength) index=start; / 起始位置起始位置 max=length; / 长度长度 i+;start=i; length=1;t=SubString(s,index,max); / 求子串函数求子串函数 实战实战3:m个苹果放到个苹果放到n个盘子上个盘子上(允许有空盘允许有空盘子子)