第4章 數(shù)組與矩陣(修訂).ppt

1、2020/8/3,第5章,1,第4章 數(shù)組,前幾章討論的線性結(jié)構(gòu)中的數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素的值是不再分解的。本章討論一種特殊的線性表，其特殊性在于，表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。,2020/8/3,第5章,2,一維數(shù)組（Array）是n(n1)個(gè)相同類型數(shù)據(jù)元素a0,a1,an-1構(gòu)成的有限序列，且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中。由此可見，一維數(shù)組可以看成是一個(gè)線性表或一個(gè)向量，一維數(shù)組的定義類似于采用順序存儲(chǔ)的線性表。 對(duì)于一維數(shù)組，一旦a0的存儲(chǔ)地址Loc(a0)確定，若每個(gè)數(shù)據(jù)元素占用L個(gè)存儲(chǔ)單元，則任一數(shù)據(jù)元素ai的存儲(chǔ)地址Loc(ai)可由以下公式求出：

2、Loc(ai)= Loc(a0)+i*L 一維數(shù)組中任一數(shù)據(jù)元素的存儲(chǔ)地址可直接計(jì)算得到，因此，一維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。,4.1 數(shù)組,2020/8/3,第5章,3,二維數(shù)組可以看成是一維數(shù)組的推廣。設(shè)A是一個(gè)有m行、n列的二維數(shù)組，則A可以表示為：,2020/8/3,第5章,4,顯然，在二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)直接前驅(qū)和兩個(gè)直接后繼（邊界除外）。 可以看成是由m個(gè)行向量組成的向量，也可以看成是n個(gè)列向量組成的向量。 行向量形式：把每一行看成是一個(gè)數(shù)據(jù)元素,2020/8/3,第5章,5,列向量形式：把每一列看成是一個(gè)數(shù)據(jù)元

3、素 二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組。,2020/8/3,第5章,6,三、多維數(shù)組 同理，三維數(shù)組中的數(shù)據(jù)元素（邊界除外）最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼。可以把三維以上的數(shù)組稱為多維數(shù)組，多維數(shù)組中的數(shù)據(jù)元素（邊界除外）可有多個(gè)直接前驅(qū)和多個(gè)直接后繼，故多維數(shù)組是一種非線性結(jié)構(gòu)。 n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。,2020/8/3,第5章,7,數(shù)組具有以下性質(zhì)： 1.數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定，一旦定義了一個(gè)數(shù)組，其數(shù)據(jù)元素?cái)?shù)目不再有增減變化； 2.數(shù)組中的每個(gè)數(shù)據(jù)元素具有相同的數(shù)據(jù)

4、類型； 3. 數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組唯一的下標(biāo)相對(duì)應(yīng)； 4. 數(shù)組是一種隨機(jī)存取結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。,2020/8/3,第5章,8,數(shù)組的順序表示和實(shí)現(xiàn),由于數(shù)組一般不作插入或刪除操作，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。因此，適合采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。本章中，僅重點(diǎn)討論二維數(shù)組的存儲(chǔ)，三維及三維以上的數(shù)組可以作類似分析。 由于存儲(chǔ)單元是一維的結(jié)構(gòu)，而二維數(shù)組是個(gè)多維的結(jié)構(gòu)，則用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問題。 兩種順序存儲(chǔ)方式： 以行序?yàn)橹餍颍ㄐ袃?yōu)先順序） 以列序?yàn)橹餍颍袃?yōu)先順序）,2020/8/3,第5章

5、,9,一、以行序?yàn)橹餍颍?1存放規(guī)則 行優(yōu)先順序也稱為低下標(biāo)優(yōu)先或右邊下標(biāo)優(yōu)先于左邊下標(biāo)。具體實(shí)現(xiàn)時(shí)，按行號(hào)從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類推 BASIC語言、PASCAL語言、C/C+語言都是按行優(yōu)先順序存放的。 例如，對(duì)二維數(shù)組Amn ，可用如下形式存放到內(nèi)存：a00，a01,a0n-1，a10，a11，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即二維數(shù)組按行優(yōu)先存放到內(nèi)存后，變成了一個(gè)線性序列（線性表）。,2020/8/3,第5章,10,2地址計(jì)算 假設(shè)二維數(shù)組Amn每個(gè)元素占L個(gè)字節(jié)，元素aij的存儲(chǔ)地址應(yīng)為第

