《數(shù)據(jù)結(jié)構(gòu)（java版）第4章串與數(shù)組課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)（java版）第4章串與數(shù)組課件.ppt（111頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)(Java(Java語(yǔ)言描述語(yǔ)言描述)第四章第四章 串與數(shù)組串與數(shù)組數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）第四章第四章 串與數(shù)組串與數(shù)組章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映教學(xué)內(nèi)容教學(xué)內(nèi)容4.1 串的基本概念串的基本概念 4.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu) 4.3 順序串的實(shí)現(xiàn)順序串的實(shí)現(xiàn) 4.4 串的模式匹配操作串的模式匹配操作 4.5 串的應(yīng)用舉例串的應(yīng)用舉例 4.6 數(shù)組的概念及順序存儲(chǔ)結(jié)構(gòu)數(shù)組的概念及順序存儲(chǔ)

2、結(jié)構(gòu) 4.7 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ) 4.8 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）第四章第四章 串與數(shù)組串與數(shù)組章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn)與難點(diǎn)重點(diǎn)：重點(diǎn)：u掌握串類型定義中各基掌握串類型定義中各基本操作的定義以本操作的定義以及串中基本操作的應(yīng)用。及串中基本操作的應(yīng)用。u掌握數(shù)組的定義、操作和存儲(chǔ)結(jié)構(gòu)掌握數(shù)組的定義、操作和存儲(chǔ)結(jié)構(gòu)難點(diǎn)：難點(diǎn)：u串的基本

3、操作的應(yīng)用，即如何運(yùn)用串串的基本操作的應(yīng)用，即如何運(yùn)用串的基本操作來(lái)實(shí)現(xiàn)其它串的復(fù)雜操作。的基本操作來(lái)實(shí)現(xiàn)其它串的復(fù)雜操作。u矩陣的壓縮存儲(chǔ)。矩陣的壓縮存儲(chǔ)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄1 1、串：串：是由是由零個(gè)零個(gè)或或多個(gè)多個(gè)字符組成的有限序列。字符組成的有限序列。一般記為一般記為s=s=a a0 0a a1 1a an-1 n-1,其中其中s s為為串名串

4、名，雙引號(hào)括起來(lái)的字符序列是，雙引號(hào)括起來(lái)的字符序列是串值串值。2 2、串的長(zhǎng)度：串的長(zhǎng)度：串中串中字符的個(gè)數(shù)字符的個(gè)數(shù)。3 3、空串：空串：長(zhǎng)度為長(zhǎng)度為0 0的串，即不包含任何字符的的串，即不包含任何字符的串，表示為串，表示為。4 4、空白串：空白串：由一個(gè)或多個(gè)空白字符組成的串，由一個(gè)或多個(gè)空白字符組成的串，如：如：。注意：注意：空串與空白串的區(qū)別空串與空白串的區(qū)別串也是一種特殊的線性表。串也是一種特殊的線性表。4.1.1 4.1.1 串的基本概念串的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)

5、布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄5 5、子串：子串：主串：主串：串中任意個(gè)串中任意個(gè)連續(xù)字符連續(xù)字符組成的組成的子子序列序列稱為該串的子串。稱為該串的子串。包含子串的串相應(yīng)地稱為包含子串的串相應(yīng)地稱為主主串。串。6 6、字符在串中的位置：字符在串中的位置：子串在主串中的位置：子串在主串中的位置：如：如：s1=s1=cdababefcdababef,s2=,s2=abab字符在串中的序號(hào)值。字符在串中的序號(hào)值。子串在主串中第一次子串在主串中第一次出現(xiàn)時(shí)的第一個(gè)字符在主串中的序號(hào)值。出現(xiàn)時(shí)的第一個(gè)字

6、符在主串中的序號(hào)值。注意：注意：空串是任意串的子串空串是任意串的子串,任意串是其自任意串是其自 身的子串。身的子串。4.1.1 4.1.1 串的基本概念串的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄7 7、兩個(gè)串相等：兩個(gè)串相等：長(zhǎng)度相等長(zhǎng)度相等各個(gè)字符對(duì)應(yīng)相等各個(gè)字符對(duì)應(yīng)相等串值相等串值相等4.1.1 4.1.1 串的基本概念串的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)

