【正文】 前面幾節(jié)討論的串運(yùn)算都是針對西文串的 ， 其運(yùn)算原則同樣適用于漢字串 ， 但在使用具體語言定義漢字串的運(yùn)算時(shí)要注意漢字內(nèi)碼雙字節(jié) （ 對雙字節(jié)內(nèi)碼而言 ） 的特點(diǎn) 。 漢字區(qū)位碼轉(zhuǎn)換為機(jī)內(nèi)碼的過程 ?以漢字 “ 雹 ” 為例的轉(zhuǎn)換過程如下： 采用漢字標(biāo)識法的多個(gè)字節(jié)代碼 ?在每個(gè)漢字代碼前增加一個(gè)標(biāo)識字節(jié) ， 就形成所謂 多字節(jié)的漢字機(jī)內(nèi)碼 。 ?區(qū)位碼轉(zhuǎn)換為國標(biāo)碼的方法是 ， 先將十進(jìn)制區(qū)位碼轉(zhuǎn)換成十六進(jìn)制 ， 然后在兩個(gè)字節(jié)上分別加 20（ 十六進(jìn)制 ） 就得到國標(biāo)碼 。 以漢字 “ 大 ” 為例 ， 其機(jī)內(nèi)碼如下圖 。 如下圖 ?這種存儲方法 ， 對于順序地從前向后逐個(gè)處理的運(yùn)算操作是很適用的 ， 但對于某些隨機(jī)性的操作卻不很方便 。 漢字代碼轉(zhuǎn)換關(guān)系示意圖 采用漢字串標(biāo)識法的七位碼方法 ?以 ASCII碼集或其子集作為 基集 ， 由 兩個(gè)或兩相以上 的ASCII字符構(gòu)成一個(gè) 漢字機(jī)內(nèi)碼 。 漢字串（續(xù)） ?對于西文來說 ， 由于借助于拼音規(guī)則可只用少量字母拼成文字 ， 因而其機(jī)內(nèi)碼 、 輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)都比較簡單； ?在設(shè)計(jì)這些代碼時(shí)已盡可能做到相互一致 ， 代碼間的轉(zhuǎn)換也非常簡單 。 /*建立子串 t的存儲映像 */ tstart=sstart+i。 這里給出共享實(shí)現(xiàn)算法如下： void SubString(t,s,i,len) /*將 s中第 i個(gè)字符開始的 len個(gè)字符構(gòu)成的子串送到 t中 */ STRING *t,*s。 /*復(fù)制 s到 l中去 */ StrCopy(p,t)。 堆式動態(tài)存儲的 串聯(lián)接 算法 ?只要分別將 s串和 t串復(fù)制到 store中為 l開辟的存儲區(qū) ， 并建立 l的存儲映像即可完成串聯(lián)接運(yùn)算 。 slength=tlength。 {int i。 /*建立存儲映像 */ slength=len。 堆式動態(tài)存儲的 串賦值 算法 (續(xù) ) if((len1)||(free1+lenMAXSIZE)) printf(“串常量為空串或堆的尚未分配區(qū)間空間不足 \n”)； else {for(i=0。 {int i,len。 /*堆 store中尚未分配區(qū)間的開始地址指示器變量*/ 堆式動態(tài)存儲的 串賦值 算法 ?該運(yùn)算把存儲于字符串?dāng)?shù)組 chars中的字符串常量存入堆store中 ， 并為 s建立存儲映像 。 /*串長度 */ int start。 串的堆式動態(tài)存儲分配示意圖 其中： length指示串值序列的長度 ， start指示串值序列在 store中的開始地址 。 堆式動態(tài)存儲的思想 ?應(yīng)用系統(tǒng)在內(nèi)存中開辟一個(gè)容量很大且地址連續(xù)的一片存儲空間 ， 作為存放所有串值的可利用空間即堆空間 。 ?index_KMP算法的最大特點(diǎn)是不需回溯主串的指示器變量 i， 整個(gè)匹配過程只需從頭到尾掃描主串一遍 ，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配 ， 無需回頭重讀 。 } 一種改進(jìn)的模式匹配算法（續(xù)） ?算法 getnext的時(shí)間復(fù)雜度為 O(m)。 /*初始化指示器變量并給 next[0]賦零值 */ while(i tlen) if((j==0)||(tch[i]==tch[j]) {i++。 } } 運(yùn)用算法 index_KMP的匹配過程 求模式串 t的 next函數(shù)值的算法 void getnext(STRING *t, int next[]) /*求模式串 t的 next函數(shù)值并存入數(shù)組 next[]中 */ {int i,j。 j++。 j=0。 改進(jìn)的模式匹配的 KMP算法描述 int index_KMP(s,t) STRING *s, *t。 改進(jìn)的模式匹配的一般化思路 ?對于模式串 t=“t0t1… tm1”和主串 s=“s0s1… sn1”， 當(dāng)匹配過程中 si≠ tj產(chǎn)生失配時(shí) ， 模式串向右滑動多遠(yuǎn)距離 ？ ?或者說失配時(shí) i指示器變量不回溯 ， 主串中第 i個(gè)字符應(yīng)該與模式串中哪個(gè)字符再繼續(xù)比較 ？ ?設(shè)此時(shí)應(yīng)該與模式串中第 k(kj)個(gè)字符比較 ， 則模式 t中前k1個(gè)字符的子串應(yīng)該滿足如下關(guān)系： “ t0t1… tk2”=“sik+1sik+2… si1” ?且不存在大于 k的這樣的關(guān)系式 。 一種改進(jìn)的模式匹配算法（續(xù)） ?回顧前述的匹配過程示例 ， 在第三趟的匹配中當(dāng) i= j=4比較字符不等時(shí) ， 又從 i= j=0重新開始比較 。 ?然而在最壞情況下 ， 即每趟不成功的匹配都發(fā)生在模式串 t中最后一個(gè)字符時(shí) ， 其時(shí)間復(fù)雜度為O(n*m)， 算法效率很低 。 ?依次類推 ， 直到模式 t中每個(gè)字符都和主串 s中的一個(gè)連續(xù)字符序列對應(yīng)相等則匹配成功 ， 函數(shù)值為模式 t中第一個(gè)字符所對應(yīng)的字符在主串 s中的序號； ?若掃描完主串 s后還未找到模式 t 的出現(xiàn)則匹配失敗 ， 函數(shù)值為 1。 else i++。 while((i=nm)amp。 n=StrLength(s)。然而模式匹配不是串的基本運(yùn)算 ， 它可以借用串的基本運(yùn)算來實(shí)現(xiàn) 。 /*為子串 t添加結(jié)束標(biāo)志 */ tlen=len。 （續(xù)） else if((len0)||(lensleni)) printf(“子串的長度 len越過主串錯誤 \n”)。 ?求子串的算法描述如下： void SubString(t,s,i,len) STRING *t,*s。 ?然而 ， 串的聯(lián)接運(yùn)算是滿足結(jié)合律的；在多個(gè)串聯(lián)接時(shí) ， 只要位置次序不變 ， 先聯(lián)接哪兩個(gè)都無所謂 ，最終結(jié)果都是一樣的 。 l[i+j]=’\0’。i++) lch[i]=sch[i]。 {int i,j。 /*初始化數(shù)組下標(biāo)和串長域 len*/ slen=0。 {return slen。 return sch[i]tch[i]。amp。 ?由于串賦值和串復(fù)制在高級程序設(shè)計(jì)語言中是通過賦值語句來完成的 ， 所以在這里只討論其余四種基本運(yùn)算 ， 即串比較 、 求串長 、 串聯(lián)接和求子串運(yùn)算 。 ?這種存儲方式既不浪費(fèi)空間 ， 又使串中每個(gè)字符與惟一地址對應(yīng)方便了運(yùn)算 ， 對于按字節(jié)編址的計(jì)算機(jī)而言是非常合適的 。 ?例如對串 s=“data structure ”的非緊縮存儲如右圖所示 。 這種存儲方式的優(yōu)點(diǎn)是充分地利用了空間 ， 然而四個(gè)字符一個(gè)地址運(yùn)算不太方便 。 用雙引號括起來的字符序列為字符串常量 ， 也可以用宏定義 define來定義字符串常量的標(biāo)識符 ， 如 define CITY shanghai ?對于字符串變量 ， C語言的說明為一維字符型數(shù)組 ， 如 static char C[100]； ?為字符串分配一個(gè)固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為 定長順序存儲分配 。 運(yùn)算的結(jié)果是以串 v替換所有在串 s中出現(xiàn)的和非空串 t相等的不重疊的子串后得到的新串 。 ?StrIndex(s,t)： 子串定位 。 其中 ，1≤ i≤ StrLength(s)+1。 該運(yùn)算要求1≤i≤StrLength(s)+ 1且 0≤len≤StrLength(s) i +1。 把串 t的值緊接著串 s的值之后形成的新串值存入串變量 l中返回 。 若 st返回值 0， 若 s=t返回值 =0，若 st 返回值 0。 把字符串常量 chars的值賦給串變量 s。字符在串中的序號稱作該字符在串中的位置 ， 子串在主串中的位置用子串的第一個(gè)字符在主串中的位置來表示 。 記作 : s=“a1a2… an” (n≥ 0) 其中： s是串名 ， 用雙引號括起來的字符序列是串的值 （ 不含雙引號 ） ； ai（ 1≤i≤n ） 是相應(yīng)程序設(shè)計(jì)語言中允許使用的字符集中的任意字符； n為串中的字符個(gè)數(shù) ， 稱作 串的長度 。 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)組 串 串 ?所謂串 ， 就是我們在高級語言程序設(shè)計(jì)課程中學(xué)習(xí)和使用過的字符串 ， 是大家熟知的概念 。 ?處在下三角的元素 aij， 其前 i1行共有 i*(i1)/2個(gè)元素 ， 在第 i行它處于第 j個(gè)位置 ， 即 aij處于存儲分配區(qū)的第 i*(i1)/2+j個(gè) 。 故有 k=2*( i1)+ j 三對角矩陣的壓縮存儲圖示 壓縮存儲 ?上三角矩陣是指矩陣的主對角線以下的所有元素均為同一常數(shù)c或零的 n階矩陣 。 其非零元素壓縮存儲位置 k與矩陣下標(biāo)的對應(yīng)關(guān)系為 k=i或 k=j， 通過這個(gè)關(guān)系可對矩陣中的非零元素隨機(jī)存取 。 ?所謂 壓縮存儲 ， 是指為多個(gè)值相同的元素只分配一個(gè)元素的存儲空間 ， 對零元素不分配存儲空間 。 ?對于一般情況下的數(shù)組 A[c1‥ d1,c2‥ d2] ?在 行為主序 之下 aij的地址計(jì)算公式為 loc(aij)= loc(a11)+((ic1)*(d2c2+1)+jc2)*e ?在 列為主序 之下 aij的地址計(jì)算公式為 loc(aij)= loc(a11)+((ic2)*(d1c1+1)+ic1)*e 數(shù)組 數(shù)組及其運(yùn)算 數(shù)組的順序存儲結(jié)構(gòu) 特殊矩陣的壓縮存儲 特殊矩陣的壓縮存儲 ?在科學(xué)計(jì)算和工程應(yīng)用中 ， 常常要用到矩陣的概念 。 a11 a12 ┄ a1n a21 a22 ┄ a2n ┄ ┄ am1 am2 ┄ amn 第 1行 第 2行 第 m行 列為主序的優(yōu)先存儲策略 ?列為主序 的優(yōu)先存儲策略是將數(shù)組元素按列優(yōu)先關(guān)系排列 ， 第 j+1列中的元素緊跟在第 j列中元素的后面；同一列中的元素以行下標(biāo)次序排列 。 二維數(shù)組的順序存儲結(jié)構(gòu)舉例 ?二維數(shù)組可以把它看作是由每一行元素作為一個(gè)元素構(gòu)成的一維數(shù)組 （ 行為主序 ） ， ?二維數(shù)組也可以看作是由每一列元素作為一個(gè)元素構(gòu)成的一維數(shù)組 （ 列為主序 ） 。 ?數(shù)組的線性的 、 均勻的結(jié)構(gòu)和計(jì)算機(jī)內(nèi)存單元的一維結(jié)構(gòu) ， 決定了對數(shù)組采用順序存儲結(jié)構(gòu)是最佳選擇 。 ?如在 C語言中 ， int A[8]就說明了一個(gè)一維整型數(shù)組 A；進(jìn)而就可以對 A施加不同的操作 ， 一般方法是利用循環(huán)控制變量值的變化 ， 從下標(biāo)下界到上界之間 （ 或相反次序 ）訪問相應(yīng)的數(shù)組元素 ， 其一般格式是 for(i=0。 也可以說數(shù)組是由數(shù)組元素和下標(biāo)構(gòu)成的有序?qū)Y(jié)構(gòu) ， 結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素都與一組下標(biāo)有關(guān) 。 ?數(shù)組結(jié)構(gòu)的 特點(diǎn) 是： ?數(shù)組元素的個(gè)數(shù)固定 ， 元素間的邏輯關(guān)系由數(shù)組元素的序號 （ 即數(shù)組的下標(biāo) ） 來體現(xiàn) 。 ?另一方面 ， 把抽象數(shù)據(jù)類型的實(shí)現(xiàn)作為私有部分封裝在其實(shí)現(xiàn)模塊內(nèi) ， 讓使用者看不到 ， 也不能直接操作該類型所存儲的數(shù)據(jù) ， 只能通過界面中的服務(wù)來訪問這些數(shù)據(jù) 。 ?需要指