6、一個(gè)元素的地址加上排在aij前面的元素所占用的單元數(shù)，而aij 的前面有i行(0i-1)共in個(gè)元素，而第i行上aij前面又有j個(gè)元素，故aij的前面一共有in+j個(gè)元素，設(shè)a00的地址為L(zhǎng)OC(a00)，則aij的地址為： LOC(aij)=LOC(a00)+（in+j）L 同理，三維數(shù)組Amnp按低下標(biāo)優(yōu)先存放的地址計(jì)算公式為： LOC(aijk)=LOC(a000)+(inp+jp+k)L,2020/8/3,第5章,11,二、以列序?yàn)橹餍颍?1存放規(guī)則 列優(yōu)先順序也稱為高下標(biāo)優(yōu)先或左邊下標(biāo)優(yōu)先于右邊下標(biāo)。具體實(shí)現(xiàn)時(shí)，按列號(hào)從小到大的順序，先將第一列中元素全部存放好，再存放第二列元素，第三

7、列元素，依次類推 在FORTRAN語言中，數(shù)組是按列優(yōu)先順序存放的。例如，二維數(shù)組Amn，可以按如下的形式存放到內(nèi)存：a00， a10， am-10， a01，a11， ， am-1 1， a0 m-1，a1m-1，.， am-1 n-1。 即二維數(shù)組按列優(yōu)先存放到內(nèi)存后，也變成了一個(gè)線性序列（線性表）。,2020/8/3,第5章,12,2地址計(jì)算 與行優(yōu)先存放類似，若知道第一個(gè)元素的內(nèi)存地址，則同樣可以求得按列優(yōu)存放的某一元素aij的地址。 對(duì)二維數(shù)組有： LOC(aij)=LOC(a00)+(jm+i)L 對(duì)三維數(shù)組Amnp按高下標(biāo)優(yōu)先存放的地址計(jì)算公式為： LOC(aijk)=LOC(a

8、000)+(kmn+jm+i)L,2020/8/3,第5章,13,例1：對(duì)C語言中的二維數(shù)組 A54，計(jì)算： 1)數(shù)組A中的元素?cái)?shù)目； 2)若數(shù)組A的起始地址為2000，且每個(gè)數(shù)組元素長(zhǎng)度為32位（即4個(gè)字節(jié)），求數(shù)組元素A32的內(nèi)存地址。 解： 1）該數(shù)組的元素?cái)?shù)目共有5*4=20個(gè)。 2）由于C語言中數(shù)組的行、列下界均為0，該數(shù)組行下標(biāo)為04，列下標(biāo)為03，并采用行序?yàn)橹餍虻拇鎯?chǔ)方式，有： LOC(a32)=LOC(a00)+(i*n+j)*L =2000+(3*4+2)*4 =2056,2020/8/3,第5章,14,例2：二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)

9、j從0到9，從首地址SA開始存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為 。 A. SA+141 B. SA+180 C. SA+222 D. SA+225,解：LOC(a47)=LOC(a00)+(j *m+ i)*L = SA+(7*8+4)*3 = SA+180,2020/8/3,第5章,15,例3：對(duì)于二維數(shù)組A0.20.5，當(dāng)按行優(yōu)先順序存儲(chǔ)時(shí)，元素A23是第幾個(gè)元素？當(dāng)按列優(yōu)先順序存儲(chǔ)時(shí)，元素A24是第幾個(gè)元素？,解：m=3,n=6 當(dāng)按行優(yōu)先順序存儲(chǔ)時(shí)，元素A23的序號(hào)為： 1+i*n+j=1+2*6+3=16 其中1表示元素A00 當(dāng)按列優(yōu)先順序存儲(chǔ)時(shí)，元素A24的

