MATLAB程序设计语言(3.3)---一切皆为数组3(结构体和元胞数组的底层实现)

公众号：理念世界的影子

文不可无观点，观点不可无论据。

转载请注明出处

MATLAB功能强大，编程方便，是国际广泛使用的计算软件。目前已有很多书籍介绍其在工程上的应用，但很少有从程序设计语言的角度写的书或文章。

本期为矩阵存储续，下期关注MATLAB的传值和写时复制机制，从而可以看到MATLAB怎么在易用性和效率中间找到平衡。下期更精彩！

结构体和元胞数组的嵌套存储

+

对于结构体、元胞等，运行

1  a.abc=uint8([1 2;3 4]);a.cdef=uint8([1 3;5 8]);  % 结构体中申请两个变量

1  dispmem_href(getaddr(a));

2   b={uint8([1 3 5 8]), {uint8([2 4 7 6])}};

3  dispmem_href(getaddr(b));

按下图位置点击查看相应内存内容，可解析结构体和元胞存储数据结构如下。

图 结构体数据结构解析

图 元胞数组数据结构解析

摒弃细节，可将之绘制为如下图形，其中数值矩阵mxArray直接引用了一块线性排列的连续区域，从而对矩阵的操作可以在连续区域进行，实现了效率的最大化。元胞数组和结构体实现了一种嵌套的层次性数据结构。

图 嵌套数据结构示意图

在数学上，如将运算应用于集合，产生的元素仍在集合内，则称集合对于运算封闭。譬如自然数集合对于加法运算是封闭的，但对于减法则不是。通过引入元胞数组和结构体，MATLAB的内嵌数据数据类型，对于元素的拼接运算封闭性（实际上构成了一个幺半群），我们将这种能力称为内嵌数据对象的封闭性质(后续会再次讲到)。

在MATLAB下可以表达为嵌套的元胞数组。

1  function abstractdata

2  root=@(a) a{1};   % 父节点

3  left_tree=@(a) a{2};  % 左子树

4  right_tree=@(a) a{3};% 右子树

5  data={4 {2 {1} {3}} {5 {} {6}}};

6  isintree(data, 2.3) % 判断2.3是否在数组1、2、3～6内

7      function b=isintree(tree, x)

8          if(isempty(tree)) b=false;  % 树为空，没找到

9          elseif(x==root(tree)) b=true;  % 树的父节点

10          elseif(length(tree)==1) b=false; % 树仅为叶子节点;

11          elseif(x<root(tree)) b=isintree(left_tree(tree), x);  % 从左子树找

12          elseif(x>root(tree)) b=isintree(right_tree(tree), x);  % 从右子树找

13          end

14      end

15  end

图 数值1～6的查找树

程序的第2～4行定义了父节点、左右子树的访问；

第5行采用元胞数组定义了查找树；

第8～12行表示了查找树的表示方法。

对MATLAB元胞数组的想法

+

笔者有一点疑问，为什么MATLAB的元胞数组中，指针排列仍做成线性结构，而不做成链表结构。即上图指针的p2不是指向内嵌数据类型，而是指向内嵌数据类型的地址。在这种情况下，数组的随机访问效率由O(1)上升为O(n)，但其修改效率由O(n^2)急剧下降为O(1)。

笔者使用元胞数组时，修改远比访问用的多。猜测是软件作者认为访问效率更为重要，或者这种实现方式与其它的各种设计存在不相容之处？如有了解的网友盼回复！

---

往期文章：

MATLAB

微信扫一扫

关注“理念世界的影子”

版权声明：本文是"洞穴之外"作者原创文章，欢迎转载，须署名并注明来自“理念世界的影子”公众号。