《數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第4章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第4章.ppt（90頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 第四章 串 【 課前思考 】 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)僅在于了解串類型定義中各 基本
2、操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這 些基本操作來(lái)實(shí)現(xiàn)串的其它操作。本章的 難點(diǎn) 是理 解實(shí)現(xiàn) 串匹配的 KMP算法 的思想，但它不屬本章學(xué) 習(xí)的基本要求，更不是重點(diǎn)學(xué)習(xí)內(nèi)容。 【 知識(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è)是和
3、KMP算法相關(guān)的練習(xí)。 4.1 串類型的定義 4.2 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法 4.1串的類型定義 一、 基本概念 1 串的定義 串 ( string) 是由零個(gè)或多個(gè)字符組成的有限序列 ， 記作 s=a1a2 an， 其中 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ù) ，
4、一般用符號(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， 真子串
5、 個(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); i
6、f (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)度的串值則被舍去，稱之為 “截?cái)唷?。 特點(diǎn) : Status Con
7、cat(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) / 未截?cái)?else if (S10 MAXSTRSIZE) / 截?cái)?else / 截?cái)?(僅取 S1) T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLEN S10; T0 = MAXSTRLEN; uncut = FAL
8、SE; 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-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch
9、i ; 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 ) 插入前 圖 4 1 順序串的插入 ( b ) 插入后 ( i = 3 ) else if (pos+t.lenMAXLEN, 但串 t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i-) s-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch i ; s-len=MAXLEN; els
10、e /* 串 t的部分字符序列要舍棄 */ for (i=0;ich i+pos =t.ch i ; s-len=MAXSTRLEN; return(1); (2) 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-ch i-len =s-ch i ; s-len=s-len - len; return(1); 【 算法 串刪除函數(shù) 】 a b c i j k a
11、b c d e f g h i j k ( a ) 刪除前 圖 4 - 2 順序串的刪除 ( i = 4 , j = 5 ) ( b ) 刪除后 (3) StrCopy(s, t) /* 將串 t的值復(fù)制到串 s中 */ SString *s, t; int i; for (i=0;ich i =t.ch i ; s-len=t.len; 【 算法 串復(fù)制函數(shù) 】 (4) StrEmpty(s) /* 若串 s為空 (即串長(zhǎng)為 0), 則返回 1, 否則返回 0 */ SString s; if (s.len=0) return(1); else return(0); 【 算法 判空函數(shù) 】
12、(5) 串比較函數(shù) 。 StrCompare(s, t) /* 若串 s和 t相等 , 則返回 0；若 st， 則返回 1；若 st， 則 返 回 -1 */ SString s, t; int i; for (i=0;is.len return(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-ch i =t.ch i-s-len ; s-len+=t.len;flag=1; else
13、if (s-lenlen;ich i =t.ch i-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
14、=0;ich i =s.ch i+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)度 HSt
15、ring; 二、串的堆分配存儲(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(S
16、1.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; / 空子串 el
17、se / 完整子串 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)
18、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 串的模式匹配算
19、法 子串的定位操作通常稱為串的 模式匹 配 ，是各種串處理系統(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算法 例如
20、,設(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 = c d d c d c i = 2 t = c d c j = 2 失敗 第 2 次匹配 s = c d d c d c i = 1 t = c d c j = 0 失敗 第 3 次匹配 s = c d d c d c i = 2 t = c d c j = 0 失敗 第 4 次匹配 s = c d d c d c i = 5
21、t = c d c 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è)字符，
22、 再 比較模式串的最后一個(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; / 模式串的“尾字符”不匹
23、配 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)行比較。 避免多余的、不必要的比較，從而提高算法性能。算法 總
24、在 0(n+m)的時(shí)間數(shù)量級(jí)上完成匹配操作。 a b a b c a b c a c b a b ab c ( a ) 第一趟匹配 s 3 t 3 ( b ) 第二趟匹配 s 7 t 5 ( c ) 第三趟匹配成功 圖 K M P 模式匹配過(guò)程 a b a b c a b c a c b a b ab cac a b a b c a b c a c b a b a b cac 2.KMP算法匹配實(shí)例： (1)模式串 t中沒(méi)有真子串 真子串 是指模式串 t存在某個(gè) k(0 k j),使得 “ t0t1 tk” =“ tj-ktj-k+1 tj” 成立 。 例如 t=cdc就是這樣的模式串 。 在
25、圖 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,比較 s3和 t0。 這樣 ,模式匹配過(guò)程主串指針 i就可 不必回溯 。 (2)模式串中存在真子串 例如 t=“ abab” ,由于“ t0t1” =“ t2t3” (這里 k=1,j=3),則存在真子串。設(shè) s=“ abacabab” ,t=“
26、abab” ,第一次匹配過(guò)程如下所 示。 第 1 次匹配 s = a ba c a ba b i= 3 t = a ba b 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=s0s1s n-1,t=t0t1t m-1,當(dāng) sitj (0in-m,0j m)時(shí) ,存在 : t0t1 tj-1=si-jsi-j+1 si-1 (4.1) 若模式串中存在的真子串滿足 : t0t1 tk=
27、tj-ktj-k+1 tj (0 k j) (4.2) 由 (4.1)式說(shuō)明模式串中的子串 t0t1 tk-1已和主串 si-ksi-k+1 si-1匹配 ,下一次可直接比較 si和 tk,若不存在 (4.2) 式 ,則結(jié)合 (4.1)式說(shuō)明在 t0t1 tj-1中不存在任何以 t0為首 字符子串與 si-j+1si-j+2 si-1中以 si-1為末字符的匹配子串 , 下一次可直接比較 si和 t0。 為此 ,定義 nextj函數(shù)如下 : maxk|0kj,且 “ t0t1 tk-1” =“ tj-ktj-k+1 tj-1” 當(dāng)此集合非空時(shí) -1 當(dāng) j=0時(shí) 0 其他情況 nextj= j
28、 0 1 2 3 tj a b a b nextj -1 0 0 1 t=“ 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=
29、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)前比較字符位置 ,用指針
30、 j指 示模式串 t的當(dāng)前比較字符位置。 KMP模式匹配過(guò) 程如下所示。 第 1 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 3 , j = n e x t 3 = 2 失敗 第 2 次匹配 s = a a a b a aaab i = 3 t = aaaab j = 2 , j = n e x t 2 = 1 失敗 第 3 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 1 , j = n e x t 1 = 0 失敗 第 4 次匹配 s = a a a b a a a a b i = 3 t = a
31、aaab j = 0 , j = n e x t 0 = - 1 失敗 第 5 次匹配 s = a a a b a a a a b i = 9 t = aaaab j = 4 ,返回 9 - 5 = 4 成功 j 0 1 2 3 4 tj a a a a b nextj -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í)際上 ,因?yàn)槟Ｊ?中的第 1、 2、 3個(gè)字符
32、和第 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;
33、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= s1s2s n ， T= t1t2t m ，且 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é)院
數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第4章.ppt
