數(shù)據(jù)結(jié)構(gòu)課件第4章

第4章串內(nèi)容4.1串的類型定義

4.2串的表示和實(shí)現(xiàn)

4.3串的模式匹配算法

4.4串操作應(yīng)用舉例●基本要求：

1）了解串的概念、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)；

2）掌握串的表示與實(shí)現(xiàn)方法；

3）掌握串的模式匹配算法；

4）學(xué)會(huì)串的正確應(yīng)用；●學(xué)習(xí)重點(diǎn)：

1）串的表示與實(shí)現(xiàn)方法；

2）串的模式匹配算法；4.1串的類型定義4.1.1

串的基本概念

術(shù)語(yǔ)：1）串名：S.2）串值：'a1a2···an'，ai(1≤i≤n).3）串的長(zhǎng)度：串中所包含的字符個(gè)數(shù)，如串

‘a(chǎn)bcde’的長(zhǎng)度為5.4）空串：長(zhǎng)度為0(n=0)的串，它不包含任何

字符，記作S=''(或S=φ).定義：串是由零個(gè)或多個(gè)任意字符組成的字符序列。一般記作：s='a1a2...an'(n>=0)

4.1串的類型定義4.1.1

串的基本概念

術(shù)語(yǔ)：5）空格串：由空格符(ASCII值32)組成的串，如S=‘’.注意S=‘’與S=‘’不

同，前者是長(zhǎng)度為1的非空串，它含有

一個(gè)空格字符，而后者是長(zhǎng)度為0的空

串。

6）子串：串中任意個(gè)連續(xù)的字符組成的子序

列。比如'abcde'中的'bcd'.4.1串的類型定義4.1.1

串的基本概念

用二元組的形式來(lái)定義串：串是一個(gè)二元組,

string=(D,R)其中，D={ai|ai∈字符集,i=1,2,···,n,n≥0}R={N}

有序偶的集合N={<ai-1,ai>|ai-1,ai∈D,i=2,3,···n}

故串的邏輯結(jié)構(gòu)和線性表極為相似。區(qū)別僅在D的定義上。線性表的數(shù)據(jù)對(duì)象可以是任意數(shù)據(jù)類型，而串的數(shù)據(jù)對(duì)象是字符集。4.1串的類型定義4.1.2

串的ADT定義

ADTString{數(shù)據(jù)對(duì)象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：StrAssign(&T,chars)//chars是字符常量。生成一個(gè)其值//等于chars的串T。StrCopy(&T,S)//串S存在則由串S復(fù)制得串TStrEmpty(S)//串S存在則若S為空串,返回真否則返回假pare(S,T)//串S和T存在,若S>T,則返回值大于0,//若S=T,則返回值=0,若S<T,則返回值<04.1串的類型定義4.1.2

串的ADT定義

StrLength(S)//串S存在,返回S的元素個(gè)數(shù)稱為串的長(zhǎng)度.

ClearString(&S)//串S存在,將S清為空串

Concat(&T,S1,S2)//串S1和S2存在,用T返回由S1和S2聯(lián)接

//而成的新串

SubString(&Sub,S,pos,len)//串S存在,求從位置pos開(kāi)始//長(zhǎng)度為len的子串

//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1

Index(S,T,pos)//串S和T存在,T是非空。1<=pos<=StrLength(S)

//若主串S中存在和串T值相同的子串,則返回它在主串S中

//第一次出現(xiàn)的位置,否則函數(shù)值為0

Replace(&S,T,V)//串S,T和V存在,T是非空串,用V替換主串S中

//出現(xiàn)的所有與T相等的不重疊的子串

StrInsert(&S,pos,T)//串S和T存在,1<=pos<=StrLength(S)+1,//在串S的第pos個(gè)字符之前插入串T

StrDelete(&S,pos,len)//串S存在,1<=pos<=StrLength(S)-//len+1從串中刪除第pos個(gè)字符起長(zhǎng)度為len的子串

DestroyString(&S)//串S存在,則串S被銷毀}ADTString4.1串的類型定義4.1.2

串的ADT定義

返回目錄用一組地址連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)串的字符序列。每個(gè)字符占用一個(gè)字節(jié)（Byte）。串中相鄰的字符順序地存放在相鄰的字節(jié)中。4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