7、（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述 clear()1 1）串的置空操作：）串的置空操作：isEmpty()2 2）串的判空操作：）串的判空操作：length()3 3）求串的長(zhǎng)度操作：）求串的長(zhǎng)度操作：4 4）取字符元素操作：）取字符元素操作：5 5）截取子串操作：）截取子串操作：charAT(index)substring(ben

8、gin,end)6 6）插入操作：）插入操作：insert(offset,str)1.1.基本操作基本操作數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述 delete(begin,end )7 7）刪除操作：）刪除操作：concat(str)8 8）串的連接操作：）串的連接操作：compareTo(str )9 9）

9、串的比較操作：）串的比較操作：1010）子串定位操作：）子串定位操作：indexOf(str,begin)1.1.基本操作基本操作數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述charAT(index)讀取并返回串中的第讀取并返回串中的第indexindex個(gè)字符值個(gè)字符值,其中其中:0:0indexindexlen

10、gth()-1length()-1 例如例如:當(dāng)前串為當(dāng)前串為abcdefg charAT(0)=?acharAT(3)=?dcharAT(6)=?g數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述substring(bengin,end)截取當(dāng)前串中從序號(hào)截取當(dāng)前串中從序號(hào)beginbegin開(kāi)始開(kāi)始,到序號(hào)到序號(hào)e

11、nd-1end-1為止的子串并返回其值為止的子串并返回其值,其中其中:0beginlength()-1,1 1endendlength()length()例如例如:當(dāng)前串為當(dāng)前串為commander substring(3,6)=?man substring(0,9)=?commander substring(8,9)=?r substring(3,10)=?substring(9,1)=?數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放

12、映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述 將串將串strstr插入到當(dāng)前串中的第插入到當(dāng)前串中的第offsetoffset個(gè)字個(gè)字符的前面符的前面,并返回操作結(jié)果。其中并返回操作結(jié)果。其中:0offsetlength()例如例如:當(dāng)前串為當(dāng)前串為chater,則則insert(3,rac）=?character insert(offset,str)insert(0,rac)=?racchater insert(6,rac)=?chaterrac 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言

13、描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述delete(bengin,end)刪除當(dāng)前串中從序號(hào)刪除當(dāng)前串中從序號(hào)beginbegin開(kāi)始開(kāi)始,到序號(hào)到序號(hào)end-1end-1為止的子串為止的子串,并返回操作結(jié)果。其中并返回操作結(jié)果。其中:0beginlength()-1,1 1endendlength()length()例如例如:當(dāng)前串為當(dāng)前串為commanderdelete(

14、3,6)=?comder delete(0,9)=?delete(8,9)=?commande delete(3,10)=?delete(9,1)=?數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述 concat(str)將串將串strstr連接在當(dāng)前串的后面，連接在當(dāng)前串的后面，并返回其值。并返回其值。例如例如:當(dāng)前

15、串為當(dāng)前串為man,則則concat(kind)=?mankind 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述 compareTo(str)將當(dāng)前串與目標(biāo)串將當(dāng)前串與目標(biāo)串strstr進(jìn)行比較進(jìn)行比較,若若:當(dāng)前串當(dāng)前串 str str，則返回值，則返回值 0 0；當(dāng)前串當(dāng)前串 str str，則返回值，則返回值

16、 0 0；當(dāng)前串當(dāng)前串 strstr，則返回值，則返回值 0 0。例如例如:當(dāng)前串為當(dāng)前串為 cat compareTo(case)?0 compareTo(cate)?0compareTo(cht )?0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（JavaJava語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述語(yǔ)言描述）4.1串的基本概念串的基本概念作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置作業(yè)布置結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映結(jié)束放映章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄章節(jié)目錄4.1.2 4.1.2 串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型描述indexOf(str,begin)在當(dāng)前串中從在當(dāng)前串中從beginbegin位置開(kāi)始去找與位置開(kāi)始去找與非空串非空串strstr相等的子串相等的子串,若查找成功則返回在當(dāng)前串中的位置若查找成功則返回在當(dāng)前串中的位置,否則返回否則返回-1,-1,其中其中:0beginlength()-1 例如例如:當(dāng)前串為當(dāng)前串為 bcaabcaaabc,str=,str=bca indexOf(str,0)=?0indexOf(str,2)=?4indexOf(str,6