数据结构中的串课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 串（,String,）,数 据 结 构（,Data Structure,）,主讲：李耀国,第,4,章 串,4.1,串的定义和操作,4.2,串的表示和实现,4.2.1,定长顺序存储表示,4.2.2,堆分配存储表示,4.2.3,块链存储表示,4.3,正文模式匹配*,4.4,正文编辑,-,串操作应用举例,44,第,4,章 串,字符串,数据是计算机,非数值处理,的主要对象之一。在早期字符串字符串作为输入输出的常量出现，现已发展成为字符串类型，可以进行一系列的操作。,字符串一般简称为串。在汇编和编译程序中，源程序是字符串数据。在事务处理程序中，顾客的姓名和地址及货物的名称、产地等也是字符串。此外，如信息检索系统、文字编辑程序、自然语言翻译系统等都是以字符串为处理对象。,然而，目前的计算机硬件结构主要是面向数值计算的需要，基本上没有提供处理字符串数据操作的指令，需要用软件来实现字符串类型。由于各种应用具有不同的特点，要有效的实现字处理，必须根据具体情况使用合适的存储结构。,4.1,串的定义和操作,串,(String),或称字符串是由零个或多个字符组成的有限序列。一般记为：,S=“a,0,a,1,a,n-1,”(n 0),其中，,S,是串的名称，用双号括起来的字符序列是串的值；,a,i,(0in-1),可以是字母、数字或其它字符（字符的序号从,0,开始，与,C,、,C+,、,JAVA,等语言的习惯一致）；串中字符的数目,n,称为串的,长度,。零个字符的串称为,空串,(null string),，它的长度为零。,串中任意个连续的字符组成的子序列称为该串的,子串,。包含子串的的串相应地称为,主串,。通常称字符在序列中的序列号为该字符在串中的,位置,。子串在主串中的位置则以,子串第,0,个字符,在主串的位置来表示。,4.1,串的定义和操作,例如：下面,a,，,b,，,c,，,d,都是串,a=“BEI”,长度为,3,b=“JING”,长度为,4,c=“BEIJING”,长度为,7,d=“BEI JING”,长度为,8,串的逻辑结构和线性表极为相似，区别仅仅在于串的数据对象约束为,字符集,。但是串的基本操作和线性表有很大的差别。,在线性表的操作中大多数以“单个元素”为操作对象，而在串的操作中大多数以“串的整体”为操作对象。,4.1,串的定义和操作,两个串之间可以进行比较。,称两个串相等，当且仅当这两个串的值相等，包括两个串的,长度相等,，并且各个,对应位置的字符,都相等。,当两个串不相等时，可按“字典顺序”分大小。令,s=“s,0,s,1,s,m-1,”(m0),t=“t,0,t,1,t,n-1,”(n0),假设，两者最大有前,k,个子序列相等（最大相等前缀子串），,s,和,t,的大小由,s,k,和,t,k,的大小来决定。在,C,语言中字符的大小按,ASCII,码的大小为准,4.1,串的定义和操作,串值必须用一对双引号括起来，但双引号不属于串，它的作用只是为了避免与变量或常量混淆。例如：,x=“123”;,其中，,X,是一个串变量名，赋给它的值是字符序列,123,而不是整数,123,。之间可以进行比较。,aString=“aString”;,左边的,aString,是一个串变量名，而右边的字符序列,aString,是赋给它的值,在各种应用中，空格通常是串的字符集合中的一个元素，可以出现在其它字符之间，由一个或多个空格组成的串称为,空,格,串,“”；和“”；都是空格串。,为了清楚起见我们以后用,来表示,空串,串的基本操作（,1,）,ADT String,数据对象,:D=a,i,|a,i,CharacterSet,i=1,2,.,n,n0,数据关系,:R1=|a,i-1,a,i,D,i=2,.,n,基本操作：,StrAssing(&T,chars),:chars,是字符串常量，生成一个值等于,chars,的串,T,StrCopy(&T,S),:,串,S,存在，由串,S,复制得串,T,StrEmpty(S),:,如果串,S,为空，返回,TRUE,，否则返回,FALSE,StrCompare(S,T),:,若,ST,返回,0;,若,S=T,返回,=0;,若,ST,返回,=0),n=,StrLength,(S);m=,StrLength,(T);i=pos;,while,(i=n-m),SubString,(sub,S,i,m);,/,返回,S,中从,i,起长度为,m,的子串,if,(,SubCompare,(sub,T)!=0)i+;,else,return,i;,/while,/if,return,-1;,/Index,4.2,串的表示和实现,如果在程序设计语言中，串只是作为输入输出的常量出现，则只需存储这个串常量值，即字符序列即可。,但在多数非数值处理情况的程序中，串也以变量的形式出现。因此需要根据串的操作的特点，合理地选择和设计串值的存储结构及其维护方式。,1,定长顺序存储表示,2,堆分配存储表示,3,块链存储表示,4.2.1,串的顺序存储,类似于线性表的顺序存储表示方法，可用一组,地址连续,的存储单元存储串值的字符序列。,例如，在,C,语言中，字符串的一种处理方法就是将字符串作为字符数组来处理。假设：,char str10;,/,固定长为,10,的存储区,在,C,语言中，字符串的结束标志为,0,，同时我们应注意到,0,也占一个字符的空间。,4.2.1,串的顺序存储,void,Concat_Sq(,char,S1,char,S2,char,T),/,用,T,返回,S1,和,S2,联接而成的新串,k=0;j=0;,while,(S1j!=0),Tk+=S1j+;,j=0;,while,(S2j!=0),Tk+=S2j+;,Tk=0;,/Concat_Sq,算法,4.2,4.2.1,串的顺序存储,void,SubString_Sq(,char,Sub,char,S,int,pos,int,len),/,用,Sub,返回串,S,的第,pos,个字符起长度为,len,的字符,其中,/0=posStrLength(S),且,0=len=StrLength(S)-pos,slen=StrLength_Sq(S);,if,(posslen-1,|,lenslen-pos),ERRORMSG(“,参数不合法”,);,return;,for,(j=0;j0),i=0;,while,(S1i=Si)!=0)i+;,delete S;S=new charslen+tlen+1;,for(,i=0,k=0;,i0),S1=,strdup,(S);,S=,new,charslen+tlen+1;,strncpy,(S,S1,pos);,Spos=0;,strcat,(S,T);,Sub=S1+pos;,strcat,(S,Sub);delete S1;,/if,/StrInsert_HSq,算法,4.4(,使用,C,语言库函数实现,string.h),4.2.3,块链存储表示,和线性表的链式存储类似，串值也可以用,链表,来存储。但由于串结构的特殊性，存在着“一个结点大小”的问题。,另外，在一般情况下，串的操作都是从前往后进行的，因此链表通常不设双链，但为了方便诸如串的联接等操作，链表中还是,附设尾指针,，同时还需要设定一个,指示串长的域,。,1.,结构定义：,const CHUNKSIZE=80;,/,可由用户定义的块（节点）大小,typedef struct Chunk,/,节点结构,char chCHUNKSIZE,；,struct Chunk*next;,Chunk,;,typedef struct,/,串的链表结构,Chunk,*,head,*,tail,;/,头尾指针,int,curlen,;/,串的当前长度,Lstring,；,4.2.3,块链存储表示,在以链表存储串值时，节点大小的选择将直接影响串处理的效率。,定义串的,存储密度,=,串值所占的存储空间,/,实际分配的存储空间,；显然存储密度小，操作方便，但存储占用量大。,通常情况下，以块链作存储结构时实现串的操作比较麻烦，如：在串中插入一个子串时可能需要分割节点，联接两个串时，若第一个串的最后一个节点没有添满，还需要填充其他字符。,但是，在实际应用中可将串的链表存储和定长结构结合使用。例如在正文编辑系统中，可将正文看成一个串，将一行看成一个子串，构成一个节点（,80,个字符）。行与行之间可用指针相联接。,4.3,正文模式匹配,在计算机所处理的各类数据中，有很大一部分是,正文数据,，也常称为,文本型数据,。,文本型数据是在任何平台和系统都可以接受的数据形式，在计算机行业有很长的历史。在最初的应用中，这些文字材料仅由可打印字符组成，首先由字符组成行，然后再由行构成整个正文。,我们注意到，在已有的正文编辑软件中，都提供,“,查找,”,功能，这种操作就是为串定位的工作，通常称为,正文模式匹配,4.3,正文模式匹配,例子：,若,S=,“,concatenation,”,T=,“,cat,”,我们的目的是在串,S,中查找有没有串,T,，及,T,在,S,中的位置。在这里我们称主串,S,中存在和模式串,T,相同的子串，起始位置为,3,，即,Index(S,T,0)=3;,正文模式匹配有多种算法，为了简单起见，采用,C,语言中定长表示描述算法。其实算法,4.1,就是这样的算法，只是在算法,4.1,中利用了串的其他操作，下面我们给出不依赖其他串操作的算法,4.6,4.3,正文模式匹配,我们应注意到，算法,4.6,可以实现,从任意位置起的查询，其方法是,起始,pos=i+Strlength(T),int,Index,(char S,char T,int pos),/,若串,S,中，从第,pos,个字符起存在和串,T,相同的子串，则称匹,/,配成功，返回第一个这样的子串在串,S,中的位置，否则返回,-1,i=pos;j=0;,while(Si+j!=0&Tj!=0),if(Si+j=Tj),j+,;,/,继续比较后一字符,else,i+;j=0,;,/,重新开始新的一轮比较,if(Tj=0)return i;,/,匹配成功,else return-1;,/S,中,(,第,pos,个字符起,),不存在和,T,相同的子串,/Index,算法,4.6,4.3,正文模式匹配,书上算法,int Index(SString S,SString T,int pos),/,返回子串,T,中在主串,S,中第,pos,个字符之后的位置,.,不存在为,0,i=pos;j=1;,while(i=S0&j T0)return i-T0;,else return 0;,/Index,4.3,正文模式匹配,小的改进,int Index(SString S,SString T,int pos),/,返回子串,T,中在主串,S,中第,pos,个字符之后的位置,.,不存在为,0,i=pos;,while(,i=S0-T0+1,),j=1;,while(j T0)return i;,else i+;,return 0;,/Index,4.3,正文模式匹配,前面的算法统称,串匹配的平凡算法,如果以单个字符之间的比较为基本操作，算法,Index,的最坏情形时间复杂度应为,O(n,m),阶。,串匹配问题的平凡算法是可以改进的。,T,：,ABABC,，,m=5,S,：,ABABABCAC,，,n=9,算法的执行过程相当于在,n-m+1=5,个长度为,m,的单词中检索单词,T,。这,5,个单词为：,ABABA,，,BABAB,，*,ABABC,，,BABCA,，,ABCAC,4.3,正文模式匹配,由于样本,T,与字典中的第三个单词相同，故返回值为,i=3,。,不难发现这里的字典有其特殊性