數(shù)據(jù)結(jié)構(gòu)與算法4-串

4.2串及其運算4.3串的存儲結(jié)構(gòu)及實現(xiàn)第4章串4.4串的模式匹配4.1應(yīng)用實例4.5實例分析與實現(xiàn)4.6算法總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第1頁。4.1應(yīng)用實例應(yīng)用實例：文本編輯軟件文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作，甚至用于報刊和書籍的編輯排版。常用的簡單文本編輯程序Edit，和文字處理軟件WPS、Word等，究其實質(zhì)，都是修改字符數(shù)據(jù)的形式或格式?？捎糜谖谋揪庉嫷某绦蚝芏啵δ懿煌覐娙醪顒e很大，但基本操作是一樣的，一般都包含串的查找、插入和刪除等基本操作。數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第2頁。4.2串及其運算是由零個或多個字符組成的有限序列。

S=a0a1a2…an-1

(n≥0)子串：第4章串串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串相應(yīng)地稱為主串。位置：字符在序列中的序號。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。相等：兩個串的長度相等，并且對應(yīng)位置的字符都相等?？沾c空白串?dāng)?shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第3頁。串的抽象數(shù)據(jù)類型的定義第4章串ADTString{

數(shù)據(jù)元素：D={ai|ai∈CharacterSet,記為V,i=1,2,…，n;n≥0}

數(shù)據(jù)關(guān)系：R＝｛<ai,ai+1>|ai,ai+1∈V，i=1,2,…,n-1;n-1≥0

｝

基本操作：

（1）StrAssign(S,chars)

（2）StrInsert(S,pos,T)

（3）StrDelete(S,pos,len)

………p106}ADT

String4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第4頁?；静僮鳎旱?章串StrInsert(S,pos,T)初始條件：串S和T存在，1≤pos≤StrLength(S)+1。

操作結(jié)果：在串S的下標(biāo)為pos的字符之前插入串T。StrInsert(S,pos,T)例如：S=chater，T=rac，則執(zhí)行StrInsert(S,3,T)之后S=

character4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第5頁?；静僮鳎旱?章串StrDelete(S,pos,len)初始條件：串S存在1≤pos≤StrLength(S)+1。

操作結(jié)果：從串S中刪除下標(biāo)為pos的字符起長度為len的子串。

StrDelete(S,pos,len)例如：S=character，則執(zhí)行StrDelete(S,3,3)之后S=chater4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第6頁。基本操作：第4章串StrCat(S,T)初始條件：串S和T存在。

操作結(jié)果：返回由S和T聯(lián)接而成的新串。StrCat(S,T)例如：StrCat(man,kind)=mankind4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第7頁。基本操作：第4章串SubString(Sub,S,pos,len)初始條件：串S存在，1≤pos≤Length(S)

且0≤len≤Length(S)-pos+1。操作結(jié)果：用Sub返回串S的第pos個字符起長度為len的子串。SubString(Sub,S,pos,len)例如：SubString(sub1,commander,4,3)sub1=manSubString(sub2,

commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串長度之間存在約束關(guān)系!4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第8頁。基本操作：第4章串StrIndex(S,pos,T)

初始條件：主串S和T存在，T是非空串操作結(jié)果：若主串S中存在和串T值相同的子串,則返回它在主串S中從第pos個字符開始第一次出現(xiàn)的位置；否則函數(shù)值為0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=64.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第9頁。基本操作：第4章串StrReplace(S,T,V)

初始條件：串S,T和V均已存在，且T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)的所有與（模式串）T相等的不重疊的子串。StrReplace(S,T,V)例如：S=abcaabcaaabca,T=bca,V=xS=axaxaax給出一個由小寫字母組成的串s和一個不超過s的長度的正整數(shù)l，求s所有長度不小于l的子串在s中不重疊地重復(fù)出現(xiàn)次數(shù)最多的子串。4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第10頁。對于串的基本操作集可以有不同的定義方法，在使用高級程序設(shè)計語言中的串類型時，應(yīng)以該語言的參考手冊為準(zhǔn)?；静僮鞯?章串4.2串及其運算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第11頁。①定長順序串4.3串的存儲及實現(xiàn)常用的實現(xiàn)方法：第4章串②堆串③塊鏈串?dāng)?shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第12頁。①定長順序串常用的實現(xiàn)方法：第4章串存儲表示：靜態(tài)數(shù)組結(jié)構(gòu)#defineMAXLEN40typedefstruct{charstr[MAXLEN];intlength;}SString;4.3串的存儲及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第13頁。①定長順序串常用的實現(xiàn)方法：第4章串基本操作：

插入、刪除、復(fù)制、判空、比較、求串長、清空、連接、求子串。參見P78~80頁4.3串的存儲及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第14頁。②堆串常用的實現(xiàn)方法：第4章串存儲表示：

動態(tài)地分配一組地址連續(xù)的存儲單元。typedefstruct{char*ch;intlen;}HString;4.3串的存儲及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第15頁。poolelpmasNAMEINFORMATION?,6?,4pool4elpmas6NAMEINFORMATION??數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第16頁。②堆串常用的實現(xiàn)方法：基本操作：

賦值、插入、刪除。參見P81~82頁4.3串的存儲及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第17頁。③塊鏈串常用的實現(xiàn)方法：第4章串存儲表示：可用鏈表來存儲串值，由于串的數(shù)據(jù)元素是一個字符，它只有8位二進制數(shù)，因此用鏈表存儲時，通常一個結(jié)點中存放的不是一個字符，而是一個字符串。#defineBLOCK_SIZE4

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

}BLString;4.3串的存儲及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第18頁。4.4簡單的行編輯器

整個文本編輯區(qū)可以看成是一個字符串，稱為文本串。每一頁是文本串的一個子串，每一行是每一頁的一個子串，即:同一行的串用定長結(jié)構(gòu)(80個字符),行和行之間用行指針相鏈接，頁和頁之間用頁指針相鏈接。數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第19頁。4.5串的模式匹配算法首先，回憶一下串匹配(查找)的定義:StrInex(S,pos,T)初始條件：主串S和T存在，T是非空串并且1≤pos≤Length(S)。

操作結(jié)果：若主串S中存在和串T值相同的子串,則返回它在主串S中從第

pos個字符開始第一次出現(xiàn)的位置；

否則函數(shù)值為0。數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第20頁?！白哟谥鞔械奈恢谩币庵缸哟械牡谝粋€字符在主串中的位序。例如：S=abcaabcaaabc,T=bcaStrInex(S,1,T)=StrInex(S,4,T)=624.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第21頁。下面討論以定長順序結(jié)構(gòu)表示串時的幾種算法。①簡單匹配算法（Brute-Force）②首尾匹配算法③KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)算法4.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第22頁。*4.4串的模式匹配算法①簡單匹配算法（Brute-Force）intStrIndex(SStrings,intpos,SStringt){ inti,j,start; if(t.len==0) return(0);

start=pos;

i=start;

j=0; while(i<s.len&&j<t.len)

if(s.ch[i]==t.ch[j]) {

i++;

j++;

} else {

start++;

i=start;

j=0;

} if(j>=t.len) return(start);

else

return(-1);}數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第23頁。②首尾匹配算法先比較模式串中的第一個字符再比較模式串中的最后一個字符最后比較模式串中從第二個到第n-1個字符4.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁，當(dāng)前為第