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