數(shù)據(jù)結(jié)構(gòu)（Java語言） 課件 淡海英 項(xiàng)目5、6 串-模式匹配、矩陣-核算產(chǎn)品費(fèi)用

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

5.2.2串的存儲結(jié)構(gòu)1.串的順序存儲使用順序存儲的串稱為順序串，可用一組地址連續(xù)的空間存儲字符序列，即使用字符數(shù)組來存儲串中的字符，串中的每一個字符占據(jù)一個空間。例如，字符串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)的，串中的每一個字符都用一個結(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)造一個能保存n個字符的串 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++)//對串中的值逐個進(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位置開始向后移動長度為t.getLength個字符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)前串中尋找某個子串的過程稱為模式匹配，其中該子串稱為模式串。Brute-Force算法又稱為樸素的模式匹配，是一種帶回溯的匹配算法。設(shè)主串S="ababc"，子串T="abc"，pos的值為0，即從主串S的第0個位置開始進(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個位置重新開始匹配，子串T從頭開始（即從第0個位置開始），如圖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個位置重新開始匹配，子串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]){ //主串和模式串依次比較每一個字符i++;j++;}else{ //進(jìn)行回溯，過渡到下一趟i=i-j+1; //轉(zhuǎn)向主串中下一字符j=0; //子串重頭開始}}if(j>=t.getLength()){ //模式串已經(jīng)循環(huán)完畢returni-t.getLength(); //匹配成功，第一個字母的索引號}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("請輸入要刪除的位置："); intlocation=sc.nextInt(); System.out.print("請輸入要刪除的長度："); 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()+"個字符"); }}

