數(shù)據(jù)結(jié)構(gòu)第08講串的定義表示和實現(xiàn)ppt課件.ppt

《數(shù)據(jù)結(jié)構(gòu)第08講串的定義表示和實現(xiàn)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第4章串4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法4.4串操作應(yīng)用舉例4.1串類型的定義1.串的概念由零個或多個字符組成的有限序列，記作s=‘a(chǎn)1a2…an’其中：s為串的名字；用成對的單引號括起來的字符序列為串的值，但兩邊的單引號不算串值，不包含在串中；ai(1≤i≤n)可以是字母、數(shù)字或其它字符；n為串中字符的個數(shù)，稱為串的長度?？沾翰缓魏巫址拇ｉL度n=0，記為s=‘’；空格串：含有空格的串，長度n>0，記為s=‘’。子串、主串:串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次

2、出現(xiàn)時，該子串的首字符對應(yīng)的主串中的序號稱為子串在主串中的位置。例：A和B分別為A=‘Thisisastring’B=‘is’空串是任意串的子串，任意串是其自身的子串。串的比較大小：‘a(chǎn)’<‘a(chǎn)b’，‘a(chǎn)bc’<‘a(chǎn)bd’兩串相等：當且僅當這兩個串的值相等（長度相等,對應(yīng)位置上的字符也相等）時。2.串的抽象類型定義ADTString數(shù)據(jù)對象：D＝{ai

3、ai∈CharacterSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{

4、ai-1,ai∈D,i=2,…,n}基本操作：}ADTString串的常用操作(1)StrAssign(&

5、T,chars)條件：chars是字符串常量；結(jié)果：把chars賦為T的值(2)StrCopy(&T,S)條件：串S存在；結(jié)果：將串S的值復制到串T(3)DestroyString(&S)條件：串S存在；結(jié)果：串S被銷毀(4)StrEmpty(S)條件：串S存在；結(jié)果：若S為空串，返回真，否則假(5)StrCompare(S,T)條件：串S和T存在；結(jié)果：若S>T，則返回值>0；若S=T，則返回值=0若S

6、在；結(jié)果：用T返回由S1和S2聯(lián)接而成的新串(8)SubString(&Sub,S,p,len)條件：串S存在，且1≤p≤StrLength(S)0≤len≤StrLength(S)-p+1。結(jié)果：用Sub返回串S的第p個字符起長度為len的子串(9)Index(S,T,p)條件：串S和T存在，T非空,1≤p≤StrLength(S)結(jié)果：若主串S中存在和串T值相同的子串,則返回它在主串S中第p個字符之后第一次出現(xiàn)的位置，否則函數(shù)值為0。(10)ClearString(&S)條件：串S存在；結(jié)果：將S清為空串(11)Replace(&S,T,V)條件：串

7、S,T和V存在，T是非空串且是S的子串結(jié)果：用V替換S中所有與T相等的不重疊的子串(12)StrInsert(&S,p,T)條件：串S和T存在，1≤p≤StrLength(S)＋1結(jié)果：在串S的第p個字符之前插入串T(13)StrDelete(&S,p,len)條件：串S存在，1≤p≤StrLength(S)-len+1結(jié)果：從串S中刪除第p個字符起長度為len的子串設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。求：例：StrLength(s)＝StrLength(t)＝SubString(s,8,7)＝SubString(t

8、,2,1)＝Index(s,‘A’)＝Index(s,t)＝Replace(s,‘STUDENT’,q)＝144‘STUDENT’‘O’30（s中沒有t！）’IAMAWORKER’考慮：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？注意事項：對串的基本操作集可以有不同的定義方法，讀者在使用高級程序設(shè)計語言中的串類型時，應(yīng)以該語言的參考手冊為準。串類型的最小操作子集包括：串賦值StrAssign、求串長StrLength、串比較StrCompare、求子串SubString、串聯(lián)接Concat等操

9、作。例：利用判等、求串長和求子串等操作實現(xiàn)定位函數(shù)Index(S,T,p)。算法的基本思想：在主串S中取從第i(i的初值為p)個字符起、長度和串T相等的子串和串T比較，若相等，則求得函數(shù)值為i，否則i值增1，直至串S中不存在和串T相等的子串為止。intIndex(StringS,StringT,intp){//T為非空串。若主串S中第p個字符之后存在與T相等的子串，//則返回第一個這樣的子串在S中的位置，否則返回0if(p>0){n=StrLength(S);m=StrLength(T);i=p;while(i<=n-m+1){SubString(&su

10、b,S,i,m);if(StrCompare(sub,T)!=0)++i;els