1、第四章 串串即字符串 是計算機非數值處理的主要對象之一 第一節 串的類型定義 串（string，或稱字符串）是 n 個字符的有限序列。通常記作s = “a1,a2 an (n0) S是串的名 串中字符的數目 n 稱為串的長度 含零個字符的串稱為空串(null string)由一個或多個空格組成的串稱為空格串(blank string) ，用符號表示空格串。 串的抽象數據類型 ADT String 數據對象：D ai | ai CharacterSet, i=1,2,.,n, n0 數據關系：R1 | ai-1 , ai D, i=2,.,n 基本操作：StrAssign (&T, chars)

2、初始條件：chars 是串常量。操作結果：賦于串T的值為 chars。StrCopy (&T, S)初始條件：串 S 存在。操作結果：由串 S 復制得串 T。DestroyString (&S)初始條件：串 S 存在。操作結果：串 S 被銷毀。StrEmpty (S)初始條件：串 S 存在。操作結果：若 S 為空串，則返回 TRUE，否則返回 FALSE。StrCompare (S, T)初始條件：串 S 和 T 存在。操作結果：若ST，則返回值0；若S=T，則返回值=0；若ST，則返回值 0) n = StrLength(S); m = StrLength(T); / 求得串長i = pos

3、;while ( i = n-m+1) SubString (sub, S, i, m); / 取得從第 i 個字符起長度為 m 的子串if (StrCompare(sub,T) != 0) +i ;else return i ; / 找到和 T 相等的子串 return 0; / S 中不存在滿足條件的子串 void replace(String& S, String T, String V)n=StrLength(S); m=StrLength(T); pos = 1;StrAssign(news, NullStr); / 初始化 news 串為空串i=1;while ( pos = n-

4、m+1 & i )i=Index(S, T, pos); / 從pos指示位置起查找串Tif (i!=0) SubString(sub, S, pos, i-pos); / 不置換子串Concat(news, news, sub); / 聯接S串中不被置換部分Concat(news,news, V);/ 聯接V串pos = i+m; / pos 移至繼續查詢的起始位置 SubString(sub, S, pos, n-pos+1); / 剩余串Concat( S, news, sub ); / 聯接剩余子串并將新的串賦給S 4-1-2replace.swf第二節 串的表示和實現 串的定長順序存

5、儲表示 用一組地址連續的存儲單元存儲串值的字符序列 #defin MAXSTRLEN 255Typedef unsigned char SStringMAXSTRLENvoid Concat( char S1 , char S2 , char T )/ 以T返回由S1和S2聯接而成的新串j=0; k=0; while ( S1j != 0) Tk+ = S1j+; / 復制串 S1j = 0;while ( S2j != 0) Tk+ = S2j+; / 緊接著復制串 S2Tk = 0; / 置結果串T的結束標志 bool SubString ( char Sub , char S, int

6、pos, int len ) / 若參數合法(即1posStrLength(S) 且0lenStrLength(S)-pos+1),則以Sub帶回串S中第pos個字符起長度為len的子串，并返回TRUE，否則返回FALSEslen=StrLength(S); / 求串S的長度if (pos slen | len slen-pos+1)return FALSE;for ( j = 0; j len; j+ ) Sub j = S pos + j - 1 ;/ 向子串Sub復制字符Sublen = 0; / 置串Sub的結束標志return TRUE; 串的堆分配存儲表示 串的堆分配存儲的特點是，

7、程序中出現的所有串變量的存儲空間都是在程序執行過程中動態分配而得的。堆分配存儲結構的串定義如下：typedef structchar *ch;int length; HString; bool StrInsert (Hstring& S, int pos, Hstring T) / 若1posStrLength(S)1，則改變串S，在串S的第pos個字符之前插入串T，并返回TRUE,否則串S不變，并返回FALSEif (pos S.length+1)return FALSE; / 插入位置不合法char S1S.length ; / S1 作為輔助串空間用于暫存 S.chif (T.lengt

8、h) / T 非空，則為S重新分配空間并插入 Tp=S.ch; i=0;while (i S.length)S1i+ = *(p+i); / 暫存串SS.ch = new charS.length + T.length ;/ 為S重新分配串值存儲空間for ( i=0, k=0; ipos-1; i+)S.chk+ = S1i; / 保留插入位置之前的子串j = 0;while (jT.length) S.chk+ = T.chj+; / 插入 Twhile ( istr) free(s-str); /若s已經存在，將它占據的空間釋放掉 for (len=0,ch=string_constan

9、t;ch;len+,ch+); /求string_constant串的長度 if (!len) s-str=(char*)malloc(sizeof(char);s-str0=0; s-length=0; /空串else s-str=(char*)malloc(len+1)*sizeof(char); /分配空間 if (!s-str) return ERROR; s-str0.len=string_constant0.len; /對應的字符賦值 s-length=len; /賦予字符串長度 return OK;（2）判斷串是否為空int StringEmpty(STRING s) if (!

10、s.length) return TRUE; else return FALSE;（3）求串的長度int Length(STRING s) return s.length;（4）串連接int Concat(STRING *s1,STRING s2) STRING s; StringAssign(&s,s1-str); /將s1原來的內容保留在s中 len=Length(s1)+Length(s2); /計算s1和s2的長度之和 free(s1-str); /釋放s1原來占據的空間 s1-str=(char*)malloc(len+1)*sizeof(char); /重新為s1分配空間if (!

11、s1) return ERROR; else /連接兩個串的內容 s1-str0.Length(s)-1 =s.str0.Length(s)-1); s1-strLength(s).len+1 =s2.str0.Length(s2); s1-length=len; free(s-str); /釋放為臨時串s分配的空間 return OK; （5）求子串int SubStr(STRING *s1,STRING s2,int start,int len) len2=Length(s2); /計算s2的長度 if (startlen2|len2len2-start+1) /判斷start和len的合

