數(shù)據(jù)結(jié)構(gòu)-Python語(yǔ)言描述課件第4章

1、第4章 串和數(shù)組第4章 串和數(shù)組主要內(nèi)容4.1 串的基本概念、抽象描述和分類4.2 串的模式匹配4.3 數(shù)組的概念、特性、遍歷4.4 特殊矩陣的壓縮存儲(chǔ)總結(jié)主要內(nèi)容4.1 串的基本概念、抽象描述和分類4.1串的基本概念、抽象描述和分類4.1串的基本概念、抽象描述和分類字符串也叫串，是由字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)。串的邏輯結(jié)構(gòu)是線性表，串是一種特殊的線性表，其每個(gè)數(shù)據(jù)元素都是一個(gè)字符。但是串的操作特點(diǎn)與線性表不同，主要是對(duì)子串進(jìn)行操作，通常采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。字符串可以表示為str=a0a1aian-1，其中str為串名，也叫串變量； i為字符ai在串中的位序號(hào)； 雙引號(hào)中的字

2、符序列稱為串值； n為串的長(zhǎng)度； 當(dāng)n=0時(shí)字符串不包含任何字符，為空串； 當(dāng)字符串由一個(gè)或多個(gè)空白字符組成時(shí)為空白串。4.1.1 串的基本概念字符串也叫串，是由字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)4.1.1 串的基本概念字符串中任意個(gè)連續(xù)字符組成的子序列稱為字符串的子串，此字符串為該子串的主串。子串在主串中的位置是指子串在主串中第一次出現(xiàn)時(shí)的第一個(gè)字符在主串中的位置。空串是任意串的子串，每個(gè)字符串都是其自身的子串，除自身外，主串的其他子串稱為主串的真子串。串的比較規(guī)則和字符的比較規(guī)則有關(guān)，字符的比較規(guī)則由所屬的字符集的編碼決定。兩個(gè)串相等是指串長(zhǎng)度相同并且各對(duì)應(yīng)位置上的字符也相同。兩個(gè)

3、串的大小由對(duì)應(yīng)位置上的首個(gè)不同字符的大小決定，字符比較次序是從頭開(kāi)始依次向后。當(dāng)兩個(gè)串的長(zhǎng)度不等而對(duì)應(yīng)位置上的字符都相同時(shí)較長(zhǎng)的串定義為較大。4.1.1 串的基本概念字符串中任意個(gè)連續(xù)字符組成的4.1.2 串的抽象數(shù)據(jù)類型描述字符串是數(shù)據(jù)元素類型為字符的線性表，其抽象數(shù)據(jù)類型描述與線性表相似，又根據(jù)串在實(shí)際問(wèn)題中的應(yīng)用抽象出串的基本操作，可得串的抽象數(shù)據(jù)類型Python語(yǔ)言描述如左邊所示。 4.1.2 串的抽象數(shù)據(jù)類型描述字符串是數(shù)據(jù)元素類型4.1.2 串的抽象數(shù)據(jù)類型描述字符串的抽象數(shù)據(jù)類型Python抽象類包含了串的主要基本操作，如果要使用這個(gè)接口，還需要具體的類來(lái)實(shí)現(xiàn)。串的Python抽

4、象類的實(shí)現(xiàn)方法主要有以下兩種： (1) 基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序串； (2) 基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈串。4.1.2 串的抽象數(shù)據(jù)類型描述字符串的抽象數(shù)據(jù)類型4.1.3 順序串1. 順序串的描述：順序串與順序表的邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)類似，均可用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)元素。但串具有獨(dú)特的不同于線性表的操作，屬于特殊類型的線性表。下圖所示為順序串。4.1.3 順序串1. 順序串的描述：4.1.3 順序串實(shí)現(xiàn)IString抽象類的順序串類的Python語(yǔ)言描述如下： 4.1.3 順序串實(shí)現(xiàn)IString抽象類的順序串類4.1.3 順序串 2. 順序串基本操作的實(shí)現(xiàn) 順序串有許多基本操作，例如，求子串操作

