专栏首页决胜机器学习PHP数据结构(六) ——数组的相乘、广义表

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

相关阅读:

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

本文分享自微信公众号 - 决胜机器学习(phpthinker),作者:linhxx

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP数据结构(五) ——数组的压缩与转置

    PHP数据结构(五)——数组的压缩与转置 (原创内容,转载请注明来源,谢谢) 1、数组可以看作是多个线性表组成的数据结构,二维数组可以有两种存储方式:一种是以行...

    用户1327360
  • PHP数据结构(六) ——树与二叉树之概念及存储结构

    PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

    用户1327360
  • PHP数据结构(九) ——图的定义、存储与两种方式遍历

    PHP数据结构(九)——图的定义、存储与两种方式遍历 (原创内容,转载请注明来源,谢谢) 一、定义和术语 1、不同于线性结构和树,图是任意两个...

    用户1327360
  • 【死磕Java并发】-----J.U.C之阻塞队列:PriorityBlockingQueue

    我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的...

    用户1655470
  • (译)云原生安全白皮书

    云原生的开发和部署模式已经成为业界趋势,技术、产品、标准和解决方案的生态系统也在同步的扩张之中,决策者面临着跟进复杂设计的挑战。CISO 要在这个动荡的战场中实...

    崔秀龙
  • python网络-多任务实现之协程(27)

    协程不是进程,也不是线程,它就是一个函数,一个特殊的函数——可以在某个地方挂起,并且可以重新在挂起处继续运行。所以说,协程与进程、线程相比,不是一个维度的概念。

    Se7eN_HOU
  • ​第3届云原生技术实践峰会(CNBPS 2020)重磅开启,“原”力蓄势待发!

    CNBPS 2020将在11月19-21日全新启动!作为国内最有影响力的云原生盛会之一,云原生技术实践峰会(CNBPS)至今已举办三届。

    灵雀云
  • 结对编程的正确姿势,你会了吗?

    极限编程的各个实践已经广为人知,也颇具争议,我听到最多的话题当属结对了: “我的小伙伴总拿着键盘不放,只听过麦霸,来到骚窝竟然还有键霸!” “我总算明白为什么面...

    ThoughtWorks
  • CSS in JS 简介

    1、 以前,网页开发有一个原则,叫做"关注点分离"(separation of concerns)。 ? 它的意思是,各种技术只负责自己的领域,不要混合在一起,...

    ruanyf
  • CSS in JS

    1、以前,网页开发有一个原则,叫做“关注点分离”(separation of concerns)。

    javascript.shop

扫码关注云+社区

领取腾讯云代金券