第4章 串和數(shù)組12主要內(nèi)容4.1串的基本概念、抽象描述和分類4.2串的模式匹配4.3數(shù)組的概念、特性、遍歷4.4特殊矩陣的壓縮存儲總結(jié)4.13串的基本概念、抽象描述和分類字符串也叫串，是由字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)。串的邏輯結(jié)構(gòu)是線性表，串是一種特殊的線性表，其每個數(shù)據(jù)元素都是一個字符。但是串的操作特點與線性表不同，主要是對子串進行操作，通常采用順序存儲結(jié)構(gòu)存儲。字符串可以表示為str="a0a1…ai…an-1"，其中str為串名，也叫串變量；i為字符ai在串中的位序號；雙引號中的字符序列稱為串值；n為串的長度；當(dāng)n=0時字符串不包含任何字符，為空串；當(dāng)字符串由一個或多個空白字符組成時為空白串?！?.1.1串的基本概念——45——4.1.1串的基本概念——字符串中任意個連續(xù)字符組成的子序列稱為字符串的子串，此字符串為該子串的主串。子串在主串中的位置是指子串在主串中第一次出現(xiàn)時的第一個字符在主串中的位置?？沾侨我獯淖哟?，每個字符串都是其自身的子串，除自身外，主串的其他子串稱為主串的真子串。串的比較規(guī)則和字符的比較規(guī)則有關(guān)，字符的比較規(guī)則由所屬的字符集的編碼決定。兩個串相等是指串長度相同并且各對應(yīng)位置上的字符也相同。兩個串的大小由對應(yīng)位置上的首個不同字符的大小決定，字符比較次序是從頭開始依次向后。當(dāng)兩個串的長度不等而對應(yīng)位置上的字符都相同時較長的串定義為較大。——4.1.2串的抽象數(shù)據(jù)類型描述——字符串是數(shù)據(jù)元素類型為字符的線性表，其抽象數(shù)據(jù)類型描述與線性表相似，又根據(jù)串在實際問題中的應(yīng)用抽象出串的基本操作，可得串的抽象數(shù)據(jù)類型Python語言描述如左邊所示。6——4.1.2串的抽象數(shù)據(jù)類型描述——字符串的抽象數(shù)據(jù)類型

Python抽象類包含了串的主要基本操作，如果要使用這個接口，還需要具體的類來實現(xiàn)。串的Python抽象類的實現(xiàn)方法主要有以下兩種：基于順序存儲的實現(xiàn)，為順序串；基于鏈?zhǔn)酱鎯Φ膶崿F(xiàn)，為鏈串。7——4.1.3順序串——1.順序串的描述：順序串與順序表的邏輯結(jié)構(gòu)相同，存儲結(jié)構(gòu)類似，均可用數(shù)組來存儲數(shù)據(jù)元素。但串具有獨特的不同于線性表的操作，屬于特殊類型的線性表。下圖所示為順序串。8——4.1.3順序串——實現(xiàn)IString抽象類的順序串類的Python語言描述如下：910——4.1.3順序串——2.順序串基本操作的實現(xiàn)順序串有許多基本操作，例如，求子串操作、插入操作、刪除操作、連接操作、比較操作。下面，我們對這幾個操作逐個使用Python實現(xiàn)?！?.1.3順序串——求子串操作subString(begin,end)是返回長度為n的字符串中位序號從

begin到end-1的字符序列，其中

0≤begin≤n-1，begin<end≤n。其主要步驟如下：檢查參數(shù)begin

和end0≤begin≤n-1和begin<end≤n，若不滿足，拋出異常。返回位序號為begin

到end-1

的字符序列。代碼如左圖所示1)求子串操作11——4.1.3順序串——插入操作insert(i,str)是在長度為n的字符串的第i個元素之前插入串str，其中0≤i≤n。其主要步驟如下：判斷參數(shù)

i

是否滿足

0≤i≤n

，若滿足，則拋出異常。重新分配存儲空間為

n+m

，

m插入的字符串str的長度。將第i

個及之后的數(shù)據(jù)元素向后移動m個存儲單元。將str插入到字符串從i開始的位置。2)插入操作12——4.1.3順序串——3)刪除操作刪除操作delete(begin,end)是將長