5、、插入操作、刪除操作、連接操作、比較操作。 下面，我們對(duì)這幾個(gè)操作逐個(gè)使用Python實(shí)現(xiàn)。4.1.3 順序串 2. 順序串基本操作的實(shí)現(xiàn)4.1.3 順序串求子串操作subString(begin,end)是返回長(zhǎng)度為n的字符串中位序號(hào)從begin到end-1的字符序列，其中0beginn-1，beginendn。其主要步驟如下： (1) 檢查參數(shù)begin和end是否滿足0beginn-1和beginendn，若不滿足，拋出異常。(2) 返回位序號(hào)為begin到end-1的字符序列。代碼如左圖所示1) 求子串操作4.1.3 順序串求子串操作subString(be4.1.3 順序串插入操作i

6、nsert(i,str)是在長(zhǎng)度為n的字符串的第i個(gè)元素之前插入串str，其中0in。其主要步驟如下： (1) 判斷參數(shù)i是否滿足0in，若不滿足，則拋出異常。(2) 重新分配存儲(chǔ)空間為n+m，m為插入的字符串str的長(zhǎng)度。(3) 將第i個(gè)及之后的數(shù)據(jù)元素向后移動(dòng)m個(gè)存儲(chǔ)單元。(4) 將str插入到字符串從i開(kāi)始的位置。2) 插入操作4.1.3 順序串插入操作insert(i,str)4.1.3 順序串刪除操作delete(begin,end)是將長(zhǎng)度為n的字符串的位序號(hào)為begin到end-1的元素刪除，其中參數(shù)begin和end滿足0begincurLen-1和beginendcurLen

7、。其主要步驟如下： (1) 判斷參數(shù)begin和end是否滿足0begincurLen-1和begin end curLen，若不滿足，則拋出異常。(2) 將字符串位序號(hào)為end的數(shù)據(jù)元素及其之后的數(shù)據(jù)元素向前移動(dòng)到位序號(hào)為begin的位置。(3) 字符串長(zhǎng)度減小end-begin。3) 刪除操作4.1.3 順序串刪除操作delete(begin,4.1.3 順序串4) concat(str)是將串str插入到字符串的尾部，此時(shí)調(diào)用insert(curLen,str)即可實(shí)現(xiàn)。5) 比較操作compareTo(str)是將字符串與串str按照字典序進(jìn)行比較。若當(dāng)前字符串較大，返回1； 若相等，

8、返回0。若當(dāng)前字符串較小，返回-1。其主要步驟如下： (1) 確定需要比較的字符的個(gè)數(shù)n為兩個(gè)字符串長(zhǎng)度的較小值。(2) 從下標(biāo)0至n-1依次進(jìn)行比較。4) 連接操作5) 比較操作4.1.3 順序串4) concat(str)是將串4.1.3 順序串【例4.1】編寫一個(gè)程序，完成構(gòu)造串、判斷串是否為空、返回串的長(zhǎng)度、求子串等操作。示例答案：4.1.3 順序串【例4.1】編寫一個(gè)程序，完成構(gòu)造4.1.4 鏈串鏈串的描述：鏈串采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類似，可以采用單鏈表存儲(chǔ)串值。鏈串由一系列大小相同的結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)用數(shù)據(jù)域存放字符，指針域存放指向下一個(gè)結(jié)點(diǎn)的指針。與線性表不同的

9、是每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域可以是一個(gè)字符或者多個(gè)字符。若每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)橐粋€(gè)字符，這種鏈表稱為單字符鏈表； 若每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)槎鄠€(gè)字符，則稱為塊鏈表。在塊鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域不一定被字符占滿，可通過(guò)添加空字符或者其他非串值字符來(lái)簡(jiǎn)化操作。如圖所示為兩種不同類型的鏈串。4.1.4 鏈串鏈串的描述：4.1.4 鏈串鏈串的優(yōu)缺點(diǎn)：在串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，單字符鏈表的插入、刪除操作較為簡(jiǎn)單，但存儲(chǔ)效率低。塊鏈表雖然存儲(chǔ)效率較高但插入、刪除操作需要移動(dòng)字符，較為復(fù)雜。此外，與順序串相比，鏈串需要從頭部開(kāi)始遍歷才能訪問(wèn)某個(gè)位置的元素。所以用戶在應(yīng)用中需要根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。4.1.4 鏈串鏈串的優(yōu)

10、缺點(diǎn)：4.2串的模式匹配4.2串的模式匹配4.2 串的模式匹配串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式串的過(guò)程，主要的模式匹配算法有Brute Force算法和KMP算法。4.2 串的模式匹配串的模式匹配也叫查找定位，指的是4.2.1 Brute Force 算法Brute Force算法從主串的第一個(gè)字符開(kāi)始和模式串的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較后續(xù)字符； 否則從主串的第二個(gè)字符開(kāi)始重新和模式串進(jìn)行比較。依此類推，直到模式串的每個(gè)字符依次與主串的字符相等，匹配成功。4.2.1 Brute Force 算法Brute 4.2.1 Brute Force 算法Brute Fo

