第5章串及数组1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构课程的内容,1,补充,：,C,语言中常用的串运算,串比较，,int,strcmp,(,chars1,char s2,);,/,StrCompare(S,T,),求串长，,int,strlen,(,char,s,);,/,StrLength(S,),串连接，,char,strcat,(,char,to,char from),/,Concat(,&,T,S1,S2),子串,T,定位，,char,strchr,(,char,s,char c,);,/,Index(S,T,pos),Concat,concatenation,，,在字符串处理中,把多个短字符串合成为长字符串的操作。,注：用,C,处理字符串时，要调用标准库函数,#include,2,第,5,章 串和数组,5.2,串的表示和实现,5.3,串的模式匹配算法,1.,定义,2.,逻辑结构,3.,存储结构,4.,运算规则,5.,实现方式,5.1,串类型的定义,3,记为：,s=“a,1,a,2,.,a,n,”(n0),串名,串值（用,”,括起来）,串中字符个数（,n0,）,.n=0,时称为空串,。,由一个或多个空格符组成的串。,串,s,中任意个连续的字符序列叫,s,的子串,;S,叫,主串,。,子串的第一个字符的序号。,字符在串中的序号。,串长度相等，且对应位置上字符相等。,串,即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,5.1,串类型的定义,若干术语：,串长：,空白串：,子串：,子串位置：,字符位置：,串相等：,隐含结束符,/0,，即,ASCII,码,NUL,4,练,1,：,串是由,字符组成的序列，一般记为,。,练,2,：,现有以下,4,个字符串：,a=“BEI”b=“JING”c=“BEIJING”d=“BEI JING”,问：他们各自的长度？,a,是哪个串的子串？在主串中的位置是多少？,a=3，b=4，c=7，d=8,a,是,c,和,d,的子串，在,c,和,d,中的位置都是,1,练,3,：,空串和空白串有无区别？,答：,有区别,。,空串,(Null String),是指长度为零的串；而空白串,(Blank String),是指包含一个或多个空白字符,”“(,空格键,),的字符串,.,0,个或多个,S=“a,1,a,2,a,n,”,5,5.2,串的表示和实现,定长顺序存储表示,用一组地址连续的存储单元存储串值的字符序列,堆分配存储表示,用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。,串的块链存储表示,链式方式存储,首先强调：,串与线性表的运算有所不同，是以“,串的整体,”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,串有三种机内表示方法：,顺序存储,链式存储,6,定长顺序存储特点：,用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的,上界预先给出,，故称为静态存储分配,。,例如：,#define,Maxstrlen,255 /,用户可用的最大串长,typedef,unsigned char,SString,Maxstrlen,1;,SString,s;/s,是一个可容纳,255,个字符的顺序串。,注：,一般用,SString0,来存放串长信息；,C,语言约定在串尾加结束符,0,，以利操作加速，但不计入串长；,若字符串超过,Maxstrlen,则自动截断（因为静态数组存不 进去）。,讨论：,想存放,超长,字符串怎么办？,静态数组有缺陷！,实现方式：,参见教材,P73,编程两例，两串连接和,求子串,改用,动态,分配的一维数组,“堆”！,7,例：,用顺序存储方式实现求子串函数,SubString(Sub,S,pos,len,),Status,SubString,(char,sub,char S,int,pos,int,len,),slen,=,StrLength_Sq(S,);,/,求字符串,S,的长度,if(pos,slen-1,|,len,slen,-pos),return ERROR;,/pos,不合法则告警,for(j,=0;j0),/T,非空，则为,S,重新分配空间并插入,T,S1=,strdup(S,);,/,系统通过,strdup,函数自动为,S1,分配空间，暂存串,S,S=new,charstrlen,+,strlen,+1;,/,为,S,串重新分配空间,Sub=S1+pos-1;,/Sub,是插入位置之后的子串,strncpy,(S,S1,pos-1);,/,复制插入位置之前的子串,spos-1=0;,/,暂时为,S,置结束标志，以便使用操纵,S,串的有关串函数,strcat,(S,T);,/,插入,T,串,strcat,(S,Sub);,/,复制插入位置之后的子串,/if,/,StrInsert,例：,用“堆”实现串插入操作,(,教材,P94,),10,讨论：,法,1,存储密度为,；,法,2,存储密度为,；,显然，若,数据元素很多，用法,2,存储更优,称为,块链结构,链式存储特点：,用链表存储串值，易插入和删除。,法,1,：,链表结点（数据域）大小取,1,法,2,：,链表结点（数据域）大小取,n(,例如,n=4),1/2,9/15=3/5,A,B,C,I,NULL,head,head,A B C D,E F G H,I#NULL,11,#define,CHUNKSIZE,80,/,可由,用户定义的块大小,typedef,struct,Chunk,/,首先定义结点类型,char,ch,CHUNKSIZE,;,/,结点中的数据域,struct,Chunk*next;,/,结点中的指针域,Chunk;,块链类型定义：,例略,typedef,struct,/,其次定义用链式存储的串类型,Chunk *head;,/,头指针,Chunk *tail;,/,尾指针,int,curLen,;,/,结点个数,Lstring,;,/,串类型只用一次，前面可以不加,Lstring,12,再次强调：,串与线性表的运算有所不同，是以“,串的整体,”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,这类操作中均涉及到,定位问题,，称为,串的模式匹配,。它是串处理系统中最重要的操作之一。,算法目的：,确定主串中所含子串第一次出现的位置,（,定位,）,即如何实现,Index(S,T,pos),函数,5.3,正文模式匹配算法,模式匹配,(Pattern Matching),即,子串定位运算（,Index,函数,）,。,初始条件：,串,S,和,T,存在，,T,是非空串，,1posStrLength(s),操作结果：,若主串,S,中存在和串,T,值相同的子串，则返回它在主串,S,中第,pos,个字符之后,第一次,出现的位置；否则函数值为,0,。,注：,S,称为,被匹配的串,，,T,称为,模式串,。若,S,包含串,T,，,则称“匹配成功”。否则称“匹配不成功”。,13,BF,算法设计思想：,将主串的第,pos,个字符和模式的第,1,个字符比较，,若,相等,，继续逐个比较后续字符；,若,不等,，从主串的下一字符（,pos+1,）,起，重新与第一个字符比较。,BF,算法,（又称古典或经典的、朴素的、穷举的）,KMP,算法,（特点：速度快）,算法种类：,直到主串的一个连续子串字符序列与模式相等。返回值为,S,中与,T,匹配的子序列,第一个字符的序号,，即匹配成功。,否则，匹配失败，返回值,0.,S=a b a b c a b c a c b a b,T=,a b c a c,pos=5,14,int,Index_BF,(char,S,char T,int,pos),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;,/,匹配不成功,/,Index_BF,BF,算法的实现,即,Index,（）,操作的实现,（见教材,P96,）,S=a b a b,c,a b c a c b a b,T=,a b c a c,pos=4,相当于串,T,向右滑动一个字符位置,i,j,15,