12、理性 s1-str=(char*)malloc(sizoef(char); s1-str0=0 ;s1-length=0;return ERROR; /if s1-str=(char*)malloc(len+1)*sizeof(char); if (!s1.str) return ERROR; s1-str0.len-1=s2.strstart-1.start+len -2; s1-strlen=0; s1-length=len; return OK;串的塊鏈存儲表示 const CHUNKSIZE = 80; /可由用戶定義的塊(結點)大小typedef struct Chunk / 結點結

13、構char chCUNKSIZE;struct Chunk *next; Chunk;typedef struct / 串的鏈表結構 Chunk *head, *tail; / 串的頭指針和尾指針int curlen; / 串的當前長度 LString;s t r i n g SS s t r i n g # # # # 第三節 模式匹配 若 S =concatenation，T =cat，則稱主串S中存在和模式串T相同的子串，起始位置為4，即 Index(S,T,1)=4 。 串的模式匹配的簡單算法 int Index_BF ( char S , char T , int pos )/ 若串

14、 S 中從第pos(1posStrLength(S)個字符起存在和串 T 相同的子串，則稱匹配成功，返回第一個這樣的子串在串 S 中的位置，否則返回 0i = pos-1; j = 0;while ( Si+j != 0& Tj != 0)if ( Si+j = Tj ) j +; / 繼續比較后一字符else i +; j = 0; / 重新開始新的一輪匹配if ( Tj = 0) return (i+1); / 匹配成功else return 0; / 串S中(第pos個字符起)不存在和串T相同的子串 4-3-1.swf串的模式匹配的改進算法 按此算法進行模式串 T = abcac 和主串

15、 S =ababcabcabcacabca 在 pos=0 的情況 int Index_BF1 ( char S , char T , int pos )/ 若串 S 中從第pos(1posStrLength(S)個字符起存在和串 T 相同的子串，則稱匹配成功，返回第一個這樣的子串在串 S 中的位置，否則返回 0i = pos-1; j = 0;while ( Si != 0& Tj != 0)if ( Si = Tj ) i+; j +; / 繼續比較后一字符else i = i-j+1; j = 0; / 重新開始新的一輪匹配if ( Tj = 0) return (i-j); / 匹配成

16、功else return 0; / 串S中(第pos個字符起)不存在和串T相同的子串 4-3-2.swf改進后的4-3-3.swfKMP 算法 匹配過程中指針 i 沒有回溯。 KMP算法的核心思想是利用已經得到的部分匹配信息來進行后面的匹配過程 s1s2.si-1 sisn p1p2pj-1pjpm sipj 此時主串的i應該與模式串的第k個字符相比較,即p1p2pk-1= si-k+1si-k+2.si-1 而pj-k+1pj-k+2pj-1= si-k+1si-k+2.si-1 所以p1p2pk-1= pj-k+1pj-k+2pj-1 0當j=1Nextj= Maxk|1kj且p1p2pk

17、-1= pj-k+1pj-k+2pj-1 當集合不空 1其它情況j12345678模式串abaabcacNextj01122312int Index_KMP(char S, char T, int pos)/ 利用模式串T的next函數求T在主串S中第pos個字符之后第一次出現的位置的KMP算法。其中1posStrLength(S)i = pos; j = 1;while ( i=S0 & jT0) return (i- T0 ); / 匹配成功else return 0; 求s的逆串void String_Reverse(Stringtype s,Stringtype &r) StrAssi

18、gn(r,); /初始化r為空串for(i=Strlen(s);i;i-)StrAssign(c,SubString(s,i,1);StrAssign(r,Concat(r,c); /把s的字符從后往前添加到r中 從串s中刪除所有與t相同的子串,并返回刪除次數 int Delete_SubString(Stringtype &s,Stringtype t) for(n=0,i=1;i=Strlen(s)-Strlen(t)+1;i+)if(!StrCompare(SubString(s,i,Strlen(t),t)StrAssign(head,SubString(S,1,i-1);StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1);StrAssign(S,Concat(head,tail); /把head,tail連接為新串n+; return n, 將串S中所有子串T替換為V,并返回置換次數 int Replace(Stringtype &S,Stringtype T,Stringtype V) for(n=0,i=1;i=Strlen(S)-Strlen