第章 數(shù)組 (Array)北京科技大學(xué)

1、“串串”（StringString）是字符串的簡稱）是字符串的簡稱，它也是一種，它也是一種特殊的線性表特殊的線性表，由它組，由它組成的線性表的數(shù)據(jù)元素最為簡單，僅成的線性表的數(shù)據(jù)元素最為簡單，僅為單個字符為單個字符1234 (1)(1)串是由零個或多個字符組成的串是由零個或多個字符組成的有序序列有序序列。 (2)(2)值為空格的字符串值為空格的字符串不同不同于空串。于空串。 (3)(3)值為單個字符的字符串值為單個字符的字符串不同不同于單個字符。于單個字符。 (4)(4)一個串中任意多個連續(xù)的字符組成的子序一個串中任意多個連續(xù)的字符組成的子序 列稱為該串的列稱為該串的子串子串。包含該子串的串稱

2、為。包含該子串的串稱為 主串主串。(5) (5) 子串在主串中的位置指的是該子串的第一個子串在主串中的位置指的是該子串的第一個 字符在主串中的位置。字符在主串中的位置。(6) (6) 兩個兩個串相等串相等指兩個串中的字符序列一一對應(yīng)指兩個串中的字符序列一一對應(yīng)(7) (7) 一個串的一個串的長度長度指的是串中所包含的字符個數(shù)指的是串中所包含的字符個數(shù)(8) (8) 在在C C語言中語言中, ,串是由雙引號括起來的，雙引號串是由雙引號括起來的，雙引號 本身不是串的組成部分。本身不是串的組成部分。舉例舉例S1 = “I am a student”S2 = “child”S3 = “a”S4 = “

3、student”S5 = “student ” S1S1是是S3S3和和S4S4的主串，子串的主串，子串S3S3在在S1S1中的位中的位置為置為3 3，子串，子串S4S4在在S1S1中的位置為中的位置為8 8。S4S4的長度的長度是是7 7，S5S5的長度是的長度是8 8，S4S4和和S5S5不相等，不相等，S5S5不是不是S1S1的子串。的子串。12341.串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)2.串的鏈?zhǔn)酱鎯Y(jié)構(gòu)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.串的索引存儲結(jié)構(gòu)串的索引存儲結(jié)構(gòu) 串的順序存儲結(jié)構(gòu)簡稱為串的順序存儲結(jié)構(gòu)簡稱為順序串順序串。順序。順序串中的字符被順序地存放在內(nèi)存的一片相鄰串中的字符被順序地存放在內(nèi)

4、存的一片相鄰的單元中。的單元中。 在在C C語言中，用一個特定的、不會出現(xiàn)在語言中，用一個特定的、不會出現(xiàn)在串中的字符作為串的終結(jié)符，這就是串中的字符作為串的終結(jié)符，這就是00This is a string00Maxsize-1串的順序存儲形式串的順序存儲形式#define maxsize 32typedef struct char chmaxsize;int curlen; seqstring;鏈串的定義與單鏈表類似，串鏈串的定義與單鏈表類似，串的鏈接存儲形式為的鏈接存儲形式為typedef struct linknode char data;struct linknode *next;

5、linkstring;abcdefga b c de f g 0a b c xf g 0 0y z d e結(jié)點(diǎn)大小為結(jié)點(diǎn)大小為1 1的鏈串的鏈串結(jié)點(diǎn)大小為結(jié)點(diǎn)大小為4 4的鏈串的鏈串結(jié)點(diǎn)大小為結(jié)點(diǎn)大小為4 4的鏈串在第三個字符后插入的鏈串在第三個字符后插入“xyz”xyz” 該方法是用串變量的名字作為關(guān)鍵字該方法是用串變量的名字作為關(guān)鍵字組織名字表，該表中存儲的是串名和串值之組織名字表，該表中存儲的是串名和串值之間的對應(yīng)關(guān)系。名字表一般是順序存放的。間的對應(yīng)關(guān)系。名字表一般是順序存放的。s17s23. a b c d e fg b c d .帶長度的名字表帶長度的名字表name length

6、stadrname length stadr串的索引存儲形式帶長度的名字表串的索引存儲形式帶長度的名字表typedef struct char namemaxsize;int length;char *stadr; lnodes17s23. a b c d e fg b c d .帶長度的名字表帶長度的名字表name length stadrname length stadrs1s2. a b c d e fg b c d .帶末指針的名字表帶末指針的名字表name enadr stadrname enadr stadr串的索引存儲形式帶末指針的名字表串的索引存儲形式帶末指針的名字表typed

7、ef struct char namemaxsize;char *stadr,*enadr; enode;s10s21bcd0. a b c d e fg 0帶特征位的名字表帶特征位的名字表 name tag stadr name tag stadr/value/value.串的索引存儲形式帶特征位的名字表串的索引存儲形式帶特征位的名字表typedef struct char namemaxsize;union char *stadr; char value4; uval; cedure. var i:integer在索引存儲表示下，在索引存儲表示下