11、rce算法的實(shí)現(xiàn)簡(jiǎn)單，但效率非常低。m為模式串的長(zhǎng)度，n為主串的長(zhǎng)度。（1） 最好情況： 第一次匹配即成功，比較次數(shù)為模式串的長(zhǎng)度m，時(shí)間復(fù)雜度為O(m)。（2） 最壞情況： 每次匹配比較至模式串的最后一個(gè)字符，并且比較了目標(biāo)串中所有長(zhǎng)度為m的子串，此時(shí)的時(shí)間復(fù)雜度為O(mn)。缺點(diǎn)：每次匹配沒(méi)有利用前一次匹配的比較結(jié)果，使算法中存在較多的重復(fù)比較，降低了算法的效率； 如果利用部分字符匹配的結(jié)果，可將算法的效率提高。因此提出了KMP算法，在下一節(jié)進(jìn)行介紹。4.2.1 Brute Force 算法Brute 4.2.2 KMP 算法1. 算法分析設(shè)主串為s=aba bcabdabcabca、模式

12、串為p=abcabc，指針i、j分別指示主串和模式串所比較字符的位序號(hào)。當(dāng)某次匹配不成功時(shí)有sipj，并且si-jsi-j+1si-1=p0p1pj-1。此時(shí)需要尋找前綴子串p0p1pk-1=pj-kpj-k+1pj-1，其中0kj，這時(shí)候即滿足si-ksi-k+1si-1=p0p1pk-1，下一次匹配可直接比較si和pk。此外，為了減少比較次數(shù)，k應(yīng)取最大值，即p0p1pk-1應(yīng)為滿足此性質(zhì)的最長(zhǎng)前綴子串。若k不存在，下一次匹配則直接比較si和p0。4.2.2 KMP 算法1. 算法分析4.2.2 KMP 算法2. K值的計(jì)算通過(guò)前面的分析已知，每次模式串開(kāi)始比較的位置（即k的值）僅與模式串

13、本身有關(guān)。一般用nextj來(lái)表示pj對(duì)應(yīng)的k值。初始時(shí)可定義next0=-1，next1=0。設(shè)nextj=k，則p0p1pk-1=pj-kpj-k+1pj-1，k為滿足等式的最大值。計(jì)算nextj+1的值。(1) 若pk=pj，則存在p0p1pk-1pk=pj-kpj-k+1pj-1pj，此時(shí)nextj+1=k+1。(2) 若pkpj，可以把計(jì)算nextj的值的問(wèn)題看成新的模式匹配過(guò)程，主串為p，模式串為p的前綴子串。出現(xiàn)不匹配，應(yīng)將模式串的比較位置變?yōu)閗=nextk，若pj=p_(k )，則nextj+1=k+1=nextk+1，否則繼續(xù)執(zhí)行步驟(2)，直到pj=pk，或者當(dāng)k=0并且pj

14、pk時(shí)nextj+1=0。4.2.2 KMP 算法2. K值的計(jì)算4.2.2 KMP 算法2. K值的計(jì)算代碼實(shí)現(xiàn)：4.2.2 KMP 算法2. K值的計(jì)算4.2.2 KMP 算法3. KMP算法步驟KMP算法的主要步驟如下。 (1) 計(jì)算模式串的next函數(shù)值。(2) i為主串的比較字符位序號(hào)，j為模式串的比較字符位序號(hào)。當(dāng)字符相等時(shí)，i、j分別加1后繼續(xù)比較； 否則i的值不變，j=nextj，繼續(xù)比較。(3) 重復(fù)步驟(2)，直到j(luò)等于模式串的長(zhǎng)度時(shí)匹配成功，否則匹配失敗。設(shè)主串的長(zhǎng)度為n、模式串的長(zhǎng)度為m，求next的時(shí)間復(fù)雜度為O(m)。在KMP中，因主串的下標(biāo)不需要回退，比較次數(shù)最多

