數(shù)據(jù)結(jié)構(gòu)（Java語言） 課件 項(xiàng)目五 串-模式匹配

項(xiàng)目五串---模式匹配目錄項(xiàng)目五5123

典型工作任務(wù)5.1串項(xiàng)目需求分析典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)典型工作任務(wù)5.4串軟件測試執(zhí)行典型工作任務(wù)5.5串軟件文檔編寫46典型工作任務(wù)5.6串項(xiàng)目驗(yàn)收交付知識目標(biāo)掌握串的常用概念和術(shù)語掌握串的邏輯結(jié)構(gòu)及兩種不同的存儲結(jié)構(gòu)掌握兩類存儲結(jié)構(gòu)的表示方法：順序串和鏈串掌握順序串的基本操作算法技能目標(biāo)能進(jìn)行項(xiàng)目需求分析會(huì)進(jìn)行串的算法分析及編程能用串的知識編程解決問題能進(jìn)行軟件測試及項(xiàng)目功能調(diào)整能撰寫格式規(guī)范的軟件文檔思政目標(biāo)以文字編輯器為例，培養(yǎng)學(xué)生嚴(yán)謹(jǐn)治學(xué)、認(rèn)真工作的態(tài)度培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)倪壿嬎季S和應(yīng)用能力鍛煉發(fā)現(xiàn)問題分析問題解決問題的邏輯思維學(xué)以致用養(yǎng)成嚴(yán)謹(jǐn)求實(shí)的學(xué)習(xí)習(xí)慣總體要求

文本編輯的實(shí)質(zhì)就是修改字符數(shù)據(jù)的形式或格式。雖然各種文本編輯工具的功能有所不同，但是基本的操作大多是一樣的，一般包括分頁、分段，字符串的查找、刪除、插入、替換等操作。為了編輯方便，可以利用換頁符把文本劃分成若干頁，也可以利用換行符表示段落，每個(gè)段落又包含若干行?？梢园盐谋井?dāng)作是一個(gè)字符串，成為文本串；頁是文本串的子串，行是頁的子串。如圖5-1所示。圖5-1簡單的文本編輯器功能模塊圖典型工作任務(wù)5.1串項(xiàng)目需求分析5.2.1串的術(shù)語1.字符串（String）字符串又稱為串，是由0個(gè)或者多個(gè)字符組成的有限序列，記為：S="a1a2…an"（n≥0）2.串的長度串的長度是指字符串中字符的個(gè)數(shù)n。3.空串長度為0的字符串，即沒有任何字符（s=""）。4.空白串空白串是指由一個(gè)或多個(gè)空格組成的字符串，例如：s=""。5.子串與主串串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。任意串都是自身的子串，空串是任意串的子串。典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6.字符在主串中的位置通常將字符在串中的序號稱為該字符在串中的位置。例如,字符'H'在串S="Hello"中的位置是0。7.子串在主串中的位置子串在主串中的位置是以子串的第一個(gè)字符首次在主串中的位置來表示。例如，設(shè)有字符串S1="ChinaBeijing"和S2="in"，S2在S1中出現(xiàn)了兩次，其中首次出現(xiàn)的位置是2，故子串S2在主串S1中的位置是2。8.串相等當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱兩個(gè)串是相等的，即兩個(gè)串的長度相等且每個(gè)對應(yīng)位置的字符都相等時(shí)才相等。典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

