第 4章 串（ String） 4.1 串類型的定義 4.2 串的表示和實現(xiàn) 4.3 串的模式匹配算法 記為： s = a1 a2 . a n (n0 ) 串名 串值（用 括起來） 串 即字符串，是由零個或多個字符組成的 有限 序列， 是 數(shù)據(jù) 元素為單個字符 的特殊線性表。 4.1 串類型的定義 隱含結束符 0 ，即 ASCII 碼 NULL 為何要單獨討論串類型？ 1） 字符串操作比其他數(shù)據(jù)類型更復雜（如拷貝、連接操作） 2） 程序設計中，處理對象很多都是串類型。 若干術語： 串長： 串中字符的個數(shù)（ n0 ） . n=0 時稱為空串 。 空白串： 由一個或多個 空格符 組成的串。 問：空串和空白串有無區(qū)別？ 答： 有區(qū)別。 空串 (Null String)是指長度為零的串； 而空白串 (Blank String),是指包含一個或多 個空白字符 (空格鍵 )的字符串 . 子串： 子串位置： 字符位置： 串相等： 例 1： 現(xiàn)有以下 4個字符串： a =BEI b =JING c = BEIJING d = BEI JING 問： 他們各自的長度？ a是 c和 d的子串，在 c和 d中的位置都是 1 串 S中 任意個連續(xù)的字符 序列叫 S的子串 ; S叫 主串 。 子串的第一個字符在主串中的序號。 字符在串中的序號。 串長度相等，且對應位置上字符相等。 a是哪個串的子串？在主串中的位置是多少？ a =3， b =4， c = 7， d=8 “空串是任意串的子串；任意串 S都是 S本身的子串，除 S本身 外， S的其他子串稱為 S的 真子串 。 ” 數(shù)據(jù)結構與算法 中山大學出版社 空串是哪個串的子串？ a是不是自己的子串？ C語言中已有類似串運算函數(shù)！ ADT String Objects: D=ai | ai CharacterSet, i=1, 2, ， n, n0 Relations: R1= | ai-1,ai D, i=2, ， n functions: /至少有 13種基本操作 StrAssign( 求串長： int strlen(char *s); 串連接： char strcat(char *to,char *from) 子串 T定位： char strchr(char *s,char *c); 注：用 C處理字符串時，要調(diào)用標準庫函數(shù) #include 類 C StrCompare(S,T) StrLength(S) Concat( /P73 SString s; /s 是一個可容納 255個字符的順序串。 注： 一般用 SString0來存放 串長 信息（如 pascal語言）； C語言約定在串尾加結束符 0，以利操作加速，但不 計入串長 （用首址和串長、或首址和尾標記來描述串數(shù) 組） 若字符串超過 Maxstrlen 則自動截斷 （因為靜態(tài)數(shù)組存不 進去）。 例： 用 順序存儲方式 編寫 求子串函數(shù) SubString( /若 pos和 len參數(shù)越界，則告警 Sub1 len=Spos pos+len-1; Sub0=len; return OK; 將串 S中從第 pos個字符開始、長度為 len的字符序列復制到串 Sub中。 （注：考慮到函數(shù)的通用性，應當讓串 Sub的預留長度與 S一樣） 子串長度 s = a1 a2 . a n pos len Sub 討論：想存放 超長 字符串怎么辦？ 改用 動態(tài)分配 的一維數(shù)組 堆 思路： 利用 malloc函數(shù)合理預設串長空間。 特點： 若在操作中串值改變，還可以利用 realloc函數(shù) 按新串長度 增加空間 （即動態(tài)數(shù)組概念） 。 Typedef struct char *ch; /若非空串 ,按串長分配空間 ; 否則 ch=NULL int length; /串長度 HString 堆分配存儲特點： 仍用一組連續(xù)的存儲單元來存放串，但 存儲空間是在程序執(zhí)行過程中 動態(tài)分配 而得。 堆 T的存儲結構描述： T.ch T.length C是指針變量，可以自增！ 意即每次后移一個數(shù)據(jù)單 元。 直到終值為 “ 假 ” 停止，串尾特征是 c 0 NULL 0 Status StrAssign(HString /釋放 T原有空間 for (i=0, c=chars; c; +i, +c); /求 chars的串長度 i 例 1： 編寫 建堆函數(shù) (參見教材 P76） 此處 T.ch0沒有 用來裝串長，因為 另有 T.length 分 量 if ( !i ) T.ch = NULL; T.length = 0; else if (!(T.ch = (char*)malloc( i *sizeof(char) exit(OVERFLOW); T.ch0.i-1 = chars0.i-1; T.length =i; Return OK; /StrAssign Status StrInsert ( HString /pos不合法則告警 if(T.length) /只要串 T不空，就需要重新分配 S空間，以便插入 T if (!（ S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) ) exit(OVERFLOW); /若開不了新空間，則退出 for ( i=S.length-1; i=pos-1; -i ) S.chi+T.length = S.chi; / 為插入 T而騰出 pos之后的位置，即從 S的 pos位置起全部字符均后移 S.chpos-1pos+T.length -2 = T.ch0T.length -1; /插入 T，略 /0 S.length + = T.length; /刷新 S串長度 return OK; /StrInsert 例 2： 用 “ 堆 ” 方式編寫 串插入函數(shù) (參見教材 P75) 討論： 法 1存儲密度為 ；法 2存儲密度為 ； 顯然，若 數(shù)據(jù)元素很多，用法 2存儲更優(yōu) 稱為 塊鏈結構 鏈式存儲特點 ： 用鏈表存儲串值，易插入和刪除。 法 1： 鏈表結點的數(shù)據(jù)分量長度取 1（個字符） 法 2： 鏈表結點（數(shù)據(jù)域）大小取 n(例如 n=4) 1/2 9/15=3/5 A B C I NULL head head A B C D E F G H I # # # NULL 對塊鏈表的整體描述 #define CHUNKSIZE 80 /每塊大小，可由用戶定義 typedef struct Chunk /首先定義結點類型 char ch CHUNKSIZE ; /每個結點中的數(shù)據(jù)域 struct Chunk * next ; /每個結點中的指針域 Chunk; 塊鏈類型定義： 塊鏈函數(shù)的編寫略 typedef struct /其次定義用鏈式存儲的串類型 Chunk *head; /頭指針 Chunk *tail; /尾指針 int curLen; /結點個數(shù) Lstring; /串類型只用一次，前面可以不加 Lstring 對每個結點的描述 算法目的： 確定主串中所含子串第一次出現(xiàn)的位置 （ 定位 ） 4.3 串的模式匹配算法 （屬于選講部分） BF算法 （又稱古典的、經(jīng)典的、樸素的、窮舉的） KMP算法 算法種類： 帶回溯，速度慢 避免回溯，匹配速度快， 是全課程的亮點之一 定位問題稱為串的模式匹配 (Pattern Matching)，即子串定位運 算， 它是串處理系統(tǒng)中最重要的操作之一。 典型函數(shù)為 Index(S,T,pos)， 見教材 P71 BF算法的實現(xiàn) 即編寫 Index(S,T,pos)函數(shù) 例 1： S=ababcabcacbab， T=abcac， pos=1， 求：串 T在串 S中第 pos個字符之后的位置。 利用 演示系統(tǒng) 看 BF算法執(zhí)行過程。 BF算法設計思想： 將主串 S的第 pos個字符和模式 T的第 1個字符比較， 若 相等 ，繼續(xù)逐個比較后續(xù)字符； 若 不等 ，從主串 S的下一字符（ pos+1）起，重新與 T第一 個字符比較。 直到主串 S的一個連續(xù)子串字符序列與模式 T相等。返回值 為 S中與 T匹配的子序列 第一個字符的序號 ，即匹配成功。 否則，匹配失敗，返回值 0 . Int Index(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 /子串結束，說明匹配成功 else return0; /Index 例 2： S=ababcabcacbab， T=abcac， 求 Index(S,T,5) （參見教材 P79） 相當于子串向右滑動一個字符位置 匹配成功后指針仍要回溯！因為要返回的 是被匹配的首個字符位置。 i j S=a b a b c a b c a c b a b T=a b c a c pos=5 討論： 若 n為主串長度， m為子串長度，則串的 BF匹配算法最壞的情 況下需要比較字符的總次數(shù)為 (n-m+1)*m O(n*m) 一般的情況是： O(n+m) 推導方法： 要從最好到最壞情況統(tǒng)計總的比較次數(shù)，然后 取平均。 BF算法的時間復雜度 最好的情況是： 一配就中！ 只比較了 m次。 能否利用已 部分匹配過 的信息而加快模式串的滑動速度？ 能！ 而且主串 S的指針 i不必回溯 ！最壞情況也能達到 O(n+m) 請看 KMP算法！ 最惡劣情況是： 主串前面 n-m個位置都 部分匹配 到子串的最后 一位，即這 n-m位比較了 m次，別忘了最后 m位也各比較了一次， 還要加上 m！所以總次數(shù)為： (n-m)*m+m (n-m+1)*m KMP算法 （特點：速度快） KMP算法設計思想 KMP算法的推導過程 KMP算法的實現(xiàn) （關鍵技術 :計算 nextj） KMP算法的時間復雜度 全書一大亮點！