工學(xué)第三章串ppt課件-資料下載頁(yè)
2024-11-03 20:42本頁(yè)面
【正文】 ‘ T1?=?T2?成立否， No則屬于其他情況 j=4時(shí) , k={2， 3}， 要查看 ‘ T1?=?T3? 及 ‘ T1T2?=?T2 T3? 是否成立 j=5時(shí) , k={2， 3， 4}， 要查看‘ T1?=?T4? ， ?T1T2?=?T3T4? 和 ‘ T1T2T3?=?T2T3T4?是否成立 以此類(lèi)推，可得后續(xù) next[j]值。 next[j]與 s無(wú)關(guān)，可以預(yù)先計(jì)算 例： 1 第 3章 特殊線性表 ——串 1. 在串 S和串 T中分別設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 S中所剩字符長(zhǎng)度小于 T的長(zhǎng)度或 T中所有字符均比較完畢 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個(gè)字符；否則 將 j向右滑動(dòng)到 next[j]位置 ， 即 j=next[j]； 如果 j=0， 則將 i和 j分別加 1， 準(zhǔn)備下一趟比較； 3. 如果 T中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回 0； KMP算法用偽代碼描述 void GetNext(char T[ ], int next[ ]) { next[1]=0。 j=1。 k=0。 while (jT[0]) if ((k==0)| |(T[j]= =T[k])) { j++。 k++。 next[j]=k。 } else k=next[k]。 } 第 3章 特殊線性表 ——串 求模式串 T的 next函數(shù)值算法 第 3章 特殊線性表 ——串 求 next數(shù)組的算法只需將模式掃描一遍，設(shè)模式串的長(zhǎng)度為 m，則算法的時(shí)間復(fù)雜度為 O(m)。而 KMP算法的時(shí)間復(fù)雜度為O(n+m)。 KMP算法與 BF算法相比，增加了很大的難度，我們主要學(xué)習(xí)該算法的設(shè)計(jì)技巧。 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c i j i j i j 第一趟， i=3， j=3失敗， i不動(dòng) next[3]=1， j滑動(dòng)到 1的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第二趟 i=7， j=5失敗， i不動(dòng) next[5]=2， j滑動(dòng)到 2的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第三趟， i=11， j=6， T中全部字符都比較完畢，匹配成功 第 3章 特殊線性表 特殊線性表 棧 隊(duì) 列 串 ⑴ 棧的定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 隊(duì)列定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 串的定義 ⑵ 基本概念 ⑶ ADT定義 順序棧 鏈 棧 循環(huán)隊(duì)列 鏈隊(duì)列 順序存儲(chǔ) 鏈接存儲(chǔ) 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 比 較 模式匹配 比較 比較 ⑴ 基本操作的實(shí)現(xiàn) ⑵ 時(shí)間性能 ⑴ 基本操作的實(shí)現(xiàn) ⑵ 時(shí)間性能 第 3章 特殊線性表 1938年出生， 25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士，留校任教， 28歲時(shí)任副教授。 30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任正教授。從 31歲起，開(kāi)始出版他的歷史性經(jīng)典巨著： The Art of Computer Programming。 他計(jì)劃共寫(xiě) 7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)Turing Award， 此時(shí)，他年僅 36歲。他有一個(gè)奇妙的承諾：在他定期進(jìn)行的講座中，會(huì)不斷提出一些新的難題。如果有人能在給定的期限內(nèi)解出任何一道難題，他將為那個(gè)人的博士論文簽名 (大約相當(dāng)于名譽(yù)導(dǎo)師吧 )！不知道世界之大，有沒(méi)有哪位后起之秀能獲得這樣的殊譽(yù)？
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1