孫麗云數(shù)據(jù)結(jié)構(gòu)串第講市公開課一等獎省賽課獲獎?wù)n件

4.1串及其運算4.1.1串定義串（或字符串）是由零個或多個字符組成有限序列。普通記作：s=〃c0c1c2…cn-1〃(n≥0)其中：s為串名，用雙引號括起來字符序列是串值；ci(0≤i≤n-1)能夠是字母、數(shù)字或其它字符；雙引號為串值定界符，不是串一部分；字符串字符數(shù)目n稱為串長度。例：s=“computer”分別指出其串名、串值及串長度。串是一個特殊線性表，它數(shù)據(jù)對象是字符集合。1孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第1頁注意1、空串和空格串區(qū)分：零個字符串稱為空串，通常以兩個相鄰雙引號來表示空串。如：s=“”，它長度為零；僅由空格組成串稱為空格串。如：s=〃〃，它長度為空格個數(shù)。2、若串中含有空格，在計算串長時，空格應(yīng)計入串長度中如：s=“I’mastudent〃長度為13。4.1.1串定義2孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第2頁兩個串相等條件：（1）兩個串長度相等；（2）各對應(yīng)位置上字符都相同。串中任意個連續(xù)字符組成序列稱為該串子串。包含子串串被稱為主串。如，“com”、“om”、“a”和“man”都是“commander”子串。4.1.1串定義尤其：空串是任意串子串，任意串是其本身子串。判斷：長度相等且包含相同字符兩個字符串必定相等。（）×3孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第3頁子串在主串中位置是指子串在主串中首次出現(xiàn)時該子串首字符對應(yīng)主串中序號。比如：（1）子串“man”在主串“commander”中位置為4。（2）設(shè)A和B分別為A=“Thisisastring”B=“is”求子串在主串中位置。4.1.1串定義34孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第4頁串是一個簡單數(shù)據(jù)結(jié)構(gòu)，它邏輯結(jié)構(gòu)與線性表十分相同，區(qū)分僅在于串?dāng)?shù)據(jù)對象是字符集。串基本運算與線性表基本運算有很大差異。通常在串基本運算中，以“串整體”作為操作對象；而在線性表基本運算中，大多以“單個元素”作為操作對象。4.1.1串定義5孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第5頁4.1.2串基本運算1．Strassign(s,chars)功效：賦值運算。將串常量chars值賦給串變量s。比如：執(zhí)行strassign(s，“abcd”)運算之后，s值為“abcd”。2．Assign(s,t)功效：賦值運算。將串變量t值賦給串變量s。比如：t="abcd"，則執(zhí)行Assign(s,t)運算之后，s值為"abcd"。6孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第6頁4.1.2串基本運算3．Equal(s,t)功效：判相等運算。若s與t值相等則運算結(jié)果為1，不然為0。4．Length(s)

功效：求串長運算。求串s序列中字符個數(shù)，即串長度。5．Concat(s,t)功效：聯(lián)接運算。將串t第一個字符緊接在串s最終一個字符之后，聯(lián)接得到一個新串。比如s="man",t="kind"，則執(zhí)行Concat(s,t)運算后得到新串為"mankind"。7孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第7頁6．Insert(s,pos,t)功效：插入運算，當(dāng)1≤pos≤Length(s)+1時，在串s第pos個字符之前插入串t。7．Delete(s,pos,len)功效：刪除運算。當(dāng)1≤pos≤Length(s)且0≤len≤Length(s)-pos+1時，從串s中刪去從第pos個字符起長度為len子串。

8．Replace(s,pos,len,t)功效：置換運算。當(dāng)1≤pos≤Length(s)且0≤len≤Length(s)-pos+1時，用串t替換串s中從第pos個字符起長度為len子串。4.1.2串基本運算8孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第8頁例:已知s=“(xyz)+*”,t=“(x+z)*y”。試?yán)寐?lián)接、求子串和置換等基本運算，將s轉(zhuǎn)換為t。voidtrans(){ chara[10]=“(xyz)+*”; strings,t,s1,s2,s3,s4,s5; Strassign(s,a); s1=SubStr(s,3,1); s2=SubStr(s,6,1); s3=SubStr(s,7,1); s4=SubStr(Replace(s,3,1,s2),1,5); s5=concat(s4,s3); t=concat(s5,s1);}s1=“y”s2=“+”s3=“*”9孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第9頁練習(xí)設(shè)S1=“DataStructureCourse”，S2=“Structure”，S3=“Base”，求：

（1）Length(S1)；（2）Insert(S1,5,S3)；

（3）Delete(S1,6,9)；