DATASTRUCTURES11+11+21+15······圖4.1串的順序存儲(chǔ)結(jié)構(gòu)定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)串定義：#definemaxlen255//允許最大的長(zhǎng)度typedefunsignedcharString[maxlen+1];//下標(biāo)0的位置存放長(zhǎng)度實(shí)現(xiàn)：串的聯(lián)接函數(shù)、求子串的函數(shù)、求子串位置的定位函數(shù)1、串的聯(lián)接函數(shù)Concat(L,s,t)4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

其中，L,s,t是String；

[分析]相當(dāng)于求L=s+t，若s與t連接后的串值長(zhǎng)度超過(guò)maxlen，則超過(guò)部分將被截?cái)唷＿\(yùn)算結(jié)果有三種可能情況。

1)length(s)+length(t)≤maxlen

Length(s)Length(t)s.cht.chL.chLength(L)maxlen圖4.2串的聯(lián)結(jié)操作示意圖（1）1、串的聯(lián)接函數(shù)Concat(L,s,t)4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

2)length(s)+length(t)>maxlen，而length(s)<maxlen需將t的一部分截?cái)?，所得串L中包含s的全部與t的一個(gè)子串圖4.3串的聯(lián)結(jié)操作示意圖（2）Length(s)Length(t)s.cht.chL.chmaxlent中被截去的字符序列Length(L)1、串的聯(lián)接函數(shù)Concat(L,s,t)4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

3)length(s)=maxlen得到的串L是s的串。圖4.4串的聯(lián)結(jié)操作示意圖（3）Length(s)Length(t)s.cht.chL.chmaxlent串被全部截去Length(L)1、串的聯(lián)接函數(shù)Concat(L,s,t)4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

4)函數(shù)實(shí)現(xiàn)StatusConcat(string&L,strings,stringt){/*返回s和t聯(lián)接的結(jié)果，s和t的值不變。*/switch{caselength(s)+length(t)≤maxlen://正常聯(lián)接

L[1..length(s)]=s[1..length(s)];L[length(s)+1..length(s)+length(t)]=t[1..length(t)];L[0]=s[0]+t[0];overflow=false;1、串的聯(lián)接函數(shù)Concat(L,s,t)4.2串的表示和實(shí)現(xiàn)4.2.1

串的定長(zhǎng)順序存儲(chǔ)表示

4)函數(shù)實(shí)現(xiàn)caselength(s)<maxlen://串t截尾

overflow=true;L[1..length(s)]=s[1..length(s)];L[length(s)+1..maxlen]=t[1..maxlen–length(s)];L[0]=maxlen;default://串中只含soverflow=true;L[1..maxlen]=s[1..maxlen];L[0]=maxlen;}//switchreturnoverflow;}//Concat●

用堆結(jié)構(gòu)存儲(chǔ)串值4.2串的表示和實(shí)現(xiàn)4.2.2

串的堆分配存儲(chǔ)表示

特點(diǎn)：每個(gè)串的串值各存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元中，但它們的存儲(chǔ)地址是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。

typedefstruct{ char*ch; intlength; }HString;使用時(shí)必須分配(malloc)和回收(free)內(nèi)存。4.2串的表示和實(shí)現(xiàn)4.2.2

串的堆分配存儲(chǔ)表示

●

用堆結(jié)構(gòu)存儲(chǔ)串值定義HStrings1HStrings2s1s2lengthch2115

···ASTRINGOFLENGTH21F···DATASTRUCTURES

···HeapFreeFree是尚未分配的內(nèi)存首地址圖4.5串的動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)示意圖4.2串的表示和實(shí)現(xiàn)4.2.2

串的堆分配存儲(chǔ)表示

●

聯(lián)接運(yùn)算ConcatStatusConcat(HString&t,HStrings1,HStrings2){

//連接s1,s2到t中

if(t.ch)free(t.ch);//釋放原空間

if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char))))

returnOVERFLOW;

//分配空間

t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];

//處理s1

t.length=s1.length+s2.length;

//長(zhǎng)度

t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];

//s2}4.2串的表示和實(shí)現(xiàn)4.2.3

串的塊鏈存儲(chǔ)表示

●

