數(shù)據(jù)結(jié)構(gòu)(Java)-第4章_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java)-第4章_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java)-第4章_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java)-第4章_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java)-第4章_第5頁(yè)
已閱讀5頁(yè),還剩18頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

3.串基本運(yùn)算的實(shí)現(xiàn)

4.模式匹配

5.串項(xiàng)目實(shí)踐

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

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

1、串的順序存儲(chǔ)采用一組地址連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)串的字符序列,在Java語(yǔ)言中,用字符數(shù)組實(shí)現(xiàn)。例如,串s=“Neusoft”的順序存儲(chǔ)如圖所示。2、串的鏈?zhǔn)酱鎯?chǔ)采用單鏈表來(lái)存儲(chǔ)串值,簡(jiǎn)稱鏈串。鏈串中每個(gè)結(jié)點(diǎn)的data域存放字符,next域存放下一個(gè)結(jié)點(diǎn)的地址。又根據(jù)data域存放字符個(gè)數(shù)的不同,可進(jìn)一步分為單字符鏈表和塊鏈表。(a)單字符鏈表(b)塊鏈表三、串基本運(yùn)算的實(shí)現(xiàn)

1、插入操作串的插入操作是指將某個(gè)特定串str插入當(dāng)前串的指定位置,如插入到offset標(biāo)識(shí)的索引位置。/*串插入*/ 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開(kāi)始到end-1結(jié)束的若干個(gè)串值刪掉。/* *串刪除 */ publicSeqStringdelete(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("結(jié)束位置非法,已超過(guò)串長(zhǎng)"); 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開(kāi)始到end-1結(jié)束的若干個(gè)連續(xù)字符取出,并返回這個(gè)子串。/* *求子串 */ publicSeqStringsubString(intbegin,intend){ if(begin<0) thrownewStringIndexOutOfBoundsException("起始位置非法"); if(end>len) thrownewStringIndexOutOfBoundsException("結(jié)束位置非法,已超過(guò)串長(zhǎng)"); 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串值,則返回一個(gè)正整數(shù);若當(dāng)前串值小于str串值,則返回一個(gè)負(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è)有兩個(gè)串:目標(biāo)主串target和模式串pattern,在目標(biāo)主串target中查找與模式串pattern相等的一個(gè)子串并確定該子串位置的操作稱為模式匹配。如果在target串中找到等于pattern的子串,則模式匹配成功,返回子串在主串中首次出現(xiàn)的存儲(chǔ)位置或序號(hào);否則模式匹配失敗,返回-1。1、Brute-Force算法算法描述:已知目標(biāo)串和模式串。從目標(biāo)主串target的第一個(gè)字符開(kāi)始試著對(duì)模式串pattern進(jìn)行匹配,直至匹配成功或搜尋到串尾確定不成功為止。設(shè)i()表示目標(biāo)串中某個(gè)子串的序號(hào)。算法步驟為:(1)從t0開(kāi)始,取長(zhǎng)度為m的子串,與模式串pattern作比較,(2)如果前一步比較完成后,二者相等則匹配成功,算法結(jié)束;否則繼續(xù)取目標(biāo)主串的下一子串與模式串pattern作比較。(3)重復(fù)這個(gè)過(guò)程,直至某一個(gè)子串與模式串pattern匹配成功,算法返回i值;或者當(dāng)i值超過(guò)剩余子串長(zhǎng)度與模式串長(zhǎng)度之差時(shí),標(biāo)志最終匹配失敗,算法返回-1結(jié)束。例如:設(shè)目標(biāo)主串,模式串,模式匹配過(guò)程如圖所示,其中設(shè)置了兩個(gè)指針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)){

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論