8、， 串值空間的動態(tài)分配示意串值空間的動態(tài)分配示意name length stadrname length stadr0 14 free0 14 free1234(1) (1) 賦值賦值(2) (2) 聯(lián)接聯(lián)接(3) (3) 求串長求串長(4) (4) 求子串求子串(5) (5) 比較串的大小比較串的大小(6) (6) 插入插入(7) (7) 刪除刪除(8) (8) 子串定位子串定位(9) (9) 置換置換程序程序12341.求子串位置的定位函數(shù)求子串位置的定位函數(shù)2.簡單的模式匹配簡單的模式匹配3.無回溯的模式匹配無回溯的模式匹配(KMP算法算法) 子串的定位操作通常稱為串的子串的定位操作通常

9、稱為串的模式匹配模式匹配，它是串處理系統(tǒng)中最重要的操作之一，其操作它是串處理系統(tǒng)中最重要的操作之一，其操作記為記為Index(S,TIndex(S,T) )；其中；其中S=“sS=“s0 0s s1 1s sn-1n-1”為為主主串串，T=“tT=“t0 0t t1 1t tm-1m-1”為為子串子串（模式模式） 其意義是，若在其意義是，若在S S中存在一個與中存在一個與T T相等的子相等的子串，則稱匹配成功，函數(shù)返回串，則稱匹配成功，函數(shù)返回T T在在S S中首次出現(xiàn)中首次出現(xiàn)的開始位置；否則，稱為匹配失敗，函數(shù)返回的開始位置；否則，稱為匹配失敗，函數(shù)返回值為值為-1.-1.基本思想：基本思

10、想： 從主串從主串S S的第一個字符和子串的第一個字符和子串T T的第一個字的第一個字符開始比較，若相等，則比較它們的下一個字符開始比較，若相等，則比較它們的下一個字符；若不等，則不論前邊已經(jīng)有幾個字符相符；若不等，則不論前邊已經(jīng)有幾個字符相等，子串等，子串T T都要從第一個字符開始與主串都要從第一個字符開始與主串S S的第的第二個字符重新比較；依次類推，直到子串二個字符重新比較；依次類推，直到子串T T的每的每個字符依次和主串個字符依次和主串S S的一個連續(xù)的字符序列相的一個連續(xù)的字符序列相等，則模式匹配成功等，則模式匹配成功 i=2 i=2 第一次匹配第一次匹配 s = c d d c d

11、 e s = c d d c d e 失敗失敗 t = c d et = c d e j=2 j=2 i=1i=1第二次匹配第二次匹配 s = c d d c d e s = c d d c d e 失敗失敗 t = c d et = c d e j=0 j=0 i=2i=2第三次匹配第三次匹配 s = c d d c d e s = c d d c d e 失敗失敗 t = c d et = c d e j=0 j=0 i=6i=6第四次匹配第四次匹配 s = c d d c d e s = c d d c d e 成功成功 t = c d e t = c d e 返回返回i-ji-j=3=

12、3 j=3 j=3 簡單模式匹配算法簡單模式匹配算法int Index(seqstring *S,seqstring *T) int i=0,j=0; while (icurlen)&(jcurlen)if (S-chi=T-chj) i+; j+;elsei=i-j+1; j=0; if (j=T-curlen) return(i-T-curlen); else return(-1); 鏈串上的子串定位運(yùn)算鏈串上的子串定位運(yùn)算linkstring *INDEXL(linkstring *S,linkstring *T) linkstring *first,*sptr,*tptr; f

13、irst=S; sptr=first; tptr=T; while (sptr&tptr) if (sptr-data=tptr-data) sptr=sptr-next; tptr=tptr-next; else first=first-next; sptr=first; tptr=T; if (tptr=NULL) return(first); else return(NULL) 算法分析算法分析 在最壞情況下，第在最壞情況下，第i i趟匹配成功，前面趟匹配成功，前面i-1i-1趟的不成功的匹配中，每趟比較了趟的不成功的匹配中，每趟比較了m m次，第次，第i i趟成功時也比較了趟成