（4）SubStr(S1,6,9)；(5)Index(S1,S2);21DataBaseStructureCourseDataCourseStructure6中間有兩個空格10孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第10頁C語言中字符串處理函數(shù)●字符串輸出函數(shù)puts（string）charstring[];●字符串輸入函數(shù)gets（string）charstring[];●字符串連接函數(shù)strcat（string1,string2）charstring1[];charstring2[];將string1與string2連接，結(jié)果放在string1中?！褡址截惡瘮?shù)strcpy（string1,string2）charstring1[];charstring2[];將string2中字符拷貝到string1中?！駵y試字符串長度函數(shù)strlen(string）charstring[];測試字符串長度,函數(shù)值為字符串長度值。11孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第11頁C語言中字符串處理函數(shù)●字符比較函數(shù)strcmp（string1,string2）charstring1[];charstring2[];將string1與string2字符從左至右逐一相比較,比較結(jié)果由函數(shù)值帶回。string1=string2,函數(shù)值為0；string1>string2,函數(shù)值為一正整數(shù)；string1<string2,函數(shù)值為一負(fù)整數(shù)?！褡址址髮戅D(zhuǎn)換成小寫函數(shù)strlwr（string）charstring[];將string中字符轉(zhuǎn)換成小寫。●字符串字符小寫轉(zhuǎn)換成大寫函數(shù)strupr（string）charstring[];將string中字符轉(zhuǎn)換成大寫。12孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第12頁4.2串存放結(jié)構(gòu)串是一個特殊線性表，其存放結(jié)構(gòu)與線性表存放結(jié)構(gòu)類似。串有3種存放結(jié)構(gòu)：1、次序存放結(jié)構(gòu)；2、鏈?zhǔn)酱娣沤Y(jié)構(gòu)；3、堆分配存放結(jié)構(gòu)。13孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第13頁4.2.1串次序存放結(jié)構(gòu)串次序存放結(jié)構(gòu)是采取與其邏輯結(jié)構(gòu)相對應(yīng)存放結(jié)構(gòu)，將串中各個字符按次序依次存放在一組地址連續(xù)存放單元里，邏輯上相鄰字符在內(nèi)存中也相鄰。這是一個靜態(tài)存放結(jié)構(gòu)，串值存放分配是在編譯時完成。所以，需要預(yù)先定義串存放空間大小。假如定義空間過大，則會造成空間浪費；假如定義空間過小，則會限制串一些運算，如聯(lián)接、置換運算等。14孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第14頁4.2.1串次序存放結(jié)構(gòu)在次序存放結(jié)構(gòu)中，串類型定義描述以下：#defineMaxLen<最大串長>;//定義能處理最大串長度typedefstruct{charstr[MaxLen];//定義可容納MaxLen個字符字符數(shù)組intcurlen;//定義當(dāng)前實際串長度}string;15孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第15頁4.2.2串鏈?zhǔn)酱娣沤Y(jié)構(gòu)用單鏈表存放串，若每個結(jié)點僅存放一個字符，即使運算輕易實現(xiàn)，運算速度快，但每個結(jié)點指針域所占空間比字符域所占空間要大得多。為了提升空間利用率，能夠使每個結(jié)點存放多個字符，稱為塊鏈結(jié)構(gòu)。這種存放方式空間利用率高，但運算速度要慢。用特殊字符補全16孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第16頁堆存放結(jié)構(gòu)特點：仍以一組空間足夠大、地址連續(xù)存放單元存放串值字符序列，但它們存放空間是在程序執(zhí)行過程中動態(tài)分配。所以也稱為動態(tài)存放分配次序表。每當(dāng)產(chǎn)生一個新串時，系統(tǒng)就從剩下空間起始處為串值分配一個長度和串值長度相等存放空間。在C語言中，存在一個稱為“堆”自由空間，由動態(tài)分配函數(shù)malloc()分配一塊實際串長所需存放空間，假如分配成功，則返回這段空間起始地址，作為串基址。由free()釋放串不再需要空間。

4.2.3串堆分配存放結(jié)構(gòu)17孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第17頁4.3串模式匹配模式匹配：子串定位運算稱為模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個模式串t；模式匹配不成功則指目標(biāo)串s中不存在模式串t。Index(s,t)功效：定位運算。若主串s中存在和串t相同子串，則運算結(jié)果為該子串在主串s中第一次出現(xiàn)位置；不然運算結(jié)果為0。注意:t是非空串。例：word中“查找”功效，就是模式匹配。18孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第18頁4.3.1Brute-Force算法假設(shè)s=“cddcdc”，t=“cdc”，則模式匹配過程以下：19孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第19頁Brute-Force算法C語言描述以下：intIndex(strings,stringt){inti,j;i=0;//指向串s第1個字符j=0;//指向串t第1個字符while((i<s.curlen)&&(j<t.curlen))if(s.str[i]==t.str[j])//比較兩個子串是否相等 {++i;//繼續(xù)比較后繼字符 ++j;}else {i=i-j+1;//串s指針回溯重新開始尋找串t

j=0;}if(j>=t.curlen)

return(i-t.curlen+1);elsereturn0;//匹配失敗返回0}

“==”也能夠20孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第20頁在有些情況下，該算法效率很低。如當(dāng)s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"，t=“aaaaaab“KMP算法對該算法進(jìn)行改進(jìn)。4.3.1Brute-Force算法21孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第21頁KMP算法消除了Brute-Force算法中串s指針回溯。4.3.2KMP算法假設(shè)s=“abacabab”，t=“abab”，第一次匹配過程以下：下次能夠直接進(jìn)行第三次匹配，即i=3，j=0。由此可見，在KMP算法中當(dāng)s.str[i]和t.str[j]比較不相等時，串s指針i無須回溯。

22孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第22頁目標(biāo)串S:ababcabcaabcbaabc模式串T:ababcabdbabc引例分別求next[j]值23孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第23頁KMP算法基本思想設(shè)目標(biāo)串為s，模式串為t

i、j分別為指示s和t指針，i、j初值均為0。若有si=tj，則i和j分別增1；不然，i不變，j退回至j=next[j]位置；比較si和tj。若相等則指針各增1；不然j再退回到下一個j=next[j]位置，再比較si和tj。依次類推，直到以下兩種情況之一：1)j退回到某個j=next[j]時有si=tj，則指針各增1，繼續(xù)匹配；2)j退回至j=-1，此時令指針各增l，即下一次比較si+1和t0

。

關(guān)鍵P89(一定要會求)模式串next值只與模式串本身相關(guān),與目標(biāo)串無關(guān).例:求abaabcacnext值24孫麗云數(shù)據(jù)結(jié)構(gòu)串第講第24頁#defineMaxLen<最大串長度>//定義最大串存放空間intIndex_KPM(strings,stringt){inti,j,next[MaxLen];GetNext(t，next);//先求得模式串next函數(shù)值i=0;//指向串s第1個字符j