《數(shù)據(jù)結(jié)構(gòu)》矩陣

1、本節(jié)內(nèi)容矩陣王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM矩陣a0a1a2a00a01a02a10a11a12a20a21a223*3 二維數(shù)組數(shù)組是由n（n1）個相同類型的數(shù)據(jù)元素構(gòu)成的有限序列，一個數(shù)組的所有元素在內(nèi)存中占用一段連續(xù)的存儲空間 對于二維數(shù)組而言，有兩種映射方法：按行優(yōu)先和按列優(yōu)先 王道考研/CSKAOYAN.COM矩陣行優(yōu)先：先行后列，先存儲行號較小的元素，行號相等先存儲列號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2a00a01a02a10a11a12a20a21a22a00a01a02a10a11a12a20a21a22

2、內(nèi)存中的存放形式王道考研/CSKAOYAN.COM矩陣行優(yōu)先：先行后列，先存儲行號較小的元素，行號相等先存儲列號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2二維數(shù)組第一個元素的地址前面有幾整行一整行的元素個數(shù)最后一行前面的元素數(shù)量a3,0a5,35-3=2整行一整行有5-0+1=6個元素l1=3h1=5l2=0 h2=5最后一行前面還有3-0=3個元素王道考研/CSKAOYAN.COM矩陣行優(yōu)先：先行后列，先存儲行號較小的元素，行號相等先存儲列號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2更常見的就是l1=0,l2=0,上式化為王道考研/

3、CSKAOYAN.COM矩陣列優(yōu)先：先列后行，先存儲列號較小的元素，列號相等先存儲行號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2a00a01a02a10a11a12a20a21a22a00a10a20a01a11a21a02a12a22內(nèi)存中的存放形式王道考研/CSKAOYAN.COM矩陣列優(yōu)先：先列后行，先存儲列號較小的元素，列號相等先存儲行號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2二維數(shù)組第一個元素的地址前面有幾整列一整列的元素個數(shù)最后一列前面的元素數(shù)量a3,0a5,3最后一列前面還有5-3=2個元素l1=3h1=5l2=0 h

4、2=5一整列有5-3+1=3個元素前面還有3-0=3整列王道考研/CSKAOYAN.COM矩陣列優(yōu)先：先列后行，先存儲列號較小的元素，列號相等先存儲行號較小的元素 設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為l1，h1與l2，h2更常見的就是l1=0,l2=0,上式化為王道考研/CSKAOYAN.COM矩陣的壓縮存儲矩陣的壓縮存儲：指為多個值相同的元素只分配一個存儲空間，對零元素不分配存儲空間。 特殊矩陣：指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布有一定規(guī)律性的矩陣 。對稱矩陣、上（下）三角矩陣、對角矩陣 王道考研/CSKAOYAN.COM對稱矩陣對稱矩陣：若一個n階方陣A1

5、n1n中的任一個元素ai,j，都有ai,j=aj,i（1i，jn），則稱其為對稱矩陣。 上三角區(qū)：ij1 2 31 2 3對于n階對稱矩陣，上三角區(qū)所有元素和下三角區(qū)對應(yīng)元素相同，所以我們只需要存儲對角線上的元素和下三角區(qū)的元素。王道考研/CSKAOYAN.COM對稱矩陣上三角區(qū)：ij1 2 31 2 3將矩陣中關(guān)鍵字存儲到一維數(shù)組Bn(n+1)/2中矩陣中元素ai,j對應(yīng)數(shù)組B中下標(biāo)為k的元素存儲下三角區(qū)和對角線上元素aij第一行存儲元素1 一共1個第二行存儲元素2和5 一共2個第三行存儲元素3和4和8 一共3個第i-1行存儲i-1個元素第i行存儲j個元素王道考研/CSKAOYAN.COM對

6、稱矩陣上三角區(qū)：ij1 2 31 2 3125348123254348下標(biāo)012345012345678下標(biāo)王道考研/CSKAOYAN.COM對稱矩陣上三角區(qū)：ij1 2 31 2 3125348下標(biāo)012345王道考研/CSKAOYAN.COM三角矩陣三角矩陣：下三角矩陣的上三角區(qū)都是同一常數(shù)，上三角矩陣的下三角區(qū)都是同一常數(shù)上三角區(qū)：ij1 2 31 2 3存儲思想：與對稱矩陣類似，不同之處在于存儲完下三角區(qū)和主對角線上的元素之后，緊接著存儲對角線上方的常量一次，故可以將下三角矩陣A1n1n壓縮存儲在Bn(n+1)/2+1中。上三角區(qū)：ij1 2 31 2 3下三角矩陣上三角矩陣王道考研/

7、CSKAOYAN.COM三角矩陣上三角區(qū)：ij1 2 31 2 3下三角矩陣王道考研/CSKAOYAN.COM三角矩陣對于上三角矩陣上三角區(qū)：ij1 2 31 2 3上三角矩陣王道考研/CSKAOYAN.COM三角矩陣對于上三角矩陣上三角區(qū)：ij1 2 31 2 3上三角矩陣對于下三角區(qū)元素，只用存儲一個即可，存在B中下標(biāo)為n(n+1)/2的位置即可王道考研/CSKAOYAN.COM三對角矩陣三對角矩陣：對角矩陣也稱為帶狀矩陣。對于n階方陣A中的任一元素ai,j，當(dāng)|i-j|1時，有ai,j=0（1i，jn），則稱為三對角矩陣， 存儲思想：將3條對角線上的元素按行優(yōu)先方式存放在一維數(shù)組B中 1

8、2345456元素ai,j對應(yīng)數(shù)組B中的下標(biāo)為k=2i+j-3 當(dāng)i=1，k顯然等于j-1當(dāng)i1時，第一行存儲兩個元素，接下來除去最后一行和第一行一共i-2行，每行都有三個元素ai,j在最后一行是第j-i+2個元素。所以ai,j在數(shù)組中是第2+(i-2)*3+j-i+2=2i+j-2個元素所以下標(biāo)k=2i+j-3 檢查i=1的情況，也滿足這個式子。所以元素ai,j對應(yīng)數(shù)組B中的下標(biāo)為k=2i+j-3 王道考研/CSKAOYAN.COM三對角矩陣三對角矩陣：對角矩陣也稱為帶狀矩陣。對于n階方陣A中的任一元素ai,j，當(dāng)|i-j|1時，有ai,j=0（1i，jn），則稱為三對角矩陣， 存儲思想：將

9、3條對角線上的元素按行優(yōu)先方式存放在一維數(shù)組B中 12345456若已知三對角線矩陣中某元素ai,j在一維數(shù)組B中存放于第k個位置，則可求得i=(k+1)/3+1，j=k-2i+3 位置k的元素的實(shí)際是第k+1個元素 前面一共有k個元素除去第一行，還有k-2個元素，這k-2每達(dá)到3，那么k+1元素就進(jìn)入下一行，所以它的行數(shù)便增1，而且是從第二行開始的。如果達(dá)不到三個，那第k+1個元素也到不了下一行，但是k-2不一定是3的整數(shù)，所以進(jìn)行向下取整。即i= (k-2)/3+2= (k+1)/3+1由于在第i行，前i-1行有2+3*(i-2)=3i-4個元素，所以是第i行非0元素的第k+1-(3i-4)=k-3i+5個關(guān)鍵字第i行前面有i-2(i2)個0，所以j=k-3i+5+i-2=k-2i+3王道考研/CSKAOYAN.COM稀疏矩陣稀疏矩陣：矩陣中元素個數(shù)s相對于矩陣中非0元素個數(shù)t來說