数据结构(Java)-第4章

基本内容1.串的基本概念第4章串2.串的存储结构

3.串基本运算的实现

4.模式匹配

5.串项目实践

1、串的定义串（String）是由零个或多个字符组成的有限序列，一般记作：s=“a1a2…ai…an”其中s是串名，用双引号括起来的字符序列是串值（不包括引号本身）。串的字符ai（1≤i≤n）可以是字母、数字或者其他有效字符，i是元素ai在串s中的序号，指明了元素ai的位置。串中所包含的字符个数n称为串的长度。可以将串看作一种特殊的线性表，其数据元素由单个字符构成。一.串的基本概念2、基本术语（1）空串：长度为零的字符串。（2）空格串：由一个或多个连续空格组成的串。（3）串相等：指两个串的长度相等且对应字符完全相同，即串值相等。（4）子串：串中任意个连续的字符组成的子序列称为该串的子串。（5）主串：包含子串的串称为该子串的主串。注意：空串是任意串的子串，任意串是其自身的子串。子串在主串中的位置以子串在主串中首次出现时，其第一个字符在主串中的索引位置来标识。3、举例设有5个串，如下所示：串串长s1=""0s2=""1s3="NeusoftCorporation"19s4="Neusoft"7s5="Corporation"11其中，s1是空串，s2是空格串。S4、s5都是s3的子串，s4在s3中的位置是1，s5在s3中的位置是9。4、串的运算（1）求串长：length()初始条件：串已存在操作结果：返回串中字符的个数。（2）求子串：subString(begin,end)初始条件：串已存在操作结果：返回串中的一个子串，从第begin个字符开始，到第end个字符结束。（3）子串查找：patternMatching（str）初始条件：串已存在操作结果：返回子串str在主串中首次出现的索引位置。（4）串连接：concat（str）初始条件：2个串已存在。操作结果：将str串连接到当前串的结尾，当前串的值发生变化。（5）串比较：compare(str)初始条件：2个串已存在。操作结果：将当前串与str串的串值进行比较。若二者值相等，则返回0；若当前串值大于str串值，则返回一个正整数；若当前串值小于str串值，则返回一个负整数。（6）串插入：insert(offset,str)初始条件：2个串已存在。操作结果：将str串插入到当前串中第offset个索引位置，当前串的值发生变化。（7）串删除：delete(begin,end)初始条件：串已存在。操作结果：删除串中的某一段字符，从第begin个字符开始，到第end个字符结束。（8）判空串：isEmpty()初始条件：串已存在。操作结果：若串为空串，则返回true，否则返回false。（9）返回串中索引为i的字符：charAt(i)初始条件：串已存在。操作结果：若参数i合法（），则读取并返回串中索引为i的字符，否则抛出异常。/**串接口*/publicinterfaceStringInterface{ booleanisEmpty(); intlength(); SeqStringsubString(intbegin,intend); charcharAt(inti); intcompare(SeqStringstr); SeqStringinsert(intoffset,SeqStringstr); SeqStringdelete(intbegin,intend);}

二、串的存储结构

1、串的顺序存储采用一组地址连续的存储单元来存储串的字符序列，在Java语言中，用字符数组实现。例如，串s=“Neusoft”的顺序存储如图所示。2、串的链式存储采用单链表来存储串值，简称链串。链串中每个结点的data域存放字符，next域存放下一个结点的地址。又根据data域存放字符个数的不同，可进一步分为单字符链表和块链表。（a）单字符链表（b）块链表三、串基本运算的实现

1、插入操作串的插入操作是指将某个特定串str插入当前串的指定位置，如插入到offset标识的索引位置。/*串插入*/ publicSeqStringinsert(intoffset,SeqStringstr){ if((offset<0)||offset>len){ thrownewStringIndexOutOfBoundsException("插入位置非法"); } intcount=str.length(); intnewCapacity=this.len+count; if(newCapacity>value.length){ allocate(newCapacity); } for(inti=this.len-1;i>=offset;i--){ value[i+count]=value[i]; } for(inti=0;i<count;i++){ value[offset+i]=str.charAt(i); } len=newCapacity; returnthis; }2、删除操作删除操作是指将当前串从begin开始到end-1结束的若干个串值删掉。/* *串删除 */ publicSeqStringdelete(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("结束位置非法，已超过串长"); if(begin>end) thrownewStringIndexOutOfBoundsException("参数非法");

for(inti=0;i<len-end;i++) value[begin+i]=value[end+i]; len=len-(end-begin); returnthis; }

3、求子串操作将当前串从指定位置begin开始到end-1结束的若干个连续字符取出，并返回这个子串。/* *求子串 */ publicSeqStringsubString(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("结束位置非法，已超过串长"); if(begin>end) thrownewStringIndexOutOfBoundsException("参数非法"); char[]temp=newchar[end-begin]; for(inti=0;i<temp.length;i++) temp[i]=value[i+begin]; returnnewSeqString(temp); }

4、串比较操作将当前串与str串的串值进行比较。若二者值相等，则返回0；若当前串值大于str串值，则返回一个正整数；若当前串值小于str串值，则返回一个负整数。 publicintcompare(SeqStringstr){ char[]temp=str.value; intn=Math.min(len,str.length()); intk=0; while(k<n){ if(value[k]!=temp[k]) returnvalue[k]-temp[k]; k++; } returnlen-str.length(); }四、模式匹配

设有两个串：目标主串target和模式串pattern，在目标主串target中查找与模式串pattern相等的一个子串并确定该子串位置的操作称为模式匹配。如果在target串中找到等于pattern的子串，则模式匹配成功，返回子串在主串中首次出现的存储位置或序号；否则模式匹配失败，返回-1。1、Brute-Force算法算法描述：已知目标串和模式串。从目标主串target的第一个字符开始试着对模式串pattern进行匹配，直至匹配成功或搜寻到串尾确定不成功为止。设i()表示目标串中某个子串的序号。算法步骤为：（1）从t0开始，取长度为m的子串，与模式串pattern作比较，（2）如果前一步比较完成后，二者相等则匹配成功，算法结束；否则继续取目标主串的下一子串与模式串pattern作比较。（3）重复这个过程，直至某一个子串与模式串pattern匹配成功，算法返回i值；或者当i值超过剩余子串长度与模式串长度之差时，标志最终匹配失败，算法返回-1结束。例如：设目标主串，模式串，模式匹配过程如图所示，其中设置了两个指针i、j，分别指示目标串和模式串当前正在比较的字符。//模式匹配 publicintpatternMatching(SeqStringpattern,intstart){ inttlen=this.length(); intplen=pattern.length(); if(this!=null&&pattern!=null&&plen>0&&tlen>plen){ inti=start,j=0; while((i<tlen)&&(j<plen)){