孫麗云數(shù)據(jù)結(jié)構(gòu)串第講

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

功能：求串長(zhǎng)運(yùn)算。求串s序列中字符的個(gè)數(shù)，即串的長(zhǎng)度。5．Concat(s,t)功能：聯(lián)接運(yùn)算。將串t的第一個(gè)字符緊接在串s的最后一個(gè)字符之后，聯(lián)接得到一個(gè)新串。例如s="man",t="kind"，則執(zhí)行Concat(s,t)運(yùn)算后得到的新串為"mankind"。76．Insert(s,pos,t)功能：插入運(yùn)算，當(dāng)1≤pos≤Length(s)+1時(shí)，在串s的第pos個(gè)字符之前插入串t。7．Delete(s,pos,len)功能：刪除運(yùn)算。當(dāng)1≤pos≤Length(s)且0≤len≤Length(s)-pos+1時(shí)，從串s中刪去從第pos個(gè)字符起長(zhǎng)度為len的子串。

8．Replace(s,pos,len,t)功能：置換運(yùn)算。當(dāng)1≤pos≤Length(s)且0≤len≤Length(s)-pos+1時(shí)，用串t替換串s中從第pos個(gè)字符起長(zhǎng)度為len的子串。4.1.2串的基本運(yùn)算8例:已知s=“(xyz)+*”,t=“(x+z)*y”。試?yán)寐?lián)接、求子串和置換等基本運(yù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練習(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中間有兩個(gè)空格10C語(yǔ)言中的字符串處理函數(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(cè)試字符串長(zhǎng)度函數(shù)strlen(string）charstring[];測(cè)試字符串長(zhǎng)度,函數(shù)值為字符串的長(zhǎng)度值。11C語(yǔ)言中的字符串處理函數(shù)●字符比較函數(shù)strcmp（string1,string2）charstring1[];charstring2[];將string1與string2的字符從左至右逐個(gè)相比較,比較結(jié)果由函數(shù)值帶回。string1=string2,函數(shù)值為0；string1>string2,函數(shù)值為一正整數(shù)；string1<string2,函數(shù)值為一負(fù)整數(shù)?！褡址址髮?xiě)轉(zhuǎn)換成小寫(xiě)函數(shù)strlwr（string）charstring[];將string中的字符轉(zhuǎn)換成小寫(xiě)?！褡址址?xiě)轉(zhuǎn)換成大寫(xiě)函數(shù)strupr（string）charstring[];將string中的字符轉(zhuǎn)換成大寫(xiě)。124.2串的存儲(chǔ)結(jié)構(gòu)串是一種特殊的線性表，其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類(lèi)似。串有3種存儲(chǔ)結(jié)構(gòu)：1、順序存儲(chǔ)結(jié)構(gòu)；2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；3、堆分配存儲(chǔ)結(jié)構(gòu)。134.2.1串的順序存儲(chǔ)結(jié)構(gòu)串的順序存儲(chǔ)結(jié)構(gòu)是采用與其邏輯結(jié)構(gòu)相對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)，將串中的各個(gè)字符按順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里，邏輯上相鄰的字符在內(nèi)存中也相鄰。這是一種靜態(tài)存儲(chǔ)結(jié)構(gòu)，串值的存儲(chǔ)分配是在編譯時(shí)完成的。因此，需要預(yù)先定義串的存儲(chǔ)空間大小。如果定義的空間過(guò)大，則會(huì)造成空間浪費(fèi)；如果定義的空間過(guò)小，則會(huì)限制串的某些運(yùn)算，如聯(lián)接、置換運(yùn)算等。144.2.1串的順序存儲(chǔ)結(jié)構(gòu)在順序存儲(chǔ)結(jié)構(gòu)中，串的類(lèi)型定義描述如下：#defineMaxLen<最大串長(zhǎng)>;//定義能處理的最大的串長(zhǎng)度typedefstruct{charstr[MaxLen];//定義可容納MaxLen個(gè)字符的字符數(shù)組intcurlen;//定義當(dāng)前實(shí)際串長(zhǎng)度}string;154.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用單鏈表存放串，若每個(gè)結(jié)點(diǎn)僅存儲(chǔ)一個(gè)字符，雖然運(yùn)算容易實(shí)現(xiàn)，運(yùn)算速度快，但每個(gè)結(jié)點(diǎn)的指針域所占空間比字符域所占空間要大得多。為了提高空間的利用率，可以使每個(gè)結(jié)點(diǎn)存放多個(gè)字符，稱(chēng)為塊鏈結(jié)構(gòu)。這種存儲(chǔ)方式空間利用率高，但運(yùn)算速度要慢。用特殊字符補(bǔ)全16堆存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：仍以一組空間足夠大的、地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的。所以也稱(chēng)為動(dòng)態(tài)存儲(chǔ)分配的順序表。每當(dāng)產(chǎn)生一個(gè)新串時(shí)，系統(tǒng)就從剩余空間的起始處為串值分配一個(gè)長(zhǎng)度和串值長(zhǎng)度相等的存儲(chǔ)空間。在C語(yǔ)言中，存在一個(gè)稱(chēng)為“堆”的自由空間，由動(dòng)態(tài)分配函數(shù)malloc()分配一塊實(shí)際串長(zhǎng)所需的存儲(chǔ)空間，如果分配成功，則返回這段空間的起始地址，作為串的基址。由free()釋放串不再需要的空間。

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

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

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

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

22目標(biāo)串S:ababcabcaabcbaabc模式串T:ababcabdbabc引例分別求next[j]值23KMP算法基本思想設(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再退回到下一個(gè)j=next[j]的位置，再比較si和tj。依次類(lèi)推，直到下列兩種情況之一：1)j退回到某個(gè)j=next[j]時(shí)有si=tj，則指針各增1，繼續(xù)匹配；2)j退回至j=-1，此時(shí)令指針各增l，即下一次比較si+1和t0

。

關(guān)鍵P89(一定要會(huì)求)模式串的next值只與模式串本身有關(guān),與目標(biāo)串無(wú)關(guān).例:求abaabcac的next值24#defineMaxLen<最大串的長(zhǎng)度>//定義最大串存儲(chǔ)空間intIndex_KPM(strings,stringt){inti,j,next[MaxLen];GetNext(t，next);//先求得模式串的next函數(shù)值i=0;//指向串s的第