PHP数据结构（五） ——数组的压缩与转置
PHP数据结构（五）——数组的压缩与转置
（原创内容，转载请注明来源，谢谢）
1、数组可以看作是多个线性表组成的数据结构，二维数组可以有两种存储方式：一种是以行为主序，另一种是以列为主序。
2、当数组存在特殊情况时，为了节省存储空间，可以进行压缩存储，把相同值并有规律分布的元素只分配一个存储空间，对于零元素不进行存储。
有两种情况可以进行压缩存储——特殊矩阵与稀疏矩阵。
3、当数组为特殊的矩阵，例如数组为n阶对称矩阵（满足aij=aji）。对于该类型矩阵，可以只存储一半的数值加上对角线的内容，一共需要分配n*(n+1)/2的存储空间。同时，上（下）三角矩阵也可以用此方式进行存储。（三角矩阵为一半有值，另一半值为0的矩阵）
存储N阶对称矩阵的方式，即以对称对角线为分界，仅取其中一半的内容以及对角线进行存储。
PHP压缩与还原n阶对称矩阵的源码如下：
<?php
//存储n阶对称矩阵
function symmetricMatrixSave($n,$arr){
$arrResult= array();
$k= 0;//结果数组的下标
for($i=0;$i<$n;$i++){
for($j=0;$j<=$i; $j++){
$arrResult[$k++]= $arr[$i][$j];
}
}
return$arrResult;
}
//还原n阶对称矩阵
function symmetricMatrixRe($arr){
$rank= $arr[0];
$arrResult= array();
$row= 0;
$col= 0;
for($k=0;$k<count($arr); $k++){
//根据取出的值还原半边
$arrResult[$row][$col]= $arr[$k];
//根据对称性还原另一半
$arrResult[$col][$row]= $arrResult[$row][$col];
$col++;
//根据存储规则，只存一半的值，因此col不会大于row
if($col> $row){
$col= 0;
$row++;
}
}
return$arrResult;
}
//调用n阶矩阵的存储还原
$arr = array(
0=> array(0, 1, 2, 3),
1=> array(1, 2, 3, 4),
2=> array(2, 3, 4, 5),
3=> array(3, 4, 5, 6)
);
print_r($arr);
//打印原数组Array ( [0]=> Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 ) [1] => Array( [0] => 1 [1] => 2 [2] => 3 [3] => 4 ) [2] => Array ( [0] =>2 [1] => 3 [2] => 4 [3] => 5 ) [3] => Array ( [0] => 3 [1] =>4 [2] => 5 [3] => 6 ) )
echo '<br />';
$arrResult = symmetricMatrixSave(4, $arr);
print_r($arrResult);
//压缩后的结果Array ( [0]=> 0 [1] => 1 [2] => 2 [3] => 2 [4] => 3 [5] => 4 [6] => 3[7] => 4 [8] => 5 [9] => 6 )
echo '<br />';
$arrRe = symmetricMatrixRe($arrResult);
print_r($arrRe);
//还原后的结果，与压缩前相同Array ([0] => Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 ) [1] =>Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 ) [2] => Array ( [0]=> 2 [1] => 3 [2] => 4 [3] => 5 ) [3] => Array ( [0] => 3 [1]=> 4 [2] => 5 [3] => 6 ) )4、当矩阵为稀疏矩阵，即在m*n的矩阵中，有t个不为0的元素，且满足t/(m*n)<=0.5。稀疏矩阵通常用三元数组进行存储，（i，j，value）分别表示不为零的元素的行、列以及值。
除了上述的三元数组的压缩方式，稀疏矩阵还有两种压缩方式。分别是行逻辑链接的顺序表、十字链表。
4.1 三元组顺序表
三元组顺序表以行为主序，以列为次序，从小到大进行排列。例如：[(0,1,30),(0,3,50),(1,2,18),(3,5,20)]，表示该稀疏矩阵共有四个非零元素，分别在(0,1)、(0,3)、(1,2)、(3,5)四个位置，值分别是30、50、18、20。
该方法存储的表，要进行转置操作非常便利。转置需要进行三步操作，分别是：行列的值进行转换、i和j进行转换、重新从小到大排列i和j。因此，转置的重点在于最后一步——排序。
对于排序，可以通过从0开始扫描原数组的列，并将结果相应放入新数组的行。也可以采用下述的快速转置法。
快速转置数组算法：
假设原矩阵为M，新矩阵为T，引入两个新的数组，数组num[col]为第col列非零元的个数，cpot[col]为第col列第一个非零元在新矩阵T生成的三元组顺序表的位置。在转置前，先通过原矩阵M获取这两个数组，用于快速转换的计算。
PHP快速转置稀疏矩阵的源码如下：
<?php
//快速转置稀疏矩阵
//根据原标准三元数组获取每一列非零元个数及第一个非零元的位置
/* 输入要求
array(
0=>array(0,1,33),
1=>array(0,5,67),
2=>array(1,2,66),
3=>array(3,4,55)
)*/
function getAuxiliaryArray($arr){
$num= array();//每一列非零元个数
foreach($arras $key => $val){
$num[next($val)]++;//next($val)获取列值
}
ksort($num);//根据键对数组升序排列
$row_position= 0;
$cpot= array();
foreach($numas $key => $val){
$cpot[$key]= $row_position;
$row_position= $row_position + $val;
}
returnarray('num'=>$num, 'cpot'=>$cpot);
}
//转置方法
function getReverse($arr, $num, $cpot){
$arrResult= array();
foreach($arras $key => $val){
$row= current($val);
$col= next($val);
$val= next($val);
$arrResult[$cpot[$col]]= array($col, $row, $val);
$cpot[$col]++;//用于存放同一列下一个值的位置
}
return$arrResult;
}
$arrPrev = array(
0=>array(0,1,33),
1=>array(0,5,67),
2=>array(1,2,66),
3=>array(2,2,69),
4=>array(3,4,55)
);
$arrTemp = getAuxiliaryArray($arrPrev);
$arrAfter = getReverse($arrPrev,$arrTemp['num'], $arrTemp['cpot']);
print_r($arrAfter);
//输出Array ( [0] =>Array ( [0] => 1 [1] => 0 [2] => 33 ) [1] => Array ( [0] => 2[1] => 1 [2] => 66 ) [2] => Array ( [0] => 2 [1] => 2 [2] =>69 ) [3] => Array ( [0] => 4 [1] => 3 [2] => 55 ) [4] => Array ([0] => 5 [1] => 0 [2] => 67 ))——written by linhxx 2017.06.23
相关阅读：
腾讯云开发者
