数组与广义表可看作是线性表的推广，其特点是数据元素仍然是一个表。
（一）数组
1.数组的定义及基本运算
（1）数组的定义
数组是定长线性表在维数上的扩展，即线性表中的元素又是一个线性表。
n维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
数组的特点：
- 数组元素数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化；
- 数据元素具有相同的类型；
- 数据元素的下标关系具有上下界的约束且下标有序。
（2）数组的两个基本运算
- 给定一组下标，存取相应的数据元素；
- 给定一组下标，修改相应的数据元素中某个数据项的值。
2.数组的顺序存储
数组一般不做插入和删除运算，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
二维数组的存储结构可分为以行为主序和以列为主序的两种方法：
二维数组的两种存储方式
地址计算公式：
- 以行为主序
Loc(aij)=Loc(a11)+((i-1)*n+(j-1))*L
- 以列为主序
Loc(aij)=Loc(a11)+((j-1)*m+(i-1))*L
（二）矩阵
为了节省存储空间，对有相同的元素或是0的元素的矩阵进行压缩，即多个值相同的元素只分配一个存储单元，对0不分配存储单元。
假如值相同的元素或0元素在矩阵中的分布有一定的规律，则称此类矩阵为特殊矩阵，否则称其为稀疏矩阵。
1.特殊矩阵
特殊矩阵：矩阵中元素（或非0元素）的分布有一定的规律的矩阵。
常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。
2.稀疏矩阵
稀疏矩阵：非0元素的个数远远少于0元素的个数，且非0元素的分布没有规律的矩阵。
在存储非0元素时必须同时存储其位置（行号和列号），所以三元组（i,j,aij）可唯一确定矩阵A中的一个元素。
（三）广义表
广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
广义表于线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。
广义表一般记为：
LS=(a1,a2,...,an)
其中，ai(1<=i<=n)既可以是单个元素，又可以是广义表，分别称为原子和子表。
广义表的长度是指广义表中元素的个数。
广义表的深度是指广义表展开后所含的括号的最大层数。
1.广义表的基本操作
包括：查找、插入、删除等操作。
取表头：非空广义表的第一个元素称为表头，它可以是一个单元素，也可以是一个子表。
取表尾：在非空广义表中，除表头元素之外，由其余元素所构成的表称为表尾。（非空广义表的表尾必定是一个表。）
2.广义表的特点
- 可以是多层次的结构，广义表的元素可以是子表，而子表的元素还可以是子表；
- 表中元素可以是已经定义的广义表的名字，一个广义表可被其他广义表所共享；
- 可以是一个递归的表，表中元素也可以是广义表的名字。
3.广义表的存储结构
由于广义表中的元素本市又可以具有结构，它是一种带有层次的非线性结构，因此通常采用链式存储结构。
广义表（a,(b,c,d)）的存储结构示意图
网友评论