[工學(xué)]數(shù)據(jù)結(jié)構(gòu)——第4章 串c-預(yù)覽頁
【正文】 { =null。對應(yīng)的算法如下： public void StrAssign(string cstr) { int i。i++) //循環(huán)建立字符結(jié)點(diǎn) { p=new LinkNode()。 //將 p結(jié)點(diǎn)插入到尾部 } =null。對應(yīng)的算法如下： public void StrCopy(LinkStringClass t) { LinkNode p=,q,r。 =q。 //尾結(jié)點(diǎn)的 next置為 null } （ 3）求串長 StrLength() 返回當(dāng)前串中的字符個(gè)數(shù)。 p=。對應(yīng)的算法如下： public LinkStringClass Concat(LinkStringClass t) { LinkStringClass nstr=new LinkStringClass()。 =。 } p=。 r=q。 //返回新建的鏈串 } （ 5）求子串 SubStr(i,j) 返回當(dāng)前串中從第 i個(gè)字符開始的連續(xù) j個(gè)字符組成的子串。//新建一個(gè)空串 int k。 //參數(shù)不正確時(shí)返回空串 for (k=0。k=j。 r=q。 //返回新建的鏈串 } （ 6）串插入 InsStr(i,t) 將串 t插入到當(dāng)前串中的第 i個(gè)位置產(chǎn)生一個(gè)新串，并返回這個(gè)新串。//新建一個(gè)空串 int k。 for (k=1。 =q。 =。 } while (p!=null) //將 p及其后的結(jié)點(diǎn) ?nstr { q=new LinkNode()。 //將 q結(jié)點(diǎn)插入到尾部 p=。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。 LinkNode p=,q,r。 ki1。 r=q。k++) //讓 p沿 next跳 j個(gè)結(jié)點(diǎn) p=。 r=q。 //返回新建的鏈串 } （ 8）串替換 RepStr(i,j,t) 將當(dāng)前串中第 i個(gè)字符開始的連續(xù) j個(gè)字符用串 t替換而產(chǎn)生一個(gè)新串，并返回這個(gè)新串。//新建一個(gè)空串 int k。 //參數(shù)不正確時(shí)返回空串 for (k=0。 =q。kj。 =q。 =。 } =null。 LinkNode p=。 //p指向下一個(gè)結(jié)點(diǎn) } } return mystr。對應(yīng)的算法如下： public bool StrEqueal(LinkStringClass s, LinkStringClass t) { LinkNode p = 。 q!=null) { if (!=) return false。amp。 依次類推，若從模式串 s的第 i個(gè)字符開始，每個(gè)字符依次和目標(biāo)串 t中的對應(yīng)字符相等，則匹配成功，該算法返回 i；否則，匹配失敗，算法返回 1。模式匹配過程如下所示。 j) { if ([i]==[j]) //繼續(xù)匹配下一個(gè)字符 { i++。 //子串從頭開始匹配 } } if (j=) return ()。在最壞情況下的時(shí)間復(fù)雜度為 O(n m)。當(dāng)進(jìn)行第1趟匹配時(shí)，匹配失敗處為 i=3， j=3。所謂真子串就是指模式串 t存在某個(gè) k（ 0＜ k＜ j），使得t0t1… tk1=tjktjk+1… tj1成立。 k=1。 next[j]=k。 //求出部分匹配信息 next數(shù)組 while (i amp。 } //i,j各增 1 else j=next[j]。 【 例 】 設(shè)主串 s=ababcabcacbab，模式串 t=abcac。 j 0 1 2 3 4 t[j] a a a a b next[j] 1 0 1 2 3 a a a b a a a a b a a a a b i =3 j =3 （ a ） 第 1 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 2 a a a b a a a a b a a a a b i =3 j =2 （ b ） 第 2 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 1 a a a b a a a a b a a a a b i =3 j =1 （ c ） 第 3 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 0 a a a b a a a a b a a a a b i=3 j=0 （ d ） 第 4 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ]= 1 a a a b a a a a b a a a a b i =9 j =5 （ f ） 第 5 趟匹配，返回 i t. le n g th =4 主串： 模式串： 修改為 i = i + 1 = 4 j = j + 1 = 0 采用KMP算法的模式匹配過程 缺陷： i=3,next[3]=2,而 2號位置與 3號位置的字符相同，沒有必須進(jìn)行下趟匹配。 nextval[0]=1。 else nextval[j]=nextval[k]。 while (i amp。 } else j=nextval[j]。 【 例 】 設(shè)目標(biāo)串為 t=abcaabbabcabaacbacba，模式串 t=abcabaa。 j 0 1 2 3 4 5 6 模式 t a b c a b a a next[j] 1 0 0 0 1 2 1 nextval[j] 1 0 0 1 0 2 1 利用 KMP算法的匹配過程如下： 第 1 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =4 t = a b c a b a a j =4 失敗 修改為 i =4 j = n e x tv a l[ 4 ] = 0 第 2 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =6 t = a b c a b a a j =2 失敗 修改為 i =6 j = n e x tv a l[ 2 ] = 0 第 3 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =6 t = a b c a b a a j =0 失敗 修改為 i =6 j = n e x tv a l[ 0 ] = 1 修改為 i = i + 1 = 7 j = j + 1 = 0 第 4 次匹配 s = a b c a a b b a b c a b a a c b a c b a i = 1 4 t = a b c a b a a j =7 成功，返回 i t. le n g th =7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1