前言
一入編程深似海，從此磚頭是愛(ài)人，日日搬，夜夜搬，搬到天荒地老，精盡人亡，直教人失去了自我，忘記了時(shí)間，忽然之間發(fā)現(xiàn)九月份快沒(méi)了，趕緊寫(xiě)篇博客打個(gè)卡，證明一下我還活著。。。
數(shù)組與矩陣
數(shù)組是由一組相同類型的數(shù)據(jù)元素構(gòu)成的有限序列，訪問(wèn)數(shù)據(jù)元素的方式是使用元素各自的序號(hào)進(jìn)行訪問(wèn)，也就是下標(biāo)。數(shù)組它本身是線性表的推廣，一維數(shù)組就是一個(gè)向量形式的線性表，二維數(shù)組就是由一維數(shù)組組成的線性表。
在許多科學(xué)計(jì)算和工程應(yīng)用中，經(jīng)常要用到矩陣的概念，我們用的最多的其實(shí)就是Mysql的表，表數(shù)據(jù)都是行列存儲(chǔ)，這就是矩陣。
由于矩陣具有元素?cái)?shù)目固定以及元素按下標(biāo)關(guān)系有序排列等特點(diǎn)，所以在使用高級(jí)語(yǔ)言編程時(shí)，一般都是用二維數(shù)組來(lái)存儲(chǔ)矩陣。
數(shù)組的順序存儲(chǔ)
為什么是順序存儲(chǔ)？
我想問(wèn)這個(gè)問(wèn)題就太低級(jí)了。因?yàn)樗菙?shù)組，數(shù)據(jù)的存儲(chǔ)方式分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種，數(shù)組一旦被定義，他的維數(shù)和維界就已固定，除結(jié)構(gòu)的初始化和銷毀外，數(shù)組只會(huì)有存取元素和修改元素的操作，不存在插入和刪除操作，所以數(shù)組適合用順序存儲(chǔ)。
數(shù)組存放在內(nèi)存中的映射關(guān)系
數(shù)組可以是多維的，但是內(nèi)存空間卻是一維的，所以我們就要把多維數(shù)組通過(guò)一定的映射順序把它變成一維的，然后存儲(chǔ)到內(nèi)存空間之中。
在大多數(shù)高級(jí)編程語(yǔ)言中，多維數(shù)組在內(nèi)存中通常有兩種不同的順序存儲(chǔ)方式，按行優(yōu)先順序存儲(chǔ) 和 按列優(yōu)先順序存儲(chǔ)。
舉個(gè)例子，以下3行4列的一個(gè)二維數(shù)組矩陣：
a1,a2,a3,a4
b1,b2,b3,b4
c1,c2,c3,c4
按行優(yōu)先順序存儲(chǔ)：
按列優(yōu)先順序存儲(chǔ)：
地址計(jì)算
地址計(jì)算的意思就是給定數(shù)組下標(biāo)，求在一維內(nèi)存空間的地址，從而取出數(shù)據(jù)。
我們先來(lái)看一維數(shù)組的地址計(jì)算
一維數(shù)組內(nèi)的元素只有一個(gè)下標(biāo)，存儲(chǔ)方法和普通的線性表一樣。
如一維數(shù)組 A = [a1,a2,a3,......ai,.........,an]，每個(gè)元素占用size個(gè)存儲(chǔ)單元（就是內(nèi)存大?。?，那么元素ai的存儲(chǔ)地址為 A[0]的位置 + (i-1)*size
再來(lái)看二維數(shù)組的地址計(jì)算
以二維數(shù)組Amn為例，首元素為A[0][0]，數(shù)組中任意元素A[i][j]的地址為：A[0][0]的位置 + （n * (i-1) + (j-1)）* size；
比如：一個(gè)5行4列的二維數(shù)組A，按行存儲(chǔ)，其中每個(gè)元素占2個(gè)存儲(chǔ)單元，首元素地址是1000，求第3行第2列的元素在內(nèi)存中的地址。
我們把參數(shù)套進(jìn)公式中，答案 = 1000 + (4 * (3-1) + (2-1)) * 2 = 1018;
如果把矩陣畫(huà)在紙上觀察就一目了然：
公式的內(nèi)容就是求出格子數(shù)，乘以每個(gè)格子所占用的存儲(chǔ)單元，再加上首地址。
矩陣轉(zhuǎn)置
設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)矩陣A(m*n) 轉(zhuǎn)置為矩陣B(n*m)，簡(jiǎn)單的說(shuō)，就是行列互換。
$arr = [ ['張三','男','北京'], ['李四','女','上海'], ['王五','男','廣州'], ]; function transpose($a){ $b = []; for ($i = 0;$i < count($a); $i ++){ for($j = 0;$j < count($a[$i]); $j ++){ $b[$j][$i] = $a[$i][$j]; } } return $b; } $result = transpose($arr);
結(jié)果為：
$result = [
['張三','李四','王五'],
['男','女','男'],
['北京','上海','廣州'],
];
特殊矩陣
特殊矩陣的壓縮存儲(chǔ)
特殊矩陣指的是具有許多相同元素或者零元素，并且這些元素的分布有一定規(guī)律性的矩陣。
這種矩陣如果還使用前面的方式來(lái)存儲(chǔ)，就會(huì)產(chǎn)生大量的空間浪費(fèi)，為了節(jié)省存儲(chǔ)空間，可以對(duì)這類矩陣采用壓縮存儲(chǔ)，壓縮存儲(chǔ)的方式是把那些呈現(xiàn)規(guī)律性分布的相同元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配存儲(chǔ)空間。
三角矩陣
三角矩陣我們以下三角來(lái)做例子，如圖所示：
所有空格之中裝的數(shù)據(jù)都是null或者都是同一常量，也就是空格中全都是相同的數(shù)據(jù)。
按行方式存儲(chǔ)的情況下，一維存儲(chǔ)內(nèi)存空間的大小是：1+2+3+4+5+6+7 = n(n+1)/2 = 7 * (7+1) / 2 = 28，當(dāng)然，在最后還要加一個(gè)存儲(chǔ)空間，用來(lái)存儲(chǔ)上三角中相同的數(shù)據(jù)。
那么對(duì)于任意元素aij，在一維存儲(chǔ)內(nèi)存空間中的地址仍然是要靠計(jì)算格子來(lái)得到，先算出占滿行的總格子數(shù)，再加上當(dāng)前行的格子數(shù)：a[0][0]的位置 + (i * (i+1) / 2 + j) * size;
我們使用公式來(lái)驗(yàn)證一下，a42的所在格子數(shù) = (i * (i+1) / 2 + j) = 4 * 5 / 2 + 2 = 12
帶狀矩陣
帶狀矩陣也叫做對(duì)角矩陣，如圖所示：
帶狀矩陣的特征是：所有非0元素都集中在以主對(duì)角線為中心的3條對(duì)角線區(qū)域，其他區(qū)域的元素都為0。
除了第一行和最后一行僅2個(gè)非零元素，其余行都是3個(gè)非零元素，換句話說(shuō)就是每行都是3個(gè)非零元素，但是第一行少了1個(gè)，最后一行少了1個(gè)，所以所需的一維空間大小為：3n - 2；
那么對(duì)于任意一個(gè)元素 aij，怎么計(jì)算它在內(nèi)存空間的地址呢？
經(jīng)過(guò)觀察可以得知i和j都在對(duì)角線附近，相減后的結(jié)果與分布情況分別如下
j - i = 1；對(duì)角線上面
j - i = 0; 對(duì)角線
j - i = -1;對(duì)角線下面
不管是在對(duì)角線的哪個(gè)位置，我們都可以使用通用的辦法來(lái)計(jì)算地址，也就是先計(jì)算出上面行所占的格子，再加上當(dāng)前行的格子。
上面的行數(shù)：i，由于行列都是0開(kāi)頭計(jì)數(shù)，所以上面的行數(shù)就是i這個(gè)值。
上面的格子數(shù)： 3 * i - 1，減1是因?yàn)榈谝恍猩僖粋€(gè)格子。
當(dāng)前行格子數(shù)： j - i + 1；根據(jù)i和j的關(guān)系，我們把相減后的值加1，得到當(dāng)前行的格子數(shù)。
那么最后aij的內(nèi)存地址 = a00首地址 + ((3 * i -1) + ( j-i+1)) * size； size為每個(gè)數(shù)據(jù)所占用的存儲(chǔ)單元大小。
比如首地址為1000，每個(gè)數(shù)據(jù)占用2個(gè)存儲(chǔ)單元，那么a45在內(nèi)存中的地址 = 1000 + 13 * 2 = 1026；
稀疏矩陣的壓縮存儲(chǔ)
由于特殊矩陣中非零元素的分布是有規(guī)律的，所以總是可以找到矩陣元素與一維數(shù)組下標(biāo)的對(duì)應(yīng)關(guān)系，但還有一種矩陣，矩陣中大多數(shù)元素都為0，一般情況下非零元素個(gè)數(shù)只占矩陣元素總數(shù)的30%以下，并且元素的分布是沒(méi)有任何規(guī)律的，這樣的矩陣我們稱為稀疏矩陣。
如果采用常規(guī)方法存儲(chǔ)稀疏矩陣，就會(huì)相當(dāng)浪費(fèi)存儲(chǔ)空間，因此我們需要只存儲(chǔ)非零元素。由于稀疏矩陣中非零元素的分布是沒(méi)有規(guī)律的，所以除了存儲(chǔ)非零元素的值之外，我們還需要同時(shí)存儲(chǔ)非零元素的行、列位置，也就是三元組（i,j,aij）。
如圖：
所謂三元組，也就是一個(gè)矩陣，一個(gè)二維數(shù)組，每一行都三個(gè)列，分別為行號(hào)、列號(hào)、元素值。
由于三元組在稀疏矩陣與內(nèi)存地址間扮演了一個(gè)中間人的角色，所以稀疏矩陣進(jìn)行壓縮存儲(chǔ)后，便失去了隨機(jī)存取的特性。
|轉(zhuǎn)載請(qǐng)注明來(lái)源地址：蜘蛛池出租 http://www.wholesalehouseflipping.com/
專注于SEO培訓(xùn)，快速排名黑帽SEO https://www.heimao.wiki