数据结构——串学生讲解反转课堂.pptx

《数据结构——串学生讲解反转课堂.pptx》由会员分享，可在线阅读，更多相关《数据结构——串学生讲解反转课堂.pptx（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、目录content03040201串及其运算串的存储结构及实现串的模式匹配实例分析第1页/共45页串的应用程序设计中的源程序、目标程序事物处理程序中，顾客姓名、地址、货物的产地、名称软件系统方面的字符编辑、情报检索、词法分析等多入侵检测系统 DNA序列检测 第2页/共45页串的定义 由零个或多个字符组成的有限序列，一般记作：S=a1a2a3an(1)S为串的名字(2)单引号括起来的字符序列为串的值将串值括起来的单引号本身不属于串，它的作用是避免串与常数或与标识符混淆123 123La La(3)ai(1in)可以是字母、数字或其他字符(4)n为串中字符的个数，称为串的长度特殊的线性表，数据元素

2、限制为字符集第3页/共45页(1)空串(2)空白串(3)子串(4)主串(7)位置(8)相等串(5)前缀子串、真前缀子串(6)后缀子串、真后缀子串(9)模式匹配长度为0的串，不包含任何字符仅由一个或多个空格组成的串，长度1是长度为0的空串 长度为1的空白串串中任意个连续字符组成的子序列包含子串的串空串？自身？B=datastructureA=dataC=data structure字符在串中的序号 子串在主串中的位置？两个串的长度相等 每个对应位置字符相等子串从主串的某一位置开始，其在主串中首次出现的位置ddadatadatadataatataD=structure主串：A=abcaabcaaa

3、bc 子串：B=bca 子串B在主串中，从第1个位置开始的位置是：子串B在主串中，从第2个位置开始的位置是：26第4页/共45页串的基本运算串的抽象数据类型定义：ADT String数据对象：数据关系：基本操作：ADT StringD=ai|aiCharacterSet，i=1,2,n,n0R=|ai-1,aiD，i=2,3,nStrAssign(S,chars)StrCopy(S,T)StrLength(S)StrInsert(S,pos,T)StrDelete(S,pos,len)StrCompare(S,T)StrCat(S,T)SubString(T,S,pos,len)StrInde

4、x(S,pos,T)StrReplace(S,T,V)StrEmpty(S)StrClear(S)StrDestory(S)这些串的基本操作通常以“串的整体”“串的一部分”作为操作对象第5页/共45页串的基本运算 对于以上串的基本操作，C语言的函数库文件 string.h 包括其中几个字符串操作函数：gets(S)输入字符串puts(S)输出字符串strcat(S1,S2)连接字符串S2至S1后strcmp(S1,S2)比较字符串S1和S2strcpy(S1,S2)复制字符串S2至S1strlen(S)求字符串S的有效长度第6页/共45页串的基本运算StrInsert(S,pos,T)例:S=

5、chater,T=rac,运行StrInsert(S,4,T)在字符串S的第pos个字符之前插入字符串T串S和串T存在，1posStrLength(S)+1操作结果：初始条件：结果：S=character第7页/共45页串的基本运算StrDelete(S,pos,len)例:S=chapter,运行StrDelete(S,5,3)从串S中删除从第pos个字符开始连续len个字符后形成的子串串S存在，1posStrLength(S)-len+1操作结果：初始条件：结果：S=chap第8页/共45页串的基本运算StrCat(S,T)例:S=man,运行StrCat(S,kind)将字符串T的值连接

6、在串S的后面串S和串T存在操作结果：初始条件：结果：S=mankind第9页/共45页串的基本运算SubString(T,S,pos,len)例:S=commander,运行SubString(T1,S,4,3)截取字符串S中从第pos个字符开始连续len个字符形成的子串，并赋值给串T串S存在，1posStrLength(S)且0lenStrLength(S)-pos+1操作结果：初始条件：结果：T1=man运行SubString(T2,S,5,0)运行SubString(T3,S,4,7)结果：T2=结果 T3无结果，函数返回错误第10页/共45页串的基本运算StrIndex(S,pos,T

7、)例:S=abcaabcaaabc,T=bca,运行StrInsert(S,1,T)若字符串S从第pos个字符后存在与字符串T相等的子串，则返回字符串T在串S中第pos个字符后首次出现的位置，否则返回0串S和串T存在，1posStrLength(S)操作结果：初始条件：结果：2运行StrInsert(S,4,T)结果：6第11页/共45页串的基本运算StrReplace(S,T,V)例:S=abcaabcaaabca,T=bca,若V=x运行StrReplace(S,T,V)用字符串V替换字符串S中出现的所有与串T相等的不重叠的子串串S和串V存在，且串T为非空串操作结果：初始条件：结果：S=a

