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

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

S=a0a1a2…an-1

(n≥0)子串：第4章串串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串相應(yīng)地稱為主串。位置：字符在序列中的序號(hào)。子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示。相等：兩個(gè)串的長(zhǎng)度相等，并且對(duì)應(yīng)位置的字符都相等?？沾c空白串?dāng)?shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第3頁(yè)。串的抽象數(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串及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第4頁(yè)?；静僮鳎旱?章串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串及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第5頁(yè)?；静僮鳎旱?章串StrDelete(S,pos,len)初始條件：串S存在1≤pos≤StrLength(S)+1。

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

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

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

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

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

初始條件：主串S和T存在，T是非空串操作結(jié)果：若主串S中存在和串T值相同的子串,則返回它在主串S中從第pos個(gè)字符開(kāi)始第一次出現(xiàn)的位置；否則函數(shù)值為0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=64.2串及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第9頁(yè)。基本操作：第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給出一個(gè)由小寫(xiě)字母組成的串s和一個(gè)不超過(guò)s的長(zhǎng)度的正整數(shù)l，求s所有長(zhǎng)度不小于l的子串在s中不重疊地重復(fù)出現(xiàn)次數(shù)最多的子串。4.2串及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第10頁(yè)。對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)?；静僮鞯?章串4.2串及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第11頁(yè)。①定長(zhǎng)順序串4.3串的存儲(chǔ)及實(shí)現(xiàn)常用的實(shí)現(xiàn)方法：第4章串②堆串③塊鏈串?dāng)?shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第12頁(yè)。①定長(zhǎng)順序串常用的實(shí)現(xiàn)方法：第4章串存儲(chǔ)表示：靜態(tài)數(shù)組結(jié)構(gòu)#defineMAXLEN40typedefstruct{charstr[MAXLEN];intlength;}SString;4.3串的存儲(chǔ)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第13頁(yè)。①定長(zhǎng)順序串常用的實(shí)現(xiàn)方法：第4章串基本操作：

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

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

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

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

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

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

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

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

否則函數(shù)值為0。數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第20頁(yè)。“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。例如：S=abcaabcaaabc,T=bcaStrInex(S,1,T)=StrInex(S,4,T)=624.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第21頁(yè)。下面討論以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的幾種算法。①簡(jiǎn)單匹配算法（Brute-Force）②首尾匹配算法③KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)算法4.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第22頁(yè)。*4.4串的模式匹配算法①簡(jiǎn)單匹配算法（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頁(yè)，當(dāng)前為第23頁(yè)。②首尾匹配算法先比較模式串中的第一個(gè)字符再比較模式串中的最后一個(gè)字符最后比較模式串中從第二個(gè)到第n-1個(gè)字符4.5串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)與算法4-串全文共25頁(yè)，當(dāng)前為第