線性部分之串

湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華1第七章串

什么是串？(即串抽象數(shù)據(jù)類型)

串的存儲結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)串的模式匹配湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華2什么是串String？串的定義一些相關(guān)概念串的基本運(yùn)算湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華3串的定義Definition

串(String)是一種數(shù)據(jù)元素受限的線性表，它的每個數(shù)據(jù)元素僅由一個字符組成。因此，串是零個或多個字符的有限序列。記作：S=“a1a2…an”其中，S為串名；雙引號為定界符，它不屬于串；

a1a2…an為串值。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華4一些相關(guān)概念串長

串中所含字符的個數(shù)n?？沾瓻mptyString

不包含任何字符的串。(即長度為0的串)

記為：

空格串BlankString

由一個或多個空格組成的串。(n≥1)湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華5一些相關(guān)概念（Cont.）主串CurrentString&子串Substring

串中任意個連續(xù)字符組成的子序列，稱為該串的子串，而包含這個子串的串稱為主串。例如：S1=“ABCAEDFCAE”，S2=“CAED”，S3=“AE”，

S4=“CAF”；S2是S1的子串，S1是S2的主串；S3是S1的子串，S1是S3的主串；S4不是S1的子串，S1不是S4的主串。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華6一些相關(guān)概念（Cont.）字符在串中的位置

字符在字符序列中的序號。子串在主串中的位置子串在主串中第一次出現(xiàn)時，其首字符在主串中的位置。例如：S1=“ABCAEDFCAE”

S2=“CAED”，S3=“AE”；S2在S1中的位置是3；S3在S1中的位置是4。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華7一些相關(guān)概念（Cont.）串相等

當(dāng)且僅當(dāng)兩個串的串值相等時，才稱這兩個串相等。也就是說，如果兩個串相等，那么：

①它們的長度相等；②它們對應(yīng)位置上的元素(字符)相同。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華8串的基本運(yùn)算StrAssign(&T,chars)串賦值運(yùn)算StrCopy(&T,S)串復(fù)制運(yùn)算StrEmpty(S)串判空運(yùn)算StrCompare(S,T)串比較運(yùn)算StrLength(S求串長運(yùn)算Concat(&T,S1,S2)串連接運(yùn)算SubString(&Sub,S,pos,len)求子串運(yùn)算StrIndex(S,T)串定位運(yùn)算湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華9串的邏輯結(jié)構(gòu)與線性表的邏輯結(jié)構(gòu)的區(qū)別

串的數(shù)據(jù)元素固定為字符。串的基本操作與線性表的基本操作的差別

線性表的操作大多以“單個數(shù)據(jù)元素”為操作對象；而串操作通常以“串的整體”或“子串”作為操作對象。串的基本運(yùn)算（Cont.）湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華10串的存儲結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)串的順序存儲結(jié)構(gòu)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)（塊鏈結(jié)構(gòu)）串的堆結(jié)構(gòu)湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華11串的順序存儲結(jié)構(gòu)什么是串的順序存儲結(jié)構(gòu)？類似于線性表的順序存儲表示方法，用一組地址連續(xù)的存儲單元來依次存放串值的字符序列。采用順序存儲的串稱為順序串。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華12串的順序存儲結(jié)構(gòu)（Cont.）順序串的類型定義

#defineMAX100typedefstruct{

char

data[MAX];intlength;//記錄當(dāng)前串的長度

}SqString;湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華13串的順序存儲結(jié)構(gòu)（Cont.）關(guān)于串長表示的說明顯示的方式表示用一個整型的輔助變量來記錄當(dāng)前串的實(shí)際長度。隱式的方式表示在串值后面加一個不計(jì)入串長的結(jié)束標(biāo)記字符。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華14順序串中基本運(yùn)算的實(shí)現(xiàn)串連接運(yùn)算Concat_sq串的順序存儲結(jié)構(gòu)（Cont.）湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華15串連接運(yùn)算

