資料結構之串

串：是由零個或多個字元組成的有限序列，又名字元串。

串的比較是通過組成串的字元之間的編碼來進行的，而字元的編碼指的是字元在對應字元集中的序号

給定兩個串s=“a1a2。。。。。an” t=“b1b2。。。。。。bm”當滿足以下條件之一時 s<t.

1.n<m 且ai=bi（i=1，2。。。。，n）

例如s=“hap” t=“happy” 因為t比s多出2個字元 是以s<t

2.存在某個k<=min（m，n） 使的ai=bi（i=1，2。。。。。。，k-1），ak<bk

例如當s=“happen” t=“happy” 因為兩串的前4個字元相同 第5個字母（k值），字母e的ASCLL碼是101，而字母y的ASCLL碼是121 顯然e<y 是以s<t。

串的抽象資料類型

ADT 串 （string）

Data

    串中元素僅由一個字元組成，相鄰元素具有前驅和後繼關系

Operation

StrAssign（T，*chars）：生成一個其值等于字元串常量chars的串T

StrCopy（T,S）：串S存在，由串S指派得串T

ClearString（S）：串S存在，将串清空。

StringEmpty（S）：若串S為空，傳回true，否則傳回false

StrLength（S）：傳回串S的元素個數，即串的長度

StrCompare（S，T）：若S>T，傳回值>0，若S=T 傳回0，若S<T，傳回值<0

Concat（T，S1,S2）：用T傳回由S1和S2聯接而成的新串。

SubString（Sub，S，pos，len）：串S存在，1<=pos<=StrLength（S），且                                               0<=len<=StrLength（S）-pos+1，用Sub傳回串S的                                               第pos個字元起長度為len的子串。

Index（S,T,pos）：串S和T存在，T是非空串，1<=pos<=StrLength（S），若主串S中                                  存在和串T值相同的子串，則傳回它在主串S中第pos個字元之後第                                  一次出現的位置，否則傳回0

Replace（S,T,V）：串S，T和V存在，T是非空串，用V替換主串S中出現的所有與T相等                                  的不重疊的子串

StrInsert（S，pos，T）：串S和T存在，1<=pos<=StrLength（S）+1.在串S的第pos個                                  字元之前插入串T

StrDelete（S，pos，len）：串S存在，1<=pos<=StrLength（S）-len+1。從串S中删                                  除第pos個字元起長度為len個子串

endADT

Index實作算法

T為非空串，若主串S中第pos個字元之後存在與T相等的子串

則傳回第一個這樣的子串在S中的位置，否則傳回0

int Index(String S,String T,int pos)

{

int n,m,i;

String sub;

if(pos > 0)

n = StrLength(S);   得到主串S的長度

m = StrLength(T);   得到子串T的長度

i = pos;

while(i <= n-m+1)

SubString(sub,S,i,m); 取主串第i個位置 長度與T相等子串給sub

if(StrCompare(sub,T) != 0)  如果兩串不相等

++i;

else     如果兩串相等

return i;           則傳回i值

}

return 0;    若無子串與T相等 傳回0

串的順序存儲結構

串的順序存儲結構是用一組位址連續的存儲單元來存儲串中的字元序列的。按照預定義的大小，為每個定義的串變量配置設定一個固定長度的存儲區。一般是用定長數組。\0來表示串值的終結。

串的鍊式存儲結構

一個結點可以存放一個字元或者多個字元，最後一個結點若是未被占滿時，可以用#或其他非串值補全

模式比對：子串的定位操作

對主串的每一個字元作為子串開頭，與要比對的字元串進行比對。

假設主串S和要比對的子串T的長度存在S[0]與T[0]。

傳回子串T在主串S中第pos個字元之後的位置，若不存在，則函數傳回值為0.

T非空，1<=pos<=StrLength（S）。

int Index（String S，String T，int pos）

｛

int i = pos;           i用于主串S中目前位置下标，若pos不為1。則從pos位置開始比對

int j = 1;             j用于子串T中目前位置下标值

while（i<=S[0] && j <=T[0]）      若i小于S長度且j小于T的長度時循環

if(S[i] == T[j])   兩字母相等則繼續

++j;

｝

else                       指針後退重新開始比對

i = i-j+2;         i退回到上次比對首位的下一位