典型工作任務(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”，輸入要刪除字符串的位置及長度，刪除對應(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ì)字符串中的字符總個數(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é)構(gòu)存儲字符串實(shí)現(xiàn)簡單文本編輯器程序，在初始化模塊中可能出現(xiàn)未給數(shù)組分配空間、串初始化時(shí)直接賦值等。表4-1初始化模塊測試表

典型工作任務(wù)5.5串軟件文檔編寫編號摘要描述預(yù)期結(jié)果正確代碼sxc-csh-01存儲串的數(shù)組沒有分配空間程序報(bào)錯增加代碼：this.chars=newchar[this.maxSize];sxc-csh-02串在初始化時(shí)直接給值程序報(bào)錯增加代碼：publicSeqString(Strings){ this.maxSize=s.length(); this.chars=s.toCharArray(); this.length=s.length(); }5.5.2

查找模塊測試

典型工作任務(wù)5.5串軟件文檔編寫編號摘要描述預(yù)期結(jié)果正確代碼sxc-cz-01未找到子串時(shí)，沒有提示提示用戶增加代碼：if(num==0)System.out.print("文本中沒有該內(nèi)容");sxc-cz-02查找出來的子串位置中，個別位置輸出了兩遍每個位置只輸出一遍修改代碼：start=location+s.getLength()-1;5.5.3

刪除模塊測試

典型工作任務(wù)5.5串軟件文檔編寫編號摘要描述預(yù)期結(jié)果正確代碼sxc-sc-01是否刪除成功未提示用戶提示用戶修改代碼：if(string.delete(location,len))System.out.println("刪除完成！");elseSystem.out.println("刪除失?。?);5.5.4

插入模塊測試

典型工作任務(wù)5.5串軟件文檔編寫

編號摘要描述預(yù)期結(jié)果正確代碼sxc-cr-01無法接收到用戶輸入的子串正確接收修改代碼：Scannersc1=newScanner(System.in);Stringstr=sc1.nextLine();sxc-cr-02新增字符串無響應(yīng)程序報(bào)錯增加代碼：SeqStrings=newSeqString(str);sxc-cr-03是否新增子串成功未提示用戶提示用戶修改代碼：if(string.insert(location,s))System.out.println("插入完成！");elseSystem.out.println("插入失敗！");

典型工作任務(wù)5.6串項(xiàng)目驗(yàn)收交付驗(yàn)收項(xiàng)目驗(yàn)收標(biāo)準(zhǔn)驗(yàn)收情況驗(yàn)收測試功能1、項(xiàng)目主要功能

（1）存儲文本內(nèi)容；

（2）查找指定文本內(nèi)容；

（3）刪除指定文本內(nèi)容；

（4）插入指定文本內(nèi)容；

（5）清空文本內(nèi)容；

（6）統(tǒng)計(jì)文本長度；

（7）輸出整個文本。

2、數(shù)據(jù)及界面要求

（1）文本內(nèi)容不宜過長，符合編碼規(guī)則；

（2）輸出界面上信息清晰、完整、正確無誤；

（3）算法調(diào)用后實(shí)現(xiàn)對應(yīng)的功能

性能運(yùn)行代碼后響應(yīng)時(shí)間小于3秒

（1）該標(biāo)準(zhǔn)適用于所有功能項(xiàng)；

（2）該標(biāo)準(zhǔn)適用于所有被測數(shù)據(jù)。

驗(yàn)收項(xiàng)目驗(yàn)收標(biāo)準(zhǔn)驗(yàn)收情況軟件設(shè)計(jì)需求規(guī)范說明需求符合正確；

功能描述正確；

語言表述準(zhǔn)確。

設(shè)計(jì)說明方法的定義、功能、參數(shù)和返回值描述。

數(shù)據(jù)結(jié)構(gòu)說明順序串的存儲結(jié)構(gòu)；

順序串的操作算法有窮、確定、可行、輸入、輸出；

程序源代碼類、方法的定義與文檔相符；

類、方法、變量、數(shù)組、指針等命名規(guī)范，符合“見名知義”的原則；

注釋清晰、完整、語言準(zhǔn)確、規(guī)范；

實(shí)參數(shù)據(jù)有效，無歧義、無重復(fù)、無沖突；

代碼質(zhì)量較高，無明顯功能缺陷；

冗余代碼少。

測試測試數(shù)據(jù)覆蓋全部需求及功能項(xiàng)；

測試數(shù)據(jù)充分、完整，；

測試結(jié)果功能全部實(shí)現(xiàn)。

用戶使用使用說明覆蓋全部功能，無遺漏功能項(xiàng)；

運(yùn)行結(jié)果正確，達(dá)到預(yù)期目標(biāo)；

建議使用軟件JDK或者eclipse。

感謝觀看項(xiàng)目六矩陣---核算產(chǎn)品費(fèi)用目錄項(xiàng)目六5123

典型工作任務(wù)6.1矩陣項(xiàng)目需求分析典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)典型工作任務(wù)6.3矩陣軟件代碼設(shè)計(jì)典型工作任務(wù)6.4矩陣軟件測試執(zhí)行典型工作任務(wù)6.5矩陣軟件文檔編寫46典型工作任務(wù)6.6矩陣項(xiàng)目驗(yàn)收交付知識目標(biāo)掌握數(shù)組的概念與性質(zhì)掌握數(shù)組的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)掌握矩陣的壓縮存儲掌握矩陣的基本運(yùn)算技能目標(biāo)能進(jìn)行項(xiàng)目需求分析能進(jìn)行矩陣的算法分析及編程能用矩陣的知識編程解決問題能進(jìn)行軟件測試及項(xiàng)目功能調(diào)整能撰寫格式規(guī)范的軟件文檔思政目標(biāo)掌握數(shù)組順序存儲，樹立規(guī)矩意識掌握稀疏矩陣特殊處理，培養(yǎng)善于思考創(chuàng)新意識鍛煉發(fā)現(xiàn)問題分析問題解決問題的邏輯思維編寫算法細(xì)致嚴(yán)謹(jǐn)，養(yǎng)成科學(xué)嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)習(xí)慣總體要求