Concat_sq考慮將下面兩個串S1、S2首尾聯(lián)接成一個新串T。S1=“How_are”S2=“_you?”并假設(shè)有：#defineMAX15因?yàn)镾1.length+S2.length≤MAX，因此可以實(shí)現(xiàn)S1和S2的完整聯(lián)接。具體過程如下所示。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華16順序串S1的存儲結(jié)構(gòu)如下所示：S1.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]owHar＿e7S1.lengthS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.length順序串S2的存儲結(jié)構(gòu)如下所示：湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華17S1.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]owHar＿e7S1.lengthS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.lengthT.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length初始時湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華18S1.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]owHar＿e7S1.lengthT.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length先將S1拷貝到T中for(i=0;i<=S1.length-1;i++)

T.data[i]=S1.data[i];owHar＿eii湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華19T.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length再將S2接著拷貝到T中for(i=0;i<=S2.length-1;i++)

T.data[i

+S1.len]=S2.data[i];owHar＿eii

+S1.lengthS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.length＿湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華20T.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length再將S2接著拷貝到T中owHar＿eS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.lengthy＿ii

+S1.lengthfor(i=0;i<=S2.length-1;i++)

T.data[i

+S1.len]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華21T.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length再將S2接著拷貝到T中owHar＿eS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.lengthyo＿ii

+S1.lenfor(i=0;i<=S2.length-1;i++)

T.data[i

+S1.len]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華22T.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]0T.length再將S2接著拷貝到T中owHar＿eS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.lengthyo＿uii

+S1.lengthfor(i=0;i<=S2.length-1;i++)

T.data[i

+S1.len]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華230T.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]T.length再將S2接著拷貝到T中owHar＿eS2.data[1][2][0][4][5][3][7][8][6][10][11][9][12][13][14]?yo＿u5S2.length?yo＿uii

+S1.length12T.length=S1.length+S2.length;for(i=0;i<=S2.length-1;i++)

T.data[i

+S1.len]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華24考慮將下面兩個串S1、S2首尾聯(lián)接成一個新串T。S1=“How_are”S2=“_you?”如果假設(shè)：#defineMAX10因?yàn)镾1.length+S2.length

＞MAX，因此S2將被截?cái)?，S1和S2進(jìn)行不完整聯(lián)接。具體過程如下所示。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華25S1.data[1][2][0][4][5][3][7][8][6][9]owHar＿e7S1.lengthS2.data[1][2][0][4][5][3][7][8][6][9]?yo＿u5S2.lengthT.data[1][2][0][4][5][3][7][8][6][9]0T.length初始時湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華26S1.data[1][2][0][4][5][3][7][8][6][9]owHar＿e7S1.lengthT.data[1][2][0][4][5][3][7][8][6][9]0T.length先將S1拷貝到T中for(i=0;i<=S1.length-1;i++)

T.data[i]=S1.data[i];owHar＿eii湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華27再將S2接著拷貝到T中，S2將被截?cái)鄁or(i=0;i<=MAX-S1.length-1;i++)

T.data[i

+S1.length]=S2.data[i];T.data[1][2][0][4][5][3][7][8][6][9]0T.lengthowHar＿eii

+S1.lengthS2.data[1][2][0][4][5][3][7][8][6][9]?yo＿u5S2.length＿湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華28再將S2接著拷貝到T中，S2將被截?cái)郥.data[1][2][0][4][5][3][7][8][6][9]0T.lengthowHar＿eS2.data[1][2][0][4][5][3][7][8][6][9]?yo＿u5S2.length＿yii

+S1.lengthfor(i=0;i<=MAX-S1.length-1;i++)

T.data[i

+S1.length]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華29再將S2接著拷貝到T中，S2將被截?cái)?S2.data[1][2][0][4][5][3][7][8][6][9]?yo＿u5S2.lengthT.data[1][2][0][4][5][3][7][8][6][9]T.lengthowHar＿e＿yoii

+S1.lengthT.length=MAX;10for(i=0;i<=MAX-S1.length-1;i++)

