資源描述：
《串的表示和實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、4.1串的抽象數(shù)據(jù)類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法4.1串的抽象數(shù)據(jù)類型的定義如下：ADTString{數(shù)據(jù)對象：D＝{ai
2、ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
3、ai-1,ai∈D,i=2,...,n}串是有限長的字符序列，由一對單引號相括，如:?astring?基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLe
4、ngth(S)Concat(&T,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的值。StrCopy(&T,S)初始條件：串S存在。操作結(jié)果：由串S復制得串T。DestroyString(&S)初始條件：串S存在。操
5、作結(jié)果：串S被銷毀。StrEmpty(S)初始條件：串S存在。操作結(jié)果：若S為空串，則返回TRUE， 否則返回FALSE。??表示空串，空串的長度為零。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的元素個數(shù) 稱為串的長度。Concat(&T,S1,S
6、2)初始條件：串S1和S2存在。操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。例如：Concate(T,?man?,?kind?)求得T=?mankind?SubString(&Sub,S,pos,len)初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作結(jié)果：用Sub返回串S的第pos個字符起長度為len的子串。例如：SubString(sub,?commander?,4,3)求得sub=?man?；SubString(sub,?commander?,
7、1,9)求得sub=?commander?；SubString(sub,?commander?,9,1)求得sub=?r?；子串為“串”中的一個字符子序列SubString(sub,?commander?,4,7)sub=?SubString(sub,?beijing?,7,2)=?sub=?SubString(?student?,5,0)=??起始位置和子串長度之間存在約束關(guān)系長度為0的子串為“合法”串Index(S,T,pos)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：
8、若主串S中存在和串T值相同 的子串,則返回它在主串S中第pos個 字符之后第一次出現(xiàn)的位置； 否則函數(shù)值為0。假設S=?abcaabcaaabc?,T=?bca?Index(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；“子串在主串中的位置”意指子串中的第一個字符在主串中的位序。Replace(&S,T,V)初始條件：串S,T和V均已存在， 且T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn) 的所有與（模式串）T相等的不重疊的子串。例如：假設S=?abcaabcaaabca?，T=?bca
9、?若V=?x?，則經(jīng)置換后得到S=?axaxaax?若V=?bc?，則經(jīng)置換后得到S=?abcabcaabc?StrInsert(&S,pos,T)初始條件：串S和T存在，1≤pos≤StrLength(S)＋1。操作結(jié)果：在串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。操作結(jié)果：從串S中刪除第pos個字
10、符 起長度為len的子串。ClearString(&S)初始條件：串S存在。操作結(jié)果：將S清為空串。對于串的基本操作集可以有不同的定義方法，在使用高級程序設計語言中的串類型時，應以該語言的參考手冊為準。gets(str)輸入一個串；puts(str)輸出一個串；strcat(str1,str2)串聯(lián)接函數(shù)；strcpy(str1,str2,k)串復制函數(shù)；s
