第 四 章串 【課前思考】1. 串就是線性表的結(jié)論是否正確？從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)來(lái)說(shuō)，串是一種特殊的線性表;但就數(shù)據(jù)類型而言，串不是線性表。2. 串和線性表的主要差別是什么？ 希望你帶著這個(gè)問(wèn)題開(kāi)始這一章的學(xué)習(xí)，并能在學(xué)完這一章的內(nèi)容之后能得出正確的結(jié)論。 【學(xué)習(xí)目標(biāo)】 1. 理解“串”類型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作。 2. 理解串類型的各種存儲(chǔ)表示方法。 3. 理解串匹配的各種算法。 【重點(diǎn)和難點(diǎn)】 相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作。本章的難點(diǎn)是理解實(shí)現(xiàn)串匹配的KMP算法的思想，但它不屬本章學(xué)習(xí)的基本要求，更不是重點(diǎn)學(xué)習(xí)內(nèi)容?！局R(shí)點(diǎn)】串的類型定義、串的存儲(chǔ)表示、串匹配、KMP算法 【學(xué)習(xí)指南】 雖然目前各常用的高級(jí)語(yǔ)言中都已經(jīng)實(shí)現(xiàn)了串類型，但由于它是通過(guò)軟件實(shí)現(xiàn)的，因此作為一個(gè)軟件工作者還是應(yīng)該了解串的實(shí)現(xiàn)方法。本章沒(méi)有必須完成的算法設(shè)計(jì)題，如果有興趣可以試試以下幾個(gè)題:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6個(gè)是練習(xí)串的基本操作的應(yīng)用，后2個(gè)是和KMP算法相關(guān)的練習(xí)。 4.1 串 類 型 的 定 義4.2 串 的 表 示 和 實(shí) 現(xiàn)4.3串 的 模 式 匹 配 算 法 4.1串的類型定義一、 基本概念 1 串 的 定 義串( string) 是由零個(gè)或多個(gè)字符組成的有限序列，記作s=a1a2an，其中s為串的名字，用成對(duì)的單引號(hào)括起來(lái)的字符序列為串的值，但兩邊的引號(hào)不算串值，不包含在串中。ai(1in)可以是字母、數(shù)字或其它字符。n為串中字符的個(gè)數(shù)，稱為串的長(zhǎng)度。2 空 串不含任何字符的串稱為空串，它的長(zhǎng)度n=0，記為s=。 3 空 格 串 含有一個(gè)或多個(gè)空格的串，稱為空格串，它的長(zhǎng)度n為空格的個(gè)數(shù)，一般用符號(hào)“ ”表示空串。 串 是 有 限 長(zhǎng) 的 字 符 序列 ， 由 一 對(duì) 單 引 號(hào) 相括 ， 如 : a string 4 子 串 、 主 串 通常將字符在串中的序號(hào)稱為該字符在串中的位置。子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示。若一個(gè)串是另一個(gè)串中連續(xù)的一段，則這個(gè)串稱為另一個(gè)串的子串，而另一個(gè)串相對(duì)于該串稱為主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，則s1為s2的子串，s2相對(duì)于s1為主串。 另外，空串是任意串的子串，任意串是自身的子串。若一個(gè)串的長(zhǎng)度為n，則它的子串?dāng)?shù)目為 +1，真子串個(gè)數(shù)為 (除串本身以外的子串都稱為真子串)。 當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是相等的，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等, 并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。 2 )1( nn 2 )1( nn 二 、 串 的 抽 象 數(shù) 據(jù) 類 型 的 定 義 如 下 ：ADT String 數(shù) 據(jù) 對(duì) 象 ：D ai |ai CharacterSet, i=1,2,.,n, n0 數(shù) 據(jù) 關(guān) 系 ：R1 | ai-1, ai D, i=2,.,n 基 本 操 作 ： StrAssign ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中 不 存 在 與 T相 等 的 子 串 / Index 又 如 串 的 置 換 函 數(shù)： Replace( / 0號(hào) 單 元 存 放 串 的 長(zhǎng) 度 或：typedef struct /* 串結(jié)構(gòu)定義 */ char chMAXLEN; int len; SString; 按 這 種 串 的 表 示 方 法 實(shí) 現(xiàn) 的 串 的運(yùn) 算 時(shí) ， 其 基 本 操 作 為 “ 字 符 序 列的 復(fù) 制 ” 。 串 的 實(shí) 際 長(zhǎng) 度 可 在 這 個(gè) 予 定 義 長(zhǎng)度 的 范 圍 內(nèi) 隨 意 設(shè) 定 ， 超 過(guò) 予 定 義長(zhǎng) 度 的 串 值 則 被 舍 去 ， 稱 之 為“ 截 斷 ” 。特點(diǎn): Status Concat(SString S1, SString S2, SString / Concat例 如 ： 串 的 聯(lián) 接 算 法 中 需 分 三 種 情 況 處 理 ： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未 截 斷 else if (S10 MAXSTRSIZE) / 截 斷 else / 截 斷 (僅 取 S1)T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLEN S10;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; (1) 串插入函數(shù)。StrInsert(s, pos, t) /*在串s中序號(hào)為pos的字符之前插入串t */SString *s, t;int pos;int i;if (poss-len) return(0); /* 插入位置不合法 */if (s-len + t.lenlen + t.len-1;i=t.len + pos;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos=t.chi; s-len=s-len+t.len; 定長(zhǎng)順序存儲(chǔ)的操作實(shí)施： 【算法 串插入函數(shù)】 a b x y z c d e f x y z a b c d e f x y z T串 S串 T串 S串 (a) 插入前 圖41順序串的插入 (b) 插入后(i=3) else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i-) s-chi=s-chi-t.len; for (i=0;ichi+pos=t.chi; s-len=MAXLEN; else /* 串t的部分字符序列要舍棄 */ for (i=0;ichi+pos=t.chi; s-len=MAXSTRLEN; return(1); (2) 串刪除函數(shù)。StrDelete(s, pos, len) /* 在串s中刪除從序號(hào)pos起len個(gè)字符 */SString *s;int pos, len;int i;if (pos(s-len-len) return(0);for (i=pos+len;ilen;i+) s-chi-len=s-chi;s-len=s-len - len;return(1); 【算法 串刪除函數(shù)】 a b c i j k a b c d e f g h i j k (a)刪除前 圖4-2 順序串的刪除(i=4,j=5) (b) 刪除后 (3) 串復(fù)制函數(shù)。StrCopy(s, t) /* 將串t的值復(fù)制到串s中 */SString *s, t;int i;for (i=0;ichi=t.chi;s-len=t.len; 【算法 串復(fù)制函數(shù)】 (4) 判空函數(shù)。StrEmpty(s) /* 若串s為空(即串長(zhǎng)為0), 則返回1, 否則返回0 */SString s;if (s.len=0) return(1);else return(0); 【算法 判空函數(shù)】 (5) 串比較函數(shù)。StrCompare(s, t) /* 若串s和t相等, 則返回0；若st，則返回1；若st，則返 回-1 */SString s, t;int i;for (i=0;is.lenreturn(1); 【算法 清空函數(shù)】 (8) 連接函數(shù)。 Concat(s, t) /* 將串t連接在串s的后面 */SString *s, t;int i, flag;if (s-len + t.lenlen; ilen + t.len; i+) s-chi=t.chi-s-len; s-len+=t.len;flag=1; else if (s-lenlen;ichi=t.chi-s-len; s-len=MAXSTRLEN;flag=0; else flag=0;/* 串s的長(zhǎng)度等于MAXLEN, 串t不被連接 */ return(flag); 【算法 連接函數(shù)】 (9) 求子串函數(shù)。 SubString(sub, s, pos, len) /* 將串s中序號(hào)pos起len個(gè)字符復(fù)制到sub中 */SString *sub, s;int pos, len;int i;if (poss.len | lens.len-pos) sub-len=0;return(0);else for (i=0;ichi=s.chi+pos; sub-len=len;return(1); 【算法 求子串函數(shù)】 (10) 定位函數(shù)。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */SString s, t;int pos;int i, j;if (t.len=0) return(0);i=pos;j=0;while (is.len else return(0); 【算法 定位函數(shù)】 typedef struct char *ch; / 若 是 非 空 串 ， 則 按 串 長(zhǎng) 分 配 存 儲(chǔ) 區(qū) ， / 否 則 ch為 NULL int length; / 串 長(zhǎng) 度 HString;二 、 串 的 堆 分 配 存 儲(chǔ) 表 示特點(diǎn)：仍用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列，但其存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。 通 常 ， C語(yǔ) 言 中 提 供 的 串 類 型 就 是 以 這 種存 儲(chǔ) 方 式 實(shí) 現(xiàn) 的 。 系 統(tǒng) 利 用 函 數(shù) malloc( )和free( )進(jìn) 行 串 值 空 間 的 動(dòng) 態(tài) 管 理 ， 為 每 一 個(gè) 新產(chǎn) 生 的 串 分 配 一 個(gè) 存 儲(chǔ) 區(qū) ， 稱 串 值 共 享 的 存儲(chǔ) 空 間 為 “ 堆 ” 。 C語(yǔ) 言 中 的 串 以 一 個(gè) 空 字 符 為 結(jié) 束 符 ， 串 長(zhǎng) 是 一 個(gè) 隱 含 值 。 這 類 串 操 作 實(shí) 現(xiàn) 的 算 法 為 ： 先 為 新 生 成 的 串 分 配 一 個(gè) 存 儲(chǔ) 空 間 ， 然 后 進(jìn) 行 串 值 的 復(fù) 制 。 Status Concat(HString / 釋 放 舊 空 間 if (!(T.ch = (char *) malloc(S1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat Status SubString(HString if (Sub.ch) free (Sub.ch); / 釋 放 舊 空 間 if (!len) Sub.ch = NULL; Sub.length = 0; / 空 子 串 else / 完 整 子 串 return OK; / SubString Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; 三 、 串 的 塊 鏈 存 儲(chǔ) 表 示也 可 用 鏈 表 來(lái) 存 儲(chǔ) 串 值 ， 由 于 串 的 數(shù) 據(jù)元 素 是 一 個(gè) 字 符 ， 它 只 有 8 位 二 進(jìn) 制 數(shù) ，因 此 用 鏈 表 存 儲(chǔ) 時(shí) ， 通 常 一 個(gè) 結(jié) 點(diǎn) 中 存放 的 不 是 一 個(gè) 字 符 ， 而 是 一 個(gè) 子 串 。存 儲(chǔ) 密 度 = 數(shù) 據(jù) 元 素 所 占 存 儲(chǔ) 位實(shí) 際 分 配 的 存 儲(chǔ) 位 #define CHUNKSIZE 80 / 可 由 用 戶 定 義 的 塊 大 小 typedef struct Chunk / 結(jié) 點(diǎn) 結(jié) 構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串 的 鏈 表 結(jié) 構(gòu) Chunk *head, *tail; / 串 的 頭 和 尾 指 針 int curlen; / 串 的 當(dāng) 前 長(zhǎng) 度 LString; 例 如 : 在 編 輯 系 統(tǒng) 中 ， 整 個(gè) 文 本 編 輯 區(qū)可 以 看 成 是 一 個(gè) 串 ， 每 一 行 是 一 個(gè) 子 串 ，構(gòu) 成 一 個(gè) 結(jié) 點(diǎn) 。 即 : 同 一 行 的 串 用 定 長(zhǎng) 結(jié) 構(gòu)(80個(gè) 字 符 ), 行 和 行 之 間 用 指 針 相 聯(lián) 接 。實(shí) 際 應(yīng) 用 時(shí) ， 可 以 根 據(jù) 問(wèn) 題 所 需 來(lái)設(shè) 置 結(jié) 點(diǎn) 的 大 小 。 這 是 串 的 一 種 重 要 操 作 ， 很 多 軟 件 ， 若 有 “ 編 輯 ” 菜 單 項(xiàng) 的 話 ， 則 其 中 必 有 “ 查 找 ” 子 菜 單 項(xiàng) 。4.3串 的 模 式 匹 配 算 法 子串的定位操作通常稱為串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。 初 始 條 件 ： 串 S和 T存 在 ， T是 非 空 串 ， 1posStrLength(S)。操 作 結(jié) 果 ： 若 主 串 S中 存 在 和 串 T值 相 同 的 子 串 返 回 它 在 主 串 S中 第 pos個(gè) 字 符 之 后 第 一 次 出 現(xiàn) 的 位 置 ； 否 則 函 數(shù) 值 為 0。 首 先 ， 回 憶 一 下 串 匹 配 (查 找 )的 定 義 :INDEX (S, T, pos) 下 面 討 論 以 定 長(zhǎng) 順 序 結(jié) 構(gòu)表 示 串 時(shí) 的 幾 種 算 法 。一 、 簡(jiǎn) 單 算 法二 、 首 尾 匹 配 算 法三 、 KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算 法 一 、 簡(jiǎn) 單 算 法 Brute-Force算法 例 如 ,設(shè) 目 標(biāo) 串 s=“cddcdc”,模 式 串 t=“cdc”。 s的 長(zhǎng)度 為 n(n=6),t的 長(zhǎng) 度 為 m(m=3)。 用 指 針 i指 示 目 標(biāo) 串 s的 當(dāng) 前 比 較 字 符 位 置 ,用 指 針 j指 示 模 式 串 t的 當(dāng) 前 比較 字 符 位 置 。 BF模 式 匹 配 過(guò) 程 如 下 所 示 。 第1次匹配 s=cddcdc i=2 t=cdc j=2 失敗 第2次匹配 s=cddcdc i=1 t=cdc j=0 失敗 第3次匹配 s=cddcdc i=2 t=cdc j=0 失敗 第4次匹配 s=cddcdc i=5 t=cdc j=2 成功 這 個(gè) 算 法 簡(jiǎn) 單 ,易 于 理 解 ,但 效 率 不 高 ,主 要 原 因 是 :主 串 指 針 i在 若 干 個(gè) 字 符 序 列 比 較 相 等 后 ,若 有 一 個(gè) 字符 比 較 不 相 等 ,仍 需 回 溯 (即 i=i-j+1)。 該 算 法 在 最 好 情況 下 的 時(shí) 間 復(fù) 雜 度 為 O(m),即 主 串 的 前 m個(gè) 字 符 正 好等 于 模 式 串 的 m個(gè) 字 符 。 在 最 壞 情 況 下 的 時(shí) 間 復(fù) 雜 度為 O(n*m)。 int index(SqString s,SqString t) int i=0,j=0,k; while (is.len /*返 回 匹 配 的 第 一 個(gè) 字 符 的 下 標(biāo) */ else k=-1; /*模 式 匹 配 不 成 功 */ return k; 先 比 較 模 式 串 的 第 一 個(gè) 字 符 ， 再 比 較 模 式 串 的 最 后 一 個(gè) 字 符 ， 最 后 比 較 模 式 串 中 從 第 二 個(gè) 到 第 n-1個(gè) 字 符 。二 、 首 尾 匹 配 算 法 int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重 新 查 找 匹 配 起 始 點(diǎn) else if (Si+tLength-1 != patEndChar) +i; / 模 式 串 的 “ 尾 字 符 ” 不 匹 配 else return 0; / 檢 查 中 間 字 符 的 匹 配 情 況 k = 1; j = 2; while ( j tLength +j; if ( j = tLength ) return i; else +i; / 重 新 開(kāi) 始 下 一 次 的 匹 配 檢 測(cè) 三 、 模 式 匹 配 的 改 進(jìn) 算 法（ KMP算 法 ）此方法由克努特(D.E.Knuth)莫里斯(J.H.Morris)普拉特(V.R.Pratt)同時(shí)發(fā)現(xiàn)。1.基本思想：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符不等時(shí)，不需回溯i指針，而是利用已得到的部分匹配結(jié)果，將模式串向右滑動(dòng)盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較。避免多余的、不必要的比較，從而提高算法性能。算法總在0(n+m)的時(shí)間數(shù)量級(jí)上完成匹配操作。 ababcabcacbab abc (a) 第一趟匹配s3t3 (b) 第二趟匹配s7t5 (c) 第三趟匹配成功 圖 KM P模式匹配過(guò)程 ababcabcacbab abcac a b a b c a bcacbab abcac 2.KMP算法匹配實(shí)例： (1)模 式 串 t中 沒(méi) 有 真 子 串 真 子 串 是 指 模 式 串 t存 在 某 個(gè) k(0 k j),使 得“ t0t1tk”=“tj-ktj-k+1tj”成 立 。 例 如 t=cdc就 是 這 樣 的 模 式 串 。 在 圖 4.6中 的 第 一次 回 溯 ,當(dāng) s0=t0,s1=t1,s2t2時(shí) ,算 法 中 取 i=1,j=0,使 主 串 指針 回 溯 一 個(gè) 位 置 ,比 較 s1和 t0。 因 t0t1,所 以 一 定 有 s1t0。另 外 ,因 有 t0=t2,s0=t0,s2t2,則 一 定 可 推 出 s2t0,所 以 也 不必 取 i=2,j=0去 比 較 s2和 t0。 可 直 接 在 第 二 次 比 較 時(shí) 取i=3,j=0,比 較 s 3和 t0。 這 樣 ,模 式 匹 配 過(guò) 程 主 串 指 針 i就 可不 必 回 溯 。 (2)模 式 串 中 存 在 真 子 串 例 如 t=“abab”,由 于 “ t0t1”=“t2t3”(這 里 k=1,j=3),則存 在 真 子 串 。 設(shè) s=“abacabab”,t=“abab”,第 一 次 匹 配過(guò) 程 如 下 所 示 。 第1次匹配 s=abacabab i=3 t=abab j=3 失敗 此 時(shí) 不 必 從 i=1(i=i-j+1=1),j=0重 新 開(kāi) 始 第 二 次 匹配 。 因 t0t1,s1=t1,必 有 s1t0,又 因 t0 =t2,s2=t2,所 以 必 有s2=t0。 因 此 ,第 二 次 匹 配 可 直 接 從 i=3,j=1開(kāi) 始 。 現(xiàn) 在 我 們 討 論 一 般 情 況 。 設(shè) s=s0s1sn-1,t=t0t1tm-1,當(dāng) sitj (0in-m,0jm)時(shí) ,存 在 : t0t1tj-1=si-jsi-j+1si-1 (4.1)若 模 式 串 中 存 在 的 真 子 串 滿 足 : t0t1tk=tj-ktj-k+1tj (0 k j) (4.2) 由 (4.1)式 說(shuō) 明 模 式 串 中 的 子 串 t0t1tk-1已 和 主 串 si- ksi-k+1si-1匹 配 ,下 一 次 可 直 接 比 較 si和 tk,若 不 存 在 (4.2)式 ,則 結(jié) 合 (4.1)式 說(shuō) 明 在 t0t1tj-1中 不 存 在 任 何 以 t0為 首 字符 子 串 與 si-j+1si-j+2si-1中 以 si-1為 末 字 符 的 匹 配 子 串 ,下一 次 可 直 接 比 較 si和 t0。 為 此 ,定 義 nextj函 數(shù) 如 下 : maxk|0kj,且 “ t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng) 此 集 合 非 空 時(shí) -1 當(dāng) j=0時(shí) 0 其 他 情 況nextj= j 0 1 2 3tj a b a bnextj -1 0 0 1t=“ abab” 對(duì) 應(yīng) 的 next數(shù) 組 如 下 : 由 模 式 串 t求 出 next值 的 算 法 如 下 :void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.len-1) if (k=-1 | t.chj=t.chk) /*k為 -1或 比 較 的 字 符 相 等 時(shí) */ j+;k+; nextj=k; else k=nextk; int KMPIndex(SqString s,SqString t) /*KMP算 法 */ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (is.len /*返 回 匹 配 模 式 串 的 首 字 符 下 標(biāo) */ else v=-1; /*返 回 不 匹 配 標(biāo) 志 */ return v; 設(shè) 主 串 s的 長(zhǎng) 度 為 n,子 串 t長(zhǎng) 度 為 m,在 KMP算 法中 求 next數(shù) 組 的 時(shí) 間 復(fù) 雜 度 為 O(m),在 后 面 的 匹 配中 因 主 串 s的 下 標(biāo) 不 減 即 不 回 溯 ,比 較 次 數(shù) 可 記 為 n,所 以 KMP算 法 總 的 時(shí) 間 復(fù) 雜 度 為 O(n+m)。 例 如 ,設(shè) 目 標(biāo) 串 s=“aaabaaaab”,模 式 串 t=“aaaab”。s的 長(zhǎng) 度 為 n(n=9),t的 長(zhǎng) 度 為 m(m=5)。 用 指 針 i指 示 目標(biāo) 串 s的 當(dāng) 前 比 較 字 符 位 置 ,用 指 針 j指 示 模 式 串 t的 當(dāng)前 比 較 字 符 位 置 。 KMP模 式 匹 配 過(guò) 程 如 下 所 示 。 第1次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失敗 第2次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失敗 第3次匹配 s=aaabaaaab i=3 t=aaaab j=1,j=next1=0 失敗 第4次匹配 s=aaabaaaab i=3 t=aaaab j=0,j=next0=-1 失敗 第5次匹配 s=aaabaaaab i=9 t=aaaab j=4,返回9-5=4 成功 j 0 1 2 3 4tj a a a a bnextj -1 0 1 2 3 上 述 定 義 的 next在 某 些 情 況 下 尚 有 缺 陷 。 例 如 ,模 式 “ aaaab”在 和 主 串 “ aaabaaaab”匹 配 時(shí) ,當(dāng)i=3,j=3時(shí) ,s.ch3t.ch3,由 nextj的 指 示 還 需 進(jìn) 行 i=3、j=2,i=3、 j=1,i=3、 j=0等 三 次 比 較 。 實(shí) 際 上 ,因 為 模 式中 的 第 1、 2、 3個(gè) 字 符 和 第 4個(gè) 字 符 都 相 等 ,因 此 ,不 需要 再 和 主 串 中 第 4個(gè) 字 符 相 比 較 ,而 可 以 將 模 式 一 次 向右 滑 動(dòng) 4個(gè) 字 符 的 位 置 直 接 進(jìn) 行 i=4,j=0時(shí) 的 字 符 比 較 。 KMP算法的改進(jìn)： 這 就 是 說(shuō) ,若 按 上 述 定 義 得 到 nextj=k,而 模 式中 pj=pk,則 為 主 串 中 字 符 si和 pj比 較 不 等 時(shí) ,不 需 要再 和 pk進(jìn) 行 比 較 ,而 直 接 和 pnextk進(jìn) 行 比 較 ,換 句 話說(shuō) ,此 時(shí) 的 nextj應(yīng) 和 nextk相 同 。 為 此 將 nextj修 正 為 nextvalj。 由 模 式 串 t求 出 nextval值 :void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (jnext，再設(shè)一個(gè)對(duì)尾指針q-rear指向鏈隊(duì)列尾部。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可定義如下： typedef struct node typedef struct char data; slnode *h; struct node *next; slnode ; slnode *rear;lqtype;四、思考題 1、 比較鏈隊(duì)列與鏈棧的相同點(diǎn)與不同點(diǎn)。 2、在鏈隊(duì)列中， q-rear指針能否省去？若能，怎樣才能找到隊(duì)尾？ 實(shí)驗(yàn)六 串的模式匹配 一、實(shí)驗(yàn)?zāi)康?熟悉串的有關(guān)概念，掌握串的存儲(chǔ)結(jié)構(gòu)及串的模式匹配算法。二、實(shí)驗(yàn)內(nèi)容 由用戶隨意輸入兩個(gè)串：主串S和模式串T，設(shè)S=s1s2sn，T=t1t2tm，且0m=n。用簡(jiǎn)單和KMP模式匹配算法判斷模式串T是否在主串S中，若在，則輸出模式串在主串的第一匹配位置，否則，匹配失敗，返回零值。三、實(shí)驗(yàn)要點(diǎn)及說(shuō)明 簡(jiǎn)單模式匹配算法和KMP模式匹配算法的主要區(qū)別在于后者將有效利用已有的匹配結(jié)果，省去不必要的匹配過(guò)程，提高匹配性能。 利用串的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。四、思考題 能否用串的塊鏈存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)KMP算法？ 重慶工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院