資源描述：
《串的抽象數(shù)據(jù)類(lèi)型的定義(精).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第四章串4.1串的抽象數(shù)據(jù)類(lèi)型的定義4.2串的表示和實(shí)現(xiàn)4.3串的模式匹配算法4.1串的抽象數(shù)據(jù)類(lèi)型的定義如下：ADTString{數(shù)據(jù)對(duì)象：D＝{ai
2、ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
3、ai-1,ai∈D,i=2,...,n}串是有限長(zhǎng)的字符序列，由一對(duì)雙引號(hào)相括，如:?astring?基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T
4、,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTStringStrAssign(&T,chars)初始條件：chars是字符串常量。操作結(jié)果：把chars賦為T(mén)的值。StrCopy(&T,S)初始條件：串S存在。操作結(jié)果：由串S復(fù)制得串T。DestroyString(&S)初始條件：串S存在。操作結(jié)果：串S被銷(xiāo)毀。StrEmpty(S)初始條件：串S存在。操作結(jié)果：
5、若S為空串，則返回true，否則返回false。??表示空串，空串的長(zhǎng)度為零。StrCompare(S,T)初始條件：串S和T存在。操作結(jié)果：若S?T，則返回值?0； 若S?T，則返回值?0；若S?T，則返回值?0。例如：StrCompare(?data?,?state?)<0StrCompare(?cat?,?case?)>0StrLength(S)初始條件：串S存在。操作結(jié)果：返回S的元素個(gè)數(shù)，稱(chēng)為串的長(zhǎng)度。Concat(&T,S1,S2)初始條件：串S1和S2存在。操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。例如：Concat(T,?man?,?
6、kind?)求得T=?mankind?SubString(&Sub,S,pos,len)初始條件：操作結(jié)果：用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。例如：SubString(sub,?commander?,4,3)子串為“串”中的一個(gè)字符子序列求得sub=?man?;SubString(sub,?commander?,1,9)SubString(sub,?commander?,9,1)求得sub=?r?求得sub=?commander?SubS
7、tring(sub,?commander?,4,7)sub=?SubString(sub,?beijing?,7,2)=?sub=?SubString(?student?,5,0)=??起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為0的子串為“合法”串Index(S,T,pos)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同 的子串,則返回它在主串S中第pos個(gè) 字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0。假設(shè)S=?abcaabcaaabc?,T=?bca?Index(S,T,1)=2;Index(
8、S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。Replace(&S,T,V)初始條件：串S,T和V均已存在， 且T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn) 的所有與（模式串）T相等的不重疊的子串。例如：假設(shè)S=?abcaabcaaabca?,T=?bca?若V=?x?,則經(jīng)置換后得到S=?axaxaax?若V=?bc?,則經(jīng)置換后得到S=?abcabcaabc?bcabcabcaStrInsert(&S,pos,T)初始條件：串S和T存在，1≤pos≤StrLength(S)＋1。操作結(jié)果：在
9、串S的第pos個(gè)字符之前插入串T。例如：S=?chater?，T=?rac?，則執(zhí)行StrInsert(S,4,T)之后得到S=?character?StrDelete(&S,pos,len)初始條件：串S存在1≤pos≤StrLength(S)-len+1。操作結(jié)果：從串S中刪除第pos個(gè)字符 起長(zhǎng)度為len的子串。ClearString(&S)初始條件：串S存在。操作結(jié)果：將S清為空串。思考題：設(shè)S為一個(gè)長(zhǎng)度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)為_(kāi)________對(duì)于串的基本操作集可以有不同的定義方法
10、，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類(lèi)型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。strlen(s
