算法與數(shù)據(jù)結(jié)構(gòu)：第四章 串

1、數(shù)據(jù)結(jié)構(gòu)-第四章 串1第四章 串 串是特殊的線性表，數(shù)據(jù)元素是單個(gè)字符。線性表的操作通常以“數(shù)據(jù)元素”為操作對(duì)象；串的操作主要以“子串”為操作對(duì)象。4.1 串類型的定義4.2 串的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)4.3 串的模式匹配算法4.4 串應(yīng)用示例文本編輯本章學(xué)習(xí)要點(diǎn)及習(xí)題數(shù)據(jù)結(jié)構(gòu)-第四章 串24.1 串類型的定義4.1.1 串的概念 串（字符串）：是由零個(gè)或多個(gè)字符組成的有限序列。 記作：s = a1a2an (n0) 串長：串中字符的個(gè)數(shù)n。 子串和主串：串中任意個(gè)連續(xù)的字符組成的子序列稱 為該串的子串。包含子串的串稱為主串。 串相等：兩個(gè)串長度相等，且對(duì)應(yīng)位置的字符都相等。 空串和空白串：空串

2、不包含任何字符,表示為 ； 空白串由一個(gè)或多個(gè)空格組成，如 。數(shù)據(jù)結(jié)構(gòu)-第四章 串34.1.2 串的常用基本操作 (1)用串常量賦值 StrAssign(&T, chars) 用串變量賦值 StrCopy(&T, S) (2)判定空串 StrEmpty(S) (3)兩串比較 StrCompare(S, T) (4)求串長 StrLength(S) (5)串清空 ClearString(&S) (6)兩串連接 Concat(&T, S1, S2) (7)求子串 SubString(&Sub, S, pos, len) (8)子串定位 Index(S, T, pos) (9)子串置換 Replac

3、e(&S, T, V) (10)插入子串 StrInsert(&S, pos, T) (11)刪除子串 StrDelete(&S, pos, len) (12)串銷毀 DestroyString(&S)串類型的最小操作子集數(shù)據(jù)結(jié)構(gòu)-第四章 串4例 設(shè)s=I am a student. t=OK! p=student q=nurse r=good (1) Concat(newstr, s, t ) newstr= I am a student. OK! (2) Replace(s, p , q); s=I am a nurse. (3) StrInsert(s, 8, r) s=I am a g

4、ood nurse. 數(shù)據(jù)結(jié)構(gòu)-第四章 串54.2 串的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)（1）定長順序存儲(chǔ)表示7 s t u d e n t0 1 2 3 4 5 6 7 8MAXSTRLEN#define MAXSTRLEN 255 /予定義最大串長typedef unsigned char SStringMAXSTRLEN+1;存放串的長度存儲(chǔ)定義B O O K 0C語言本身的串表示方式：不便于求串長等操作數(shù)據(jù)結(jié)構(gòu)-第四章 串6基本操作實(shí)現(xiàn)示例約定：串值長度上溢時(shí)，用“截尾法”處理， 即 “截?cái)唷背^予定義長度的部分。int StrCompare(SString S, SS

5、tring T)/ST,返回值0；S=T，返回0；ST，返回值 0 for (i=1; i=S0 & i=T0; i+) if (Si != Ti ) return(Si - Ti ); return S0-T0 / StrCompare操作基于“字符序列復(fù)制”i數(shù)據(jù)結(jié)構(gòu)-第四章 串7 Status Concat(SString &T, SString S1, SString S2) /用T返回串s1和s2聯(lián)接而成的新串。 /若未截?cái)?，返回TRUE，否則返回FALSE if ( S10+S20 = MAXSTRLEN ) T1.S10 = S11.S10; Ts10+1.S10+S20 = S

6、21.S20; T0= S10+S20; uncut=TRUE; else if (S10MAXSTRLEN) T1.S10 = S11.S10; Ts10+1.MAXSTRLEN = S21.MAXSTRLEN-S10; T0= MAXSTRLEN; uncut=FALSE; else T0.MAXSTRLEN= S10.MAXSTRLEN; uncut= FALSE; return uncut; / Concat數(shù)據(jù)結(jié)構(gòu)-第四章 串8 Status SubString(SString &Sub, SString S, int pos, int len) /用Sub返回串S從第pos個(gè)字符起

