《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第4章

第4章串和數(shù)組4.1串及其運(yùn)算4.2串的存儲(chǔ)結(jié)構(gòu)4.3串運(yùn)算的實(shí)現(xiàn)4.4數(shù)組的定義和運(yùn)算4.5數(shù)組的順序存儲(chǔ)結(jié)構(gòu)4.6矩陣的壓縮存儲(chǔ)

4.1串?及?其?運(yùn)?算

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

例如，有兩個(gè)串A和B，如下所示：

A=“Thisisastring”

B="string"

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

S1=“a0a1…an”

S2="b0b1…bm"

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

2．連接(StrCat)

3．求串長(StrLen)

4．求子串(SubStr)

5．比較串的大小(StrCmp)

6．插入(StrInsert)

7．刪除(StrDelete)

8．子串定位(StrIndex)

9．置換(Replace)

4.2串的存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)

串的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序串。順序串的字符被依次存放在一片連續(xù)的單元中。由于一個(gè)字符只占一個(gè)字節(jié)，因此串中相鄰的字符是順序存放在相鄰的字節(jié)中的。

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

2.鏈?zhǔn)酱鎯?chǔ)

串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈串。鏈串的類型定義如下：圖4-2鏈串示意圖

3.索引存儲(chǔ)

(1)帶長度的索引表。

帶長度的索引表如圖4-3(a)所示。帶長度的索引表結(jié)點(diǎn)類型為圖4-3串的索引存儲(chǔ)

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

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

typedefstruct{

charname[MAXSIZE];

charstadr,enadr;

}enode;

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

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

4.3串運(yùn)算的實(shí)現(xiàn)

4.3.1基本運(yùn)算的實(shí)現(xiàn)

假設(shè)順序串的類型定義如下：

1．串的連接運(yùn)算

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

2.求子串運(yùn)算

設(shè)s為主串，現(xiàn)從s中位置i處字符起，抽取n個(gè)字符構(gòu)成一個(gè)子串后返回。

3.子串定位

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

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

(4-1)

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

(4-2)

例4-1

設(shè)串采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，寫出模式匹配的算法。

用結(jié)點(diǎn)等于1的單鏈表做串的存儲(chǔ)結(jié)構(gòu)時(shí)，實(shí)現(xiàn)樸素的匹配算法較簡單。只要用一個(gè)指針first，記住每一趟匹配開始時(shí)目標(biāo)串起始比較結(jié)點(diǎn)的地址。若某一趟匹配成功，則返回first的值；若整個(gè)匹配失敗，則返回空指針。其具體算法如下：4.3.2改進(jìn)的模式匹配算法

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

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

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

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

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

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

例4-2

計(jì)算T=“abaabcac”的next值。

根據(jù)next函數(shù)的定義，可求得：

j=1next[1]=0;

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

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

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

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

4.4數(shù)組的定義和運(yùn)算

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

也由固定的六個(gè)元素構(gòu)成，每個(gè)元素由值與一對下標(biāo)構(gòu)成。此外，二維數(shù)組也可看做是由兩個(gè)一維數(shù)組與一對下標(biāo)元素定義的一維數(shù)組，這時(shí)每個(gè)數(shù)據(jù)元素受到兩個(gè)下標(biāo)關(guān)系約束，數(shù)據(jù)元素之間在每一個(gè)關(guān)系中仍具有線性特性，而在整個(gè)結(jié)構(gòu)中呈非線性。例如，二維數(shù)組：又可以寫成

或

可以發(fā)現(xiàn)，當(dāng)維數(shù)為1時(shí)，數(shù)組是一種元素?cái)?shù)目固定的線性表；當(dāng)維數(shù)大于1時(shí)，數(shù)組可以看做是線性表的推廣。數(shù)組結(jié)構(gòu)具有的性質(zhì)如下：

(1)數(shù)據(jù)元素?cái)?shù)目固定。一旦說明了一個(gè)數(shù)組結(jié)構(gòu)，其中的元素?cái)?shù)目就不再有增減變化。

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

(3)數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束，并且下標(biāo)有序。

對于數(shù)組，通常只有兩種運(yùn)算：

(1)給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。

(2)給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)的值。

4.5數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

由于數(shù)組一般不做插入和刪除運(yùn)算，也就是說，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)，因此，采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組是自然的

事了。圖4-8二維數(shù)組的兩種存儲(chǔ)方式例如：二維數(shù)組Amn按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)數(shù)據(jù)元素占用d個(gè)存儲(chǔ)單元，則有

(4-3)

式(4-3)的推導(dǎo)思路是：結(jié)構(gòu)中第aij個(gè)元素，其前面已存放了i-1行共(i-1)

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

n+j-1)

d，再以a11的存儲(chǔ)地址作起始位置，即可推得。同理，可推出二維數(shù)組Amn以列為主序的優(yōu)先存儲(chǔ)地址計(jì)算公式如下：

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

m+(i-1)]

d

(4-4)

同樣，三維數(shù)組Amnp按行優(yōu)先順序存儲(chǔ)，其地址計(jì)算公式如下：

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

n

p+(j-1)

p+(k-1)]

d

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

(4-6)

值得注意的是，在C語言中，數(shù)組下標(biāo)的下界是0，因此二維數(shù)組的地址計(jì)算公式為：

(4-7)

4.6矩陣的壓縮存儲(chǔ)

4.6.1特殊矩陣

1.對角矩陣

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

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

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

2.三角矩陣

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

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

(i+1)/2，aij處在第i+1行的第j+1個(gè)元素，則其前面已存放的元素?cái)?shù)目為i

(i+1)/2+j，也就是說，aij應(yīng)是數(shù)組A的第k個(gè)元素，k=i

(i+1)/2+j。A[k]與aij的對應(yīng)關(guān)系為

3.對稱矩陣

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

(n+1)/2，按行優(yōu)先關(guān)系存儲(chǔ)，可得A[k]?與aij的對應(yīng)關(guān)系為

k=i

(i+1)/2+j

0≤k≤n

(n+1)/2，i≥j

當(dāng)i<j時(shí)，aij在上三角矩陣中，由于aij=aji，因此

k=j

(j+1)/2+i

i<j

最后一個(gè)統(tǒng)一的k，i，j的對應(yīng)關(guān)系為

k=i

(i+1)/2+j

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

由于特殊矩陣中非零元素的分布都是有規(guī)律的，因此總可以找到矩陣中的元素與一維數(shù)組下標(biāo)之間的對應(yīng)關(guān)系。還有一類矩陣，其中也含有