資源描述：
《課前導(dǎo)學(xué)4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。
1、第四章串課前導(dǎo)學(xué)4.1串類型的定義4.2串的表示和實(shí)現(xiàn)*4.3串的模式匹配算法4.4串操作應(yīng)用舉例【學(xué)習(xí)目標(biāo)】1.理解"串"類型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作。2.理解串類型的各種存儲(chǔ)表示方法。3.理解串匹配的各種算法。【重點(diǎn)和難點(diǎn)】了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來實(shí)現(xiàn)串的其它操作?！局R(shí)點(diǎn)】串的類型定義、串的存儲(chǔ)表示、串匹配【課前思考】從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來說，串是一種特殊的線性表;但就數(shù)據(jù)類型而言，串不是線性表。區(qū)別1、它的數(shù)據(jù)元素都是字符，它的存儲(chǔ)結(jié)構(gòu)和線性
2、表有很大不同;區(qū)別2、串的基本操作通常以"串的整體"作為操作對(duì)象，而不像線性表是以"數(shù)據(jù)元素"作為操作對(duì)象。“串就是線性表”的結(jié)論是否正確？二者之間有何區(qū)別?4.1串類型的定義1.基本概念串（string）：由0個(gè)或多個(gè)字符組成的有限序列，也稱字符串。記為：s=’a1a2a3……an’(n≥0)式中s是串的名，a1a2a3……an是串的值，ai（1≤i≤n）可以是字母、數(shù)字或其它字符。串長度：串中字符的數(shù)目n。空串：不含任何字符的串，串長度=0空格串：僅由一個(gè)或多個(gè)空格組成的串子串：由串中任意個(gè)連續(xù)的字符組成的子序列主串：包含
3、子串的串。串相等的條件：當(dāng)兩個(gè)串的長度相等且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。注意：（1）串值必須用一對(duì)單引號(hào)括起來（2）串值大小是按詞典次序進(jìn)行比較的StrCompare(‘data’,’Stru’)<0StrCompare(‘cat’,’case’)>0顯然，只有在兩個(gè)串的長度相等且每個(gè)字符一一對(duì)等的情況下稱兩個(gè)串相等。2.串的抽象數(shù)據(jù)類型的定義ADTString{數(shù)據(jù)對(duì)象：D＝{ai
4、ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
5、ai-1,ai∈D,i=2,...,
6、n}基本操作：StrAssign(&T,chars)初始條件：chars是字符串常量。操作結(jié)果：把chars賦為T的值。StrCopy(&T,S)初始條件：串S存在。操作結(jié)果：由串S復(fù)制得串T。DestroyString(&S)初始條件：串S存在。操作結(jié)果：串S被銷毀。StrEmpty(S)初始條件：串S存在。操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。StrCompare(S,T)初始條件：串S和T存在。操作結(jié)果：若S>T，則返回值>0；若S=T，則返回值=0； 若S7、初始條件：串S存在。操作結(jié)果：返回S的元素個(gè)數(shù)，稱為串的長度。Concat(&T,S1,S2)初始條件：串S1和S2存在。操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。SubString(&Sub,S,pos,len)初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作結(jié)果：用Sub返回串S的第pos個(gè)字符起長度為len的子串。Index(S,T,pos)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同的子
8、串,則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0。Replace(&S,T,V)初始條件：串S,T和V存在，T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。StrInsert(&S,pos,T)初始條件：串S和T存在，1≤pos≤StrLength(S)＋1。操作結(jié)果：在串S的第pos個(gè)字符之前插入串T。StrDelete(&S,pos,len)初始條件：串S存在，1≤pos≤StrLength(S)-len+1。操作結(jié)果：從串S中刪除第pos個(gè)字符起長度為len的子串。Clea
9、rString(&S)初始條件：串S存在。操作結(jié)果：將S清為空串。}ADTString在以上操作中，串賦值StrAssign、串比較StrCompare、求串長StrLength、串聯(lián)接Concat以及求子串SubString等五種操作構(gòu)成串類型的最小操作子集，即這些操作不可能利用其他串操作來實(shí)現(xiàn)。例：假設(shè)S="abcacabcaca"，T="abca"和V="x"，則置換之后的S="xcxca"。注意定義中"不重疊"三個(gè)字，若上例中的V="ab"時(shí)，則置換后的結(jié)果應(yīng)該是S="abcabca"，而不是"abbca"。思考：串的
10、基本操作和線性表一樣，無非也就是查找、插入和刪除等，那么它們能否用線性表的操作來替代呢？串的基本操作和線性表有很大的區(qū)別，同樣是查找、插入和刪除，但對(duì)線性表而言操作對(duì)象是“數(shù)據(jù)元素”，而對(duì)串言，是以整個(gè)串作為操作對(duì)象。由此可見，串類型不能和線性表類型混為一談。4．2串的表示和