有一家光明食品廠，它們的產(chǎn)品包括罐頭、糖果、巧克力、飲料、啤酒。為了核算各類產(chǎn)品在一年中的成本費(fèi)用，我們可以按月統(tǒng)計(jì)每類產(chǎn)品的成本，然后把一年12個月的統(tǒng)計(jì)表累加起來，就可以核算出各類產(chǎn)品的成本以及企業(yè)一年的生產(chǎn)成本。

為了分類統(tǒng)計(jì)，我們可以設(shè)計(jì)如表6-1所示的產(chǎn)品成本月統(tǒng)計(jì)表。

表6-1產(chǎn)品成本月統(tǒng)計(jì)表（單位：萬元）典型工作任務(wù)6.1矩陣項(xiàng)目需求分析產(chǎn)品名稱材料成本人工成本制造成本罐頭1.451.230.35糖果0.980.870.65巧克力1.430.940.89飲料0.870.650.35啤酒0.840.610.56

有為了便于核算產(chǎn)品費(fèi)用，本項(xiàng)目以光明食品廠的產(chǎn)品各項(xiàng)成本為例，使用數(shù)組對各類產(chǎn)品的各項(xiàng)費(fèi)用進(jìn)行輸入及計(jì)算，具體需求如下：(1)使用數(shù)組存儲每個月產(chǎn)品成本；(2)顯示每個月的產(chǎn)品成本矩陣；(3)產(chǎn)品成本矩陣可進(jìn)行轉(zhuǎn)置；(4)產(chǎn)品成本矩陣可進(jìn)行加法；(5)輸出矩陣操作后結(jié)果。典型工作任務(wù)6.1矩陣項(xiàng)目需求分析6.2.1數(shù)組的概念

數(shù)組是相同類型的數(shù)據(jù)有序的集合，數(shù)組中每一個數(shù)據(jù)通常稱為數(shù)組元素，數(shù)組元素用下標(biāo)識別，下標(biāo)的個數(shù)取決于數(shù)組的維數(shù)。

如果是一個下標(biāo)確定一個元素，就是一維數(shù)組；如果是兩個下標(biāo)能確定一個元素，就是二維數(shù)組?！咎崾尽可鲜鰹閙×n階矩陣是個二維數(shù)組，其中每個元素都可以用下標(biāo)變量aij來表示，i為元素的行下標(biāo)，j為元素的列下標(biāo)典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6.2.2數(shù)組結(jié)構(gòu)具有的性質(zhì)1．?dāng)?shù)組元素?cái)?shù)目固定。一旦說明了一個數(shù)組結(jié)構(gòu)，其元素不再有增減變化；

2．?dāng)?shù)組中數(shù)據(jù)元素具有相同的數(shù)據(jù)類型；3．?dāng)?shù)組元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序；4.數(shù)組元素的值由數(shù)組名和下標(biāo)唯一確定；5.數(shù)組名是數(shù)組的首地址，每個元素是連續(xù)存放的。對數(shù)組可以施加的操作主要有以下兩種：取值操作：給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素。賦值操作：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6.2.3數(shù)組的順序存儲

一般采用順序存儲結(jié)構(gòu)表示數(shù)組。順序存儲結(jié)構(gòu)即用一塊連續(xù)的存儲空間存儲數(shù)組元素。（1）按行優(yōu)先存儲：一行分配完了接著分配下一行。如前面的m×n階矩陣的二維數(shù)組，按行存儲數(shù)據(jù)：a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn（2）按列優(yōu)先存儲：一列一列地存放。如前面的m×n階矩陣的二維數(shù)組，按列存儲數(shù)據(jù)：a11,a21,…,am1,a12,a22,…,am2,…,a1n,a2n,…,amn典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)對于一維數(shù)組A[n],數(shù)據(jù)元素的存儲地址為LOC(i)=LOC(1)+i×L(1≤i≤n),其中，LOC(i)是第i個元素的存儲地址，LOC(1)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。對于一個m×n的二維數(shù)組A[m][n]，以行為主序存儲時(shí)，數(shù)組元素aij的存儲地址為：LOC(aij)=LOC(a11)+((i-1)×n+j-1)×L(0≤i≤m,0≤j≤n)其中，LOC(aij)是第i行第j列數(shù)組元素的存儲地址，LOC(a11)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。若以列為主序存儲二維數(shù)組A[m][n]，則數(shù)組元素aij的存儲地址為：LOC(aij)=LOC(a11)+((j-1)×m+i-1)×L(1≤i≤m,1≤j≤n)典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

