数组和广义表可看成是一种特殊的线性表,其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。

二维数组,多维数组,广义表、树、图都属于非线性结构

数组
数组的顺序存储:行优先顺序;列优先顺序。数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。

关联数组(Associative Array),又称映射(Map)、字典( Dictionary)是一个抽象的数据结构,它包含着类似于(键,值)的有序对。 不是线性表。

矩阵的压缩:

对称矩阵、三角矩阵:直接存储矩阵的上三角或者下三角元素。注意区分i>=j和i<j的情况
对角矩阵:除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零。
稀疏矩阵:非零元素个数远小于矩阵元素总数。三元组或十字链表,十字链表更适合矩阵的加法乘法等操作。
三元组顺序表。三元组顺序表虽然节省了存储空间,但时间复杂度比一般矩阵转置的算法还要复杂,同时还有可能增加算法的难度。因此,此算法仅适用于t<<m*n的情况。
稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中,非零元素的分布是没有规律的,为了压缩存储,就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起,这样的结点组成的线性表中叫三元组表,它已不是简单的向量,所以无法用下标直接存取矩阵中的元素。
对于用三元组存储稀疏矩阵,每个元素要用行号,列号,元素值来表示,在用三元组表示稀疏矩阵,还要三个成员来记住矩阵的行数列数,总的元素数,即总共需要(非零元素个数)n+1个元素。
三元组转置(1)将数组的行列值相互交换(2)将每个三元组的i和j相互交换(3)重排三元组的之间的次序便可实现矩阵的转置
广义表
广义表(Lists,又称列表)是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列,其中ai或者是原子项,或者是一个广义表。若广义表LS(n>=1)非空,则a1是LS的表头,其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表,也可以是原子,广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表,表头可以为表或单元素值。所以表尾不可以是单个元素值。

例子:

A=()——A是一个空表,其长度为零。
B=(e)——表B只有一个原子e,B的长度为1。
C=(a,(b,c,d))——表C的长度为2,两个元素分别为原子a和子表(b,c,d)。
D=(A,B,C)——表D的长度为3,三个元素都是广义 表。显然,将子表的值代入后,则有D=(( ),(e),(a,(b,c,d)))。
E=(a,E)——这是一个递归的表,它的长度为2,E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).
三个结论:

广义表的元素可以是子表,而子表的元素还可以是子表。由此,广义表是一个多层次的结构,可以用图形象地表示
广义表可为其它表所共享。例如在上述例4中,广义表A,B,C为D的子表,则在D中可以不必列出子表的值,而是通过子表的名称来引用。
广义表的递归性
考点:

广义表是0个或多个单因素或子表组成的有限序列,广义表可以是自身的子表,广义表的长度n>=0,所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系
广义表的表头为空,并不代表该广义表为空表。广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()
已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是head(tail(head(tail(LS)))。根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。也就是说,广义表的head操作,取出的元素是什么,那么结果就是什么。但是tail操作取出的元素外必须加一个表——“()“。tail(LS)=((d,e,f));head(tail(LS))=(d,e,f);tail(head(tail(LS)))=(e,f);head(tail(head(tail(LS))))=e。
二维以上的数组其实是一种特殊的广义表
在(非空)广义表中:1、表头head可以是原子或者一个表 2、表尾tail一定是一个表 3.广义表难以用顺序存储结构 4.广义表可以是一个多层次的结构