8、xaxaax若V=bc运行StrReplace(S,T,V)结果：S=abcabcaabc第12页/共45页串的存储结构及实现1.定长顺序串2.堆串3.块链串 与线性表的顺序存储结构类似，使用一组地址连续的与线性表的顺序存储结构类似，使用一组地址连续的存储单元存储串的字符序列，也称为存储单元存储串的字符序列，也称为静态存储分配静态存储分配的顺的顺序串。直接使用序串。直接使用定长的字符数组定长的字符数组来定义。来定义。与定长顺序串类似，都是用一组地址连续的存储单元与定长顺序串类似，都是用一组地址连续的存储单元存储串的字符序列，存储串的字符序列，不同不同的是：其存储空间是的是：其存储空间是动态分配

9、动态分配的的 采用采用链式链式存储结构，链表的每个节点可存放一个或多存储结构，链表的每个节点可存放一个或多个字符，每个节点称为个字符，每个节点称为块块第13页/共45页串的存储结构及实现定长顺序串#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;存储结构截断 串的实际长度在预定义长度MAXLEN的范围内随意变动时，超过MAXLEN，串值被舍去的情况字符串长度 0 或者 len ，此时0号单元格不用第14页/共45页串的存储结构及实现定长顺序串串插入函数Case 1 插入后串长MAXLEN 在进行串的插入时，插入位置

10、pos将位置分为两部分，记为A、B,长度分别为LA、LB，记插入部分为T,长度为LTCase 2 插入后串长MAXLEN，且pos+LTMAXLENCase 3 插入后串长MAXLEN，且pos+LTMAXLEN第15页/共45页串的存储结构及实现定长顺序串串插入函数int SStrInsrt (SString *S ,int pos ,const SString T)int i ;if(NULL=S|NULL=S-ch|NULL=T.ch|pos S-len+1)return 0 ;return 1;if(S-len+T.lenlen+T.len;i pos+T.len;i-)S-chi=S

