【正文】 。 ?以上簡(jiǎn)略地討論了漢字機(jī)內(nèi)碼表示法及其存儲(chǔ)結(jié)構(gòu) ， 對(duì)于漢字串的運(yùn)算操作必須注意漢字機(jī)內(nèi)碼的特點(diǎn) 。 例如將漢字國標(biāo)碼轉(zhuǎn)換成字母和數(shù)字表示的三個(gè)字節(jié) ， 然后在這三個(gè)字節(jié)之前增加一個(gè)漢字標(biāo)記字節(jié) ，這種標(biāo)記字節(jié)可用來適應(yīng)各種不同的要求 。 這種兩字節(jié)的漢字機(jī)內(nèi)碼 ， 可以很方便地從漢字的序數(shù)計(jì)算出該漢字在字符串中的存儲(chǔ)位置 。 ?在國標(biāo)碼的兩個(gè)字節(jié)上各加 80（ 十六進(jìn)制 ） 就轉(zhuǎn)換為漢字機(jī)內(nèi)碼了 。 ?國標(biāo)區(qū)位碼和國標(biāo)碼之間可用計(jì)算公式相互轉(zhuǎn)換 。 采用代碼標(biāo)識(shí)法的八位碼方法 (續(xù) ) ?除了采用國標(biāo)碼外 ， 還有使用國標(biāo)區(qū)位碼的方案 。 ?現(xiàn)將國標(biāo)交換碼每個(gè)字節(jié)的最高位均置 1以形成八位碼來作漢字機(jī)內(nèi)碼 。 采用代碼標(biāo)識(shí)法的八位碼方法 ?以我國 “ 信息交換用漢字編碼字符集 —基本集 GB231280”為基礎(chǔ) ， 在每個(gè)漢字代碼中設(shè)標(biāo)志作為漢字機(jī)內(nèi)碼 。 為了與西文 ASCII字符區(qū)分 ， 可選用 “ （ ”來表示西文串的標(biāo)記符而用 “ ） ” 表示漢字串的標(biāo)記符；這樣使得括號(hào)以內(nèi)的符號(hào)全部保留 ASCII碼集字符的意義 ， 而括號(hào)以外的符號(hào)就是漢字串的機(jī)內(nèi)碼了 。 ?例如 ， 用電報(bào)碼作為漢字機(jī)內(nèi)碼 。 ?因此 ， 當(dāng)構(gòu)成串的字符集限于西文字母 、 數(shù)字和其它字符時(shí) ， 往往不考慮它的機(jī)內(nèi)碼而直接討論串值的存儲(chǔ)結(jié)構(gòu) 。 ?目前大多數(shù)計(jì)算機(jī)均以 ASCII碼作為西文的機(jī)內(nèi)碼 ， 也有用 EBCDIC碼作機(jī)內(nèi)碼的 ， 它們都是按每個(gè)字節(jié)存放一個(gè)字符設(shè)計(jì)的 。 ?對(duì)應(yīng)于不同的功能 ， 在計(jì)算機(jī)系統(tǒng)中用不同的代碼來表示： ?用戶在輸入設(shè)備上輸入文字信息時(shí) ， 由輸入設(shè)備產(chǎn)生相應(yīng)的代碼稱作 輸入碼 或 外部碼 ； ?在計(jì)算機(jī)內(nèi)部存儲(chǔ)和處理文字信息所采用的代碼稱作 機(jī)內(nèi)碼 ； ?為了表示文字字形 ， 通常是設(shè)計(jì)表示不同字形的字模點(diǎn)陣 ，這種碼稱作 字模點(diǎn)陣碼 ； ?在系統(tǒng)之間傳輸和交換信息的代碼稱作 交換碼 。 } } 串 串的基本概念 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 模式匹配 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 漢字串 漢字串 ?漢字是一種拼形和表意文字 。 else {tlength=len。 int i,len。 堆式動(dòng)態(tài)存儲(chǔ)的 求子串 算法 ? 和串復(fù)制運(yùn)算一樣 ， 求子串運(yùn)算也有復(fù)制和共享兩種實(shí)現(xiàn)方法 。 /*復(fù)制 t到 p中去 */ llength=slength+tlength。 /*設(shè)一個(gè)內(nèi)部串變量 p*/ StrCopy(l,s)。 算法如下： void StrConcat(l,s,t) STRING *l,*s,*t。 } } ?串復(fù)制運(yùn)算也可以共享堆中 t的存儲(chǔ)空間 ， 只建立 s的存儲(chǔ)映像 ， 但若對(duì)其中之一修改就會(huì)影響到另一個(gè) 。 /*建立存儲(chǔ)映像 */ sstart=free。i++) /*逐字符復(fù)制 *／ store[free+i]=store[tstart+i]。 if(free1+tlengthMAXSIZE) printf(“堆中空間不足 ” )； else {for(i=0。 算法如下： void StrCopy(s,t) STRING *s,*t。 free=free+len。 sstart=free。ilen。 len=i。 i=0。 char chars[]。 在邏輯上即為串變量 s賦一個(gè)字符串常量值 。 /*定義堆為一維數(shù)組 store*/ int free。 /*串在堆中的開始位置 */ } typedef struct string STRING。 堆式動(dòng)態(tài)存儲(chǔ)的串的類型說明 define MAXSIZE 10000 /*MAXSIZE為堆的最大容量 */ struct string /*定義串為結(jié)構(gòu)體 */ {int length。 串的存儲(chǔ)映像 ?借助 length和 start在堆結(jié)構(gòu)的串名與串值之間建立起一個(gè)對(duì)應(yīng)關(guān)系 ， 稱作 串名的存儲(chǔ)映像 。 ?每當(dāng)產(chǎn)生一個(gè)串時(shí) ， 應(yīng)用程序就在執(zhí)行過程中動(dòng)態(tài)地從free指示的位置為串值分配一個(gè)長(zhǎng)度與串長(zhǎng)相同的存儲(chǔ)空間 ， 并相應(yīng)修改 free的值； ?同時(shí)建立該串的一個(gè)描述 ， 指示串的長(zhǎng)度和該串在 store中的第一個(gè)字符位置 。 ?例如一維數(shù)組 store char store[maxsize] ?表示堆空間 ， 其中 maxsize表示這片連續(xù)存儲(chǔ)空間的最大容量 。 ?因此 ， 在許多實(shí)際應(yīng)用的串處理系統(tǒng)中采用的是堆式動(dòng)態(tài)存儲(chǔ)分配策略 。 串 串的基本概念 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 模式匹配 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 漢字串 串的堆式動(dòng)態(tài)存儲(chǔ) ?在處理串的應(yīng)用程序中 ， 所處理的串的長(zhǎng)度相差往往較大 ， 處理過的串值長(zhǎng)度變化往往也較大 。 ?算法 index_KMP僅當(dāng)模式串與主串之間存在許多部分匹配的情況下才顯得比算法 index快得多 。 通常模式串的長(zhǎng)度 m要比主串的長(zhǎng)度 n小得多 ， 因此對(duì)整個(gè)匹配算法KMP來說增加這點(diǎn)求 next函數(shù)的時(shí)間是值得的 。} else j=next[j]。 j++。 next[i]=0。 i=0。 else return 1。} else j=next[j]。(jtlen)) if((j==0)||(sch[i]==tch[j]) {i++。 while((islen)amp。 else {i=0。 {int i,j。 ?令 next[j]=k， 則可引出 next函數(shù)的定義如下： 改進(jìn)的模式匹配的一般化思路 ?由 next函數(shù)的定義可推出模式 “ abaabcac”的 next函數(shù)值為： ?有了 next函數(shù)之后 ， 匹配過程可以這樣進(jìn)行：令指示器變量 i和 j的值都為 0， 若在匹配過程中 si=tj；則 i和 j分別加 1， 否則i不變而 j退到 next[j]的位置再比較；若相等 i和 j各加 1， 否則j退到下一個(gè) next值的位置 ， 依此類推直到下面兩種可能： ?一是退到某 next值 （ next[next[… next[j]… ]]） 時(shí)字符比較相等 ，指示器變量值各加 1后繼續(xù)比較； ?另一種是退到值為零 （ 即模式的第一個(gè)字符失配 ） ， 此時(shí)需將模式繼續(xù)向右滑動(dòng)一個(gè)位置 ， 從主串的下一個(gè)字符 si+1重新開始匹配 。 而已得到的部分匹配結(jié)果可表示為： “ tjk+1tjk+2… tj1”=“sik+1sik+2… si1” ?由前面兩式可以推出下式： “ t0t1… tk2”=“tjk+1tjk+2… tj1” 改進(jìn)的模式匹配的一般化思路 ?“t0t1… tk2”=“tjk+1tjk+2… tj1”等式說明 ， 在某趟匹配過程中 si≠ tj失配時(shí) ， 如果模式串中前 j1個(gè)字符中存在首尾相同的最大子串長(zhǎng)度為 k1， 即模式 t中前 k1個(gè)字符與 tj前的 k1個(gè)字符對(duì)應(yīng)相等時(shí) ， 模式 t就可以向右滑動(dòng) k個(gè)字符位置即 si與 tk繼續(xù)比較了 。 一種改進(jìn)的模式匹配的匹配過程 ?值得注意的是在整個(gè)匹配過程中 i指示器變量的值沒有回溯 。 仔細(xì)觀察可以發(fā)現(xiàn) ， 在 i=3和 j=0、 i=4和 j=0、 i=5和 j=0這三次比較都是不必進(jìn)行的；這是由于從第三趟部分匹配的結(jié)果就可以得出主串中的第 5和 6個(gè)字符 （ 即 i= 4和 5） 和模式串中的第 3和 4個(gè)字符 （ 即 j= 2和 3） 相同為 b、 c和 a，而模式串中的第一個(gè)字符 （ 即 j=0） 是 a無需再和這三個(gè)字符進(jìn)行比較 ， 僅需將模式串向右滑動(dòng)三個(gè)字符的位置進(jìn)行i= j=1時(shí)的字符比較即可 。 ?其改進(jìn)思想是充分利用部分匹配的信息 ， 不需回溯主串指示器變量 i， 而是在匹配過程中出現(xiàn)字符比較不等時(shí) ， 將模式串 t盡可能遠(yuǎn)地向右滑動(dòng)一段距離后繼續(xù)進(jìn)行比較 。 一種改進(jìn)的模式匹配算法 ?這種改進(jìn)的模式匹配算法是 與 ， 因此人們稱它為克努特 —莫里斯 —普拉特算法 ， 簡(jiǎn)稱為 KMP算法 。 ?在這樣一種較好的匹配情況下 ， 即每趟中不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí) ， 其時(shí)間復(fù)雜度為 O(n+m)。 簡(jiǎn)單的模式匹配的過程描述 ?對(duì)于模式串 t=“abcac”和主串 s=“ababcabcacbab”使用算法 Index(s,t)的匹配過程如下： 簡(jiǎn)單的模式匹配的過程描述 (續(xù) ) 簡(jiǎn)單的模式匹配的算法（續(xù)） ?算法 Index(s,t)簡(jiǎn)單 ， 算法思想自然 ， 匹配過程容易理解 。 } 簡(jiǎn)單的模式匹配算法 ?簡(jiǎn)單的模式匹配算法的思想是： ?從主串 s的第一個(gè)字符開始和模式 t的第一個(gè)字符比較 ， ?若相等則繼續(xù)逐個(gè)比較后續(xù)字符 ， ?若某一次對(duì)應(yīng)字符不相等則從主串 s 中的第二個(gè)字符起再重新和模式 t的每個(gè)字符逐個(gè)比較 。 } if(bool0) return i。 if(StrCompare(l,t)==0) bool=1。amp。 bool=1。 /*求主串 s的長(zhǎng)度于 n*/ 模式匹配（續(xù)） m=StrLength(t)。 STRING *l。 ?利用串比較 、 求串長(zhǎng)和求子串三種基本操作實(shí)現(xiàn)模式匹配的算法描述： int StrIndex(s,t) /*匹配成功返回子串位置 ， 否則返回 1*/ STRING *s,*t。 ?模式匹配在文本編輯 、 文件檢索和各種串處理系統(tǒng)中有著廣泛的應(yīng)用 ， 因此它是最重要的串運(yùn)算之一 。 /*設(shè)置子串長(zhǎng)度 */ } } ?該算法的主要時(shí)間開銷在于從主串 s中取出子串存于 t中 ， 而子串的最大長(zhǎng)度等于主串 ， 主串最長(zhǎng)為預(yù)先定義好的定長(zhǎng)STRINGLEN， 所以其時(shí)間復(fù)雜度為 O(STRINGLEN)。j++,i++) tch[j]=sch[i] /*將所求子串存入 t串中 */ tch[j]=’\0’。 else {for(j=0。 if((i0)||(i=slen)) printf(“子串的開始位置 i越界錯(cuò)誤 \n”)。 int i,len。