度為n的字符串的位序號為begin到end-1的元素刪除，其中參數(shù)begin和end滿足0≤begin≤curLen-1和begin<end≤curLen。其主要步驟如下：判斷參數(shù)begin和end是否滿足

0≤begin≤curLen-1和begin<end≤

curLen，若不滿足，則拋出異常。將字符串位序號為

end

的數(shù)據(jù)素及其之后的數(shù)據(jù)元素向前移動到位序號為begin的位置。字符串長度減小end-begin。13——4.1.3順序串——連接操作比較操作4)

concat(str)

是將串

str

插入到串的尾部，此時調(diào)用insert(curLen,str)即可實現(xiàn)。5)

比較操作

compareTo(str)

是將符串與串str按照字典序進行比較。若當(dāng)前字符串較大，返回1；若相等，返回0。若當(dāng)前字符串較小，返回-1。其主要步驟如下：確定需要比較的字符的個數(shù)

n兩個字符串長度的較小值。從下標(biāo)0至n-1依次進行比較。14——4.1.3順序串——【例4.1】編寫一個程序，完成構(gòu)造串、判斷串是否為空、返回串的長度、求子串等操作。示例答案：15——4.1.4鏈串——鏈串的描述：鏈串采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，可以采用單鏈表存儲串值。鏈串由一系列大小相同的結(jié)點組成，每個結(jié)點用數(shù)據(jù)域存放字符，指針域存放指向下一個結(jié)點的指針。與線性表不同的是每個結(jié)點的數(shù)據(jù)域可以是一個字符或者多個字符。若每個結(jié)點的數(shù)據(jù)域為一個字符，這種鏈表稱為單字符鏈表；若每個結(jié)點的數(shù)據(jù)域為多個字符，則稱為塊鏈表。在塊鏈表中每個結(jié)點的數(shù)據(jù)域不一定被字符占滿，可通過添加空字符或者其他非串值字符來簡化操作。如圖所示為兩種不同類型的鏈串。16——4.1.4鏈串——鏈串的優(yōu)缺點：在串的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，單字符鏈表的插入、刪除操作較為簡單，但存儲效率低。塊鏈表雖然存儲效率較高但插入、刪除操作需要移動字符，較為復(fù)雜。此外，與順序串相比，鏈串需要從頭部開始遍歷才能訪問某個位置的元素。所以用戶在應(yīng)用中需要根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。174.218串的模式匹配——4.2串的模式匹配——串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式

串的過程，主要的模式匹配

算法有Brute

Force算法和

KMP算法。19——4.2.1

Brute

Force算法——BruteForce算法從主串的第一個字符開始和模式串的第一個字符進行比較，若相等，則繼續(xù)比較后續(xù)字符；否則從主串的第二個字符開始重新和模式串進行比較。依此類推，直到模式串的每個字符依次與主串的字符相等，匹配成功。20——4.2.1

Brute

Force算法——Brute

Force算法的實現(xiàn)簡單，但效率非常低。m為模式串的長度，n為主串的長度。最好情況：第一次匹配即成功，比較次數(shù)為模式串的長度m，時間復(fù)雜度為O(m)。最壞情況：每次匹配比較至模式串的最后一個字符，并且比較了目標(biāo)串中所有長度為m的子串，此時的時間復(fù)雜度為O(m×n)。缺點：每次匹配沒有利用前一次匹配的比較結(jié)果，使算法中存在較多的重復(fù)比較，降低了算法的效率；如果利用部分字符匹配的結(jié)果，可將算法的效率提高。因此提出了KMP算法，在下一節(jié)進行介紹。2122——4.2.2

KMP算法——1.算法分析設(shè)主串為s="ababcabdabcabca"、模式串為p="abcabc"，指針i、j分別指示主串和模式串所比較字符的位序號。當(dāng)某次匹配不成功時有si≠pj，并且si-jsi-j+1…si-1=p0p1…pj-1。此時需要尋找前綴子串p0p1…pk-1=pj-kpj-k+1…pj-1，其中

0<k<j，這時候即滿足si-ksi-k+1…si-1=p0p1…pk-1，下一次匹配可直接比較si和pk。此外，為了減少比較次數(shù)，k應(yīng)取最大值，即p0p1…pk-1應(yīng)為滿足此性質(zhì)的最長前綴子串。若k不存在，下一次匹配則直接比較si和p0。23——4.2.2

