【正文】 ?在實現(xiàn)串的聯(lián)接運算時 ， 要注意兩串 s和 t聯(lián)接后的結(jié)果串 L超過定長的問題 ， 即： slen+tlen=STRINGLEN時結(jié)果串超過定長 STRINGLEN， 此時算法中輸出相應(yīng)提示信息 。 {int i,j。 else {for(i=0。i++) lch[i]=sch[i]。tch[j]!=’\0’。 l[i+j]=’\0’。} } （續(xù)） ?該算法的時間開銷主要在于復(fù)制兩個串中字符到結(jié)果串中 ， 其復(fù)制字符個數(shù)為兩個串的長度之和 ， 故其時間復(fù)雜度為 O(slen+tlen)。 ?然而 ， 串的聯(lián)接運算是滿足結(jié)合律的；在多個串聯(lián)接時 ， 只要位置次序不變 ， 先聯(lián)接哪兩個都無所謂 ，最終結(jié)果都是一樣的 。 ?當(dāng) i0或 i≥s len時 ， 子串開始位置非法； ?當(dāng) len0或 lensleni時 ， 子串的長度非法 。 ?求子串的算法描述如下： void SubString(t,s,i,len) STRING *t,*s。 {int j。 （續(xù)） else if((len0)||(lensleni)) printf(“子串的長度 len越過主串錯誤 \n”)。jlen。 /*為子串 t添加結(jié)束標(biāo)志 */ tlen=len。 串 串的基本概念 串的定長順序存儲及運算實現(xiàn) 模式匹配 串的堆式動態(tài)存儲及運算實現(xiàn) 漢字串 模式匹配 ?子串的定位操作通常稱作 模式匹配 ， 子串 t稱作 模式 ，在主串 s中確定 t的位置的過程稱作 匹配過程 。然而模式匹配不是串的基本運算 ， 它可以借用串的基本運算來實現(xiàn) 。 {int n,m,i,bool。 n=StrLength(s)。 /*求模式串 t的長度于 m*/ i=0。 while((i=nm)amp。(bool0)) {SubString(l,s,i,m)。 else i++。 else return 1。 ?依次類推 ， 直到模式 t中每個字符都和主串 s中的一個連續(xù)字符序列對應(yīng)相等則匹配成功 ， 函數(shù)值為模式 t中第一個字符所對應(yīng)的字符在主串 s中的序號； ?若掃描完主串 s后還未找到模式 t 的出現(xiàn)則匹配失敗 ， 函數(shù)值為 1。 ?在許多應(yīng)用場合如文本編輯等 ， 匹配效率也較高 。 ?然而在最壞情況下 ， 即每趟不成功的匹配都發(fā)生在模式串 t中最后一個字符時 ， 其時間復(fù)雜度為O(n*m)， 算法效率很低 。 ?該算法可以在 O(n+m)的時間數(shù)量級上完成串的模式匹配運算 。 一種改進(jìn)的模式匹配算法（續(xù)） ?回顧前述的匹配過程示例 ， 在第三趟的匹配中當(dāng) i= j=4比較字符不等時 ， 又從 i= j=0重新開始比較 。 同理 ， 在第一趟匹配中出現(xiàn)字符不等時 ， 僅需將模式串向右滑動兩個字符位置進(jìn)行 i=j=0時的字符比較 。 改進(jìn)的模式匹配的一般化思路 ?對于模式串 t=“t0t1… tm1”和主串 s=“s0s1… sn1”， 當(dāng)匹配過程中 si≠ tj產(chǎn)生失配時 ， 模式串向右滑動多遠(yuǎn)距離 ？ ?或者說失配時 i指示器變量不回溯 ， 主串中第 i個字符應(yīng)該與模式串中哪個字符再繼續(xù)比較 ？ ?設(shè)此時應(yīng)該與模式串中第 k(kj)個字符比較 ， 則模式 t中前k1個字符的子串應(yīng)該滿足如下關(guān)系： “ t0t1… tk2”=“sik+1sik+2… si1” ?且不存在大于 k的這樣的關(guān)系式 。 ?模式 t中的每一個 tj都對應(yīng)一個 k值 ， 這個 k值表示當(dāng)在 tj處失配時模式 t應(yīng)向右滑動的字符數(shù) ， 它僅依賴于模式 t而與主串 s無關(guān) 。 改進(jìn)的模式匹配的 KMP算法描述 int index_KMP(s,t) STRING *s, *t。 if((tlen==0)||(slentlen)) return 1。 j=0。amp。 j++。 if(jtlen) return itlen。 } } 運用算法 index_KMP的匹配過程 求模式串 t的 next函數(shù)值的算法 void getnext(STRING *t, int next[]) /*求模式串 t的 next函數(shù)值并存入數(shù)組 next[]中 */ {int i,j。 j=1。 /*初始化指示器變量并給 next[0]賦零值 */ while(i tlen) if((j==0)||(tch[i]==tch[j]) {i++。 next[i]=j。 } 一種改進(jìn)的模式匹配算法（續(xù)） ?算法 getnext的時間復(fù)雜度為 O(m)。 ?需要說明的是 ， 算法 index的時間復(fù)雜度雖然是O(m*n)， 但在一般情況下其實際執(zhí)行時間近似于O(m+n)， 所以至今仍被采用 。 ?index_KMP算法的最大特點是不需回溯主串的指示器變量 i， 整個匹配過程只需從頭到尾掃描主串一遍 ，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配 ， 無需回頭重讀 。 ?采用定長順序存儲在多數(shù)串的串長較小時其空間利用率低 ， 且使某些運算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯誤結(jié)果 。 堆式動態(tài)存儲的思想 ?應(yīng)用系統(tǒng)在內(nèi)存中開辟一個容量很大且地址連續(xù)的一片存儲空間 ， 作為存放所有串值的可利用空間即堆空間 。 ?設(shè)整形變量 free指示該空間中尚未分配區(qū)間的開始地址（ 初始值為 1） 。 串的堆式動態(tài)存儲分配示意圖 其中： length指示串值序列的長度 ， start指示串值序列在 store中的開始地址 。 ?所有的串名存儲映像構(gòu)成了一張為系統(tǒng)中所有串名和串值之間建立一一對應(yīng)關(guān)系的映像表 （ 或符號表 ） 。 /*串長度 */ int start。 /*定義串類型標(biāo)識符為 STRING*/ char store[MAXSIZE]。 /*堆 store中尚未分配區(qū)間的開始地址指示器變量*/ 堆式動態(tài)存儲的 串賦值 算法 ?該運算把存儲于字符串?dāng)?shù)組 chars中的字符串常量存入堆store中 ， 并為 s建立存儲映像 。 ?其算法描述如下： void StrAssign(s,chars) STRING *s。 {int i,len。 /*為統(tǒng)計字符串常量中的字符個數(shù)初始化 */ while(chars[i]!=’\0’) /*統(tǒng)計 chars中字符個數(shù) */ i++。 堆式動態(tài)存儲的 串賦值 算法 (續(xù) ) if((len1)||(free1+lenMAXSIZE)) printf(“串常量為空串或堆的尚未分配區(qū)間空間不足 \n”)； else {for(i=0。i++) /*逐字符賦值 */ store[free+i]=chars[i]。 /*建立存儲映像 */ slength=len。 /*修改堆中的指示器變量 free的值 */ } } 堆式動態(tài)存儲的 串復(fù)制 算法 ? 該運算把堆中的串 t復(fù)制到 s中去 。 {int i。itlength。 slength=tlength。 free=free+tlength。 堆式動態(tài)存儲的 串聯(lián)接 算法 ?只要分別將 s串和 t串復(fù)制到 store中為 l開辟的存儲區(qū) ， 并建立 l的存儲映像即可完成串聯(lián)接運算 。 {STRING *p。 /*復(fù)制 s到 l中去 */ StrCopy(p,t)。 /*修改 l的存儲映像中的串長 */ } ? 注意 ， 為什么算法中沒有修改 l的開始位置 ？ 又為什么未見修改堆中指示器變量 free的語句 ？ 這是因為第一個串復(fù)制語句已使 l的開始位置到位 ， 而第二個串復(fù)制語句已使 free的值指向尚未分配區(qū)的開始位置 ， 故只需修改串長即可 。 這里給出共享實現(xiàn)算法如下： void SubString(t,s,i,len) /*將 s中第 i個字符開始的 len個字符構(gòu)成的子串送到 t中 */ STRING *t,*s。 {if((i0)||(len0)||(lenslengthi)) printf(“所給子串的位置或長度有錯誤 \n”)。 /*建立子串 t的存儲映像 */ tstart=sstart+i。 ?無論是西文還是漢字 ， 計算機(jī)系統(tǒng)均應(yīng)具有輸入 、 加工處理和輸出的功能 ， 并能在不同的系統(tǒng)之間進(jìn)行信息交換 。 漢字串（續(xù)） ?對于西文來說 ， 由于借助于拼音規(guī)則可只用少量字母拼成文字 ， 因而其機(jī)內(nèi)碼 、 輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)都比較簡單； ?在設(shè)計這些代碼時已盡可能做到相互一致 ， 代碼間的轉(zhuǎn)換也非常簡單 。 ?當(dāng)向計算機(jī)輸入西文信息時 ， 只要在鍵盤上按不同的鍵就可產(chǎn)生不同的輸入代碼 ， 這些輸入碼集可以簡單地等同于機(jī)內(nèi)碼集 。 漢字代碼轉(zhuǎn)換關(guān)系示意圖 采用漢字串標(biāo)識法的七位碼方法 ?以 ASCII碼集或其子集作為 基集 ， 由 兩個或兩相以上 的ASCII字符構(gòu)成一個 漢字機(jī)內(nèi)碼 。 電報碼是以 ASCII字符集的子集 C={0,1,2… 9}為基集 ， 由四個 0~9的數(shù)字字符構(gòu)成一個漢字機(jī)內(nèi)碼 。 如下圖 ?這種存儲方法 ， 對于順序地從前向后逐個處理的運算操作是很適用的 ， 但對于某些隨機(jī)性的操作卻不很方便 。 ?國標(biāo)交換碼規(guī)定由兩個字節(jié)構(gòu)成一個漢字交換碼 ， 每個字節(jié)都用七位 ， 最高位均為 0。 以漢字 “ 大 ” 為例 ， 其機(jī)內(nèi)碼如下圖 。 ?區(qū)位碼中 ， 每個漢字對應(yīng)四個十進(jìn)制數(shù)字 ， 前兩位是區(qū)號共 94個區(qū) ， 每區(qū) 94位 。 ?區(qū)位碼轉(zhuǎn)換為國標(biāo)碼的方法是 ， 先將十進(jìn)制區(qū)位碼轉(zhuǎn)換成十六進(jìn)制 ， 然后在兩個字節(jié)上分別加 20（ 十六進(jìn)制 ） 就得到國標(biāo)碼 。 ?目前應(yīng)用較為廣泛的是采用國標(biāo)碼和區(qū)位碼進(jìn)行代碼標(biāo)識 ，形成兩字節(jié)漢字機(jī)內(nèi)碼 。 漢字區(qū)位碼轉(zhuǎn)換為機(jī)內(nèi)碼的過程 ?以漢字 “ 雹 ” 為例的轉(zhuǎn)換過程如下： 采用漢字標(biāo)識法的多個字節(jié)代碼 ?在每個漢字代碼前增加一個標(biāo)識字節(jié) ， 就形成所謂 多字節(jié)的漢字機(jī)內(nèi)碼 。 但是這種機(jī)內(nèi)碼的編輯性較差 ， 占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)的輔助漢字機(jī)內(nèi)碼 。 前面幾節(jié)討論的串運算都是針對西文串的 ， 其運算原則同樣適用于漢字串 ， 但在使用具體語言定義漢字串的運算時要注意漢字內(nèi)碼雙字節(jié) （ 對雙字節(jié)內(nèi)碼而言 ） 的特點