《數(shù)據(jù)結(jié)構(gòu)》考研課程第三章矩陣

本節(jié)內(nèi)容矩陣矩陣a[0]a[1]a[2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]a[2][0]a[2][1]a[2][2]3*3二維數(shù)組數(shù)組是由n（n≥1）個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列，一個(gè)數(shù)組的所有元素在內(nèi)存中占用一段連續(xù)的存儲(chǔ)空間

對(duì)于二維數(shù)組而言，有兩種映射方法：按行優(yōu)先和按列優(yōu)先

矩陣行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相等先存儲(chǔ)列號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]a[2][0]a[2][1]a[2][2]a00a01a02a10a11a12a20a21a22內(nèi)存中的存放形式矩陣行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相等先存儲(chǔ)列號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]

二維數(shù)組第一個(gè)元素的地址前面有幾整行一整行的元素個(gè)數(shù)最后一行前面的元素?cái)?shù)量a3,0a5,35-3=2整行一整行有5-0+1=6個(gè)元素l1=3h1=5l2=0h2=5最后一行前面還有3-0=3個(gè)元素矩陣行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相等先存儲(chǔ)列號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]

更常見的就是l1=0,l2=0,上式化為

矩陣列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相等先存儲(chǔ)行號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]a[2][0]a[2][1]a[2][2]a00a10a20a01a11a21a02a12a22內(nèi)存中的存放形式矩陣列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相等先存儲(chǔ)行號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]

二維數(shù)組第一個(gè)元素的地址前面有幾整列一整列的元素個(gè)數(shù)最后一列前面的元素?cái)?shù)量a3,0a5,3最后一列前面還有5-3=2個(gè)元素l1=3h1=5l2=0h2=5一整列有5-3+1=3個(gè)元素前面還有3-0=3整列矩陣列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相等先存儲(chǔ)行號(hào)較小的元素

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為[l1，h1]與[l2，h2]

更常見的就是l1=0,l2=0,上式化為

矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)：指為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配存儲(chǔ)空間。

特殊矩陣：指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布有一定規(guī)律性的矩陣

。對(duì)稱矩陣、上（下）三角矩陣、對(duì)角矩陣

對(duì)稱矩陣對(duì)稱矩陣：若一個(gè)n階方陣A[1…n][1…n]中的任一個(gè)元素ai,j，都有ai,j=aj,i（1≤i，j≤n），則稱其為對(duì)稱矩陣。

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3對(duì)于n階對(duì)稱矩陣，上三角區(qū)所有元素和下三角區(qū)對(duì)應(yīng)元素相同，所以我們只需要存儲(chǔ)對(duì)角線上的元素和下三角區(qū)的元素。對(duì)稱矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3將矩陣中關(guān)鍵字存儲(chǔ)到一維數(shù)組B[n(n+1)/2]中矩陣中元素ai,j對(duì)應(yīng)數(shù)組B中下標(biāo)為k的元素存儲(chǔ)下三角區(qū)和對(duì)角線上元素aij第一行存儲(chǔ)元素1一共1個(gè)第二行存儲(chǔ)元素2和5一共2個(gè)第三行存儲(chǔ)元素3和4和8一共3個(gè)……第i-1行存儲(chǔ)i-1個(gè)元素第i行存儲(chǔ)j個(gè)元素

對(duì)稱矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3

125348123254348下標(biāo)012345012345678下標(biāo)對(duì)稱矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3125348下標(biāo)012345

三角矩陣三角矩陣：下三角矩陣的上三角區(qū)都是同一常數(shù)，上三角矩陣的下三角區(qū)都是同一常數(shù)

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3存儲(chǔ)思想：與對(duì)稱矩陣類似，不同之處在于存儲(chǔ)完下三角區(qū)和主對(duì)角線上的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量一次，故可以將下三角矩陣A[1…n][1…n]壓縮存儲(chǔ)在B[n(n+1)/2+1]中。

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3下三角矩陣上三角矩陣三角矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3

下三角矩陣三角矩陣對(duì)于上三角矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3上三角矩陣

三角矩陣對(duì)于上三角矩陣

上三角區(qū)：i<j主對(duì)角線：i=j下三角區(qū)：i>j1

2

31

2

3上三角矩陣對(duì)于下三角區(qū)元素，只用存儲(chǔ)一個(gè)即可，存在B中下標(biāo)為n(n+1)/2的位置即可三對(duì)角矩陣三對(duì)角矩陣：對(duì)角矩陣也稱為帶狀矩陣。對(duì)于n階方陣A中的任一元素ai,j，當(dāng)|i-j|＞1時(shí)，有ai,j=0（1≤i，j≤n），則稱為三對(duì)角矩陣，

存儲(chǔ)思想：將3條對(duì)角線上的元素按行優(yōu)先方式存放在一維數(shù)組B中

12345456……元素ai,j對(duì)應(yīng)數(shù)組B中的下標(biāo)為k=2i+j-3

當(dāng)i=1，k顯然等于j-1當(dāng)i>1時(shí)，第一行存儲(chǔ)兩個(gè)元素，接下來除去最后一行和第一行一共i-2行，每行都有三個(gè)元素ai,j在最后一行是第j-i+2個(gè)元素。所以ai,j在數(shù)組中是第2+(i-2)*3+j-i+2=2i+j-2個(gè)元素所以下標(biāo)k=2i+j-3

檢查i=1的情況，也滿足這個(gè)式子。所以元素ai,j對(duì)應(yīng)數(shù)組B中的下標(biāo)為k=2i+j-3

三對(duì)角矩陣三對(duì)角矩陣：對(duì)角矩陣也稱為帶狀矩陣。對(duì)于n階方陣A中的任一元素ai,j，當(dāng)|i-j|＞1時(shí)，有ai,j=0（1≤i，j≤n），則稱為三對(duì)角矩陣，

存儲(chǔ)思想：將3條對(duì)角線上的元素按行優(yōu)先方式存放在一維數(shù)組B中

12345456……若已知三對(duì)角線矩陣中某元素ai,j在一維數(shù)組B中存放于第k個(gè)位置，則可求得i=

(k+1)/3+1

，j=k-2i+3

位置k的元素的實(shí)際是第k+1個(gè)元素前面一共有k個(gè)元素除去第一行，還有k-2個(gè)元素，這k-2每達(dá)到3，那么k+1元素就進(jìn)入下一行，所以它的行數(shù)便增1，而且是從第二行開始的。如果達(dá)不到三個(gè)，那第k+1個(gè)元素也到不了下一行，但是k-2不一定是3的整數(shù)，所以進(jìn)行向下取整。即i=

(k-2)/3+2=

(k+1)/3+1

由于在第i行，前i-1行有2+3*(i-2)=3i-4個(gè)元素，所以是第i行非0元素的第k+1-(3i-4)=k-3i+5個(gè)關(guān)鍵字第i行前面有i-2(i>2)個(gè)0，所以j=k-3i+5+i-2=k-2i+3稀疏矩陣稀疏矩陣：矩陣中元素個(gè)數(shù)