第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)個相同類型數(shù)據(jù)元素a0,a1,an-1構(gòu)成的有限序列，且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。由此可見，一維數(shù)組可以看成是一個線性表或一個向量，一維數(shù)組的定義類似于采用順序存儲的線性表。 對于一維數(shù)組，一旦a0的存儲地址Loc(a0)確定，若每個數(shù)據(jù)元素占用L個存儲單元，則任一數(shù)據(jù)元素ai的存儲地址Loc(ai)可由以下公式求出：

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

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

4、類型； 3. 數(shù)組中的每個數(shù)據(jù)元素都和一組唯一的下標(biāo)相對應(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ù)元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動。因此，適合采用順序存儲結(jié)構(gòu)表示數(shù)組。本章中，僅重點(diǎn)討論二維數(shù)組的存儲，三維及三維以上的數(shù)組可以作類似分析。 由于存儲單元是一維的結(jié)構(gòu)，而二維數(shù)組是個多維的結(jié)構(gòu)，則用一組連續(xù)存儲單元存放數(shù)組的數(shù)據(jù)元素就有個次序約定問題。 兩種順序存儲方式： 以行序?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)時，按行號從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類推 BASIC語言、PASCAL語言、C/C+語言都是按行優(yōu)先順序存放的。 例如，對二維數(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)存后，變成了一個線性序列（線性表）。,2020/8/3,第5章,10,2地址計算 假設(shè)二維數(shù)組Amn每個元素占L個字節(jié)，元素aij的存儲地址應(yīng)為第

6、一個元素的地址加上排在aij前面的元素所占用的單元數(shù)，而aij 的前面有i行(0i-1)共in個元素，而第i行上aij前面又有j個元素，故aij的前面一共有in+j個元素，設(shè)a00的地址為LOC(a00)，則aij的地址為： LOC(aij)=LOC(a00)+（in+j）L 同理，三維數(shù)組Amnp按低下標(biāo)優(yōu)先存放的地址計算公式為： 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)時，按列號從小到大的順序，先將第一列中元素全部存放好，再存放第二列元素，第三

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)存后，也變成了一個線性序列（線性表）。,2020/8/3,第5章,12,2地址計算 與行優(yōu)先存放類似，若知道第一個元素的內(nèi)存地址，則同樣可以求得按列優(yōu)存放的某一元素aij的地址。 對二維數(shù)組有： LOC(aij)=LOC(a00)+(jm+i)L 對三維數(shù)組Amnp按高下標(biāo)優(yōu)先存放的地址計算公式為： LOC(aijk)=LOC(a

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

9、j從0到9，從首地址SA開始存放在存儲器內(nèi)，該數(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：對于二維數(shù)組A0.20.5，當(dāng)按行優(yōu)先順序存儲時，元素A23是第幾個元素？當(dāng)按列優(yōu)先順序存儲時，元素A24是第幾個元素？,解：m=3,n=6 當(dāng)按行優(yōu)先順序存儲時，元素A23的序號為： 1+i*n+j=1+2*6+3=16 其中1表示元素A00 當(dāng)按列優(yōu)先順序存儲時，元素A24的

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

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

12、/8/3,第5章,19,若ij，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）共有1+2+i=i*(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai,j-1），因此aij之前共有k個元素： k=i*(i+1)/2+j ij, 0kn(n+1)/2-1,若ij，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對應(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.三角矩陣 以主對角線劃分，三角矩陣有上三角矩陣和下三角

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

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

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

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

17、，即可實(shí)現(xiàn)隨機(jī)存取。,2020/8/3,第5章,26,4.3稀疏矩陣 非零元較零元少，且分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。 假設(shè)在m*n的矩陣中，有t個元素不為零。令=t/(m*n),稱為矩陣的稀疏因子。通常認(rèn)為0.05時稱為稀疏矩陣。 如何進(jìn)行稀疏矩陣的壓縮存儲呢？ 按照壓縮存儲的概念，只存儲稀疏矩陣的非零元。因此，除了存儲非零元的值以外，還必須同時記下它所在行和列的位置（i,j)。反之，一個三元組（i, j, aij)唯一確定了矩陣A的一個非零元。由此，稀疏矩陣可由表示非零元的三元組及其行列數(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)這一對行、列值便可作為下圖中矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。,2020/8/3,第5章,28,一、三元組順序表 假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得稀疏矩陣的一種壓縮存儲方式，稱為三元組順序表。 /稀疏矩陣的三元組順序表存儲表示 #define MAXSIZE 12500 /非零元個數(shù)的最大值 typedef struct int i，j; ElemType e； Triple； typedef struc

19、t Triple dataMAXSIZE+1；/ 非零元三元組表，data0未用， int mu，nu，tu；/矩陣的行數(shù)、列數(shù)和非零元個數(shù) TSMatrix；,data域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?2020/8/3,第5章,29,稀疏矩陣的轉(zhuǎn)置運(yùn)算 轉(zhuǎn)置運(yùn)算是一種最簡單的矩陣運(yùn)算。對于一個m*n的矩陣M，它的轉(zhuǎn)置矩陣T是一個n*m的矩陣，且aij=bij，1in，1jm。,2020/8/3,第5章,30,顯然，一個稀疏矩陣的轉(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)將每個三元組中的i和j相互調(diào)換； (3)重排三元組之間的次序 便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。前二條是容易做到的，關(guān)鍵是如何實(shí)現(xiàn)第三條。即如何使b.