資源描述：
《串類型的定義串的表示和實現(xiàn)串的模式匹配算法教學(xué)課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法第4章串重點:(1)ADT串的設(shè)計、實現(xiàn)方法和基本操作；(2)串的簡單模式匹配算法，KMP算法。難點:串的模式匹配算法中的KMP算法。本章重點難點4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法第4章串4.1串類型的定義串是由零個或多個字符組成的有限序列。記為：s=”a1a2…an”(n≥0)其中，s是串的名，用雙引號括起來的字符序列是串的值。(1)串的長度:串中字符的數(shù)目n。(2)空串(Nullstring):長度為零的串。(3)子串:串中任意個連續(xù)的字符組成的子序列。串的有關(guān)術(shù)語串(
2、String)的定義4.1串類型的定義(4)主串包含子串的串相應(yīng)地稱為主串。(5)串相等只有當兩個串的長度相等，并且各個對應(yīng)位置的字符都相等，稱兩串相等。(6)空格串(空白串)(blankstring)由一個或多個空格組成的串。要和“空串”區(qū)別，空格串有長度就是空格的個數(shù)。串的有關(guān)術(shù)語4.1串類型的定義(1)串數(shù)據(jù)對象約束為字符集。(2)基本操作的對象不同，線性表以“單個元素”為操作對象；串以“串的整體”為操作對象，操作的一般都是子串。串與一般線性表的區(qū)別ADTString{數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：基本操作：}ADTString串的ADT定義見下頁D＝{ai
3、a
4、i∈CharacterSet,i=1,2,...,n,n≥0}R1＝{
5、ai-1,ai∈D,i=2,...,n}4.1串類型的定義基本操作：StrAssign(&T,chars)//根據(jù)串常量chars生成串TStrCopy(&T,S)//把串S中內(nèi)容拷貝到T串DestroyString(&S)//銷毀串SStrEmpty(S)//判斷串是否空StrCompare(S,T)//比較串S和TStrLength(S)//求串長Concat(&T,S1,S2)//連接串4.1串類型的定義基本操作：SubString(&Sub,S,pos,len)
6、//求子串Index(S,T,pos)//子串定位ClearString(&S)//清空串SStrDelete(&S,pos,len)//刪除子串Replace(&S,T,V)//把串S中符合T的子串替換StrInsert(&S,pos,T)//插入子串4.1串類型的定義4.2串的表示和實現(xiàn)4.2.1、定長順序存儲表示4.2.2、堆分配存儲表示4.2.3、串的塊鏈存儲表示4.2.1定長順序存儲表示#defineMAXSTRLEN255//用戶可在255以內(nèi)定義最大串長typedefunsignedcharSstring[MAXSTRLEN+1];//0號單元
7、存放串的長度SstringS;串的順序存儲C語言實現(xiàn)StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2聯(lián)接而成的新串。若未截斷,則返回TRUE，否則FALSE。……………….returnuncut;}//ConcatT[1...S1[0]]=S1[1...S1[0]];T[S1[0]+1…S1[0]+S2[0]]=S2[1…S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}if(S1[0]+S2[0]<=MAXSTRLEN){//未截斷4.2.1定長順序存儲表示串的連接算法S
8、tatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2聯(lián)接而成的新串。若未截斷,則返回TRUE，否則FALSE?！?returnuncut;}//Concatelseif(S1[0]9、ringS2,SString&T){//用T返回由S1和S2聯(lián)接而成的新串。若未截斷,則返回TRUE，否則FALSE?！?returnuncut;}//Concatelse{//截斷(僅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}4.2.1定長順序存儲表示串的連接算法StatusStrDelete(SSstring&S,intpos,intlen){if(pos<1
10、
11、pos>S[0]
12、
13、len<=0)returnerror;if(pos+len
14、-1>=S[0])S[0]=pos-1;else{f