KMP算法——K值的計算通過前面的分析已知，每次模式串開始比較的位置（即k的值）僅與模式串本身有關(guān)。一般用next[j]來表示pj對應(yīng)的k值。初始時可定義next[0]=-1，next[1]=0。設(shè)next[j]=k，則p0p1…pk-1=pj-kpj-k+1…pj-1，k為滿足等式的最大值。計算next[j+1]的值。若pk=pj，則存在p0p1…pk-1pk=pj-kpj-k+1…pj-1pj，此時next[j+1]=k+1。若pk≠pj，可以把計算next[j]的值的問題看成新的模式匹配過程，主串為p，模式串為p的前綴子串。出現(xiàn)不匹配，應(yīng)將模式串的比較位置變?yōu)閗′=next[k]，若pj=p_(k^')，則

next[j+1]=k′+1=next[k]+1，否則繼續(xù)執(zhí)行步驟(2)，直到pj=pk，或者當(dāng)k=0并且pj≠pk時next[j+1]=0?！?.2.2

KMP算法——2.K值的計算代碼實現(xiàn)：24——4.2.2

KMP算法——3.KMP算法步驟KMP算法的主要步驟如下。計算模式串的next[]函數(shù)值。i為主串的比較字符位序號，

j為模式串的比較字符位序號。當(dāng)字符相等時，i、j分別加1后繼續(xù)比較；否則i的值不變，

j=next[j]，繼續(xù)比較。重復(fù)步驟(2)，直到j(luò)等于模式串的長度時匹配成功，否則匹配失敗。設(shè)主串的長度為n、模式串的長度為m，求next[]的時間復(fù)雜度為O(m)。在KMP中，因主串的下標(biāo)不需要回退，比較次數(shù)最多為n-m+1，所以KMP算法的時間復(fù)雜度為O(m+n)。2526——4.2.2

KMP算法——3.KMP算法步驟小測試：請計算

str=“abcababc”的next[j]的值參考答案：當(dāng)j=0時，next[0]=-1;當(dāng)j=1時，next[1]=0;當(dāng)j=2時，next[2]=0;當(dāng)j=3時，next[3]=0;當(dāng)j=4時，next[4]=1;當(dāng)j=5時，next[5]=2;當(dāng)j=6時，next[6]=1;當(dāng)j=7時，next[7]=2。4.327數(shù)組的概念、特性和遍歷數(shù)組是n個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲在地址連續(xù)的存儲單元中,是順序存儲的隨機存儲結(jié)構(gòu)。數(shù)組元素在數(shù)組中的位置稱為數(shù)組元素的下標(biāo)，用戶通過下標(biāo)可以訪問相應(yīng)的數(shù)組

元素。數(shù)組下標(biāo)的個數(shù)是數(shù)組的維數(shù)，具有一個下標(biāo)的數(shù)組叫一維數(shù)組，具有兩個

下標(biāo)的數(shù)組叫二維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴展。二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組。下圖所示為二維數(shù)組的矩陣表示?！?.3.1數(shù)組的基本概念——28二維數(shù)組中的每個數(shù)據(jù)元素ai,j都受到兩個關(guān)系的約束，即行關(guān)系和列關(guān)系。ai.,j+1是ai,j在行關(guān)系中的后繼元素；ai+1,j是ai,j在列關(guān)系中的后繼元素。因為二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組，所以二維數(shù)組也可看成線性表，即

A=(a0,a1,…,an-1)，其中每個數(shù)據(jù)元素ai是一個列向量的線性表，即ai=(a0i,a1i,…,am-1i);或者表述為A=(a0,a1,…,am-1)，其中每個數(shù)據(jù)元素ai是一個行向量的線性表，即ai=(a0i,a1i,…,an-1i)。其中，每個元素同時屬于兩個線性表，第i行的線性表和第j列的線性表，具體可以分析如下：a0,0是起點，沒有前驅(qū)元素；am-1,n-1是終點，沒有后繼元素。邊界元素ai,0和a0,j（1≤j<n,1≤i<m）只有一個前驅(qū)元素；ai,n-1和am-1,j（0≤j<n-1,1≤i<m-1）只有一個后繼元素。ai,j（1≤j<n-1,1≤i<m-1）有兩個前驅(qū)元素和兩個后繼元素?！?.3.1數(shù)組的基本概念——29數(shù)組元素被存放在一組地址連續(xù)的存儲單元里，并且每個數(shù)據(jù)元素的大小相同，故只要已知首地址和每個數(shù)據(jù)元素占用的內(nèi)存單元大小即可求出數(shù)組中任意數(shù)據(jù)元素的存儲地址。對于一維數(shù)組A[n]，數(shù)據(jù)元素的存儲地址為Loc(i)=Loc(0)+i×L(0≤i<n)，其中Loc(i)是第i個元素的存儲地址，Loc(0)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。對于二維數(shù)組，采用行優(yōu)先順序進行存儲，即先存儲數(shù)組的第一行，再依次存儲其他各行。對于一個n×m的數(shù)組A[n][m]，數(shù)組元素的存儲地址為Loc(i,j)=Loc(0,0)+(i×m+j)×L，其中Loc(i,j)是第i行第j列的數(shù)組元素的存儲地址，Loc(0,0)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。——4.3.2數(shù)組的特性——30將計算數(shù)組元素的存儲位置的公式推廣到一般情況，可得n維數(shù)組A[m1][m2]…[mn]的數(shù)據(jù)元素的存儲位置：在n維數(shù)組中，計算數(shù)組中數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O(1)，n維數(shù)組是一種隨機存儲結(jié)構(gòu)。——4.3.2數(shù)組的特性——31對二維數(shù)組進行遍歷操作有兩種次序，即行主序和列主序。行主序：以行序為主要次序，按行序遞增訪問數(shù)組的每行，同一行按列序遞增訪問數(shù)組元素。列主序：以列序為主要次序，按列序遞增訪問數(shù)組的每列，同一列按行序遞增訪問數(shù)組元素?！?.3.3數(shù)組的遍歷——32——4.3.3數(shù)組的遍歷——舉例：請你設(shè)計一個算法，求二維數(shù)組A[n,n]的兩條對角線元素之和。答案示例：334.434特殊矩陣的壓縮存儲在科學(xué)技術(shù)和工程計算的許多領(lǐng)域，矩陣是數(shù)值分析問題研究的對象。特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣，例如對稱矩陣、三角矩陣和對角矩陣。數(shù)據(jù)壓縮技術(shù)是計算機軟件領(lǐng)域研究的一個重要問題，圖像、音頻、視頻等多媒體信息都需要進行數(shù)據(jù)壓縮存儲。本節(jié)將以特殊矩陣為例介紹矩陣的壓縮存儲。矩陣采用二維數(shù)組進行存儲，至少占用m×n個存儲單元。當(dāng)矩陣的階數(shù)很大時，矩陣所占用的存儲空間巨大，因此需要研究矩陣的壓縮存儲問題，根據(jù)不同矩陣的特點設(shè)計不同的壓縮存儲方法，節(jié)省存儲空間，同時保證采用壓縮存儲的矩陣仍然能夠正確地進行各種矩陣運算。——4.4特殊矩陣的壓縮存儲——35常用的矩陣壓縮存儲方法主要有以下兩種：對于零元素分布有規(guī)律的特殊矩陣，采用線性壓縮或三角形的二維數(shù)組，只存儲有規(guī)律的部分元素。對于零元素分布沒有規(guī)律的特殊矩陣，只存儲非零元素。下面，我們分別介紹一下不同類型的矩陣壓縮存儲方式——4.4特殊矩陣的壓縮存儲——36三角矩陣包括上三角矩陣和下三角矩陣。假如是一個n階矩陣，由n（n+1）/2個元素組成。當(dāng)i<j時矩陣中的數(shù)據(jù)元素滿足=0，矩陣為下三角矩陣；當(dāng)i>j時，矩陣中的數(shù)據(jù)元素滿足=0，矩陣為上三角矩陣。三角矩陣中具有近一半的分布有規(guī)律的零元素，所以三角矩陣采取只存儲主對角線以及上/下三角部分的矩陣元素的壓縮方法，主要分為以下兩種：線性壓縮存儲使用三角形的二維數(shù)組壓縮存儲——4.4.1三角矩陣的壓縮存儲——371.

線性壓縮存儲將下三角矩陣的主對角線及其以下元素按行主序順序壓縮成線性存儲結(jié)構(gòu)，存儲元素的個數(shù)為n（n+1）/2，其中元素的存儲地址如下：其中，注意L為數(shù)據(jù)元素所占據(jù)存儲空間的字節(jié)數(shù)。計算各數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O（1）,三角矩陣的線性壓縮存儲結(jié)構(gòu)是隨機存儲結(jié)構(gòu)。——4.4.1三角矩陣的壓縮存儲——382.使用三角形的二維數(shù)組壓縮存儲三角形的二維數(shù)組實際上是一種動態(tài)數(shù)組結(jié)構(gòu)，第i行一維數(shù)組的長度為i+1，存儲在mat[i][j]中，如圖4.4所示。計算各數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O（1）,此壓縮存儲結(jié)構(gòu)是隨機存儲結(jié)構(gòu)?！?.4.1三角矩陣的壓縮存儲——39n階對稱矩陣是指一個n階矩陣中的數(shù)據(jù)元素滿足ai,j=aj,i。對稱矩陣在進行壓縮存儲時只存儲主對角線和上/下部分數(shù)據(jù)元素，即將對稱矩陣的主對角線及其上/下部分數(shù)據(jù)元素按行主序順序壓縮成線性存儲，占用n（n+1）/2個存儲單元,矩陣元素的線性壓縮存儲地址為：——4.4.2對稱矩陣的壓縮存儲——40如果一個矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域，則稱該矩陣為對角矩陣。它是一個n階矩陣，除了主對角線上的元素，其科元素均為0，則是主對角矩陣；除了主對角線上及主對角線上下各一個元素外，其余元素均為0，為三對角矩陣。在壓縮存儲對角矩陣時，只存儲主對角線及其兩側(cè)部分的元素。如壓縮存儲主對角矩陣，將主對角元素順序壓縮成線性存儲，存儲元素個數(shù)為n，矩陣數(shù)據(jù)元素的線性壓縮存儲地址為：——4.4.3對角矩陣的壓縮存儲——41稀疏矩陣是指矩陣中的非零元素個數(shù)遠遠小于矩陣元素個數(shù)并且非零元素的分布沒有規(guī)律的矩陣。設(shè)矩陣中有t個非零元素，非零元素占元素總數(shù)的比例稱為矩陣的稀疏因子，通常稀疏因子小于0.05的矩陣稱為稀疏矩陣。一般使用以下幾種方法進行稀疏矩陣的壓縮存儲。稀疏矩陣的非零元素三元組稀疏矩陣的十字鏈表存儲——4.4.4稀疏矩陣的壓縮存儲——421.

稀疏矩陣的非零元素三元組稀疏矩陣的壓縮存儲原則是只存儲矩陣中的非零元素，而僅存儲非零元素是不夠的，必須存儲該元素在矩陣中的位置。矩陣元素的行號、列號和元素值稱為該元素的三

元組。在Python語言中稀疏矩陣的三元組表示的結(jié)點結(jié)構(gòu)定義如下：——4.4.4稀疏矩陣的壓縮存儲——431.

稀疏矩陣的非零元素三元組稀疏矩陣的三元組順序表類的定義如下：——4.4.4稀疏矩陣的壓縮存儲——441.

稀疏矩陣的非零元素三元組初始化三元組順序表是按先行序后列序的原則掃描稀疏矩陣，并把非零元素插入到順序表中，其算法如下?！?.4.4稀疏矩陣的壓縮存儲——452.稀疏矩陣的十字鏈表存儲當(dāng)稀疏矩陣中非零元素的位置或個數(shù)經(jīng)常發(fā)生變化時不宜采用三元組順序表存儲結(jié)構(gòu)，而應(yīng)該采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。十字鏈表是稀疏矩陣的另一種存儲結(jié)構(gòu)，在十字鏈表中稀疏矩陣的非零元素用一個結(jié)點來表示，每個結(jié)點由5個域組成。row域存放該元素的行號，column域存放該元素的列號，value域存放該元素的值，right域存放與該元素同行的下一個非零元素結(jié)點的指針，down域存放與該元素同列的下一個非零元素結(jié)點的指針。每個非零數(shù)據(jù)元素結(jié)點既是某個行鏈表中的一個結(jié)點，也是某個列鏈表中的結(jié)點，整個稀疏矩陣構(gòu)成了一個十字交叉的鏈表，這樣的鏈表就稱為十字鏈表。——4.4.4稀疏矩陣的壓縮存儲——462.稀疏矩陣的十字鏈表存儲在Python語言中可以將稀疏矩陣的