串的抽象数据类型的定义优秀PPT.ppt

《串的抽象数据类型的定义优秀PPT.ppt》由会员分享，可在线阅读，更多相关《串的抽象数据类型的定义优秀PPT.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 串的抽象数据类型的定义串的抽象数据类型的定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法4.1 串的抽象数据类型的定义如下串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对双引号相列，由一对双引号相括，如括，如:a string 基本操作基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)S

2、trCompare(S,T)StrLength(S)Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String StrAssign(&T,chars)初始条件：chars 是字符串常量。操作结果：把 chars 赋为 T 的值。StrCopy(&T,S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。DestroyString(&S)初始条件：串 S 存在。操作结果：串 S

3、被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若 S 为空串，则返回 true，否则返回 false。表示空串，空串的长度为零。StrCompare(S,T)初始条件：初始条件：串 S 和 T 存在。操作结果：操作结果：若S T，则返回值 0；若S T，则返回值 0；若S T，则返回值 0。例如：例如：StrCompare(data ,state )0 StrLength(S)初始条件：串 S 存在。操作结果：返回 S 的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如：

4、Concat(T,man,kind)求得 T=mankind SubString(&Sub,S,pos,len)初始条件：操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。串 S 存在，1posStrLength(S)且 0lenStrLength(S)-pos+1。例如：例如：SubString(sub,commander,4,3)子串为子串为“串串”中的一个字符子序列中的一个字符子序列求得 sub=man ;SubString(sub,commander ,1,9)SubString(sub,commander,9,1)求得 sub=r 求得 sub=com

5、mander SubString(sub,commander,4,7)sub=?SubString(sub,beijing ,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串 Index(S,T,pos)初始初始条件：条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：操作结果：若主串 S 中存在和串 T 值相同 的子串,则返回它在主串 S 中第pos个 字符之后第一次出现的位置;否则函数值为0。假设 S=abcaabcaaabc,T

6、=bca Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。Replace(&S,T,V)初始条件：串S,T和 V 均已存在，且 T 是非空串。操作结果：用 V 替换主串 S 中出现 的全部与（模式串）T 相等的不重叠的子串。例如：假设 S=abcaabcaaabca,T=bca 若 V=x,则经置换后得到 S=axaxaax 若 V=bc,则经置换后得到 S=abcabcaabcbca bca bca StrInsert(&S,pos,T)初始条件：串S和T存在，1pos

7、StrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：S=chater，T=rac，则执行 StrInsert(S,4,T)之后得到 S=character StrDelete(&S,pos,len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。思索题：设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为_ 对于串的基本操作集可以有不同的定义方法，在运用高级程

8、序设计语言中的串类型时，应以该语言的参考手册为准。strlenstrlen(str)求串长函数；strcpy strcpy(str1,str2)串复制函数；strcatstrcat(str1,str2)串联接函数；strcmpstrcmp(str1,str2)串比较函数；strchrstrchr(str,ch)串定位函数；strrchrstrrchr(str，ch)串右定位函数；例：C+串库（string.h）中常见串函数：串赋值串赋值StrAssign、串比较、串比较StrCompare、求串长求串长StrLength、串联接、串联接Concat以及以及 求子串求子串SubString 等五

9、种操作构成串类型等五种操作构成串类型的最小操作子集的最小操作子集。在上述抽象数据类型定义的13种操作中，即：这些操作不行能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。例如，可利用串比较、求串长和求子串等操作实现定位函数 Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T),T)S 串 T 串 T 串iposn-m+1算法的基本思想为：算法的基本思想为：?0int Index(String S,String T,int pos)/T为非空串。若主串S中第

10、pos个字符之后存在与 T相等的子串，/则返回第一个这样的子串在S中的 位置，否则返回0 if(pos 0)/if return 0;/S中不存在与T相等的子串/Indexn=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)/whileSubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;又如串的置换函数：S 串 T 串 V 串 V 串pospos subinews 串sub=i+mposn-pos+1void replace(String&S,String T,String

11、V)while(pos=n-m+1&i)i=Index(S,T,pos);if(i!=0)SubString(sub,S,pos,i-pos);/不置换子串 Concat(news,news,sub,V);pos=i+m;/if/whileSubString(sub,S,pos,n-pos+1);/剩余串Concat(S,news,sub);n=StrLength(S);m=StrLength(T);pos=1;StrAssign(news,NullStr);i=1;串的逻辑结构和线性表极为相像，区分仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别

12、。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。在程序设计语言中，串只是 作为输入或输出的常量出现，则只 需存储此串的串值，即字符序列即 可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2 串的表示和实现串的表示和实现一、串的定长依次存储表示一、串的定长依次存储表示二、串的堆支配存储表示二、串的堆支配存储表示三、串的块链存储表示三、串的块链存储表示#define MAXSTRLEN 255 /用户可在255以内定义最大串长 typedef unsigned char SString MAXSTRLEN+1;/0号单元存放串的长

13、度一、串的定长依次存储表示一、串的定长依次存储表示 按这种串的表示方法实现的串的运算时，其基本操作为“字符序列字符序列的复制的复制”串串的实际长度在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断截断”特点特点:Status Concat(SString S1,SString S2,SString&T)/用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。return uncut;/Concat例如：串的联接算法中需分三种状况处理：例如：串的联接算法中需分三种状况处理：T1.S10=S11.S10;TS10+1.S10+S20=S21.S20

