【正文】 至今仍被采用 。 ?算法 index_KMP僅當(dāng)模式串與主串之間存在許多部分匹配的情況下才顯得比算法 index快得多 。 ?index_KMP算法的最大特點(diǎn)是不需回溯主串的指示器變量 i， 整個(gè)匹配過(guò)程只需從頭到尾掃描主串一遍 ，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配 ， 無(wú)需回頭重讀 。 串 串的基本概念 串的定長(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)度相差往往較大 ， 處理過(guò)的串值長(zhǎng)度變化往往也較大 。 ?采用定長(zhǎng)順序存儲(chǔ)在多數(shù)串的串長(zhǎng)較小時(shí)其空間利用率低 ， 且使某些運(yùn)算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯(cuò)誤結(jié)果 。 ?因此 ， 在許多實(shí)際應(yīng)用的串處理系統(tǒng)中采用的是堆式動(dòng)態(tài)存儲(chǔ)分配策略 。 堆式動(dòng)態(tài)存儲(chǔ)的思想 ?應(yīng)用系統(tǒng)在內(nèi)存中開(kāi)辟一個(gè)容量很大且地址連續(xù)的一片存儲(chǔ)空間 ， 作為存放所有串值的可利用空間即堆空間 。 ?例如一維數(shù)組 store char store[maxsize] ?表示堆空間 ， 其中 maxsize表示這片連續(xù)存儲(chǔ)空間的最大容量 。 ?設(shè)整形變量 free指示該空間中尚未分配區(qū)間的開(kāi)始地址（ 初始值為 1） 。 ?每當(dāng)產(chǎn)生一個(gè)串時(shí) ， 應(yīng)用程序就在執(zhí)行過(guò)程中動(dòng)態(tài)地從free指示的位置為串值分配一個(gè)長(zhǎng)度與串長(zhǎng)相同的存儲(chǔ)空間 ， 并相應(yīng)修改 free的值； ?同時(shí)建立該串的一個(gè)描述 ， 指示串的長(zhǎng)度和該串在 store中的第一個(gè)字符位置 。 串的堆式動(dòng)態(tài)存儲(chǔ)分配示意圖 其中： length指示串值序列的長(zhǎng)度 ， start指示串值序列在 store中的開(kāi)始地址 。 串的存儲(chǔ)映像 ?借助 length和 start在堆結(jié)構(gòu)的串名與串值之間建立起一個(gè)對(duì)應(yīng)關(guān)系 ， 稱(chēng)作 串名的存儲(chǔ)映像 。 ?所有的串名存儲(chǔ)映像構(gòu)成了一張為系統(tǒng)中所有串名和串值之間建立一一對(duì)應(yīng)關(guān)系的映像表 （ 或符號(hào)表 ） 。 堆式動(dòng)態(tài)存儲(chǔ)的串的類(lèi)型說(shuō)明 define MAXSIZE 10000 /*MAXSIZE為堆的最大容量 */ struct string /*定義串為結(jié)構(gòu)體 */ {int length。 /*串長(zhǎng)度 */ int start。 /*串在堆中的開(kāi)始位置 */ } typedef struct string STRING。 /*定義串類(lèi)型標(biāo)識(shí)符為 STRING*/ char store[MAXSIZE]。 /*定義堆為一維數(shù)組 store*/ int free。 /*堆 store中尚未分配區(qū)間的開(kāi)始地址指示器變量*/ 堆式動(dòng)態(tài)存儲(chǔ)的 串賦值 算法 ?該運(yùn)算把存儲(chǔ)于字符串?dāng)?shù)組 chars中的字符串常量存入堆store中 ， 并為 s建立存儲(chǔ)映像 。 在邏輯上即為串變量 s賦一個(gè)字符串常量值 。 ?其算法描述如下： void StrAssign(s,chars) STRING *s。 char chars[]。 {int i,len。 i=0。 /*為統(tǒng)計(jì)字符串常量中的字符個(gè)數(shù)初始化 */ while(chars[i]!=’\0’) /*統(tǒng)計(jì) chars中字符個(gè)數(shù) */ i++。 len=i。 堆式動(dòng)態(tài)存儲(chǔ)的 串賦值 算法 (續(xù) ) if((len1)||(free1+lenMAXSIZE)) printf(“串常量為空串或堆的尚未分配區(qū)間空間不足 \n”)； else {for(i=0。ilen。i++) /*逐字符賦值 */ store[free+i]=chars[i]。 sstart=free。 /*建立存儲(chǔ)映像 */ slength=len。 free=free+len。 /*修改堆中的指示器變量 free的值 */ } } 堆式動(dòng)態(tài)存儲(chǔ)的 串復(fù)制 算法 ? 該運(yùn)算把堆中的串 t復(fù)制到 s中去 。 算法如下： void StrCopy(s,t) STRING *s,*t。 {int i。 if(free1+tlengthMAXSIZE) printf(“堆中空間不足 ” )； else {for(i=0。itlength。i++) /*逐字符復(fù)制 *／ store[free+i]=store[tstart+i]。 slength=tlength。 /*建立存儲(chǔ)映像 */ sstart=free。 free=free+tlength。 } } ?串復(fù)制運(yùn)算也可以共享堆中 t的存儲(chǔ)空間 ， 只建立 s的存儲(chǔ)映像 ， 但若對(duì)其中之一修改就會(huì)影響到另一個(gè) 。 堆式動(dòng)態(tài)存儲(chǔ)的 串聯(lián)接 算法 ?只要分別將 s串和 t串復(fù)制到 store中為 l開(kāi)辟的存儲(chǔ)區(qū) ， 并建立 l的存儲(chǔ)映像即可完成串聯(lián)接運(yùn)算 。 算法如下： void StrConcat(l,s,t) STRING *l,*s,*t。 {STRING *p。 /*設(shè)一個(gè)內(nèi)部串變量 p*/ StrCopy(l,s)。 /*復(fù)制 s到 l中去 */ StrCopy(p,t)。 /*復(fù)制 t到 p中去 */ llength=slength+tlength。 /*修改 l的存儲(chǔ)映像中的串長(zhǎng) */ } ? 注意 ， 為什么算法中沒(méi)有修改 l的開(kāi)始位置 ？ 又為什么未見(jiàn)修改堆中指示器變量 free的語(yǔ)句 ？ 這是因?yàn)榈谝粋€(gè)串復(fù)制語(yǔ)句已使 l的開(kāi)始位置到位 ， 而第二個(gè)串復(fù)制語(yǔ)句已使 free的值指向尚未分配區(qū)的開(kāi)始位置 ， 故只需修改串長(zhǎng)即可 。 堆式動(dòng)態(tài)存儲(chǔ)的 求子串 算法 ? 和串復(fù)制運(yùn)算一樣 ， 求子串運(yùn)算也有復(fù)制和共享兩種實(shí)現(xiàn)方法 。 這里給出共享實(shí)現(xiàn)算法如下： void SubString(t,s,i,len) /*將 s中第 i個(gè)字符開(kāi)始的 len個(gè)字符構(gòu)成的子串送到 t中 */ STRING *t,*s。 int i,len。 {if((i0)||(len0)||(lenslengthi)) printf(“所給子串的位置或長(zhǎng)度有錯(cuò)誤 \n”)。 else {tlength=len。 /*建立子串 t的存儲(chǔ)映像 */ tstart=sstart+i。 } } 串 串的基本概念 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 模式匹配 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 漢字串 漢字串 ?漢字是一種拼形和表意文字 。 ?無(wú)論是西文還是漢字 ， 計(jì)算機(jī)系統(tǒng)均應(yīng)具有輸入 、 加工處理和輸出的功能 ， 并能在不同的系統(tǒng)之間進(jìn)行信息交換 。 ?對(duì)應(yīng)于不同的功能 ， 在計(jì)算機(jī)系統(tǒng)中用不同的代碼來(lái)表示： ?用戶(hù)在輸入設(shè)備上輸入文字信息時(shí) ， 由輸入設(shè)備產(chǎn)生相應(yīng)的代碼稱(chēng)作 輸入碼 或 外部碼 ； ?在計(jì)算機(jī)內(nèi)部存儲(chǔ)和處理文字信息所采用的代碼稱(chēng)作 機(jī)內(nèi)碼 ； ?為了表示文字字形 ， 通常是設(shè)計(jì)表示不同字形的字模點(diǎn)陣 ，這種碼稱(chēng)作 字模點(diǎn)陣碼 ； ?在系統(tǒng)之間傳輸和交換信息的代碼稱(chēng)作 交換碼 。 漢字串（續(xù)） ?對(duì)于西文來(lái)說(shuō) ， 由于借助于拼音規(guī)則可只用少量字母拼成文字 ， 因而其機(jī)內(nèi)碼 、 輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)都比較簡(jiǎn)單； ?在設(shè)計(jì)這些代碼時(shí)已盡可能做到相互一致 ， 代碼間的轉(zhuǎn)換也非常簡(jiǎn)單 。 ?目前大多數(shù)計(jì)算機(jī)均以 ASCII碼作為西文的機(jī)內(nèi)碼 ， 也有用 EBCDIC碼作機(jī)內(nèi)碼的 ， 它們都是按每個(gè)字節(jié)存放一個(gè)字符設(shè)計(jì)的 。 ?當(dāng)向計(jì)算機(jī)輸入西文信息時(shí) ， 只要在鍵盤(pán)上按不同的鍵就可產(chǎn)生不同的輸入代碼 ， 這些輸入碼集可以簡(jiǎn)單地等同于機(jī)內(nèi)碼集 。 ?因此 ， 當(dāng)構(gòu)成串的字符集限于西文字母 、 數(shù)字和其它字符時(shí) ， 往往不考慮它的機(jī)內(nèi)碼而直接討論串值的存儲(chǔ)結(jié)構(gòu) 。 漢字代碼轉(zhuǎn)換關(guān)系示意圖 采用漢字串標(biāo)識(shí)法的七位碼方法 ?以 ASCII碼集或其子集作為 基集 ， 由 兩個(gè)或兩相以上 的ASCII字符構(gòu)成一個(gè) 漢字機(jī)內(nèi)碼 。 ?例如 ， 用電報(bào)碼作為漢字機(jī)內(nèi)碼 。 電報(bào)碼是以 ASCII字符集的子集 C={0,1,2… 9}為基集 ， 由四個(gè) 0~9的數(shù)字字符構(gòu)成一個(gè)漢字機(jī)內(nèi)碼 。 為了與西文 ASCII字符區(qū)分 ， 可選用 “ （ ”來(lái)表示西文串的標(biāo)記符而用 “ ） ” 表示漢字串的標(biāo)記符；這樣使得括號(hào)以?xún)?nèi)的符號(hào)全部保留 ASCII碼集字符的意義 ， 而括號(hào)以外的符號(hào)就是漢字串的機(jī)內(nèi)碼了 。 如下圖 ?這種存儲(chǔ)方法 ， 對(duì)于順序地從前向后逐個(gè)處理的運(yùn)算操作是很適用的 ， 但對(duì)于某些隨機(jī)性的操作卻不很方便 。 采用代碼標(biāo)識(shí)法的八位碼方法 ?以我國(guó) “ 信息交換用漢字編碼字符集 —基本集 GB231280”為基礎(chǔ) ， 在每個(gè)漢字代碼中設(shè)標(biāo)志作為漢字機(jī)內(nèi)碼 。 ?國(guó)標(biāo)交換碼規(guī)定由兩個(gè)字節(jié)構(gòu)成一個(gè)漢字交換碼 ， 每個(gè)字節(jié)都用七位 ， 最高位均為 0。 ?現(xiàn)將國(guó)標(biāo)交換碼每個(gè)字節(jié)的最高位均置 1以形成八位碼來(lái)作漢字機(jī)內(nèi)碼 。 以漢字 “ 大 ” 為例 ， 其機(jī)內(nèi)碼如下圖 。 采用代碼標(biāo)識(shí)法的八位碼方法 (續(xù) ) ?除了采用國(guó)標(biāo)碼外 ， 還有使用國(guó)標(biāo)區(qū)位碼的方案 。 ?區(qū)位碼中 ， 每個(gè)漢字對(duì)應(yīng)四個(gè)十進(jìn)制數(shù)字 ， 前兩位是區(qū)號(hào)共 94個(gè)區(qū) ， 每區(qū) 94位 。 ?國(guó)標(biāo)區(qū)位碼和國(guó)標(biāo)碼之間可用計(jì)算公式相互轉(zhuǎn)換 。 ?區(qū)位碼轉(zhuǎn)換為國(guó)標(biāo)碼的方法是 ， 先將十進(jìn)制區(qū)位碼轉(zhuǎn)換成十六進(jìn)制 ， 然后在兩個(gè)字節(jié)上分別加 20（ 十六進(jìn)制 ） 就得到國(guó)標(biāo)碼 。 ?在國(guó)標(biāo)碼的兩個(gè)字節(jié)上各加 80（ 十六進(jìn)制 ） 就轉(zhuǎn)換為漢字機(jī)內(nèi)碼了 。 ?目前應(yīng)用較為廣泛的是采用國(guó)標(biāo)碼和區(qū)位碼進(jìn)行代碼標(biāo)識(shí) ，形成兩字節(jié)漢字機(jī)內(nèi)碼 。 這種兩字節(jié)的漢字機(jī)內(nèi)碼 ， 可以很方便地從漢字的序數(shù)計(jì)算出該漢字在字符串中的存儲(chǔ)位置 。 漢字區(qū)位碼轉(zhuǎn)換為機(jī)內(nèi)碼的過(guò)程 ?以漢字 “ 雹 ” 為例的轉(zhuǎn)換過(guò)程如下： 采用漢字標(biāo)識(shí)法的多個(gè)字節(jié)代碼 ?在每個(gè)漢字代碼前增加一個(gè)標(biāo)識(shí)字節(jié) ， 就形成所謂 多字節(jié)的漢字機(jī)內(nèi)碼 。 例如將漢字國(guó)標(biāo)碼轉(zhuǎn)換成字母和數(shù)字表示的三個(gè)字節(jié) ， 然后在這三個(gè)字節(jié)之前增加一個(gè)漢字標(biāo)記字節(jié) ，這種標(biāo)記字節(jié)可用來(lái)適應(yīng)各種不同的要求 。 但是這種機(jī)內(nèi)碼的編輯性較差 ， 占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過(guò)程中作為系統(tǒng)的輔助漢字機(jī)內(nèi)碼 。 ?以上簡(jiǎn)略地討論了漢字機(jī)內(nèi)碼表示法及其存儲(chǔ)結(jié)構(gòu) ， 對(duì)于漢字串的運(yùn)算操作必須注意漢字機(jī)內(nèi)碼的特點(diǎn) 。 前面幾節(jié)討論的串運(yùn)算都是針對(duì)西文串的 ， 其運(yùn)算原則同樣適用于漢字串 ， 但在使用具體語(yǔ)言定義漢字串的運(yùn)算時(shí)要注意漢字內(nèi)碼雙字節(jié) （ 對(duì)雙字節(jié)內(nèi)碼而言 ） 的特點(diǎn) 。