10、序號(hào)為： 1+j*m+i=1+4*3+2=15,2020/8/3,第5章,16,4.2 矩陣的壓縮存儲(chǔ),矩陣是很多科學(xué)與工程計(jì)算問題中研究的數(shù)學(xué)對(duì)象。在此，我們感興趣的不是矩陣本身，而是如何存儲(chǔ)矩陣的元從而使矩陣的各種運(yùn)算能有效地進(jìn)行。 通常，用高級(jí)語言編制程序時(shí)，都是用二維數(shù)組來存儲(chǔ)矩陣元。 然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中有許多值相同的元素或者是零元素。有時(shí)為了節(jié)省存儲(chǔ)空間，可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)是指：為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間。 假若值相同的元素或者零元素在矩陣中的分布有一定規(guī)律，則我們稱此類矩陣為特殊矩陣；反之，稱為

11、稀疏矩陣。下面分別討論它們的壓縮存儲(chǔ)。,2020/8/3,第5章,17,特殊矩陣 1. 對(duì)稱矩陣 若一個(gè)n階方陣A中元素滿足下列條件： aij=aji 其中 0 i, jn-1 則稱A為對(duì)稱矩陣。,2020/8/3,第5章,18,為節(jié)約存儲(chǔ)空間，只存儲(chǔ)對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。即為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。不失一般性，我們可以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對(duì)角線)中的元素。 假設(shè)以一維數(shù)組sa0.n(n+1)/2-1作為n階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu)，則sak和矩陣元aij之間存在著一一對(duì)應(yīng)的關(guān)系。,2020

12、/8/3,第5章,19,若ij，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）共有1+2+i=i*(i+1)/2個(gè)元素，在第i行上，aij之前恰有j個(gè)元素（即ai0,ai1,ai,j-1），因此aij之前共有k個(gè)元素： k=i*(i+1)/2+j ij, 0kn(n+1)/2-1,若ij，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到： k=j*(j+1)/2+i ij，0 kn(n+1)/2-1 矩陣A中任意元素aij和sak之間存在如下關(guān)：,2020/8/3,第5章,20,2.三角矩陣 以主對(duì)角線劃分，三角矩陣有上三角矩陣和下三角

13、矩陣兩種。 所謂上（下）三角矩陣是指矩陣的主對(duì)角線的下（上）方（不包括對(duì)角線）的元素均為常數(shù)c或零的n階矩陣。 如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。,2020/8/3,第5章,21,除了和對(duì)稱矩陣一樣只存儲(chǔ)其上（下）三角中的元之外，再加一個(gè)存儲(chǔ)常數(shù)c的存儲(chǔ)空間即可。三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n*(n+1)/2個(gè)，這樣共存儲(chǔ)了n*(n+1)/2+1個(gè)元素，因此，三角矩陣可壓縮存儲(chǔ)到向量sa0.n(n+1)/2中，其中c存放在向量的最后一個(gè)分量中。 對(duì)于下三角矩陣,任意元素aij與sak 的對(duì)應(yīng)關(guān)系和對(duì)稱矩陣情形類似：,2020/8/3,第5章,22,對(duì)于上