15、為n-m+1，所以KMP算法的時(shí)間復(fù)雜度為O(m+n)。4.2.2 KMP 算法3. KMP算法步驟KMP算4.2.2 KMP 算法3. KMP算法步驟小測(cè)試：請(qǐng)計(jì)算 str = “abcababc”的nextj 的值參考答案：當(dāng)j=0時(shí)，next0=-1;當(dāng)j=1時(shí)，next1=0;當(dāng)j=2時(shí)，next2=0;當(dāng)j=3時(shí)，next3=0;當(dāng)j=4時(shí)，next4=1;當(dāng)j=5時(shí)，next5=2;當(dāng)j=6時(shí)，next6=1;當(dāng)j=7時(shí)，next7=2。4.2.2 KMP 算法3. KMP算法步驟小測(cè)試：4.3數(shù)組的概念、特性和遍歷4.3數(shù)組的概念、特性和遍歷數(shù)組是n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)

16、成的集合，數(shù)組元素按某種次序存儲(chǔ)在地址連續(xù)的存儲(chǔ)單元中,是順序存儲(chǔ)的隨機(jī)存儲(chǔ)結(jié)構(gòu)。數(shù)組元素在數(shù)組中的位置稱為數(shù)組元素的下標(biāo)，用戶通過(guò)下標(biāo)可以訪問(wèn)相應(yīng)的數(shù)組元素。數(shù)組下標(biāo)的個(gè)數(shù)是數(shù)組的維數(shù)，具有一個(gè)下標(biāo)的數(shù)組叫一維數(shù)組，具有兩個(gè)下標(biāo)的數(shù)組叫二維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組。下圖所示為二維數(shù)組的矩陣表示。4.3.1 數(shù)組的基本概念數(shù)組是n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某二維數(shù)組中的每個(gè)數(shù)據(jù)元素ai,j都受到兩個(gè)關(guān)系的約束，即行關(guān)系和列關(guān)系。ai.,j+1是ai,j在行關(guān)系中的后繼元素； ai+1,j是ai,j

17、在列關(guān)系中的后繼元素。因?yàn)槎S數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組，所以二維數(shù)組也可看成線性表，即A=(a0,a1,an-1)，其中每個(gè)數(shù)據(jù)元素ai是一個(gè)列向量的線性表，即ai=(a0i,a1i,am-1i);或者表述為A=(a0,a1,am-1)，其中每個(gè)數(shù)據(jù)元素ai是一個(gè)行向量的線性表，即ai=(a0i,a1i,an-1i)。其中，每個(gè)元素同時(shí)屬于兩個(gè)線性表，第i行的線性表和第j列的線性表，具體可以分析如下： （1） a0,0是起點(diǎn)，沒(méi)有前驅(qū)元素； am-1,n-1是終點(diǎn)，沒(méi)有后繼元素。（2） 邊界元素ai,0和a0,j（1jn,1im）只有一個(gè)前驅(qū)元素； ai,n-1和am-1,j（0j

18、n-1,1im-1）只有一個(gè)后繼元素。（3） ai,j（1jn-1,1im-1）有兩個(gè)前驅(qū)元素和兩個(gè)后繼元素。4.3.1 數(shù)組的基本概念二維數(shù)組中的每個(gè)數(shù)據(jù)元素ai,j都受到兩個(gè)關(guān)系的約束，即行關(guān)數(shù)組元素被存放在一組地址連續(xù)的存儲(chǔ)單元里，并且每個(gè)數(shù)據(jù)元素的大小相同，故只要已知首地址和每個(gè)數(shù)據(jù)元素占用的內(nèi)存單元大小即可求出數(shù)組中任意數(shù)據(jù)元素的存儲(chǔ)地址。對(duì)于一維數(shù)組An，數(shù)據(jù)元素的存儲(chǔ)地址為L(zhǎng)oc(i)=Loc(0)+iL(0in)，其中Loc(i)是第i個(gè)元素的存儲(chǔ)地址，Loc(0)是數(shù)組的首地址，L是每個(gè)數(shù)據(jù)元素占用的字節(jié)數(shù)。對(duì)于二維數(shù)組，采用行優(yōu)先順序進(jìn)行存儲(chǔ)，即先存儲(chǔ)數(shù)組的第一行，再依次存

