第4章串和數組4.1串及其運算4.2串的存儲結構4.3串運算的實現4.4數組的定義和運算4.5數組的順序存儲結構4.6矩陣的壓縮存儲

4.1串?及?其?運?算

串(String)是由零個或多個字符組成的有限序列，一般記為S?=?"a0a1…an-1"。其中，S是串名；用兩個雙引號括起的字符序列是串值；ai可以是字母、數字或其他字符。串中所包含的字符個數稱為串的長度。長度為零的串稱為空串，它不包含任何字符。在C語言中，串一般使用不可顯示的字符'\0'作為串的結束符。

例如，有兩個串A和B，如下所示：

A=“Thisisastring”

B="string"

則串A和串B的長度分別為16和6；B是A的子串，B在A中的位置是10(位置下標從0開始計數，下同)。下面給出串的抽象數據類型的定義：串的基本運算有九種。下面為了介紹敘述方便，假設：

S1=“a0a1…an”

S2="b0b1…bm"

其中，0≤m≤n，在串S1的長度需要擴充的時候，需要保證S1具有足夠的存儲空間。1．賦值(StrCopy)

2．連接(StrCat)

3．求串長(StrLen)

4．求子串(SubStr)

5．比較串的大小(StrCmp)

6．插入(StrInsert)

7．刪除(StrDelete)

8．子串定位(StrIndex)

9．置換(Replace)

4.2串的存儲結構

1.順序存儲

串的順序存儲結構簡稱為順序串。順序串的字符被依次存放在一片連續的單元中。由于一個字符只占一個字節，因此串中相鄰的字符是順序存放在相鄰的字節中的。

順序串可用以下類型描述：圖4-1順序串示意圖

2.鏈式存儲

串的鏈式存儲結構簡稱為鏈串。鏈串的類型定義如下：圖4-2鏈串示意圖

3.索引存儲

(1)帶長度的索引表。

帶長度的索引表如圖4-3(a)所示。帶長度的索引表結點類型為圖4-3串的索引存儲

(2)帶末指針的索引表。

用一個指向串值存放的末地址的指針enadr來代替長度length，如圖4-3(b)所示。帶末指針的索引表結點類型定義為

typedefstruct{

charname[MAXSIZE];

charstadr,enadr;

}enode;

(3)帶特征位的索引表。

當串值只需要一個指針域的空間就能存放時，可將串值放在stadr域中。這樣既節約了存儲空間，又可以提高查找速度，但是，這時要增加一個特征位tag來指出stadr域中是指針還是串值，如圖4-3(c)所示。帶特征位的索引表結點類型定義為圖4-4在索引存儲下串的動態分配示意圖

4.3串運算的實現

4.3.1基本運算的實現

假設順序串的類型定義如下：

1．串的連接運算

將兩個串dest和src首尾相接連成一個串，其中dest在前；src在后。若連接成功，函數返回dest的首地址；若失敗則返回NULL。

2.求子串運算

設s為主串，現從s中位置i處字符起，抽取n個字符構成一個子串后返回。

3.子串定位

子串定位運算又稱為串的模式匹配，是串處理中最重要的運算之一。圖4-5樸素的模式匹配過程下面分析算法的時間復雜度。

在最好的情況下，每趟不成功的匹配都發生在t的第一個字符與s中相應字符的比較。設從s的第i個位置開始與t模式匹配成功的概率為pi，則在前i-1趟匹配中字符共比較了i-1次。若第i趟成功的匹配中字符比較次數為m，則總的比較次數為i-1+m。對于成功匹配的s起始位置是1到n-m+1，又設這n-m+1個起始位置上匹配成功的概率都是相等的，則最好情況下匹配成功時的平均比較次數為

(4-1)

即最好情況下算法的平均時間復雜度為O(n+m)。在最壞的情況下，每一趟不成功的匹配都發生在模式串t的最后一個字符與s中相應字符的比較不相等，則新一趟的起始位置為i-m+2。若設第i趟匹配成功，則前i-1趟不成功的匹配中，每趟都比較了m次，總共比較了i×m次。因此最壞情況下的平均比較次數為

