數(shù)據(jù)結(jié)構(gòu)(Java)-第4章

基本內(nèi)容1.串的基本概念第4章串2.串的存儲結(jié)構(gòu)

3.串基本運算的實現(xiàn)

4.模式匹配

5.串項目實踐

1、串的定義串（String）是由零個或多個字符組成的有限序列，一般記作：s=“a1a2…ai…an”其中s是串名，用雙引號括起來的字符序列是串值（不包括引號本身）。串的字符ai（1≤i≤n）可以是字母、數(shù)字或者其他有效字符，i是元素ai在串s中的序號，指明了元素ai的位置。串中所包含的字符個數(shù)n稱為串的長度?？梢詫⒋醋饕环N特殊的線性表，其數(shù)據(jù)元素由單個字符構(gòu)成。一.串的基本概念2、基本術(shù)語（1）空串：長度為零的字符串。（2）空格串：由一個或多個連續(xù)空格組成的串。（3）串相等：指兩個串的長度相等且對應(yīng)字符完全相同，即串值相等。（4）子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串。（5）主串：包含子串的串稱為該子串的主串。注意：空串是任意串的子串，任意串是其自身的子串。子串在主串中的位置以子串在主串中首次出現(xiàn)時，其第一個字符在主串中的索引位置來標(biāo)識。3、舉例設(shè)有5個串，如下所示：串串長s1=""0s2=""1s3="NeusoftCorporation"19s4="Neusoft"7s5="Corporation"11其中，s1是空串，s2是空格串。S4、s5都是s3的子串，s4在s3中的位置是1，s5在s3中的位置是9。4、串的運算（1）求串長：length()初始條件：串已存在操作結(jié)果：返回串中字符的個數(shù)。（2）求子串：subString(begin,end)初始條件：串已存在操作結(jié)果：返回串中的一個子串，從第begin個字符開始，到第end個字符結(jié)束。（3）子串查找：patternMatching（str）初始條件：串已存在操作結(jié)果：返回子串str在主串中首次出現(xiàn)的索引位置。（4）串連接：concat（str）初始條件：2個串已存在。操作結(jié)果：將str串連接到當(dāng)前串的結(jié)尾，當(dāng)前串的值發(fā)生變化。（5）串比較：compare(str)初始條件：2個串已存在。操作結(jié)果：將當(dāng)前串與str串的串值進(jìn)行比較。若二者值相等，則返回0；若當(dāng)前串值大于str串值，則返回一個正整數(shù)；若當(dāng)前串值小于str串值，則返回一個負(fù)整數(shù)。（6）串插入：insert(offset,str)初始條件：2個串已存在。操作結(jié)果：將str串插入到當(dāng)前串中第offset個索引位置，當(dāng)前串的值發(fā)生變化。（7）串刪除：delete(begin,end)初始條件：串已存在。操作結(jié)果：刪除串中的某一段字符，從第begin個字符開始，到第end個字符結(jié)束。（8）判空串：isEmpty()初始條件：串已存在。操作結(jié)果：若串為空串，則返回true，否則返回false。（9）返回串中索引為i的字符：charAt(i)初始條件：串已存在。操作結(jié)果：若參數(shù)i合法（），則讀取并返回串中索引為i的字符，否則拋出異常。/**串接口*/publicinterfaceStringInterface{ booleanisEmpty(); intlength(); SeqStringsubString(intbegin,intend); charcharAt(inti); intcompare(SeqStringstr); SeqStringinsert(intoffset,SeqStringstr); SeqStringdelete(intbegin,intend);}

二、串的存儲結(jié)構(gòu)

1、串的順序存儲采用一組地址連續(xù)的存儲單元來存儲串的字符序列，在Java語言中，用字符數(shù)組實現(xiàn)。例如，串s=“Neusoft”的順序存儲如圖所示。2、串的鏈?zhǔn)酱鎯Σ捎脝捂湵韥泶鎯Υ?，簡稱鏈串。鏈串中每個結(jié)點的data域存放字符，next域存放下一個結(jié)點的地址。又根據(jù)data域存放字符個數(shù)的不同，可進(jìn)一步分為單字符鏈表和塊鏈表。（a）單字符鏈表（b）塊鏈表三、串基本運算的實現(xiàn)

1、插入操作串的插入操作是指將某個特定串str插入當(dāng)前串的指定位置，如插入到offset標(biāo)識的索引位置。/*串插入*/ 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、刪除操作刪除操作是指將當(dāng)前串從begin開始到end-1結(jié)束的若干個串值刪掉。/* *串刪除 */ publicSeqStringdelete(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("結(jié)束位置非法，已超過串長"); if(begin>end) thrownewStringIndexOutOfBoundsException("參數(shù)非法");

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

3、求子串操作將當(dāng)前串從指定位置begin開始到end-1結(jié)束的若干個連續(xù)字符取出，并返回這個子串。/* *求子串 */ publicSeqStringsubString(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("結(jié)束位置非法，已超過串長"); if(begin>end) thrownewStringIndexOutOfBoundsException("參數(shù)非法"); char[]temp=newchar[end-begin]; for(inti=0;i<temp.length;i++) temp[i]=value[i+begin]; returnnewSeqString(temp); }

4、串比較操作將當(dāng)前串與str串的串值進(jìn)行比較。若二者值相等，則返回0；若當(dāng)前串值大于str串值，則返回一個正整數(shù)；若當(dāng)前串值小于str串值，則返回一個負(fù)整數(shù)。 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(); }四、模式匹配

設(shè)有兩個串：目標(biāo)主串target和模式串pattern，在目標(biāo)主串target中查找與模式串pattern相等的一個子串并確定該子串位置的操作稱為模式匹配。如果在target串中找到等于pattern的子串，則模式匹配成功，返回子串在主串中首次出現(xiàn)的存儲位置或序號；否則模式匹配失敗，返回-1。1、Brute-Force算法算法描述：已知目標(biāo)串和模式串。從目標(biāo)主串target的第一個字符開始試著對模式串pattern進(jìn)行匹配，直至匹配成功或搜尋到串尾確定不成功為止。設(shè)i()表示目標(biāo)串中某個子串的序號。算法步驟為：（1）從t0開始，取長度為m的子串，與模式串pattern作比較，（2）如果前一步比較完成后，二者相等則匹配成功，算法結(jié)束；否則繼續(xù)取目標(biāo)主串的下一子串與模式串pattern作比較。（3）重復(fù)這個過程，直至某一個子串與模式串pattern匹配成功，算法返回i值；或者當(dāng)i值超過剩余子串長度與模式串長度之差時，標(biāo)志最終匹配失敗，算法返回-1結(jié)束。例如：設(shè)目標(biāo)主串，模式串，模式匹配過程如圖所示，其中設(shè)置了兩個指針i、j，分別指示目標(biāo)串和模式串當(dāng)前正在比較的字符。//模式匹配 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)){