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