(4-2)

例4-1

設串采用鏈式存儲結構，寫出模式匹配的算法。

用結點等于1的單鏈表做串的存儲結構時，實現樸素的匹配算法較簡單。只要用一個指針first，記住每一趟匹配開始時目標串起始比較結點的地址。若某一趟匹配成功，則返回first的值；若整個匹配失敗，則返回空指針。其具體算法如下：4.3.2改進的模式匹配算法

改進的模式匹配算法是D.K.Knuth、V.R.Pratt和J.H.Morris同時發現的，因此，人們稱它為克努特-莫里斯-普拉特操作(簡稱KMP算法)。這種算法可以在O(n+m)的時間數量級上完成串的模式匹配操作，它的改進之處在于：每當一趟匹配過程中出現字符比較不相等時，不需回溯i值，而是利用已經得到的“部分匹配”的結果將模式向右“滑動”盡可能遠的一段距離后，繼續進行比較。現在討論一般的情況。設計一個無回溯的匹配算法，關鍵在于匹配過程中，一旦si與tj比較不相等，存在有下列條件

時能立即確定右移的位數和繼續(無回溯)比較的字符，也就是說，能確定T中哪一個字符應和S中的si進行比較。將這個字符記為tk，顯然有k＜j，且對于不同的j值，k值也不相同。對next[j]性質進行分析的步驟如下：

(1)?next[j]是一個整數，并且滿足0＜next[j]<j。

(2)匹配過程中，一旦有si與tj比較不相等，根據next[j]的意義，用tk(k?=?next[j]?≠?0)與si繼續比較。也可以看做將T右移j-next[j]位，如圖4-6所示。圖4-6t右移j-next[j]位示意圖

(3)為使T的右移不丟失任何匹配成功的可能，對于同時存在多個滿足(2)的k值應取其中的最大值，如圖4-7所示，這樣移動的位數j-k最小。例如，S="aaaabbb"，T="aaab"，當s4=a與t4=b發生比較不相等時，k可取1、2和3，但只有k取3時才能保證不丟失成功的可能匹配。圖4-7k取最大值

(4)如果在t1t2…tj-1的首尾不存在相同的子串，即子串長度為零，則k=1，表示一旦有tj≠si，則用t1與si進行比較。特殊情況，當j=1時，若t1=si比較不相等，則不能再像上面那樣進行右移了，可將t1與si+1進行比較后進入新一趟的匹配，故next[j]=0。若tj與si比較不相等，則可用(k=next[j])tk與si比較；如果已知tj=tk，則相比較必有tk≠si；此時可根據next[j]的意義再取k'=?next[k]?≠?0，用tk'與si繼續比較。所以當tj=tk時，next[j]?=?next[k]。

例4-2

計算T=“abaabcac”的next值。

根據next函數的定義，可求得：

j=1next[1]=0;

j=2沒有首尾相等的子串，next[2]=1;

j=3同j=2，next[3]=1

j=4有首尾相等的子串“a”，則有next[4]=2

依次類推，最終的結果如表4-1所示。

4.4數組的定義和運算

一維數組[a0,a1,…,an-1]，由固定的n個元素構成，每個元素除具有值以外，還帶有一個下標值，以確定該元素在表中的位置。二維數組

也由固定的六個元素構成，每個元素由值與一對下標構成。此外，二維數組也可看做是由兩個一維數組與一對下標元素定義的一維數組，這時每個數據元素受到兩個下標關系約束，數據元素之間在每一個關系中仍具有線性特性，而在整個結構中呈非線性。例如，二維數組：又可以寫成

或

可以發現，當維數為1時，數組是一種元素數目固定的線性表；當維數大于1時，數組可以看做是線性表的推廣。數組結構具有的性質如下：

(1)數據元素數目固定。一旦說明了一個數組結構，其中的元素數目就不再有增減變化。

(2)數據元素具有相同的類型。

