数据结构-第4章字符串.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,字符串(String),字符串,是 n(,0)个字符的有限序列，,记作 S=“c,1,c,2,c,3,c,n,”,其中，S 是串名字,“c,1,c,2,c,3,c,n,”是串值,c,i,是串中字符,n 是串的长度。,例如,S=“Tsinghua University”,const int maxLen=128;,class String,int curLen;,/,串的当前长度,char*ch;,/串的存储数组,public:,String(const String,String(const char*init);,String();,String()delete ch;,字符串抽象数据类型和类定义,int Length()const return curLen;,/,求当前串*,this,的实际长度,String,/取*this从pos开始len个字符组成的子串,int operator=(const String&ob),return strcmp(ch,ob.ch)=0;,/判当前串*this与对象串ob是否相等,int operator!=(const String&ob),const return strcmp(ch,ob.ch)!=0;,/判当前串*this与对象串ob是否不等,int operator!(),const return curLen=0;,/,判当前串,*this,是否空串,String,/将串ob赋给当前串*this,String,/将串ob连接到当前串*this,之后,char,/取当前串*this,的第,i,个字符,int Find(String,String:String(const String&ob),/复制构造函数：从已有串ob复制,ch=new charmaxLen+1;,/,创建串数组,if(ch=NULL),cont “,存储分配错!,”endl;,exit(1);,curLen=ob.curLen;,/复制串长度,strcpy(ch,ob.ch);,/复制串值,字符串部分操作的实现,String:String(const char*init),/,复制构造函数:从已有字符数组,*init复制,ch=new charmaxLen+1;,/,创建串数组,if(ch=NULL),cout“,存储分配错!,”endl;,exit(1);,curLen=strlen(init);,/复制串长度,strcpy(ch,init);,/复制串值,String:String(),/构造函数：创建一个空串,ch=new charmaxLen+1;,/,创建串数组,if(ch=NULL),cout“,存储分配错!,”endl;,exit(1);,curLen=0;,ch0=0;,String&String:operator()(int pos,int len),/从串中第 pos 个位置起连续提取 len 个字符,/形成子串返回,String*temp=new String;,/动态分配,if(pos=maxLen|len,curLen=0;,/返回空串,temp,-,ch0=0;,else,/提取子串,if(pos+len,-,1=curLen),temp,-,curLen=len;,/子串长度,for(int i=0,j=pos;i,chi=chj;,/传送串数组,temp,-,chlen=0;,/子串结束,return*temp;,例：串,st=“,uni,vers,ity,”,pos=3,len=4,使用示例,subSt=st(3,4),提取子串 subSt=“,vers,”,char&String:operator (int i),/按串名提取串中第 i 个字符,if(i=curLen),cout “串下标超界!n”;exit(1);,return chi;,例：串,st=“,university,”,使用示例,newSt=st；newChar=st1;,数组赋值,newSt=“,university,”,提取字符,newChar=,n,例：串 st1=“,beijing,”,st2=“,university,”,使用示例,st1+=st2;,连接结果,st1=“,beijing university,”,st2=“,university,”,串的模式匹配,定义 在串中寻找子串（第一个字符）在串中的位置,词汇 在模式匹配中，子串称为模式，串称为目标。,示例 目标 T:“Beijing”,模式 P:“jin”,匹配结果=4,int String:Find(String&pat)const,/穷举的模式匹配,for(int i=0;i=curLen,-,pat.curLen;i+),/逐趟比较,int j=0;,/从chi与模式pat.ch比较,while(j pat.curLen),if(chi+j=pat.chj)j+;,else break;,if(j=pat.curLen)return i;,/pat扫描完,匹配成功,