7、長度為len的子串 if ( (posS0 | len S0-pos+1 )return ERROR; Sub1.len= Spos.pos+len-1; Sub0= len return OK; / SubString0 1 poslenSSub數(shù)據(jù)結(jié)構(gòu)-第四章 串9（2）堆分配存儲(chǔ)表示動(dòng)態(tài)分配串值存儲(chǔ)空間，避免定長結(jié)構(gòu)的截?cái)喱F(xiàn)象。typedef struct char *ch; /串空間基址，按串長申請(qǐng)int length; /串長度HString;存儲(chǔ)定義數(shù)據(jù)結(jié)構(gòu)-第四章 串10基本操作實(shí)現(xiàn)示例int StrCompare(HString S, HString T) /ST,返回值0；S

8、=T，返回0；ST，返回值 0 for (i=0; iS.length & iT.length; i+) if (S.chi != T.chi ) return S.chi - T.chi ); return S.length-T.length ; / StrCompareS1S2數(shù)據(jù)結(jié)構(gòu)-第四章 串11 Status Concat(HString &T, HString S1, HString S2) /返回串S1和S2聯(lián)接而成的新串T if (T.ch) free(T.ch); /釋放T原有空間 if ( ! (T.ch=(char *)malloc(S1.length+S2.length

9、)* sizeof(char) exit(OVERFLOW); T.length=S1.length+S2.length; T.ch0.s1.length-1=S1.ch0.s1.length-1; T.chS1.length. T.length-1=S2.ch0.S2.length-1; return OK; / ConcatS1S2T數(shù)據(jù)結(jié)構(gòu)-第四章 串12 Status SubString(HString &Sub, HString S, int pos, int len) /求串S從第pos個(gè)字符起長度為len的子串Sub if ( (posS.length | len S.lengt

10、h-pos+1 )return ERROR; if (Sub.ch) free(Sub.ch); if ( !len ) Sub.ch=NULL; Sub.length=0; else if ( !(Sub.ch=(char *)malloc(len* sizeof(char) exit(OVERFLOW); Sub.ch0.len-1=S.chpos-1.pos+len-2; Sub.length=len; return OK; / SubStringpos-10lenS.length-1數(shù)據(jù)結(jié)構(gòu)-第四章 串134.2.2 串的塊鏈存儲(chǔ)結(jié)構(gòu)ABOOK S.headS.tailA B OO K

11、 # # S.headS.tail設(shè)置尾指針便于聯(lián)結(jié)操作#define CHUNKSIZE 4 /由用戶定義塊大小typedef struct Chunk char chCHUNKSIZE; struct Chunk * next;Chunk;typedef struct Chunk * head， * tail; /串的、尾頭指針 int curlen; /串的當(dāng)前長度LString;占用存儲(chǔ)量大且操作不便，實(shí)際應(yīng)用很少。數(shù)據(jù)結(jié)構(gòu)-第四章 串144.3 串的模式匹配算法模式匹配 即子串的定位操作。 是各種串處理系統(tǒng)中最重要的操作之一。操作定義 Index（S，T， pos） S主串，T子串

12、pos從該位序字符開始向后尋找匹配例 S=abcabcdefabcdmn T=efapq 匹配失敗 T=bcd 匹配成功，有效位移 =5以定長順序存儲(chǔ)結(jié)構(gòu)討論算法實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)-第四章 串154.3.1 樸素的模式匹配算法主串S子串T1 posn(S0)m(T0)i=pos;j=1;1子串Ti=pos+1;j=1;失配1主串S子串T1nmiji-j+1回溯 ：i=i-j+2;j=1;失配ST1 n1n-m+1m數(shù)據(jù)結(jié)構(gòu)-第四章 串16 int Index(SString S, SString T, int pos) /返回子串T在主串S中從第pos個(gè)字符開始的位置。 /若不存在，返回值為0。1

13、posStrLength(S) i=pos; j=1; /設(shè)定主串、子串字符開始比較的位置 while ( i=S0 & j T0 ) return i-T0 ; /匹配成功 else return 0; / Index最壞情況字符比較次數(shù)為：(n-m+1)m算法復(fù)雜度: O(mn)數(shù)據(jù)結(jié)構(gòu)-第四章 串174.3.2 模式匹配的一種改進(jìn)算法(KMP算法)改進(jìn)之處 在比較過程中，主串的下標(biāo)i只增不減，不回溯，可使算法復(fù)雜度提高到O(m+n) 。分析 1 2 3 4 5 6 7 8 9 10 11 12 13 主串s a b c d a b c d a b e g h s1s2sn 子串t a b

14、 c d a b e g p1p2pm mni=7j=7a b c d a b e gj=3本趟比較失配點(diǎn)：i=7, j=7 (即s7p7) 失配點(diǎn)處 p1p2=s5s6=p5p6 p1pk-1=pj-k+1pj-1下趟比較：i不變，j=k(此處即3)數(shù)據(jù)結(jié)構(gòu)-第四章 串18引入next數(shù)組nextj=k：k是當(dāng)模式(子串)中第j個(gè)字符與主串中相應(yīng)字符“失配”時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位置。 0 當(dāng) j=1 時(shí) 代表下一趟比較i=i+1，j=1 maxk |1kj 且 p1pk-1=pj-k+1pj-1 當(dāng)此集合不空時(shí) 1 其它情況(即j1且上述集合為空)例 a b c

15、d a b c d a b e g h a a a a a nextj 0 1 1 1 1 2 3 4 5 6 7 1 1 0 1 2 3 4nextj=下一趟比較i不變，j=k下一趟比較i不變，j=1kjk-1k-1k-1stik數(shù)據(jù)結(jié)構(gòu)-第四章 串19KMP算法描述int index_KMP(SString S, SString T, int pos) i=pos; j=1; while (i = S0 & j T0) return i-T0; else return 0;/index_KMPposij數(shù)據(jù)結(jié)構(gòu)-第四章 串20求next數(shù)組值算法思想：利用遞推 即已知next1=0, ne

16、xtj=k; 求nextj+1 主串 p1 . pj-k+1pj-k+2 pj-1 pj pj+1 pm 子串 p1 p2 pk-1 pk . pm算法描述p1p2 . pnextk . . . pmvoid get_next(SString T, int &next ) j=1; k=0; next1=0; while ( jT0 ) if ( k=0 | Tj=Tk ) +j; +k; nextj=k; else k= nextk; /get_nextj j+1k-1數(shù)據(jù)結(jié)構(gòu)-第四章 串21修正next數(shù)組Next數(shù)組的缺陷 s= a b c a b c a x a b c a b c a

17、 b b a c t= a b c a b c a b b a c next8=5 a b c a b c a b b a c next5=2 a b c a b c a b b a c next2=1 a b c a b c a b b a c 存在p8=p5=p2, 因此當(dāng)s8p8時(shí)，s8與p5 、 p2的比較是無意義的。改進(jìn)方法 用nextval數(shù)組代替next數(shù)組 求出Pj處的k值；若Pj=Pk，則nextvalj=nextvalk 否則nextvalj=kij數(shù)據(jù)結(jié)構(gòu)-第四章 串22例 j 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 a b c a b c a

18、 b b a c a a a a b nextj 0 1 1 1 2 3 4 5 6 1 2 0 1 2 3 4 nextvalj 0 1 1 0 1 1 0 1 6 0 2 0 0 0 0 4算法描述void get_nextval(SString T, int &nextval ) j=1; k=0; nextval1=0; while ( jT0 ) if (k=0 | Tj=Tk) +j; +k; if ( Tj != Tk ) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; /get_nextval數(shù)據(jù)結(jié)構(gòu)-第四章 串23KMP算法時(shí)間復(fù)雜度分析 get_nextval（）； index_KMP（）； 通常，模式串長度m主串長度n求next(nextval)數(shù)組：O(m) 主串與模式串匹配： O(n) 整個(gè)匹配算法O(m+n) 數(shù)據(jù)結(jié)構(gòu)-第四章 串244.4 串應(yīng)用示例文本編輯分析操作對(duì)象 文本串 （行是文本串的子串）基本操作查找插入刪除輕輕的我走了，正如我輕輕的來；我輕輕的招手，作別西天的云彩。那河畔的金柳，是夕陽中的新娘波光里的艷影，在我的心頭蕩漾。軟泥上的青荇，油油的在水底招搖；在康河的柔波里，我甘