湖北工業大學計算機學院沈華1第七章串

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

串的存儲結構及基本運算的實現串的模式匹配湖北工業大學計算機學院沈華2什么是串String？串的定義一些相關概念串的基本運算湖北工業大學計算機學院沈華3串的定義Definition

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

a1a2…an為串值。湖北工業大學計算機學院沈華4一些相關概念串長

串中所含字符的個數n。空串EmptyString

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

記為：

空格串BlankString

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

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

S4=“CAF”；S2是S1的子串，S1是S2的主串；S3是S1的子串，S1是S3的主串；S4不是S1的子串，S1不是S4的主串。湖北工業大學計算機學院沈華6一些相關概念（Cont.）字符在串中的位置

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

S2=“CAED”，S3=“AE”；S2在S1中的位置是3；S3在S1中的位置是4。湖北工業大學計算機學院沈華7一些相關概念（Cont.）串相等

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

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

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

線性表的操作大多以“單個數據元素”為操作對象；而串操作通常以“串的整體”或“子串”作為操作對象。串的基本運算（Cont.）湖北工業大學計算機學院沈華10串的存儲結構及基本運算的實現串的順序存儲結構串的鏈式存儲結構（塊鏈結構）串的堆結構湖北工業大學計算機學院沈華11串的順序存儲結構什么是串的順序存儲結構？類似于線性表的順序存儲表示方法，用一組地址連續的存儲單元來依次存放串值的字符序列。采用順序存儲的串稱為順序串。湖北工業大學計算機學院沈華12串的順序存儲結構（Cont.）順序串的類型定義

#defineMAX100typedefstruct{

char

data[MAX];intlength;//記錄當前串的長度

}SqString;湖北工業大學計算機學院沈華13串的順序存儲結構（Cont.）關于串長表示的說明顯示的方式表示用一個整型的輔助變量來記錄當前串的實際長度。隱式的方式表示在串值后面加一個不計入串長的結束標記字符。湖北工業大學計算機學院沈華14順序串中基本運算的實現串連接運算Concat_sq串的順序存儲結構（Cont.）湖北工業大學計算機學院沈華15串連接運算

Concat_sq考慮將下面兩個串S1、S2首尾聯接成一個新串T。S1=“How_are”S2=“_you?”并假設有：#defineMAX15因為S1.length+S2.length≤MAX，因此可以實現S1和S2的完整聯接。具體過程如下所示。湖北工業大學計算機學院沈華16順序串S1的存儲結構如下所示：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的存儲結構如下所示：湖北工業大學計算機學院沈華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初始時湖北工業大學計算機學院沈華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湖北工業大學計算機學院沈華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＿湖北工業大學計算機學院沈華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];湖北工業大學計算機學院沈華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];湖北工業大學計算機學院沈華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];湖北工業大學計算機學院沈華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];湖北工業大學計算機學院沈華24考慮將下面兩個串S1、S2首尾聯接成一個新串T。S1=“How_are”S2=“_you?”如果假設：#defineMAX10因為S1.length+S2.length

＞MAX，因此S2將被截斷，S1和S2進行不完整聯接。具體過程如下所示。湖北工業大學計算機學院沈華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初始時湖北工業大學計算機學院沈華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湖北工業大學計算機學院沈華27再將S2接著拷貝到T中，S2將被截斷for(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＿湖北工業大學計算機學院沈華28再將S2接著拷貝到T中，S2將被截斷T.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];湖北工業大學計算機學院沈華29再將S2接著拷貝到T中，S2將被截斷0S2.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];湖北工業大學計算機學院沈華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;}湖北工業大學計算機學院沈華31串的堆結構這種存儲方式仍然以一組地址連續的存儲單元來存放串值字符序列。它有兩個特點：串變量的存儲空間是在程序執行過程中動態分配的；程序中出現的所有串變量可用的存儲空間就是一個稱之為“堆”的共享空間。湖北工業大學計算機學院沈華32串的堆結構示意圖b串名snlength堆……自由空間已分配空間addrstartfree湖北工業大學計算機學院沈華33采用堆結構的串類型定義#defineMAXSIZE200charstore[MAXSIZE];//定義堆空間intfree;//指向堆中自由空間的起始位置typedefstruct{intlength;//串的長度intaddrstart;//串在堆中的存儲首地址}HString;湖北工業大學計算機學院沈華34在串的堆結構如何實現存儲空間的分配？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;湖北工業大學計算機學院沈華35基于堆結構的基本操作的實現串復制運算StrCopy_sq串的堆結構（Cont.）湖北工業大學計算機學院沈華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;}湖北工業大學計算機學院沈華37串的鏈式存儲結構——塊鏈結構由于串也是一種線性表，因此可以采用鏈式存儲結構，由于串的特殊性（每個數據元素是一個字符），在具體實現時，每個結點內可以存放1個或多個字符，每個結點可容納字符的個數稱為塊大小。湖北工業大學計算機學院沈華38串的塊鏈結構示意圖How＿are＿y###^9headtaillennextch如果串長不是塊大小的整數倍，那么最后一個結點需要用一個特殊的字符來補滿。湖北工業大學計算機學院沈華39串的塊鏈結構示意圖How＿are＿y###^9headtaillennextch設置尾指針是為了便于實現串的聯接操作，但要注意的是聯接時需要處理串尾的特殊(無效)字符#。湖北工業大學計算機學院沈華40串的塊鏈結構描述如下#defineCHUNKSIZE4//塊大小typedefstructChNode//塊鏈中的結點結構{ charch[CHUNKSIZE]; structChNode*next;}ChNode;typedefstruct//塊鏈結構{ ChNode*head,*tail; intlength;}LinkString;湖北工業大學計算機學院沈華41需要注意塊大小的選擇我們認為，存儲密度越接近1，越好。存儲密度=實際所需存儲量實際分配的存儲量<1下面我們來分析一下塊大小的選擇對存儲密度的影響(討論的環境是：16位機，即每個字符占1個字節，每個地址占2個字節)。詳見教材P82。湖北工業大學計算機學院沈華42串的模式匹配問題描述樸素的模式匹配算法KMP模式匹配算法(詳見教材P85)湖北工業大學計算機學院沈華43什么是模式匹配？Definition

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