14、功時也比較了m m次，所以共比次，所以共比較了較了i i m m次。因此在最壞情況下，平均次。因此在最壞情況下，平均比較次數(shù)是：比較次數(shù)是：由于由于nmnm，故上述的時間復(fù)雜度為，故上述的時間復(fù)雜度為O(mO(mn)n)2/ )2()1/()(1111mnmimnmmiPmnimnii 分析簡單匹配算法可以發(fā)現(xiàn)，算法中出分析簡單匹配算法可以發(fā)現(xiàn)，算法中出現(xiàn)的主串指針回朔并非一定必要。現(xiàn)的主串指針回朔并非一定必要。第一次匹配第一次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a

15、c a b a a b c a c第二次匹配第二次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第三次匹配第三次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第四次匹配第四次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c

16、 a c a a b c a b a a b c a c a b a a b c a c 可見，一旦可見，一旦s si i和和t tj j比較不相等，主串比較不相等，主串s s的指針不一定要回朔，主串的指針不一定要回朔，主串s si i（或（或s si+1i+1）可）可直接與直接與t tk k（0=kj0=kj）比較，）比較，k k的決定與主串的決定與主串s s并無關(guān)系，而只與模式串并無關(guān)系，而只與模式串t t本身的構(gòu)成有本身的構(gòu)成有關(guān)，即從模式串關(guān)，即從模式串t t本身就可求出本身就可求出k k值。值。 討論一般情況，設(shè)討論一般情況，設(shè)s=“ss=“s0 0s s1 1.s.sn-1n-1”

17、，t=“tt=“t0 0t t1 1.t.tm-1m-1”。假定：。假定：0 1111. .ki k i kit ttsss 若模式串中存在可互相重疊的真子串若模式串中存在可互相重疊的真子串, ,使得使得：0 1111. .kj k j kjt ttttt （1 1）說明模式串的子串說明模式串的子串“t t0 0t t1 1.t.tk-1k-1”已已和主串和主串 “ “s si-ki-ks si-k+1i-k+1.s.si-1i-1”匹配，下一次可匹配，下一次可直接比較直接比較s si i和和t tk k；（2 2）說明在說明在“t t0 0t t1 1.t.tk-1k-1”中不存在任何中不存

18、在任何以以t t0 0為首字符子串與為首字符子串與“s si-ki-ks si-k+1i-k+1.s.si-1i-1”中中以以s si-1i-1為末字符的匹配子串，下一次可直接為末字符的匹配子串，下一次可直接比較比較s si i和和t t0 0。（1 1）（2 2）定義定義nextjnextj如下：如下：10.,0|max11110jkjkjkttttttjkkjnext且其它情況當(dāng)j=0時由此定義可推出由此定義可推出nextnext的函數(shù)值：的函數(shù)值：j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 模式串模式串nextjnextj a b a a b c a c a

19、b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1int Nextmaxsize;int KMPIndex(seqstring *S,seqstring *T) int i, j, v; i = 0; j = 0; while( i curlen & j curlen) if ( i = -1 | | S-chi =T-chj) i+; j+; else j = Nextj; if ( j=T-curlen ) v = i T-curlen; else v = -1; return( v );可以用遞推的方法推出可以用遞推的方法推出nextnex

20、t的值。當(dāng)?shù)闹?。?dāng)j j時，時，nextj=-1;nextj=-1;設(shè)設(shè)nextj=knextj=k，即，即t t中存在中存在.11110ikikiktttttt 以下求以下求nextj+1nextj+1，分兩種情況討論：，分兩種情況討論：1 1、若、若t tk k=t=tj j，則表明模式串，則表明模式串t t中有：中有：.11110jikikikktttttttt且不可能存在某個且不可能存在某個k kk k滿足上式，因此滿足上式，因此nextj+1 = nextj+1 = k+1;nextj+1 = nextj+1 = k+1;其中其中k k為滿足等式的最大值。為滿足等式的最大值。2 2、

21、若、若t tk kttj j，此時可把求，此時可把求nextj+1nextj+1值的問值的問題看作是一個模式匹配問題，即把模式串題看作是一個模式匹配問題，即把模式串tt向右滑動至向右滑動至k=nextkk=nextk（0kkj0kkj），若，若t tk k=t=tj j，則說明在主串，則說明在主串t t中第中第j+1j+1個字個字符之前存在一個長度為符之前存在一個長度為kk的子串滿足：的子串滿足：.110jkikiktttttt也就是說，也就是說，nextj+1 = k+1 = nextj+1 = k+1 = nextk+1;nextk+1;此時若此時若t tk kttj j，則將模式串，則將

22、模式串tt繼續(xù)右滑至繼續(xù)右滑至k”=nextkk”=nextk。以次類推，直到某次匹配成。以次類推，直到某次匹配成功或匹配失敗。設(shè)功或匹配失敗。設(shè)k kl l次右滑匹配失敗，則有次右滑匹配失敗，則有nextknextkl-1l-1=-1=-1，則有：，則有： nextj+1=nextknextj+1=nextkl-1l-1+1=-1+1=0+1=-1+1=0舉例：現(xiàn)有如圖所示的字符串。舉例：現(xiàn)有如圖所示的字符串。j j 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7模式串模式串nextjnextj a b a a b c a c a b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1 已求得前已求得前6 6個字符的個字符的nextnext