將計(jì)算數(shù)組元素存儲地址的公式推廣到一般情況，可以得到n維數(shù)組A[m1][m2]…[mn]的數(shù)據(jù)元素a[i1][i2]…[in]的存儲地址：LOC(i1,i2,…,in)=LOC(0,0,…,0)+(i1×m2×…mn+i2×m3×…×mn+…+in-1×mn+in)×L典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

6.2.4特殊矩陣的壓縮存儲

特殊矩陣是具有很多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣。m×n矩陣用二維數(shù)組存儲時(shí)，最少需要m×n個存儲單元。當(dāng)矩陣的階數(shù)比較大時(shí)，會浪費(fèi)大量的存儲空間，顯然是不合適的。

1.對稱矩陣若n階矩陣滿足性質(zhì)：aij=aji

，則稱為對稱矩陣。為每一對對稱元素分配一個存儲空間，因此可以將n×n個元素存儲到n(n+1)/2個存儲單元中。典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

對于任意給定的一組下標(biāo)(i,j),均可以在S中找到矩陣元素aij，反之，對于所有的k=1,2,…,n(n+1)/2,都能確定s中的元素在矩陣中的位置(i,j)。

典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)a00a01a02…a0n-1a11…an-1,0…an-1,n-12.三角矩陣

三角矩陣分為上三角矩陣和下三角矩陣。下三角矩陣是指矩陣的主對角線（不包括主對角線）上方的元素的值均為0；上三角矩陣是指矩陣的主對角線（不包括主對角線）下方的元素的值均為0。

下三角矩陣上三角矩陣典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.對角矩陣

對角矩陣是指矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，即除去主對角線上和直接在主對角線上、下方若干條對角線上的元素之外，其余元素皆為零。若以一維數(shù)組進(jìn)行存儲，則存儲形式如下：典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)123456789101112a12a21a22a23a32a33a34a43a44a45a54a55

6.2.4特殊矩陣的壓縮存儲矩陣階數(shù)比較大，零元素個數(shù)比較多，非零元素個數(shù)比較少，且分布無規(guī)律，這類矩陣就是稀疏矩陣。設(shè)矩陣A是一個m×n的矩陣，其中有t個非零元素，設(shè)稱為稀疏因子，如果<=0.05，矩陣A就是稀疏矩陣。典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1.三元組表存儲對于稀疏矩陣中的每個元素，都由行下標(biāo)、列下標(biāo)和數(shù)值三個部分唯一確定，因此，可以用這三項(xiàng)內(nèi)容表示稀疏矩陣中的元素，這就是三元組表示法，如下形式：（i,j,value）i表示非零元素的行下標(biāo)，j表示非零元素的列下標(biāo)，value表示非零元素的值。典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)行下標(biāo)列下標(biāo)元素值13315221152611352254763321）三元組順序表的定義publicclassTripleNode//三元組結(jié)點(diǎn)類{ publicintrow;//行號 publicintcol; //列號 publicdoublevalue; //元素值

publicTripleNode(introw,intcol,doublevalue)//有參構(gòu)造函數(shù){ this.row=row; this.col=col; this.value=value;}publicTripleNode()//無參構(gòu)造函數(shù){this(1,1,0);}}典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)稀疏矩陣的三元組順序表類定義：publicclassSparseMatrix{ publicTripleNodedata[]; //三元組表 publicintrows; //行數(shù) publicintcols; //列數(shù) publicintnums; //非零元素個數(shù) publicSparseMatrix(intmaxSize){ //構(gòu)造方法 data=newTripleNode[maxSize];//為順序表分配maxSize個存儲單元 for(inti=0;i<data.length;i++){