j = 1;             j退回到子串T的首位

if （j >T[0]）

return i-T[0];

else

return 0;

時間複雜度O（n+m）

最壞的情況時間複雜度O((n-m)m)

KMP模式比對算法

T=abcabx

j  123456

模式串T abcdex

next[j] 011111

1.當j=1時 next[1]=0;

2.當j=2時 j由1到j-1就隻有字元a，屬于其他情況next[2]=1;

3.當j=3時 j由1到j-1串是ab，顯然a與b不相等，屬其他情況，next[3]=1;

4.以後同理，是以最終此T串next[j]為011111

j 123456

模式串T abcabx

next[j] 011123

1.當j=1  next[j]=0

2.當j=2  同上 next[2]=1

3.當j=3  同上 next[3]=1

4.當j=4  同上next[4]=1

5.當j=5  此時j由1到j-1的串是abca 字首字元a與字尾字元a相等，是以可推算出k值為2是以next[5]=2;

6.當j=6  j由1到j-1的串是abcab，由于字首字元ab與字尾ab相等是以next[6]=3

根據經驗如果前一個字元相等，k值是2，2個相等，k值是3，n個，k值n+1

代碼如下

通過計算傳回子串T的next數組

void get_next(String T，int *next)

int i，j;

i=1;

j=0;

next[1]=0;

while(i<T[0])   此處T[0]表示串T的長度

if（j==0 || T[i]==T[j]） T[i]表示字尾的單個字元，T[j]表示字首的單個字元

next[i]=j;

j=next[j]; 若字元不相同 則j值回溯

計算出目前要比對的串T的next數組。

傳回子串T在主串S中第pos個字元之後的位置，若不存在，則函數傳回值為0

T非空1<=pos<=StrLength(S)

int Index_KMP(String S，String T，int pos)

int i=pos;    i用于主串S目前位置下标值，若pos不為1，則從pos位置開始比對

int j=1;      j用于子串T中目前位置下标值

int next[255];

get_next(T，next); 定義一next數組

while（i <= S[0] && j<=T[0]）若i小于S的長度且j小于T的長度時，循環繼續 

if（j==0 || S[i]==T[j]） 兩字母相等則繼續，與樸素算法增加。j=0判斷

else            指針後退重新開始比對

j=next[j];    j退回合适的位置  i值不變

if（j>T[0]）

        KMP算法僅當模式與主串之間存在許多 部分比對 的情況下才展現出它的優勢

KMP模式比對算法改進

求模式串T的next函數修正值并存入數組nextval

void get_nextval（String T，int *nextval）

nextval[1]=0;

while（i<T[0]）

if（j==0 || T[i]==T[j]）

if（T[i] != T[j]）

nextval[i]=j;

nextval[i]=nextval[j];

j=nextval[j];

改良後對比

T=ababaaaba

j 123456789

模式串T ababaaaba

next[j] 011234223

nextval[j] 010104210

1.當j=1  nextval[1]=0

2.當j=2  因第2位字元b的next值是1，而第一位就是a，它們不相等，是以nextval[2]=next[2]=1 維持原值

3.當j=3  因為第三位字元a的next值為1，是以與第一位的a比較得知它們相等，是以nextval[3]=nextval[1]=0;

4.當j=4  第四位的字元b next值為2，是以與第二位的b相比較得到結果是相等，是以nextval[4]=nextval[2]=1

5.j=5  next值為3 第五個字元a 與第三個字元a 相等，是以nextval[5]=nextval[3]=0;

6.當j=6  next值為4 第六個字元a 與第四個字元b不相等，是以nextval[6]=4;

7.當j=7  next值為2， 第七個字元a 與第二個字元b不相等 是以nextval[7]=2

8.當j=8  next值為2，第八個字元b與第二個字元b相等  nextval[8]=nextval[2]=1

9.當j=9時  next值為3 第九個字元a 與第三個字元a 相等 nextval[9]=nextval[3]=1

        是在計算出next值的同時，如果a位字元與它next值指向的b位字元相等，則該a位的nextval就指向b位的nextval值，如果不等，則該a位的nextval值就是它自己a位的next的值

      本文轉自潘闊 51CTO部落格，原文連結：http://blog.51cto.com/pankuo/1631335，如需轉載請自行聯系原作者