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《MATLAB程序设计语言(3)---一切皆为数组2(MATLAB的底层实现)》
《MATLAB程序设计语言(2)---help的see also与六度空间理论》
微信扫一扫
关注“理念世界的影子”
版权声明：本文是"洞穴之外"作者原创文章，欢迎转载，须署名并注明来自“理念世界的影子”公众号。