data[i]=newTripleNode(); } rows=0; cols=0; nums=0; } publicvoidprintMatrix()//打印輸出稀疏矩陣 { System.out.println("稀疏矩陣的三元組存儲結(jié)構(gòu)"); System.out.print("行數(shù):"+rows+",列數(shù)"+cols+",非零元素個數(shù)："+nums+"\n");for(inti=0;i<nums;i++) System.out.print(data[i].row+"\t"+data[i].col+"\t"+data[i].value+"\n");} }典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2）三元組表的基本操作

初始化三元組順序表publicSparseMatrix(doublemat[][]) { inti,j,k=0,count=0; rows=mat.length; cols=mat[0].length; for(i=0;i<rows;i++) //統(tǒng)計(jì)非零元素的個數(shù) for(j=0;j<mat[i].length;j++) if(mat[i][j]!=0) count++; nums=count; //非零元素的個數(shù) data=newTripleNode[nums];//申請三元組結(jié)點(diǎn)空間 for(i=0;i<rows;i++) for(j=0;j<mat[i].length;j++) if(mat[i][j]!=0) { data[k]=newTripleNode(i,j,mat[i][j]); //建立三元組 k++; } }典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置是一種簡單的矩陣運(yùn)算，指的是把矩陣中每個元素的行號和列號互換。

轉(zhuǎn)置-------

矩陣A’轉(zhuǎn)置矩陣A’的三三元組表元組表(按行優(yōu)先)典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)行下標(biāo)列下標(biāo)元素值3135121215621153224573632行下標(biāo)列下標(biāo)元素值1215313363245751253226211矩陣轉(zhuǎn)置算法：publicSparseMatrixtran() { SparseMatrixtr=newSparseMatrix(nums); tr.cols=rows; tr.rows=cols; tr.nums=nums; intn=0; for(intcol=0;col<cols;col++) for(intm=0;m<nums;m++) if(data[m].col==col) { tr.data[n].row=data[m].col; tr.data[n].col=data[m].row; tr.data[n].value=data[m].value; n++; } returntr; }典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(3)矩陣快速轉(zhuǎn)置快速轉(zhuǎn)置算法的思想為：按三元組表A的次序進(jìn)行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。轉(zhuǎn)置過程中的元素并不連續(xù)放入到B.data，而是直接放到B.data中應(yīng)有的位置上，只需對A.data掃描一次。因?yàn)锳中第一列的第一個非零元素一定存儲在B.data[1]中，如果還不知道第一列非零元素的個數(shù)，那么第二列的第一個非零元素在B.data中的位置便等于第一列的第一個元素在B.data中的位置加上第一列的非零元素的個數(shù)，依次類推，因?yàn)锳中三元組的存放順序是先行后列，對同一行來說，必定先遇到列號小的元素，這樣只需要掃描一遍A.dta即可。典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

矩陣快速轉(zhuǎn)置算法：publicSparseMatrixfasttran(){

SparseMatrixtr=newSparseMatrix(nums);//創(chuàng)建矩陣對象

tr.cols=rows; //行數(shù)變列數(shù) tr.rows=cols; //列數(shù)變行數(shù) tr.nums=nums; //非零元素個數(shù) inti,j=1,k=0; int[]num,cpos; if(nums>0) { num=newint[cols+1]; cpos=newint[cols+1]; for(i=1;i<=cols;i++) { num[i]=0; } for(i=1;i<=nums;i++) { j=data[i].col; num[j]++; } cpos[1]=1;典型工作任務(wù)6.2矩陣數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

for(i=2;i<=cols;i++){ cpos[i]=cpos[i-1]+num[i-1];}//執(zhí)行轉(zhuǎn)置操作for(i=1;i<=nums;i++) //掃描整個三元組順序表{ j=data[i].col; k=cpos[j]; tr.data[k].row=data[i].col;