19、儲(chǔ)其他各行。對(duì)于一個(gè)nm的數(shù)組Anm，數(shù)組元素的存儲(chǔ)地址為L(zhǎng)oc(i,j)=Loc(0,0)+(im+j)L，其中Loc(i,j)是第i行第j列的數(shù)組元素的存儲(chǔ)地址，Loc(0,0)是數(shù)組的首地址，L是每個(gè)數(shù)據(jù)元素占用的字節(jié)數(shù)。4.3.2 數(shù)組的特性數(shù)組元素被存放在一組地址連續(xù)的存儲(chǔ)單元里，并且每個(gè)數(shù)據(jù)元素的將計(jì)算數(shù)組元素的存儲(chǔ)位置的公式推廣到一般情況，可得n維數(shù)組Am1m2mn的數(shù)據(jù)元素的存儲(chǔ)位置：在n維數(shù)組中，計(jì)算數(shù)組中數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O(1)，n維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。4.3.2 數(shù)組的特性將計(jì)算數(shù)組元素的存儲(chǔ)位置的公式推廣到一般情況，可得n維數(shù)組A對(duì)二維數(shù)組進(jìn)行遍歷操

20、作有兩種次序，即行主序和列主序。（1） 行主序： 以行序?yàn)橹饕涡?，按行序遞增訪問(wèn)數(shù)組的每行，同一行按列序遞增訪問(wèn)數(shù)組元素。（2） 列主序： 以列序?yàn)橹饕涡?，按列序遞增訪問(wèn)數(shù)組的每列，同一列按行序遞增訪問(wèn)數(shù)組元素。4.3.3 數(shù)組的遍歷對(duì)二維數(shù)組進(jìn)行遍歷操作有兩種次序，即行主序和列主序。4.舉例：請(qǐng)你設(shè)計(jì)一個(gè)算法，求二維數(shù)組An,n的兩條對(duì)角線元素之和。4.3.3 數(shù)組的遍歷答案示例：舉例：4.3.3 數(shù)組的遍歷答案示例：4.4特殊矩陣的壓縮存儲(chǔ)4.4特殊矩陣的壓縮存儲(chǔ)在科學(xué)技術(shù)和工程計(jì)算的許多領(lǐng)域，矩陣是數(shù)值分析問(wèn)題研究的對(duì)象。特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一

21、定規(guī)律的矩陣，例如對(duì)稱矩陣、三角矩陣和對(duì)角矩陣。數(shù)據(jù)壓縮技術(shù)是計(jì)算機(jī)軟件領(lǐng)域研究的一個(gè)重要問(wèn)題，圖像、音頻、視頻等多媒體信息都需要進(jìn)行數(shù)據(jù)壓縮存儲(chǔ)。本節(jié)將以特殊矩陣為例介紹矩陣的壓縮存儲(chǔ)。矩陣采用二維數(shù)組進(jìn)行存儲(chǔ)，至少占用mn個(gè)存儲(chǔ)單元。當(dāng)矩陣的階數(shù)很大時(shí)，矩陣所占用的存儲(chǔ)空間巨大，因此需要研究矩陣的壓縮存儲(chǔ)問(wèn)題，根據(jù)不同矩陣的特點(diǎn)設(shè)計(jì)不同的壓縮存儲(chǔ)方法，節(jié)省存儲(chǔ)空間，同時(shí)保證采用壓縮存儲(chǔ)的矩陣仍然能夠正確地進(jìn)行各種矩陣運(yùn)算。4.4 特殊矩陣的壓縮存儲(chǔ)在科學(xué)技術(shù)和工程計(jì)算的許多領(lǐng)域，矩陣是數(shù)值分析問(wèn)題研究的對(duì)象常用的矩陣壓縮存儲(chǔ)方法主要有以下兩種： (1) 對(duì)于零元素分布有規(guī)律的特殊矩陣，采用

22、線性壓縮或三角形的二維數(shù)組，只存儲(chǔ)有規(guī)律的部分元素。(2) 對(duì)于零元素分布沒(méi)有規(guī)律的特殊矩陣，只存儲(chǔ)非零元素。下面，我們分別介紹一下不同類型的矩陣壓縮存儲(chǔ)方式4.4 特殊矩陣的壓縮存儲(chǔ)常用的矩陣壓縮存儲(chǔ)方法主要有以下兩種： 4.4 特殊矩陣三角矩陣包括上三角矩陣和下三角矩陣。假如是一個(gè)n階矩陣，由n（n+1）/2個(gè)元素組成。當(dāng)ij時(shí)，矩陣中的數(shù)據(jù)元素滿足=0，矩陣為上三角矩陣。三角矩陣中具有近一半的分布有規(guī)律的零元素，所以三角矩陣采取只存儲(chǔ)主對(duì)角線以及上/下三角部分的矩陣元素的壓縮方法，主要分為以下兩種：線性壓縮存儲(chǔ)2. 使用三角形的二維數(shù)組壓縮存儲(chǔ)4.4.1 三角矩陣的壓縮存儲(chǔ)三角矩陣包括上