14、;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSTRSIZE)/截断 else /截断(仅取S1)T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;typedef struct char*ch;/若是非空串，则按串好用长度支配若是非空串，则按串好用长度支配 /存储区，否则存储区，否则 ch 为为NULL

15、int length;/串长度串长度 HString;二、串的堆支配存储表示二、串的堆支配存储表示 通常，C语言中供应的串类型就是以这种存储方式实现的。系统利用函数malloc()和 free()进行串值空间的动态管理，为每一个新产生的串支配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为:先为新生成的串支配一个存储空间，然后 进行串值的复制。Status Concat(HString&T,HString S1,HString S2)/用T返回由S1和S2联接而成的新串 if(T.ch)delete(T.ch);/释放旧空间

16、if(!(T.ch=new charS1.length+S2.length)exit(OVERFLOW);T.ch0.S1.length-1=S1.ch0.S1.length-1;T.length=S1.length+S2.length;T.chS1.length.T.length-1=S2.ch0.S2.length-1;return OK;/Concat Status SubString(HString&Sub,HString S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的子串 if(pos S.length|len S.length-pos+1)r

17、eturn ERROR;if(Sub.ch)delete(Sub.ch);/释放旧空间 if(!len)Sub.ch=NULL;Sub.length=0;/空子串 else /完整子串 return OK;/SubString if(!(Sub.ch=new charlen)return ERROR;Sub.ch0.len-1=S.chpos-1.pos+len-2;Sub.length=len;void StrInsert(HString&S,int pos,HString T)/1posStrLength(S)1。在串。在串 S 的的 /第第 pos 个字符之前插入串个字符之前插入串 T

18、slen=S.length;tlen=T.length;/取取得得S和和T的串长的串长 if(pos slen+1)return;/插插入入位位置置不合法不合法 S1.ch=new charslen;/S1作为帮助串作为帮助串 S1.ch0.slen-1=S.ch0.slen-1;/暂存暂存 S if(tlen0)/T 非非空空，则则为为S重重新新支支配配空空间间并并插入插入T /StrInsert _HSq S.ch=new charslen+tlen;/为 S 重新支配空间for(i=0,k=0;ipos-1;i+)S.chk+=S1.chi;/保留插入位置之前的子串for(i=0;itl

19、en;i+)S.chk+=T.chi;/插入Tfor(i=pos-1;i 0)n=StrLength(S);m=StrLength(T);i=pos;while(i mijijijinj T 串一、简洁算法一、简洁算法int Index(SString S,SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。若不存在，则函数值为个字符之后的位置。若不存在，则函数值为0。/其中，其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index

20、 先比较模式串的第一个字符，先比较模式串的第一个字符，再比较模式串的最终一个字符，再比较模式串的最终一个字符，最终比较模式串中从其次个最终比较模式串中从其次个 到第到第 n-1 个字符。个字符。二、首首尾尾匹配算法匹配算法int Index_FL(SString S,SString T,int pos)sLength=S0;tLength=T0;i=pos;patStartChar=T1;patEndChar=TtLength;while(i=sLength tLength+1)if(Si!=patStartChar)+i;/重新查找匹配起始点 else if(Si+tLength-1!=pa

21、tEndChar)+i;/模式串的“尾字符”不匹配 else return 0;检查中间字符的匹配状况 k=1;j=2;while(j tLength&Si+k=Tj)+k;+j;if(j=tLength)return i;else +i;/重新起先下一次的匹配检测KMP算法的时间困难度可以达到O(m+n)当 Si Tj 时，已经得到的结果:Si-j+1.i-1=T1.j-1 若已知 T1.k-1=Tj-k+1.j-1 则有 Si-k+1.i-1=T1.k-1三、三、KMP(KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法算法定义：定义：模式串的next函数 int

22、Index_KMP(SString S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功匹配成功 else return 0;/Index_KMP这事实上也是一个匹配的过程，不同在于：主串和模式串是同一个串 求 next 函数值的过程是一个递推过程，分析如下:已知已知：next1=0；假设假设：nextj=k；又 Tj=Tk则则：nextj+1=k+1若若：Tj Tk则则 需往前回溯，检查 Tj=T？void get_next(SString T,int&next)/求模式串T的next

23、函数值并存入数组next。i=1;next1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;/get_next 还有一种特殊状况须要考虑：例如：S=aaabaaaab T=aaaabnextj=01234 nextvalj=00004 void get_nextval(SString T,int&nextval)i=1;nextval1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else j=nextvalj;

24、/get_nextval 1.1.熟悉串的七种基本操作的定义，熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的并能利用这些基本操作来实现串的其它各种操作的方法。其它各种操作的方法。2.2.娴熟驾驭在串的定长依次存储娴熟驾驭在串的定长依次存储结构上实现串的各种操作的方法。结构上实现串的各种操作的方法。3.3.驾驭串的堆存储结构以及在其驾驭串的堆存储结构以及在其上实现串操作的基本方法。上实现串操作的基本方法。本章小结本章小结 4.4.理解串匹配的理解串匹配的KMPKMP算法，熟悉算法，熟悉NEXTNEXT函数的定义，学会手工计算给定函数的定义，学会手工计算给定模式串的模式串的NEXTNEXT函数值和改进的函数值和改进的NEXTNEXT函函数值。数值。5.5.了解串操作的应用方法和特点。了解串操作的应用方法和特点。本章作业：本章作业：4.6 4.8 4.25 4.28思索题思索题:4.7 4.9 4.18 4.23 4.7 4.9 4.18 4.23 4.29 4.30 4.29 4.30