11、-chi-T.len;for(i=pos;i chi=T.chi-pos+1;S-len=S-len+T.len;else if(pos+T.lenMAXLEN;i pos+T.len;i-)S-chi=S-chi-T.len;for(i=pos;i chi=T.chi-pos+1;S-len=MAXLEN;else for(i=pos;ichi=T.chi-pos+1;S-len=MAXLEN;#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;第16页/共45页串的存储结构及实现定长顺序串串删除函数int SSt

12、rDelete (SString *S ,int pos ,int len)int i=1;if(NULL=S|NULL=S-ch|len 0|pos S-len-len+1)return 0 ;return 1;for(i=pos;ilen-len;i+)S-chi=S-chi+len;S-len=S-len-len;#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;第17页/共45页串的存储结构及实现定长顺序串串连接函数Case 1 连接后串长MAXLEN 在进行串的连接时，假设原始串为S,长度为LS，待连接串

13、为T,长度为LTCase 2 连接后串长MAXLEN，且LAch|NULL=T.ch)return 0 ;else return 0;if(S-len+T.lenlen+1;ilen+T.len;i+)S-chi=T.chi-S-len;S-len=S-len+T.len;return 1;else if(S-lenlen+1;ichi=S-chi-S-len;S-len=MAXLEN;return 0;#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;第19页/共45页串的存储结构及实现定长顺序串求子串函数int

14、 SubSString (SString *T,SString S ,int pos ,int len)int i=1;if(NULL=T|NULL=T-ch|len 0|pos S-len|NULL=S.ch|lenS.len pos+1)return 0 ;for(i=1;ichi=S.chpos+i-1;T-len=len;return 1;弊端：截断问题第20页/共45页串的存储结构及实现堆串 不限定串的最大长度，动态地分配串值的存储空间，只要存储空间能分配成功，则在操作的过程中就不会出现“截断”的情况。存储结构：typedef struct char *ch;int len;HStr

15、ing;串初始化函数：void HStrInt(HString*S)S-ch=NULL;S-len=0;第21页/共45页串的存储结构及实现堆串串赋值函数：typedef struct char *ch;int len;HString;int HStrAssign(HString*S,const char*chars)int i=0;if(NULL=chars|NULL=S)return 0;while(charsi!=0)i+;S-len=i;if(0!=S-len)if(S-ch!=NULL)free(S-ch);S-ch=(char*)malloc(S-len+1)*sizeof(cha

16、r);if(NULL=S-ch)return 0;for(i=1;ilen;i+)S-chi=charsi-1;else S-ch=NULL;return 1;第22页/共45页串的存储结构及实现堆串 typedef struct char *ch;int len;HString;串插入函数：int HStrInsert(HString*S,int pos,const HString T)int i;char*temp;if(NULL=S|NULL=S-ch|NULL=T.ch|posS-len|poslen+T.len+1)*sizeof(char);if(NULL=temp)return

17、0;for(i=1;ichi;for(i=pos;ipos+T.len;i+)tempi=T.chi-pos+1;for(i=pos+T.len;ilen+T.len;i+)tempi=S-chi-T.len;free(S-ch);S-ch=temp;S-len=S-len+T.len;return 1;第23页/共45页串的存储结构及实现堆串 typedef struct char *ch;int len;HString;串删除函数：int HStrDelete(HString*S,int pos,int len)int i;char*temp;if(NULL=S|NULL=S-ch|len

18、0|posS-len-len+1)return 0;temp=(char*)malloc(S-len-len+1)*sizeof(char);if(NULL=temp)return 0;for(i=1;ichi;for(i=pos;ilen-len;i+)tempi=S-chi+len;free(S-ch);S-ch=temp;S-len=S-len-len;return 1;第24页/共45页串的存储结构及实现堆串 typedef struct char *ch;int len;HString;串连接函数：int HStrCat(HString*S,const HString T)int i

19、=1;if(NULL=S|NULL=S-ch|NULL=T.ch)return 0;S-ch=(char*)realloc(S-ch,(S-len+T.len+1)*sizeof(char);if(NULL=S-ch)return 0;for(i=S-len+1;ilen;i+)S-chi=T.chi-S-len;S-len=S-len+T.len;return 1;第25页/共45页串的存储结构及实现堆串 typedef struct char *ch;int len;HString;求子串函数：int SubHString(HString*THString S,int pos,int le

20、n)int i=1;if(NULL=T|NULL=T-ch|NULL=S.ch|lenS.len-pos+1|posS.le)return 0;T-len=len;if(NULL!=T-ch)free(T-ch);T-ch=(char*)malloc(T-len+1)*sizeof(char);if(NULL=T-ch)return 0;for(i=1;ilen;i+)T-chi=S.chpos+i-1;return 1;第26页/共45页串的存储结构及实现块链串块链的存储结构#define BLOCK_SIZE 4typedef struct block char chBLOCK_SIZE;

21、struct block*next;Block;typedef structBlock*head;Block*tail;int len;LString;因需要连接字符串，设置尾指针可便于操作，注意连接时需要处理第一个串的最后一个结点中的无效字符块大小，指块链表中结点存放字符的个数。在这种存储方式中，块大小直接影响到串处理的效率，因此就需要考虑串值的存储密度。第27页/共45页串的存储结构及实现块链串存储密度=串值所占的存储位实际分配的存储位当BLOCK_SIZE1：当BLOCK_SIZE=1：此时块链表结构同线性链表其存储密度为 1/3由于串长不一定是块大小的整数倍，则链表的最后一个结点不一定

22、完全被串值所占满，此时需补上#或其他字符块大小为4的块链表，其存储密度为1/2ABCDI#EFGHheadtail第28页/共45页串的模式匹配定义：找字串在主串中从第pos个字符后首次出现的位置应用：文本编辑软件中的查找电子字典中查阅英文单词S a c a b a b a a c b a b a aT a b a a从S的第1个字符开始，T首次出现的位置为：从S的第7个字符开始，T首次出现的位置为：511第29页/共45页串的模式匹配算法：BF模式匹配算法KMP模式匹配算法目标串：主串S模式串：子串Ta c a b a b a a c b a ba b a a第30页/共45页串的模式匹配B

23、F算法Brute-Force 算法，蛮力匹配算法a c a b a b a a c b a ba b a a第一趟匹配第一趟匹配第二趟匹配第二趟匹配第三趟匹配第三趟匹配第四趟匹配第四趟匹配第五趟匹配第五趟匹配a c a b a b a a c b a b a b a a a c a b a b a a c b a b a b a aa c a b a b a a c b a b a b a aa c a b a b a a c b a b a b a ai=1j=1i=2j=2i=2i=3i=6i=4i=9i=5j=1j=1j=1j=4j=1j=5字符相等i+;j+;字符不相等 j=1;i 回

24、溯 i=2-2+2 i=2-1+2 i=6-4+2 i=4-1+2 匹配成功的条件 规律：i=i-j+2 jT.len,返回i-T.len第31页/共45页串的模式匹配BF算法int Index(SString S，int pos,SString T)int i=pos,j=1;while(i=S.len&j T.len)return i-T.len;else return 0;else i=i-j+2;j=1;BF算法的时间复杂度第32页/共45页串的模式匹配KMP模式匹配算法由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的改进算法KMP算法与BF算法的不同之处：消除

25、 主串S的指针 回溯a b a b c a b c a c b a ba b c a c第一趟匹配第一趟匹配i=1j=3第二趟匹配第二趟匹配第三趟匹配第三趟匹配a b a b c a b c a c b a b a b c a ca b a b c a b c a c b a b a b c a ci=3i=3i=7i=11i=7j=1j=1j=2j=5j=6第33页/共45页串的模式匹配KMP模式匹配算法S=S1S2 Si-j+1S i-j+2 Si-k+1 Si-1 Si SnT=T1 T2 Tj-k+1 Tj-1 Tj T=T1 Tk-1Tk 0 当当j=1nextj=Max1kj且且T

26、1 Tk-1=T j-k+1 Tj-1 当此集合不为空时当此集合不为空时 1 其他情况其他情况第34页/共45页串的模式匹配KMP模式匹配算法模式串模式串abaabcac的的next值推导过程值推导过程当j=1时，next1=0当j=2时，next2=1j值子串真前缀子串真后缀子串结果 3 ab 串不等串不等 a b ab 串不等串不等 a a ba aba 串长度为串长度为14 j12345678 串abaabcacnextj011221 235子串长度为1串不等ab串不等abaabaabaaaaaa子串长度为2串不等ababaaabaab6baabab串不等aababaabaabc7aba

27、abbaabc串不等abaaaabc串不等abaabc串不等abbc串不等串不等ac8abaabcaabaabcabaabbaabcaaabcaabaaabcaababcaabcaaa串不等串不等串不等串不等子串长度为1串不等继而讨论如何用算法求已知模式串next函数值：第35页/共45页串的模式匹配KMP模式匹配算法T=T1 Tk-1 Tk T=T=T1 Tj-k+1 Tj-1 Tj Tm=(1)nextj+1 =k+1=nextj+1Tj-k,+1 Tj-1 Tj TmTj-k,+1 Tk-1 Tk T1 Tk,-1 Tk,=nextk (2)若若Tj=Tk,则则nextj =k+1=ne

28、xtk+1 若若Tj Tk,则继续比较则继续比较Tj和和Tnextk，即比较，即比较Tj和和Tnextnextk 然后一直重复下去，若直到最后然后一直重复下去，若直到最后j=0时都一直比较不时都一直比较不成功，则成功，则nextj=1 .第36页/共45页串的模式匹配KMP模式匹配算法void Get_Next(SString T，int next)int j=1,k=0;next 1=0;while(j=T.len)if (k=0|T.ch j=T.chk)+j;+k;nextj=k;else k=next k;第37页/共45页串的模式匹配KMP模式匹配算法a c a b a a b a

29、a b c a c a a b ca b a a b c a c 第一趟匹配第一趟匹配i=1j=2第二趟匹配第二趟匹配第三趟匹配第三趟匹配i=2i=2i=8i=14i=8j=1j=1j=3j=1j=9在求得模式串的next函数之后，匹配可按如下方式进行 j12345678 串abaabcacnextj01122312a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a

30、 b c a c 第四趟匹配第四趟匹配next2=1next1=0next6=3j=6i=3第38页/共45页串的模式匹配KMP模式匹配算法int Index_KMP(SString S，int pos,SString T)int i=pos,j=1;while(i=S.len&j T.len)return i T.len;else return 0;KMP算法的时间复杂度O(n+m)第39页/共45页串的模式匹配KMP模式匹配算法a a a b a a a a b a a a a b 第一趟匹配第一趟匹配i=1j=4第二趟匹配第二趟匹配第三趟匹配第三趟匹配i=4i=4i=5i=10i=4j=

31、1j=3j=1j=2j=1但是上述定义的next函数在某些情况下是有缺陷的：j12345 串aaaabnextj01234a a a b a a a a b a a a a b a a a b a a a a b a a a a b a a a b a a a a b a a a a b 第四趟匹配第四趟匹配next4=3next3=2next2=1j=6i=4next1=0a a a b a a a a b a a a a b 第五趟匹配第五趟匹配第40页/共45页串的模式匹配KMP模式匹配算法a a a b a a a a b a a a a b 第一趟匹配第一趟匹配j=4i=1j=1j=

32、6a a a b a a a a b a a a a b 第二趟匹配第二趟匹配i=4i=5i=10j=1T=T1 Tk-1 Tk T=T=T1 Tj-k+1 Tj-k,+1 Tj-1 Tj TmTj-k,+1 Tk-1 Tk T1 Tk,-1 Tk,=nextk=nextvalj=nextjnextvalj=nextvalnextj j12345 串aaaabnextj01234nextvalj00004第41页/共45页串的模式匹配KMP模式匹配算法int Get_Nextval(SString T,int next,int nextval)int j=2,k=0;Get_Next(T,next);nextval 1=0;if (T.chj=T.chk)nextvalj=nextvalk;elsenextvalj=nextj;while(j=T.len)j+;第42页/共45页实例分析简单文本编辑器软件页、行、字符typedef struct WHString char*ch;int len;struct WHString*next;struct WHString*pre;int row;WHString;输入、统计、查找、删除、插入第43页/共45页Thanks.Made by W_L第44页/共45页感谢您的观看！第45页/共45页