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

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

4.1任務(wù)一認(rèn)識(shí)串4.1.1子任務(wù)1初識(shí)串

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

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

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

(2)求長(zhǎng)度運(yùn)算：返回串S的長(zhǎng)度值。

(3)連接運(yùn)算：將串S1和S2連接成為一個(gè)新串。

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

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

(6)插入運(yùn)算：將子串S1插入到串S的從第i個(gè)字符開(kāi)始的位置上。

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

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

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

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

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

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

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

for(;;){中止標(biāo)號(hào)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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-求串的長(zhǎng)度5-截取字符串6-連接串");System.out.print("7-插入8-刪除9-字母大小寫(xiě)轉(zhuǎn)換0-退出\n");System.out.println("\n請(qǐng)選擇:");intchoose=Choose.nextInt();switch(choose)//開(kāi)始菜單選擇

{case1://賦值

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

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

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

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

{chuan.TuiChu();breakText1;}default:System.out.println("輸入錯(cuò)誤!請(qǐng)重新輸入.");}}}catch(Exceptionex){System.out.print("您輸入了非法字符!系統(tǒng)自動(dò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("請(qǐng)輸入串S:");//輸入串SChuanS=input.next();System.out.print("請(qǐng)輸入串T:");//輸入串TChuanT=input.next();System.out.println("賦值成功!");}publicvoidXianShi(){//顯示串

if(ChuanS!=null){System.out.println("串S的值為:"+ChuanS);}elseif(ChuanS==null){System.out.println("串S還沒(méi)有賦值");}if(ChuanT!=null){System.out.println("串T的值為:"+ChuanT);}elseif(ChuanT==null){System.out.println("串T還沒(méi)有賦值");}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的長(zhǎng)度相等.");}else{System.out.println("串S與串T的長(zhǎng)度不相等.");}}else{System.out.println("串S或串T還沒(méi)有賦值");}}publicvoidChangDu(){//求串的長(zhǎng)度

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

if(ChuanS!=null){System.out.println("串S共有:"+ChuanS.length()+"位");System.out.print("請(qǐng)輸入要從串S第幾位開(kāi)始截取:");intbeginIndex=input.nextInt();System.out.print("請(qǐng)輸入要截取到第幾位:");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還沒(méi)有賦值.");}}publicvoidLianJie(){//連接串S和串Tif(ChuanS!=null&&ChuanT!=null){ChuanL=ChuanS.concat(ChuanT.toString());System.out.println("連接成功!連接串L為:"+ChuanL);}else{System.out.println("串S或串T還沒(méi)有賦值");}}publicvoidCharu(){//插入

if(ChuanS!=null){System.out.print("請(qǐng)輸入要在串S(長(zhǎng)度為"+ChuanS.length()+")中插入的位置:");intnum=input.nextInt();System.out.print("請(qǐng)輸入插入串的值:");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還沒(méi)有賦值