用線性鏈表的方式存儲(chǔ)串值結(jié)點(diǎn)大小問(wèn)題？^H優(yōu)點(diǎn)：便于實(shí)現(xiàn)插入、刪除等操作缺點(diǎn)：浪費(fèi)存儲(chǔ)空間，存儲(chǔ)利用率最多1/21）結(jié)點(diǎn)大小等于1，即一個(gè)結(jié)點(diǎn)存放1個(gè)字符DATAS^head······圖4.6串值的鏈表存儲(chǔ)方式（結(jié)點(diǎn)大小為1）4.2串的表示和實(shí)現(xiàn)4.2.3

串的塊鏈存儲(chǔ)表示

●

用線性鏈表的方式存儲(chǔ)串值結(jié)點(diǎn)大小問(wèn)題？^H優(yōu)點(diǎn)：存儲(chǔ)效率較高缺點(diǎn)：實(shí)現(xiàn)插入、刪除等操作較復(fù)雜2）結(jié)點(diǎn)大小等于4，即一個(gè)結(jié)點(diǎn)存放4個(gè)字符DATASTRUCTURES^head圖4.7串值的鏈表存儲(chǔ)方式（結(jié)點(diǎn)大小為4）4.2串的表示和實(shí)現(xiàn)4.2.3

串的塊鏈存儲(chǔ)表示

●

用線性鏈表的方式存儲(chǔ)串值

為便于進(jìn)行串的操作，當(dāng)以鏈表存儲(chǔ)串值時(shí)，給出頭、尾指針，加當(dāng)前串的長(zhǎng)度。稱如此定義的串存儲(chǔ)結(jié)構(gòu)為塊鏈結(jié)構(gòu)。

設(shè)尾指針的目的是為了便于進(jìn)行聯(lián)接操作。clst15DATASTRUCTURES#^頭尾長(zhǎng)度圖4.8塊鏈結(jié)構(gòu)示意圖4.2串的表示和實(shí)現(xiàn)4.2.3

串的塊鏈存儲(chǔ)表示

●

用線性鏈表的方式存儲(chǔ)串值//－－－－－－－串的塊鏈存儲(chǔ)表示－－－－－－－#defineCHUNKSIZE80//用戶定義的結(jié)點(diǎn)大小typedefstructchunk{charch[CHUNKSIZE];//塊大小

structchunk*next;//指針}chunk;typedefstruct{chunk*head，*tail;//串的頭、尾指針

intlength;

//串的當(dāng)前長(zhǎng)度}LString;LStringclst;模式匹配算法，其中p為模式設(shè)有兩個(gè)串

s='s1s2···sn'p='p1p2···pm'(0<m≤n)稱主串S為目標(biāo)（串），子串p為模式（串）。串的模式匹配：在目標(biāo)S中尋找模式為p的子串的過(guò)程.串模式匹配的結(jié)果：（1）成功，Index(S,p)>0

（2）失敗，Index(S,p)==0其中Index返回第一個(gè)模式為p的子串在主串s中的位置。4.3串的模式匹配算法4.3.1

求子串位置的定位函數(shù)

Index(s,p)

使用串的基本操作(如Equal，Length，Substr等)實(shí)現(xiàn)求子串位置的定位函數(shù)Index(s,p)的算法：intIndex(strings,stringp){n=Length(S);m=Length(p);i=1;while(i≤n–m+1)if(Equal(Substr(S,i,m),p))returni;elsei++;return0;}

//index4.3串的模式匹配算法4.3.1

求子串位置的定位函數(shù)

Index(s,p)

例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”簡(jiǎn)單的模式匹配算法（BF算法）s：acabaabaabcacaabct：abaabcaci=1j=1s：acabaabaabcacaabct：abaabcaci=2j=1if（s[i]==t[j]）{i++；j++；}if（s[i]！=t[j]）

{i回溯到本趟開(kāi)始的下一個(gè)；

j回溯到1；}算法思想：s：acabaabaabcacaabct：abaabcaci=2j=1s：acabaabaabcacaabct：abaabcaci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5i=8j=6s：acabaabaabcacaabct：abaabcaci=4j=1s：acabaabaabcacaabct：abaabcaci=5j=1i=6j=2s：acabaabaabcacaabct：abaabcaci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j=8i=14j=9（2）