《數(shù)據(jù)結(jié)構(gòu)與算法項目化教程》課件第4章

學習情境４串4.1任務一認識串4.2任務二串的存儲結(jié)構(gòu)4.3任務三程序?qū)崿F(xiàn)串的操作字符串(string，簡稱串)是由字符組成的有限序列，它是計算機中最常用的一種非數(shù)值型的數(shù)據(jù)。從邏輯結(jié)構(gòu)看，串是一種特殊的線性表，特殊性表現(xiàn)在每個數(shù)據(jù)是一個字符，這種特殊性使得其存儲結(jié)構(gòu)和運算與線性表存在一定的差異。串的各種操作與線性表不同。本學習情境主要學習串的常見基本操作。本學習情境首先介紹字符串的基本概念，分析串的順序和鏈式兩種存儲結(jié)構(gòu)存儲的優(yōu)缺點，然后以Java語言的字符串類String實現(xiàn)串的各種操作算法。

4.1任務一認識串4.1.1子任務1初識串

1．認識串的定義串是一種特殊的線性表，每個數(shù)據(jù)是一個字符。一個串記為S?="s0s1……sn-1"其中，n≥0，S是串名，字符系列s0s1……sn-1是串值，si(i=0，1，…，n-1)為特定字符集中的一個字符。一個串中包含的字符個數(shù)稱為串的長度。如S="String"，串S的長度為6。長度為0的串稱為空串，記作""，空串不包含任何字符。與空串不同，由一個或多個空格構(gòu)成的非空字符串，如?""?稱為空格串，不是空串。在Java語言中，由雙引號括起來的是字符串常量，數(shù)據(jù)類型是String類，注意對比由單引號界定的數(shù)據(jù)類型是字符，其數(shù)據(jù)類型是char，占用2個字節(jié)，如'S'。在Java中，無論半角英語字母("ABab")、數(shù)字("1234")，還是漢字("數(shù)據(jù)結(jié)構(gòu)")、全角的英語字母("ABab")或全角數(shù)字("1234")，每個字符長度都是1，上述圓括號、雙引號中字符串的長度均為4。一個字符在串中的位置指該字符串中的序號(index)，用一個整數(shù)表示。約定串中第一個字符的序號為0，最后一個是length-1，-1表示某字符不在指定串中。

2．子串由串S中任意連續(xù)字符組成的一個子序列sub稱為S的子串。S稱為sub的主串。例如，"ing"是"String"的子串。特別地，空串是任意串的子串。任意串S都是它自身的子串。除自身外，S的其他子串稱為S的真子串。子串的序號指該子串的第一個字符在主串中的序號。例如："ing"?在?"String"?中的序號為3。4.1.2子任務2串的基本運算對串通常有如下基本運算：

(1)賦值運算：將一個串S1的內(nèi)容全部傳送給串S。

(2)求長度運算：返回串S的長度值。

(3)連接運算：將串S1和S2連接成為一個新串。

(4)求子串：返回串S中從第i個數(shù)據(jù)開始的到j所組成的子串。

(5)判斷串是否相等：比較串是否相等，因而可采用equal方法返回false與true，分別表示相等關系的不成立和成立。

(6)插入運算：將子串S1插入到串S的從第i個字符開始的位置上。

(7)刪除運算：刪除串S中從第i個字符開始的j個字符。4.2任務二串的存儲結(jié)構(gòu)由于串是一種特殊的線性表，故可采用線性的存儲結(jié)構(gòu)形式，即串有順序存儲和鏈式存儲兩種存儲結(jié)構(gòu)。4.2.1子任務1串的順序存儲結(jié)構(gòu)

1．認識串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)采用字符數(shù)組將串中的字符序列依次連續(xù)存儲在數(shù)組的相鄰單元中。使用字符數(shù)組有兩種方案：數(shù)組容量等于或大于串長。當數(shù)組容量等于串長時，串不易增加字符，通常用于存儲串常量；當數(shù)組容量大于串長時，便于增加字符，通常用于存儲串變量，此時還要有一個整型變量記載串的長度。串的順序存儲結(jié)構(gòu)如圖4-1所示。圖4-1串的順序存儲結(jié)構(gòu)

2．串的順序存儲結(jié)構(gòu)的優(yōu)缺點順序存儲的串具有隨機存取的優(yōu)點，存取指定位置字符串的時間復雜度為O(1)；缺點是插入和刪除數(shù)據(jù)時需要移動數(shù)據(jù)，平均移動數(shù)據(jù)量是串長度的一半；當數(shù)組容量不夠時，需要重新申請一個更大的數(shù)組，并復制原數(shù)組中的所有數(shù)據(jù)。插入和刪除操作的時間復雜度為O(n)。4.2.2子任務2串的鏈式存儲結(jié)構(gòu)