(3)數據元素的下標關系具有上下界的約束，并且下標有序。

對于數組，通常只有兩種運算：

(1)給定一組下標，存取相應的數據元素。

(2)給定一組下標，修改相應數據元素中的某個數據項的值。

4.5數組的順序存儲結構

由于數組一般不做插入和刪除運算，也就是說，一旦建立了數組，則結構中的數據元素個數和元素之間的關系就不再發生變動，因此，采用順序存儲結構表示數組是自然的

事了。圖4-8二維數組的兩種存儲方式例如：二維數組Amn按行優先順序存儲在內存中，假設每個數據元素占用d個存儲單元，則有

(4-3)

式(4-3)的推導思路是：結構中第aij個元素，其前面已存放了i-1行共(i-1)

n個元素，在第i行中其前面已存放了j-1個元素，因而總共占用的空間為((i-1)

n+j-1)

d，再以a11的存儲地址作起始位置，即可推得。同理，可推出二維數組Amn以列為主序的優先存儲地址計算公式如下：

Loc(aij)=Loc(a11)+[(j-1)

m+(i-1)]

d

(4-4)

同樣，三維數組Amnp按行優先順序存儲，其地址計算公式如下：

Loc(aijk)=Loc(a111)+[(i-1)

n

p+(j-1)

p+(k-1)]

d

(4-5)上述討論均是假設數組的下界是1，而一般的二維數組是A[c1…d1，c2…d2]，這里c1，c2不一定是1。aij前一共有i-c1行，一共有d2-c2+1列，故i-c1行共有(i-c1)*(d2-c2+1)個元素，第i行上aij前一共有j-c2個元素，因此，aij的地址計算公式為

(4-6)

值得注意的是，在C語言中，數組下標的下界是0，因此二維數組的地址計算公式為：

(4-7)

4.6矩陣的壓縮存儲

4.6.1特殊矩陣

1.對角矩陣

在對角矩陣中，所有非零元素都集中在以主對角線為中心的帶狀區域中，即除了主對角線上和主對角線相鄰近的上、下方以外，其余元素均為0。圖4-9所示就是一個三對角矩陣。

現在考慮最簡單的一種，即只在主對角線上含有非零元素的對角矩陣，如圖4-10所示。圖4-9三對角矩陣

圖4-10最簡單的對角矩陣

2.三角矩陣

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指矩陣的下三角(不包含對角線)中的元素均為常數(或0)的n階矩陣；下三角矩陣與之相反。圖4-11給出了兩種三角矩陣的表示形式。圖4-11三角矩陣下面找出數組元素A[k]?與aij的關系。

在下三角矩陣中，對于aij元素，前面已存放了i行，元素的總數為i

(i+1)/2，aij處在第i+1行的第j+1個元素，則其前面已存放的元素數目為i

(i+1)/2+j，也就是說，aij應是數組A的第k個元素，k=i

(i+1)/2+j。A[k]與aij的對應關系為

3.對稱矩陣

在n階方陣A中，若A中的元素滿足aij=aji(0≤i，j≤n-1)，則稱A是對稱矩陣。圖4-12給出了一個六階對稱矩陣。圖4-12六階對稱矩陣由于對稱矩陣中的元素關于對角線對稱，因此在存儲時只需存儲矩陣中上三角或下三角中的元素，使得對稱的元素共享一個存儲空間。假如我們存儲下三角中的元素，則元素的總數為n

(n+1)/2，按行優先關系存儲，可得A[k]?與aij的對應關系為

k=i

(i+1)/2+j

0≤k≤n

(n+1)/2，i≥j

當i<j時，aij在上三角矩陣中，由于aij=aji，因此

k=j

(j+1)/2+i

i<j

最后一個統一的k，i，j的對應關系為

k=i

(i+1)/2+j

其中，i=max(i，j)；j=min(i，j)。4.6.2稀疏矩陣

由于特殊矩陣中非零元素的分布都是有規律的，因此總可以找到矩陣中的元素與一維數組下標之間的對應關系。還有一類矩陣，其中也含有