第3章-字符串(編輯修改稿)
2024-09-01 20:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 求單鏈表示的串的子串 LinkString subStr_link(LinkString s,int i,int j) 求從 s所指的帶頭結(jié)點(diǎn)的鏈串中第 i(i0)個(gè)字符 開(kāi)始連續(xù)取 j個(gè)字符所構(gòu)成的子串。 首先要為鏈串結(jié)構(gòu)和頭結(jié)點(diǎn)申請(qǐng)空間，創(chuàng)建一個(gè)空鏈表，這由算法 。然后判斷所給參數(shù) i ，j的值是否合理， i ， j的取值應(yīng)為 i0， j0。 然后從 shead開(kāi)始找第 i個(gè)結(jié)點(diǎn)，找到后，就從該結(jié)點(diǎn)開(kāi)始，為子串中的結(jié)點(diǎn)申請(qǐng)空間，并將元素值拷過(guò)去 。 程序?qū)崿F(xiàn) 模式匹配 設(shè)有兩個(gè)串 t和 p： t = t0t1… tn1 p = p0p1… pm1 其中 1＜ m≤n（通常有 m n）。我們的任務(wù)是要在 t中找出一個(gè)與 p相同的子串。 其中 t稱(chēng)為 目標(biāo) ， p稱(chēng)為 模式 。從目標(biāo) t中查找與模式 p完全相同的子串的過(guò)程叫作 模式匹配 。 匹配結(jié)果有兩種：如果 t中存在等于 p的子串，就指出該子串在 t中的位置，稱(chēng)為匹配成功；否則稱(chēng)為匹配失敗。 樸素的模式匹配 基本思想 ： 用 p中的字符依次與 t中的字符比較，如果 t0=p0， t1=p1， … ， tm1=pm1， 則匹配成功，返回第一次出現(xiàn)的位置是從第一個(gè)字符 t0開(kāi)始。 否則必有某個(gè) i（ 0≤i≤m1），使得 ti ≠pi，這時(shí)可將 p右移一個(gè)字符，用 p中字符從頭 p0開(kāi)始與 t中字符 t1依次比較 . 如此反復(fù)執(zhí)行，直到下面兩種情況之一： ?到達(dá)某步時(shí)， ti = p0， ti+1 = p1， … ， ti+m1 = pm1，匹配成功，返回第一次出現(xiàn)的位置是從 t中第i+1個(gè)字符 ti開(kāi)始 。 ? 一直將 p移到無(wú)法與 t繼續(xù)比較為止，則匹配失敗。 例 :設(shè)目標(biāo)串 t＝ abbaba和 p＝ aba“ ， t的長(zhǎng)度為 n（ n=6） ,p的長(zhǎng)度為 m（ m=3） 該算法簡(jiǎn)單，易于理解，但效率不高，一旦比較不等，就將 p所指的串右移一個(gè)字符，并從 p0（算法中用 pc[0]表示）開(kāi)始比較。在最壞的情況下，每趟比較都在最后出現(xiàn)不等，最多比較 n－ m＋ 1趟，總比較次數(shù)為 m*(n－ m＋ 1)，由于在一般情況下 m＜＜ n，所以算法運(yùn)行時(shí)間為O(m*n)。 程序?qū)崿F(xiàn) 無(wú)回溯的模式匹配 為了提高匹配速度，在匹配過(guò)程中，一旦 pi和tj比較不等，即： pi≠tj 時(shí)，能夠確定 p右移的位數(shù)（ =1）和繼續(xù)比較的字符 ,即 tj和 pk比較（無(wú)回溯） . ?Knuth等人發(fā)現(xiàn)這個(gè) k值存在，且僅依賴(lài)于
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1