PHP数据结构（六） ——数组的相乘、广义表
PHP数据结构（六）——数组的相乘、广义表
（原创内容，转载请注明来源，谢谢）
本文接PHP数据结构（五）的内容。
4.2 行逻辑链接的顺序表
行逻辑链接的顺序表，即在上述三元表的基础上，附加一个数组，用于存储每一行第一个非零元的位置。
该存储方式，主要是便于对两个稀疏矩阵进行乘法操作。
矩阵M(a行b列)和N(b行c列)相乘（m的行必须等于n的列），结果是一个a行c列的矩阵。
根据矩阵乘法的方式，计算步骤如下：
1、矩阵M的第a’行b‘列（0<=a’<=a，0<=b’<=b）的值（非零元），只需要和矩阵N的第b‘行的每个非零元所在的列col’相乘，作为第col‘列的暂存的值。
2、遍历M的第a’行的非零元，分别进行上述操作，并把暂存的值进行相加。
3、遍历完所有M的非零元，即完成乘法操作。
现假设两个稀疏矩阵如下：
M=array(
0=>array(0,1,25), 1=>array(1,3,15), 2=>array(2,2, 10), 3=>array(3,1,15)
);
N=array(
0=>array(0,3,10), 1=>array(1,4,15),2=>array(2,3,20), 3=>array(3,3,30)
);PHP计算稀疏矩阵乘法源码如下：
//稀疏矩阵乘法
//获取每一行的非零值
functiongetNotZeroRowPosi($arr){
$arrResult = array();
$row = 0;
$pos = 0;
foreach($arr as $key => $val){
$tmpRow = current($val);
if($tmpRow == $row){
if(!isset($arrResult[$row])){//考虑到第一次循环的时候的初始值
$arrResult[$row]= $pos;
}
$pos++;//计算本行占据的空间
}else{
$row = $tmpRow;
$arrResult[$row] =$pos++;
}
}
return $arrResult;
}
//乘法
functionmutiArray($arr1, $arr2){
$rowPosi2 = getNotZeroRowPosi($arr2);
$arrResult = array();
foreach($arr1 as $key => $val){//遍历第一个矩阵
$row1 = current($val);
$col1 = next($val);
$value1 = next($val);
for($i=$rowPosi2[$col1];;$i++){
if(!isset($arr2[$i])){//矩阵2取完后弹出
break;
}
$tmpArr = $arr2[$i];//取出矩阵2的第i行的非零元开始数组
$row2 =current($tmpArr);
if($row2 != $col1){
break;//循环结束矩阵2的第i行后，退出此循环
}
$col2 =next($tmpArr);
$value2 =next($tmpArr);
$value =$value1*$value2;
if(!isset($arrResult[$row1][$col2])){
$arrResult[$row1][$col2]= $value;
}else{
$arrResult[$row1][$col2]+= $value;
}
}
}
return $arrResult;
}
//调用乘法函数
$arrPrev =array(
0=> array(0,1,25),1=>array(1,3,15), 2=>array(2,2, 10), 3=>array(3,1,15)
);
$arrLast =array(
0=>array(0,3,10), 1=>array(1,4,15),2=>array(2,3,20), 3=>array(3,3,30)
);
$arrResult =mutiArray($arrPrev, $arrLast);
print_r($arrResult);
//计算结果Array ([0] => Array ( [4] => 375 ) [1] => Array ( [3] => 450 ) [2] =>Array ( [3] => 200 ) [3] => Array ( [4] => 225 ) )4.3 十字链表
十字链表主要用于稀疏矩阵相加的情况较多时的压缩存储方式。其与链表非常相似，但是有两个next指针，一个指向本行的下一个非零元（如果没有就指向null），另一个指向本列下一个非零元（如果没有就指向null）。
另外，需要设定两个头指针数组，一个指向每一列的第一个非零元，另一个指向每一行的第一个非零元。
矩阵相加的方式：
1、当矩阵M和矩阵N相加时，如果矩阵N的第（i，j）个位置M矩阵没有值，那么就在十字链表中插入此节点。
2、将插入后的节点的next指针分别指向本行、本列的下一个节点，如果没有下一个节点指向null。
3、改变该节点的上方与左方的节点的next指针指向新插入的节点，如果没有上方或左方的节点，则由相应的头指针数组指向该节点。
4、如果矩阵N的第（i，j）个位置M矩阵有值，且M和N该值相加不等于0（因为考虑到正数加负数等同于减的情况），则只需要改变该节点的值，不需要变换指针。
5、如果矩阵N的第（i，j）个位置M矩阵有值，且M和N该值相加等于0，则需要删除此节点。操作方式为将该节点的上方的节点（包括头节点）的next指向该节点的下一个节点（没有则指向null），将该节点的左边的节点（包括头节点）的next指向该节点的右边的节点（没有则指向null）。
5、广义表
5.1 广义表表示为LS=(a1,a2,…an)，其中的任意ai(1<=i<=n)可以是单个原子，如数字、字符串，也可以是广义表。即广义表是可以嵌套的。需要注意的是，’’与array()不一样，’’表示单个原子空值，array()表示没有元素的广义表。
5.2 广义表的深度即广义表中嵌套最多的层级数。
5.3 广义表通过链式结构存储，有两种存储方式。
方法一：
方法二：
5.4 根据广义表，可以做出递归算法。运用递归算法，可以算出广义表的深度。
广义表深度的计算方式，即遍历广义表的每一个ai，如果ai也是广义表，则进一步遍历ai的下一层。
广义表每一层的深度即为下一层深度的值加1，原子的深度为0，空表的深度为1。由此，可以计算广义表的深度。
PHP计算广义表的源码如下：
//计算广义表的深度
function getDeepthArr($arr){
$curMaxDeep= 0;
foreach($arras $item){
if(!is_array($item)){
continue;
}else{
$deep= getDeepthArr($item);
if($deep > $curMaxDeep){
$curMaxDeep= $deep;
}
}
}
return$curMaxDeep+1;
}
$arr = array(array('a'), 1,array(array('a', array(array()), '')), 'a');
$deep = getDeepthArr($arr);
echo $deep;//结果为5——written by linhxx 2017.06.23
相关阅读：