5.2.2串的存儲結(jié)構(gòu)1.串的順序存儲使用順序存儲的串稱為順序串，可用一組地址連續(xù)的空間存儲字符序列，即使用字符數(shù)組來存儲串中的字符，串中的每一個(gè)字符占據(jù)一個(gè)空間。例如，字符串S="Hello"使用順序存儲如圖順序串類型可描述如下：publicclassSeqString{publicchar[]chars; //字符數(shù)組，用于存放字符串信息publicintlen; //串的長度len}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

2.串的鏈?zhǔn)酱鎯κ褂面準(zhǔn)酱鎯Φ拇Q為鏈串，其也是用鏈表來實(shí)現(xiàn)的，串中的每一個(gè)字符都用一個(gè)結(jié)點(diǎn)來存儲。例如，字符串S="Hello"使用鏈?zhǔn)酱鎯θ鐖D.鏈串的類型可描述如下：publicclassNode{publicchardata;//存放結(jié)點(diǎn)值：數(shù)據(jù)域publicNodenext;//后繼結(jié)點(diǎn)的引用：指針域}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

5.2.3順序串的基本操作算法串的泛型類定義如下：publicclassSeqString{ publicintmaxSize=10;//串中字符數(shù)組的初始長度publicchar[]chars;//存儲元素的數(shù)組對象 publicintlength;//保存串的當(dāng)前長度 publicSeqString(){}//串的無參構(gòu)造方法 publicSeqString(intn){}//串的有參構(gòu)造方法 publicintgetLength(){}//求串的長度publicbooleanisEmpty(){ }//判斷串是否為空publicvoidcopy(SeqStringt){}//串的復(fù)制 publicintcompare(SeqStringt){}//串的比較 publicvoidconcat(SeqStringt){}//串的連接publicbooleandelete(intpos,intlen){}//串的刪除publicbooleaninsert(intoffset,SeqStringstr){}//串的插入publicSeqStringsubString(intpos,intlen){}//求子串publicintindex(SeqStringstr){}//求子串在主串中的位置}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1.串的初始化//無參構(gòu)造方法publicSeqString(){this.chars=newchar[this.maxSize]; this.length=0;}//有參構(gòu)造方法publicSeqString(intn){//構(gòu)造一個(gè)能保存n個(gè)字符的串 this.maxSize=n; this.chars=newchar[n]; this.length=0;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

2.求串的長度求串的長度非常簡單，只要獲取SeqString中成員length的值即可。publicintgetLength(){returnthis.length;}3.判斷串是否為空判斷串是否是空串，實(shí)際上就是判斷其長度是否為0。publicbooleanisEmpty(){returnthis.length==0;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

4.串的復(fù)制publicvoidcopy(SeqStringt){if(this.maxSize<t.maxSize)//當(dāng)前串空間不足的情況 { this.maxSize=t.maxSize; this.chars=newchar[this.maxSize]; } for(inti=0;i<t.getLength();i++)//對串中的值逐個(gè)進(jìn)行復(fù)制 { this.chars[i]=t.chars[i]; }this.length=t.length;//修改當(dāng)前串的長度}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

5.串的比較publicintcompare(SeqStringt){ inti=0; while(this.chars[i]==t.chars[i]&&i<this.length&&i<t.getLength()) {i++;} if(i==this.length&&i==t.length)//當(dāng)前串和串t相等，返回0 return0; elseif(i<this.length&&i<t.getLength()) {if(this.chars[i]>t.chars[i])//當(dāng)前串大于串t，返回1return1;elsereturn-1;//當(dāng)前串小于串t，返回-1} elseif(i<this.length&&i==t.getLength()) return1; elsereturn-1;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

6.串的連接publicvoidconcat(SeqStringt){if(this.maxSize<this.length+t.getLength()){char[]a=newchar[this.length];//當(dāng)前串容量不夠，暫存到數(shù)組afor(inti=0;i<this.length;i++)a[i]=this.chars[i]; this.maxSize=this.length+t.getLength();//對現(xiàn)有串?dāng)U充容量 this.chars=newchar[this.maxSize]; for(inti=0;i<a.length;i++)//恢復(fù)當(dāng)前串的原始狀態(tài)this.chars[i]=a[i];}for(inti=0;i<t.getLength();i++){ this.chars[this.length]=t.chars[i]; this.length++;}}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

7.串的刪除publicbooleandelete(intpos,intlen){if(pos<0||pos>(this.length-len))//pos或者len的值不合法，則返回刪除失敗returnfalse;for(inti=pos+len;i<this.length;i++)//前移后半部分this.chars[i-len]=this.chars[i];this.length=this.length-len;//修改刪除后的串長度returntrue;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

8.串的插入publicbooleaninsert(intpos,SeqStringt){if(pos<0||pos>this.length)//判斷插入位置pos是否合法returnfalse;if(this.length+t.getLength()>this.maxSize)//判斷插入后的串長度是否超過當(dāng)前串的容量{char[]a=newchar[this.length];//當(dāng)前串容量不夠，暫存到數(shù)組afor(inti=0;i<this.length;i++)a[i]=this.chars[i];this.maxSize=this.length+t.getLength();//對現(xiàn)有串?dāng)U充容量 this.chars=newchar[this.maxSize];for(inti=0;i<a.length;i++)//恢復(fù)當(dāng)前串的原始狀態(tài)this.chars[i]=a[i];}for(inti=this.length-1;i>=pos;i--)//從pos位置開始向后移動(dòng)長度為t.getLength個(gè)字符chars[i+t.getLength()]=chars[i];for(inti=0;i<t.getLength();i++)//插入串tchars[i+pos]=t.chars[i];this.length=this.length+t.getLength();//修改當(dāng)前串的長度returntrue;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)9.求子串publicSeqStringsubString(intpos,intlen){ if(pos+len>this.length) returnnull; SeqStringa=newSeqString(len); for(inti=0;i<len;i++) { a.chars[i]=this.chars[pos+i]; a.length++; } returna;}典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)5.2.4順序串的模式匹配算法在當(dāng)前串中尋找某個(gè)子串的過程稱為模式匹配，其中該子串稱為模式串。Brute-Force算法又稱為樸素的模式匹配，是一種帶回溯的匹配算法。設(shè)主串S="ababc"，子串T="abc"，pos的值為0，即從主串S的第0個(gè)位置開始進(jìn)行匹配，初始狀態(tài)如圖5-7所示。圖5-7匹配的初始狀態(tài)5-8執(zhí)行第一趟匹配后的狀態(tài)典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

進(jìn)行回溯，讓主串S從第1個(gè)位置重新開始匹配，子串T從頭開始（即從第0個(gè)位置開始），如圖5-9所示。

進(jìn)行第二趟匹配后的結(jié)果如圖5-10所示，此時(shí)主串S中位置為1的字符和子串T中位置為0的字符不相等，故不匹配。

圖5-9第一趟匹配失敗后的回溯圖圖5-10執(zhí)行第二趟匹配后的狀態(tài)典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)進(jìn)行回溯，讓主串S從第2個(gè)位置重新開始匹配，子串T從頭開始，如圖5-11所示。進(jìn)行第三趟匹配后的結(jié)果如圖5-12所示，此時(shí)主串S和子串T匹配成功，則返回子串T在主串S中的位置，即i-T.getLength()=5-3=2。

圖5-11第二趟匹配失敗后的回溯圖圖5-8執(zhí)行第三趟匹配后的狀態(tài)典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)Brute-Force算法的具體實(shí)現(xiàn)如下：publicintindexOf_BF(SeqStringt,intpos){if(t.getLength()==0||this.length<t.getLength()) //模式串為空或比主串長return-1;inti=pos,j=0;while(i<this.length&&j<t.getLength()){//循環(huán)比較,主串和模式串都不能超過長度if(this.chars[i]==t.chars[j]){ //主串和模式串依次比較每一個(gè)字符i++;j++;}else{ //進(jìn)行回溯，過渡到下一趟i=i-j+1; //轉(zhuǎn)向主串中下一字符j=0; //子串重頭開始}}if(j>=t.getLength()){ //模式串已經(jīng)循環(huán)完畢returni-t.getLength(); //匹配成功，第一個(gè)字母的索引號}else{return-1; //匹配失敗}}

典型工作任務(wù)5.2串?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

以簡單的文本編輯器處理為主，設(shè)計(jì)本系統(tǒng)的程序，由兩部分組成，第1部分為順序串的13種操作算法，第2部分為主程序Test，該程序?qū)崿F(xiàn)順序串操作算法的調(diào)用及數(shù)據(jù)的輸出和顯示。程序框圖如圖5-13所示。

圖5-13串程序框圖典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)源代碼如下：publicclassSeqString{ publicintmaxSize=10; publicchar[]chars; publicintlength;//1.初始化 publicSeqString(){ this.chars=newchar[this.maxSize]; this.length=0;} publicSeqString(intn){ this.maxSize=n; this.chars=newchar[n]; this.length=0; } publicSeqString(Strings){ this.maxSize=s.length(); this.chars=s.toCharArray(); this.length=s.length(); }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)//2.求串長publicintgetLength(){ returnthis.length; }//3.判串是否為空 publicbooleanisEmpty(){ returnthis.length==0; }//4.清空串publicvoidclear(){ this.length=0; }//5.復(fù)制串publicvoidcopy(SeqStringt){ if(this.maxSize<t.maxSize){ his.maxSize=t.maxSize; this.chars=newchar[this.maxSize];} for(inti=0;i<t.getLength();i++){ this.chars[i]=t.chars[i]; }this.length=t.length; }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)//6.比較串 publicintcompare(SeqStringt){ inti=0; while(this.chars[i]==t.chars[i]&&i<this.length&&i<t.getLength()) { i++; } if(i==this.length&&i==t.length) return0; elseif(i<this.length&&i<t.getLength()) { if(this.chars[i]>t.chars[i]) return1; else return-1; } elseif(i<this.length&&i==t.getLength()) return1; else return-1; }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)//7.連接串 publicvoidconcat(SeqStringt){ if(this.maxSize<this.length+t.getLength()){ char[]a=newchar[this.length]; for(inti=0;i<this.length;i++) a[i]=this.chars[i]; this.maxSize=this.length+t.getLength(); this.chars=newchar[this.maxSize]; for(inti=0;i<a.length;i++) this.chars[i]=a[i]; } for(inti=0;i<t.getLength();i++) { this.chars[this.length]=t.chars[i]; this.length++; } }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)//8.刪除子串 publicbooleandelete(intpos,intlen){ if(pos<0||pos>(this.length-len)) returnfalse; for(inti=pos+len;i<this.length;i++) this.chars[i-len]=this.chars[i]; this.length=this.length-len; returntrue; }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

//9.插入子串 publicbooleaninsert(intpos,SeqStringt){ if(pos<0||pos>this.length) returnfalse; if(this.length+t.getLength()>this.maxSize){ char[]a=newchar[this.length]; for(inti=0;i<this.length;i++) a[i]=this.chars[i]; this.maxSize=this.length+t.getLength(); this.chars=newchar[this.maxSize]; for(inti=0;i<a.length;i++) this.chars[i]=a[i]; } for(inti=this.length-1;i>=pos;i--) chars[i+t.getLength()]=chars[i]; for(inti=0;i<t.getLength();i++) chars[i+pos]=t.chars[i]; this.length=this.length+t.getLength(); returntrue; }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

//10、求子串 publicSeqStringsubString(intpos,intlen){ if(pos+len>this.length) returnnull; SeqStringa=newSeqString(len); for(inti=0;i<len;i++) { a.chars[i]=this.chars[pos+i]; a.length++; } returna; }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

//11、查找子串 publicintindexOf_BF(SeqStringt,intpos){ if(t.getLength()==0||this.length<t.getLength()) return-1; inti=pos,j=0; while(i<this.length&&j<t.getLength()){//循環(huán)比較,主串和模式串都不能超過長度 if(this.chars[i]==t.chars[j]){ i++; j++; } else{ i=i-j+1; j=0; } } if(j>=t.getLength()){ returni-t.getLength(); } else{ return-1; } } publicvoidstringOut(){ for(inti=0;i<this.length;i++) System.out.print(chars[i]); System.out.print("\n"); }}

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

//主程序importjava.util.Scanner;publicclassTest{ publicstaticvoidmain(Stringargs[]){ Stringstr="HelloWorld!\nIloveprograming!\nIlovedatastructure!"; SeqStrings=newSeqString(str); intflag=1; intchoice; while(flag==1) { menu(); System.out.print("請輸入您的選擇:"); Scannersc=newScanner(System.in); choice=sc.nextInt(); switch(choice){ case0:flag=0;break; case1:strout(s);break; case2:find(s);break; case3:strDelete(s);break; case4:strInsert(s);break; case5:clear(s);break; case6:total(s);break; default: System.out.println("輸入有誤，請重新輸入！"); } } System.out.println("感謝您的使用！"); }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

publicstaticvoidmenu(){ System.out.println("********************************"); System.out.println("********歡迎使用文本剪輯器*********"); System.out.println("*****1.輸出****"); System.out.println("*****2.查找****"); System.out.println("*****3.刪除****"); System.out.println("*****4.插入****"); System.out.println("*****5.清空****"); System.out.println("*****6.統(tǒng)計(jì)總字符數(shù)****"); System.out.println("*****0.退出****"); System.out.println("********************************"); } publicstaticvoidstrout(SeqStringstring){ if(string.getLength()!=0) string.stringOut(); else System.out.println("該文本沒有內(nèi)容！"); }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

publicstaticvoidfind(SeqStringstring){ System.out.print("請輸入要查找的內(nèi)容"); Scannersc=newScanner(System.in); Stringstr=sc.nextLine(); SeqStrings=newSeqString(str); intnum=0; intstart=0; while(start+s.getLength()<=string.getLength()){ intlocation=string.indexOf_BF(s,start); if(location==-1) { if(num==0) System.out.print("文本中沒有該內(nèi)容"); break; } else { if(num==0) System.out.print("文本中出現(xiàn)該內(nèi)容的位置是："); num++; System.out.print(""+location); start=location+s.getLength()-1; } } System.out.println("\n共計(jì)出現(xiàn)"+num+"次"); }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

publicstaticvoidstrDelete(SeqStringstring){ Scannersc=newScanner(System.in); System.out.print("請輸入要?jiǎng)h除的位置："); intlocation=sc.nextInt(); System.out.print("請輸入要?jiǎng)h除的長度："); intlen=sc.nextInt(); if(string.delete(location,len)) System.out.println("刪除完成！"); else System.out.println("刪除失?。?); }

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)

publicstaticvoidstrInsert(SeqStringstring){ System.out.print("請輸入要插入的位置："); Scannersc=newScanner(System.in); intlocation=sc.nextInt(); System.out.print("請輸入要插入的內(nèi)容："); Scannersc1=newScanner(System.in); Stringstr=sc1.nextLine(); SeqStrings=newSeqString(str); if(string.insert(location,s)) System.out.println("插入完成！"); else System.out.println("插入失敗！"); } publicstaticvoidclear(SeqStringstring){ string.clear(); System.out.println("清空完成！"); } publicstaticvoidtotal(SeqStringstring){ System.out.println("共有"+string.getLength()+"個(gè)字符"); }}

典型工作任務(wù)5.3串軟件代碼設(shè)計(jì)使用數(shù)據(jù)結(jié)構(gòu)中的串算法編寫簡單文本編輯程序，通過JDK編譯和運(yùn)行，按照菜單輸入對應(yīng)的字符進(jìn)行測試，選擇“1”，輸出字符串，運(yùn)行結(jié)果如圖5-14所示。選擇“2”，查找字符串“l(fā)ike”的位置，未找到，運(yùn)行結(jié)果如圖5-15所示。

圖5-14輸出字符串運(yùn)行結(jié)果圖圖5-15查找字符串運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行運(yùn)行簡單文本編輯器處理程序，選擇菜單“2”查找字符串“l(fā)ove”出現(xiàn)的位置，如圖5-16所示，選擇菜單“3”，輸入要?jiǎng)h除字符串的位置及長度，刪除對應(yīng)字符串，如圖5-17所示。

圖5-16查找字符串“l(fā)ove”運(yùn)行結(jié)果圖圖5-17刪除字符串運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行運(yùn)行簡單文本編輯器處理程序，選擇菜單“1”輸出執(zhí)行上述操作后的字符串，如圖5-18所示，選擇菜單“4”，輸入要插入字符串的位置及字符串值，如圖5-19所示。圖5-18輸出字符串運(yùn)行結(jié)果圖圖5-19插入字符串運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行運(yùn)行簡單文本編輯器處理程序，選擇菜單“1”輸出執(zhí)行上述操作后的字符串，如圖5-20所示，選擇菜單“6”，統(tǒng)計(jì)字符串中的字符總個(gè)數(shù)，如圖5-21所示。圖5-20輸出字符串運(yùn)行結(jié)果圖圖5-21統(tǒng)計(jì)字符數(shù)運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行運(yùn)行簡單文本編輯器處理程序，選擇菜單“5”清空字符串，運(yùn)行結(jié)果如圖5-22所示，選擇菜單“1”，無字符串輸出，如圖5-23所示。圖5-22清空字符串運(yùn)行結(jié)果圖圖5-23無字符串輸出運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行運(yùn)行簡單文本編輯器處理程序，選擇菜單“0”退出系統(tǒng)，運(yùn)行結(jié)果如圖5-24所示。圖5-24退出系統(tǒng)運(yùn)行結(jié)果圖

典型工作任務(wù)5.4串軟件測試執(zhí)行5.5.1

初始化模塊測試

使用順序結(jié)