《数据结构 C++版 普通高等教育十一五 国家级规划教材 教学课件 ppt 杨秀金 第4章 串-2》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育十一五 国家级规划教材 教学课件 ppt 杨秀金 第4章 串-2（24页珍藏版）》请在金锄头文库上搜索。
1、1,数据结构,第4章 串 第2讲,2,本章分为（2）讲,第1讲 4.1 串的基本概念 4.2 串的存储表示 4.3 串类及实现- 4.3.1,第2讲 4.3 串类及实现-4.3.2 4.4 串的模式匹配,供教师参考,3,4.3.1 串的类定义,class String private: char *str; /串的动态数组 int size; /串实际长度 public: String(); /构造函数，初始化空串 String(char *chx); /构造函数，生成非空串 String() /析构函数 void Creat( ) ; void Display( )； /接下页,回顾,4,4
2、.3.1 串的类定义,/接前页 int Length() return size; /求当前串长度 String SubString(int pos,int num); /求子串 void Insert(String s,int pos); /插入运算 void Delete(int pos,int num); /删除运算 String operator+(String s); /串加法运算 int Find(String T,int pos); /查找子串(模式匹配) ; /串类定义结束,回顾,5,4.3.2 串基本运算的实现,串的基本运算主要有：求子串、插入、删除、串连接等。下面给出的是重
3、要的串运算算法的函数。 在串的各种运算中常常用到“字符位置”这个参数pos。这里约定，用户角度看位置pos从1开始，到了函数代码中pos值认为从0（零）开始，用户的pos值做自减处理。,6,1求子串-算法4.1,求子串是指从当前串(主串)的pos位置起，复制出num个字符到所求子串对象中去，函数返回的就是一个子串对象。 String String:SubString(int pos,int num) String tp; pos-; if(pos = size | num = 0 ) return tp; /位置pos错或子串长num小于等于0，返回空串 int left=size-pos+1
4、; /计算当前串（主串）从pos开始的剩余字符数,7,1求子串 算法4.1 续,if(numleft) num=left; /子串长度大于剩余部分，子串长度取left值 delete tp.str; /释放原先存储空间 tp.str=new charnum+1; /重新申请存放子串的空间 for (int i=0, j=pos; inum; i+, j+) tp.stri = strj; /传送字符数组 tp.strnum =0; /子串结束标志 tp.size=num; /确定子串长度 return tp; /算法结束,8,2串的插入-算法4.2,在当前串(主串)的pos位置，插入子串s。插
5、入后的新串值仍在当前串中。 void String:Insert(String s,int pos) char *x=“ “; pos-; if(possize) cout“n pos 位置错误“; else int size0=size+s.size; /计算新的串长 strcpy(x,str); /x暂存主串原内容 delete str; /释放原先存储空间 str=new charsize0+1; /重新分配存储空间 strcpy(str,x); /恢复主串内容,9,2串的插入-算法4.2续,for (int i=size; i=pos; i-)stri+s.size=stri; /字符
6、逐个向后移，跳过s.size个 for(int j=0; js.size; j+) strj+pos=s.strj; /子串字符逐个插入 size=size0; /新的串长 strsize= 0; /新的串结束标志 /else /算法结束,10,3串的删除 算法4.3,在当前串(主串)的pos位置，删除num个字符。 void String: Delete(int pos,int num) pos-; if(pos=size) coutsize) size=pos; /删除长度超出主串，截尾 else for (int i=pos+num;isize; i+) stri-num=stri; /
7、字符逐个前移，跳过num个 size=size-num; /设置删除后的新串长 strsize= 0; /else /算法结束,11,3串的删除 算法4.3,除上述3种串的基本运算外，查找子串(模式匹配)函数int Find()在下一节详细讨论，串连接等留给读者自行练习。,12,4.4 串的模式匹配,当今世界人们几乎离不开网络，人们常在网上搜索和查找自己所需要的信息。网络的自动搜索过程，就用到了字符串匹配技术。本节介绍的串的模式匹配算法，实质上仅是串的精确搜索和查找。网站搜索技术远不止这些，有些技术还在研究探索之中。,13,4.4 串的模式匹配,串的模式匹配设，有两个字符串S和T，设S为主串，
8、也称为正文串；设T为子串，也称为模式。 在主串S中查找与子串T（模式）相匹配（相同）的子串，如果匹配成功，确定模式串T的第一个字符在主串S中出现的位置。称查找模式T在主串S中的匹配位置的运算为模式匹配。,14,4.4 串的模式匹配,在主串S中搜索的起始位置（pos）的有多种不同情况： 要求从主串的开头开始搜索，此时pos=1； 取pos为其他值，设pos=6，则从主串S的第6个字符开始匹配搜索。 模式匹配算法要求预先指定搜索的起始位置pos。算法从主串S的第pos个字符开始查找，找到一个与T相同的子串，则函数返回模式T的第一个字符在串S中出现的位置；否则函数返回1。,15,4.4.1 朴素模式
9、匹配,朴素模式匹配算法的主要思想是：从主串S的第pos个字符起和模式T的第一个字符进行比较， 若相等则继续比较S和T的后续字符； 否则从主串S的第pos+1个字符起再重新和模式T的第一个字符进行比较。 依此类推，直至模式T和主串S的一个子串完全相等，则称匹配成功，否则称匹配失败。,16,4.4.1 朴素模式匹配,在算法中主串就是类自身的数据成员，所以主串正文串S并不出现在函数中。子串对象T和初始位置pos是已知条件，做函数的形参。该函数就是4.3节串类String的成员函数。,17,朴素模式匹配算法具体匹配过程如图所示：,18,4.4.1 朴素模式匹配-算法4.4,int String:Fin
10、d(String T,int pos) pos-; /转为C+与下标 if(size=0|T.size=0) return -1; int i=pos, j=0; /i指向主串，j指向子串T首字符位置 while(i=size-1 /j恢复到子串T的首字符位置 ,19,4.4.1 朴素模式匹配-算法4.4,int String:Find(String T,int pos) /. while(i=size-1 /i在主串上移动到尾，仍找不到 ,20,应用模式匹算法：,设计一个算法search(t)，查找当前字符串(主串) 中有无子串t，输出共有几个子串t ，以及它们的位置。 viod Strin
11、g: search(String T) int n,pos,numb=0; for(pos=1;possize;pos+) n=Find(T,pos); /调用模式匹配算法 if(n!=-1) numb+; /匹配成功 cout“n “n; /输出T位置 cout“n number=“numb; /输出T出现几次 ,21,4.4.2 KMP模式匹配,教师自行处理本节内容，可不讲。建议，简短介绍一下串的模式匹配方法不唯一。方法的难度不同，时间复杂度不同。 提倡学生自己阅读。 综合两个算法，可以得出整个KMP算法的时间复杂度为O(n+m)。在大多数情况下，这个时间复杂度比简单的匹配算法的O(n*m
12、)要小得多。,教师自选,22,小 结,通过本章学习，了解串在内存中有顺序存储和链式存储两种结构。 在大多数程序设计语言中，串的存储和基本操作的实现都采用顺序存储。本章介绍的串类，就是基于堆分配存储，即动态顺序存储表示。,23,小 结,要求熟练掌握串的基本运算的算法在串类中的实现，如求子串、串插入、删除等。能够自行设计简单算法，能够应用基本算法。 给定主串S和模式T，在主串S中寻找模式T的过程称为模式匹配。要求基本掌握朴素模式匹配算法，并且在实际中加以应用。 了解KMP算法是改进的串匹配算法。了解两种模式匹配算法的不同的时间复杂度。,24,除了讲解逐步安装操作系统的过程外，本章还介绍了通过Virtual PC虚拟机安装Red Hat Linux系统的方法。同时还讨论了如何从Windows系统中卸载掉Red Hat Linux。,