1．認識串的鏈式存儲結(jié)構(gòu)為便于插入和刪除運算的實現(xiàn)，可采用鏈表結(jié)構(gòu)來存儲串。在前面所討論線性表的存儲結(jié)構(gòu)中，用鏈表中的每個節(jié)點存儲一個數(shù)據(jù)，然而，這一方法顯然不適用于串的存儲，因為一個節(jié)點中的指針所需要的存儲空間通常要多于一個字節(jié)，例如可能是4個字節(jié)，由此造成存儲空間的浪費。為此，可將每個節(jié)點中多存放幾個字符。在這個情況下，將每個節(jié)點中最多能存儲的數(shù)據(jù)個數(shù)定義為節(jié)點大小或容量。例如，節(jié)點大小為4的鏈串存儲形式。顯然，節(jié)點容量大于1的鏈串能節(jié)省存儲空間，但運行不便，而節(jié)點容量為1的鏈表串則浪費存儲空間，但是運算要方便得多。串的鏈式存儲結(jié)構(gòu)示意圖如圖4-2所示。

2．串的鏈式存儲結(jié)構(gòu)的優(yōu)缺點鏈式存儲的串，存取指定位置字符的時間復雜度為O(n)；插入/刪除操作不需要移動數(shù)據(jù)，但占用存儲空間由于增加引用而增大。圖4-2串的鏈式存儲結(jié)構(gòu)示意圖4.3任務三程序?qū)崿F(xiàn)串的操作特別說明：

(1)前面的線性表、棧和隊列的程序?qū)崿F(xiàn)的程序文件名和方法名等都采用英文命名，當然命名也可以采用漢字的拼音。盡管本教程不提倡用拼音來命名，但出于對一部分學習者而言，用拼音命名示例也未償不可。所以本學習情境串的程序?qū)崿F(xiàn)使用拼音命名，實際實現(xiàn)中學習者可以根據(jù)自己的情況而決定。

(2)主程序的菜單循環(huán)結(jié)構(gòu)采用for(;;)另外一種的方法，for()不需要任務條件，但在for之前需要有標號，在循環(huán)體中需要用break標號來中止循環(huán)，格式如下：標號：

for(;;){中止標號；

}具體實現(xiàn)見Main.java程序。4.3.1子任務1串的基本操作和算法

1．串的操作菜單本學習情境創(chuàng)建的串操作菜單如下：

2．串操作的基本算法串操作的基本算法采用Java系統(tǒng)的String字符串的功能實現(xiàn)，難度不大，所以只給出中文描述算法，程序語言描述可以直接參考程序的實現(xiàn)。

(1)賦值。中文描述算法：使用Scanner鍵盤輸入任意字符串賦值給串

(2)顯示串的內(nèi)容。中文描述算法： 串不為空 使用系統(tǒng)的輸出功能輸出串

(3)判斷串是否相等。中文描述算法： 如果兩個串不為空 如果兩個串相同 輸出“兩個串相等” 否則 輸出“兩個串不相等” 否則 輸出“串還沒賦值”

(4)求串的長度。中文描述算法： 如果串不空 調(diào)用串長度的方法 輸出串的長度 否則 輸出“串還沒賦值”

(5)截取字符串。截取字符串操作示意圖如圖4-3所示。中文描述算法： 如果串非空 提示串的實際長度 輸入截取開始位置i

輸入截取結(jié)束位置j

如果開始和結(jié)束位置合法 調(diào)用截取方法截取子字符串 否則 提示截取位置出錯 否則 提示串還沒賦值圖4-3截取子串的操作

(6)連接串。連接串操作示意圖如圖4-4所示。中文描述算法： 如果兩個串都非空 調(diào)用字符串連接方法 否則 提示串還沒賦值圖4-4連接串的操作

(7)插入。插入操作示意圖如圖4-5所示。中文描述算法： 如果串非空 輸入要插入的位置 輸入要插入的串 截取插入位置前的子串 連接插入的串 連接插入位置后的串 否則 提示串還沒賦值圖4-5串的插入操作

(8)刪除。刪除操作示意圖如圖4-6所示。中文描述算法： 如果串非空 輸入刪除開始位置 輸入要刪除的位數(shù) 截取刪除位置前的子串 連接刪除位置后的子串 否則 提示串還沒賦值圖4-6串的刪除操作

(9)字母大小寫轉(zhuǎn)換。中文描述算法： 輸入任意字符串 調(diào)用大寫轉(zhuǎn)換的方法并輸出 調(diào)用小寫轉(zhuǎn)換的方法并輸出4.3.2子任務2創(chuàng)建主程序菜單創(chuàng)建本學習情境的包，包名為ch4String，在該包下創(chuàng)建主程序Main.java，構(gòu)建串操作主程序的菜單；接著在包中再創(chuàng)建串操作程序Chuan.java文件，按串的算法創(chuàng)建各方法。與線性表操作的程序?qū)崿F(xiàn)一樣，創(chuàng)建一個操作方法就到主程序調(diào)用并調(diào)試、運行程序。編寫程序一定要分塊進行，把程序的錯誤控制在可調(diào)試的范圍內(nèi)，千萬不可把主程序和串操作程序的代碼都輸入后才調(diào)試，那會出現(xiàn)幾十個錯誤，甚至幾百個錯誤，那樣是難于調(diào)試和查錯的。由于有了前面的程序?qū)崿F(xiàn)操作基礎，因而不再占用篇幅講解，直接給出程序代碼。