14、三角矩陣，存儲(chǔ)思想與下三角矩陣類似，按行優(yōu)先順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常量。對(duì)于第0行，存儲(chǔ)n個(gè)元素，第1行存儲(chǔ)n-1個(gè)元素，第p行存儲(chǔ)(n-p)個(gè)元素，aij的前面有i行，則有： (n-0)+(n-1) +(n-(i-1)=i*(2n-i+1)/2 個(gè)元素，而在當(dāng)前行中，aij 前面有j-i個(gè)元素；所以，aij之前共有 i*(2n-i+1)/2+(j-i)個(gè)元素，因此它在sak中的下標(biāo)為：k=i*(2n-i+1)/2+j-i。 綜上所述，元素aij與sak的對(duì)應(yīng)關(guān)系為：,2020/8/3,第5章,23,3.對(duì)角矩陣 若一個(gè)n階方陣A所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域

15、中，區(qū)域外的值全為0，則稱為對(duì)角矩陣。其主對(duì)角線上下方各有b條次對(duì)角線，稱b為矩陣半帶寬，（2b+1）為矩陣的帶寬。對(duì)于半帶寬為b（0b(n-1)/2）的對(duì)角矩陣，其|i-j|=b的元素aij不為零，其余元素為零。下圖為半帶寬為b的對(duì)角矩陣和b=1的三對(duì)角矩陣 ：,2020/8/3,第5章,24,對(duì)于b=1的三對(duì)角矩陣A，只需將其非零元素aij存儲(chǔ)到一維數(shù)組sak中。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。 對(duì)于不在第0行的非零元素aij來說， 在它前面存儲(chǔ)了矩陣的前i行元素，這些元素的總數(shù)為2+3(i-1)。 若aij是本行中需存儲(chǔ)的第1個(gè)

16、元素，則k=2+3(i-1)=3i-1，此時(shí)，j=i-1，即k=2i+i-1=2i+j。 若ai,j是本行中需存儲(chǔ)的第2個(gè)元素，則k=2+3(i-1)+1=3i，此時(shí)，j=i，即k=2i+i=2i+j。 若aij是本行中需存儲(chǔ)的第3個(gè)元素，則k=2+3(i-1)+2=3i+1，此時(shí)，j=i+1，即k=2i+i+1=2i+j。 歸納起來有k=2i+j。,2020/8/3,第5章,25,對(duì)稱矩陣、三角矩陣和對(duì)角矩陣的壓縮存儲(chǔ)方法，是把有一定分布規(guī)律的值相同的元素（包括0）壓縮存儲(chǔ)到一個(gè)向量中。并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，這樣的壓縮存儲(chǔ)只需在算法中按公式就可求出矩陣元素的存儲(chǔ)地址

17、，即可實(shí)現(xiàn)隨機(jī)存取。,2020/8/3,第5章,26,4.3稀疏矩陣 非零元較零元少，且分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。 假設(shè)在m*n的矩陣中，有t個(gè)元素不為零。令=t/(m*n),稱為矩陣的稀疏因子。通常認(rèn)為0.05時(shí)稱為稀疏矩陣。 如何進(jìn)行稀疏矩陣的壓縮存儲(chǔ)呢？ 按照壓縮存儲(chǔ)的概念，只存儲(chǔ)稀疏矩陣的非零元。因此，除了存儲(chǔ)非零元的值以外，還必須同時(shí)記下它所在行和列的位置（i,j)。反之，一個(gè)三元組（i, j, aij)唯一確定了矩陣A的一個(gè)非零元。由此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。,2020/8/3,第5章,27,例如，下列三元組表 (1，2，12),(1，3，9)

18、,(3，1，-3), (3，6，14), (4，3，24) , (5，2，18),（6，1，15), (6，4，-7) 加上(6，7)這一對(duì)行、列值便可作為下圖中矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。,2020/8/3,第5章,28,一、三元組順序表 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，則可得稀疏矩陣的一種壓縮存儲(chǔ)方式，稱為三元組順序表。 /稀疏矩陣的三元組順序表存儲(chǔ)表示 #define MAXSIZE 12500 /非零元個(gè)數(shù)的最大值 typedef struct int i，j; ElemType e； Triple； typedef struc

19、t Triple dataMAXSIZE+1；/ 非零元三元組表，data0未用， int mu，nu，tu；/矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) TSMatrix；,data域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?2020/8/3,第5章,29,稀疏矩陣的轉(zhuǎn)置運(yùn)算 轉(zhuǎn)置運(yùn)算是一種最簡(jiǎn)單的矩陣運(yùn)算。對(duì)于一個(gè)m*n的矩陣M，它的轉(zhuǎn)置矩陣T是一個(gè)n*m的矩陣，且aij=bij，1in，1jm。,2020/8/3,第5章,30,顯然，一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣。假設(shè)a和b是TSMatrix型的變量，分別表示矩陣M和T。那么，如何由a得到b呢?,0 1 2 3 4 5 6 7 8,0 1 2 3 4 5 6 7 8,a.data b.data,2020/8/3,第5章,31,從分析a和b之間的差異可見，只要做到： (1)將矩陣的行列值相互交換； (2)將每個(gè)三元組中的i和j相互調(diào)換； (3)重排三元組之間的次序 便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。前二條是容易做到的，關(guān)鍵是如何實(shí)現(xiàn)第三條。即如何使b.