数组和广义表

数组Amn

数组有两种顺序存储方式：
⑴行优先顺序：每一行看作一个一维数组
——将数组元素按行排列。a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn
⑵列优先顺序：每一列看作一个一维数组
——将数组元素按列向量排列。a11,a21,…,am1,a12,a22,…am2,……,a1n,a2n,…,amn

数组的操作

（1）存取元素
（2）修改元素值
例：若按行优先顺序：
①二维数组Amn中元素aij的存储地址：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*size
②三维数组Amno中元素aijk的存储地址：LOC(aij)=LOC(a11)+[(i-1)no+(j-1)*o+(k-1)]*size

对于特殊矩阵的压缩存储

由于有时候矩阵内部会存在大量的0或重复数据，会导致数组的存储空间造成许多浪费，
这时可根据矩阵的一些特性对数组进行处理，节省存储空间。
（1）对称矩阵（aij == aji，依据对角线对称）

可将矩阵变为下三角矩阵，每一行都有i+1个元素，共 i*（i+1）个元素
将元素存储在一个一维数组中，设置对应关系：
LOC（aij）= i*（i+1）/2 + j （i>=j）
j*（j+1）/2 + i （i < j）

（2）对角矩阵（除主对角线（可为0）之外的元素都为0）
只对对角线元素进行存储

（3）稀疏矩阵（矩阵中有s个非零元素，s<<m*n)
可使用十字链表来进行存储

十字链表

包含属性：

i：行号；j：列号；val：非0值；
right:右指针，指向本行中下一个（列）结点的地址；
down:向下指针，指向本列中下一个（行）结点的地址。
例：

广义表

广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai是原子项，或是一个广义表。
表示： LS=（a1,a2,a3,…,an)。
LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。
为了区别原子和广义表，广义表用大写字母表示， 原子使用小写字母。
例：D=(( ),(e),(a,(b,c,d))) D中含有三个广义表，在子表中还存在着子表
E=（a, E） 广义表自己引用自己是一个深度无限，大小为2的表

广义表的结构特点

①“原子”的深度为“0”; “空表”的深度为1；
②广义表的长度定义为最外层包含的元素个数；
③表头可以是原子或列表; 表尾必定是列表；
④广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值；
⑤广义表的元素可以是子表，而子表的元素还可以是子表，广义表是一个多层次的结构；
⑥广义表可为其它表所共享。

广义表的存储结构

由于广义表中的数据元素可以具有不同的结构。因此，通常采用链式存储结构。
在定义的时候需要定义两种节点，一种表节点，一种原子节点。
如递归表：