1．串的主程序Main.java完整程序代碼

packagech4String;

importjava.util.Scanner;

publicclassMain{

publicstaticvoidmain(String[]args){

ScannerChoose=newScanner(System.in);

Chuanchuan=newChuan();

try{

Text1:

for(;;){

System.out.println("\n★☆★☆★☆★☆★☆★☆★★☆★");System.out.println("=====串的操作菜單=====");System.out.println("★☆★☆★☆★☆★☆★☆★★☆★");System.out.print("1-賦值2-顯示3-判斷串是否相等");System.out.print("4-求串的長度5-截取字符串6-連接串");System.out.print("7-插入8-刪除9-字母大小寫轉(zhuǎn)換0-退出\n");System.out.println("\n請選擇:");intchoose=Choose.nextInt();switch(choose)//開始菜單選擇

{case1://賦值

chuan.FuZhi();break;case7://插入

chuan.Charu();break;case8://刪除

chuan.ShanChu();break;case9://大小寫轉(zhuǎn)換

chuan.ZhuanHuan();break;case0://退出

{chuan.TuiChu();breakText1;}default:System.out.println("輸入錯誤!請重新輸入.");}}}catch(Exceptionex){System.out.print("您輸入了非法字符!系統(tǒng)自動結(jié)束."+ex.toString());}}}2．串的操作Chuan.java完整程序代碼

packagech4String;

importjava.util.Scanner;

publicclassChuan{

Scannerinput=newScanner(System.in);

StringChuanS;//串S

StringChuanT;//串T

StringChuanR;//串R

StringChuanL;//連接串L

publicvoidFuZhi(){//賦值

System.out.print("請輸入串S:");//輸入串SChuanS=input.next();System.out.print("請輸入串T:");//輸入串TChuanT=input.next();System.out.println("賦值成功!");}publicvoidXianShi(){//顯示串

if(ChuanS!=null){System.out.println("串S的值為:"+ChuanS);}elseif(ChuanS==null){System.out.println("串S還沒有賦值");}if(ChuanT!=null){System.out.println("串T的值為:"+ChuanT);}elseif(ChuanT==null){System.out.println("串T還沒有賦值");}if(ChuanR!=null){System.out.println("串R的值為:"+ChuanR);}if(ChuanL!=null){System.out.println("串L的值為:"+ChuanL);}}publicvoidPanDuan(){//判斷是否相等

if(ChuanS!=null&&ChuanT!=null){if(ChuanS.equals(ChuanT)){System.out.println("串S與串T的值相等.");}else{System.out.println("串S與串T的值不相等.");}if(ChuanS.length()==ChuanT.length()){System.out.println("串S與串T的長度相等.");}else{System.out.println("串S與串T的長度不相等.");}}else{System.out.println("串S或串T還沒有賦值");}}publicvoidChangDu(){//求串的長度

if(ChuanS!=null){System.out.println("串S的長度為:"+ChuanS.length());}elseif(ChuanS==null){System.out.println("串S還沒有賦值");}if(ChuanT!=null){System.out.println("串T的長度為:"+ChuanT.length());}elseif(ChuanT==null){System.out.println("串T還沒有賦值");}}publicvoidJieQu(){//截取字符串

if(ChuanS!=null){System.out.println("串S共有:"+ChuanS.length()+"位");System.out.print("請輸入要從串S第幾位開始截取:");intbeginIndex=input.nextInt();System.out.print("請輸入要截取到第幾位:");intendIndex=input.nextInt();if(beginIndex<ChuanS.length()&&endIndex<=ChuanS.length()){ChuanR=ChuanS.substring(beginIndex-1,endIndex);System.out.println("截取成功!截取的結(jié)果是："+ChuanR);}else{System.out.print("輸入的截取位置超出范圍");}}else{System.out.println("串T還沒有賦值.");}}publicvoidLianJie(){//連接串S和串Tif(ChuanS!=null&&ChuanT!=null){ChuanL=ChuanS.concat(ChuanT.toString());System.out.println("連接成功!連接串L為:"+ChuanL);}else{System.out.println("串S或串T還沒有賦值");}}publicvoidCharu(){//插入

if(ChuanS!=null){System.out.print("請輸入要在串S(長度為"+ChuanS.length()+")中插入的位置:");intnum=input.nextInt();System.out.print("請輸入插入串的值:");StringChuanC=input.next();ChuanS=ChuanS.substring(0,num-1)+ChuanC+ChuanS.replaceAll(ChuanS.substring(0,num-1),"");System.out.println("插入成功!插入后串S的值為:"+ChuanS);}else{System.out.println("串S還沒有賦值