23、三角矩陣和下三角矩陣。假如是一個(gè)n階矩陣，由n線性壓縮存儲(chǔ)將下三角矩陣的主對(duì)角線及其以下元素按行主序順序壓縮成線性存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)元素的個(gè)數(shù)為n（n+1）/2，其中元素的存儲(chǔ)地址如下： 其中，注意L為數(shù)據(jù)元素所占據(jù)存儲(chǔ)空間的字節(jié)數(shù)。計(jì)算各數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O（1）,三角矩陣的線性壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存儲(chǔ)結(jié)構(gòu)。4.4.1 三角矩陣的壓縮存儲(chǔ)線性壓縮存儲(chǔ)4.4.1 三角矩陣的壓縮存儲(chǔ)2.使用三角形的二維數(shù)組壓縮存儲(chǔ)三角形的二維數(shù)組實(shí)際上是一種動(dòng)態(tài)數(shù)組結(jié)構(gòu)，第i行一維數(shù)組的長(zhǎng)度為i+1，存儲(chǔ)在matij中，如圖4.4所示。計(jì)算各數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O（1）,此壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)

24、存儲(chǔ)結(jié)構(gòu)。4.4.1 三角矩陣的壓縮存儲(chǔ)2.使用三角形的二維數(shù)組壓縮存儲(chǔ)4.4.1 三角矩陣的壓n階對(duì)稱矩陣是指一個(gè)n階矩陣中的數(shù)據(jù)元素滿足ai,j=aj,i。對(duì)稱矩陣在進(jìn)行壓縮存儲(chǔ)時(shí)只存儲(chǔ)主對(duì)角線和上/下部分?jǐn)?shù)據(jù)元素，即將對(duì)稱矩陣的主對(duì)角線及其上/下部分?jǐn)?shù)據(jù)元素按行主序順序壓縮成線性存儲(chǔ)，占用n（n+1）/2個(gè)存儲(chǔ)單元,矩陣元素的線性壓縮存儲(chǔ)地址為： 4.4.2 對(duì)稱矩陣的壓縮存儲(chǔ)n階對(duì)稱矩陣是指一個(gè)n階矩陣中的數(shù)據(jù)元素滿足ai,j=aj,如果一個(gè)矩陣的所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域，則稱該矩陣為對(duì)角矩陣。它是一個(gè)n階矩陣，除了主對(duì)角線上的元素，其科元素均為0，則是主對(duì)角矩陣

25、； 除了主對(duì)角線上及主對(duì)角線上下各一個(gè)元素外，其余元素均為0，為三對(duì)角矩陣。在壓縮存儲(chǔ)對(duì)角矩陣時(shí)，只存儲(chǔ)主對(duì)角線及其兩側(cè)部分的元素。如壓縮存儲(chǔ)主對(duì)角矩陣，將主對(duì)角元素順序壓縮成線性存儲(chǔ)，存儲(chǔ)元素個(gè)數(shù)為n，矩陣數(shù)據(jù)元素的線性壓縮存儲(chǔ)地址為： 4.4.3 對(duì)角矩陣的壓縮存儲(chǔ)如果一個(gè)矩陣的所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域稀疏矩陣是指矩陣中的非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)并且非零元素的分布沒(méi)有規(guī)律的矩陣。設(shè)矩陣中有t個(gè)非零元素，非零元素占元素總數(shù)的比例稱為矩陣的稀疏因子，通常稀疏因子小于0.05的矩陣稱為稀疏矩陣。一般使用以下幾種方法進(jìn)行稀疏矩陣的壓縮存儲(chǔ)。稀疏矩陣的非零元素三元組稀疏

26、矩陣的十字鏈表存儲(chǔ)4.4.4 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣是指矩陣中的非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)并且非零稀疏矩陣的非零元素三元組稀疏矩陣的壓縮存儲(chǔ)原則是只存儲(chǔ)矩陣中的非零元素，而僅存儲(chǔ)非零元素是不夠的，必須存儲(chǔ)該元素在矩陣中的位置。矩陣元素的行號(hào)、列號(hào)和元素值稱為該元素的三元組。在Python語(yǔ)言中稀疏矩陣的三元組表示的結(jié)點(diǎn)結(jié)構(gòu)定義如下：4.4.4 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組4.4.4 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組稀疏矩陣的三元組順序表類的定義如下：4.4.4 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組4.4.4 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組初始

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