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