T.data[i

+S1.length]=S2.data[i];湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華30算法7.1voidConcat_sq(SqString*T,SqStringS1,SqStringS2){ inti; inttemp; for(i=0;i<=S1.length-1;i++) (*T).data[i]=S1.data[i]; if(S1.length+S2.length<=MAX)

temp=S2.length; else temp=MAX-S1.length; for(i=0;i<=temp-1;i++) (*T).data[i]=S2.data[i]; (*T).length=S1.length+temp;}湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華31串的堆結(jié)構(gòu)這種存儲方式仍然以一組地址連續(xù)的存儲單元來存放串值字符序列。它有兩個特點(diǎn)：串變量的存儲空間是在程序執(zhí)行過程中動態(tài)分配的；程序中出現(xiàn)的所有串變量可用的存儲空間就是一個稱之為“堆”的共享空間。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華32串的堆結(jié)構(gòu)示意圖b串名snlength堆……自由空間已分配空間addrstartfree湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華33采用堆結(jié)構(gòu)的串類型定義#defineMAXSIZE200charstore[MAXSIZE];//定義堆空間intfree;//指向堆中自由空間的起始位置typedefstruct{intlength;//串的長度intaddrstart;//串在堆中的存儲首地址}HString;湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華34在串的堆結(jié)構(gòu)如何實(shí)現(xiàn)存儲空間的分配？b堆……自由空間已分配空間free新串sn’lengthaddrstart①sn’.addrstart=free;①②for(i=0;i<=sn’.length-1;i++)

store[sn’.addrstart+i]=ch[i];sn’.lengthfree②③free=free+sn’.length;湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華35基于堆結(jié)構(gòu)的基本操作的實(shí)現(xiàn)串復(fù)制運(yùn)算StrCopy_sq串的堆結(jié)構(gòu)（Cont.）湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華36算法7.2intStrCopy_hs(HString*hs,HStringsn){inti;if(free+sn.length>MAXSIZE-1)return-1;(*hs).addrstart=free;(*hs).length=sn.length;for(i=0;i<=sn.length;i++)

store[(*hs).addrstart+i]=store[sn.addrstart+i];

free=free+(*hs).length;return0;}湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華37串的鏈?zhǔn)酱鎯Y(jié)構(gòu)——塊鏈結(jié)構(gòu)由于串也是一種線性表，因此可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，由于串的特殊性（每個數(shù)據(jù)元素是一個字符），在具體實(shí)現(xiàn)時，每個結(jié)點(diǎn)內(nèi)可以存放1個或多個字符，每個結(jié)點(diǎn)可容納字符的個數(shù)稱為塊大小。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華38串的塊鏈結(jié)構(gòu)示意圖How＿are＿y###^9headtaillennextch如果串長不是塊大小的整數(shù)倍，那么最后一個結(jié)點(diǎn)需要用一個特殊的字符來補(bǔ)滿。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華39串的塊鏈結(jié)構(gòu)示意圖How＿are＿y###^9headtaillennextch設(shè)置尾指針是為了便于實(shí)現(xiàn)串的聯(lián)接操作，但要注意的是聯(lián)接時需要處理串尾的特殊(無效)字符#。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華40串的塊鏈結(jié)構(gòu)描述如下#defineCHUNKSIZE4//塊大小typedefstructChNode//塊鏈中的結(jié)點(diǎn)結(jié)構(gòu){ charch[CHUNKSIZE]; structChNode*next;}ChNode;typedefstruct//塊鏈結(jié)構(gòu){ ChNode*head,*tail; intlength;}LinkString;湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華41需要注意塊大小的選擇我們認(rèn)為，存儲密度越接近1，越好。存儲密度=實(shí)際所需存儲量實(shí)際分配的存儲量<1下面我們來分析一下塊大小的選擇對存儲密度的影響(討論的環(huán)境是：16位機(jī)，即每個字符占1個字節(jié)，每個地址占2個字節(jié))。詳見教材P82。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華42串的模式匹配問題描述樸素的模式匹配算法KMP模式匹配算法(詳見教材P85)湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院沈華43什么是模式匹配？Definition

子串定位運(yùn)算又稱為模式匹配(PatternMatching)或串匹配(StringMatching)。在串匹配中，一般將主串稱為目標(biāo)串，子串稱之為模式串。設(shè)S為目標(biāo)串，T為模式串，將從目標(biāo)串S中查找模式串