【数据结构】数组和广义表

前面讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。数组和广义表的表中的数据元素本身也是一个数据结构。

数组的定义

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
数组可以看成是对一般线性表的扩充。一维数组即为线性表，二维数组可以定义为其数据元素为一维数组的线性表。

数组的顺序表示和实现

由于数组一般不做插入或删除操作，因此采用顺序存储结构来表示数组。
由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等，具有该特点的存储结构为随机存储结构。

矩阵的压缩存储

压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间。
特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律
稀疏矩阵：非零元较零元少，且分布没有一定规律。

特殊矩阵

对称矩阵

若n阶矩阵A中的元 aij=aji(1<=i,j<=n),则A为n阶对称矩阵。
可以为每一对对称元分配一个存储空间，可将n^2个元压缩存储到n(n+1)/2个元。
现以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij存在一一对应关系：
k= i(i-1)/2+j-1 当i>=j
j(j-1)/2+i-1 当i

称sa[n(n+1)2]为n阶对称矩阵A的压缩存储。

三角矩阵

上（下）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元均为常数c或0的n阶矩阵。除了和对称矩阵一样只存储其下（上）三角中的元以外，再加一个存储常数c的存储空间即可。

稀疏矩阵

假设在mxn的矩阵中，有t个元素不为0.令δ=t/mn，称δ为矩阵的稀疏因子。δ<=0.05时称为稀疏矩阵。
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
三元组(i,j,aij)记录了非零元在矩阵的行列位置和非零元的值。
稀疏矩阵的压缩存储方法：

• 三元组顺序表
• 行逻辑链接的顺序表
• 十字链表

三元组顺序表–解决矩阵转置运算

三元组顺序又叫有序的双下标法。它的特点是非零元在表中按行序有序存储，因此便于进行按行顺序处理的矩阵运算。

/*稀疏矩阵的三元组顺序表存储表示*/
#define MAX 12500
typedef struct{
	int i,j;//非零元的行列下标
	int e;
}Triple;
typedef struct{
	Triple data[MAX+1];//非零元三元组表，data[0]未用
	int mu,nu,tu;//矩阵的行数、列数、非零元个数
}MATarix;
1
2
3
4
5
6
7
8
9
10

在data域中表示非零元的三元组是以行序为主序顺序排列的。

一般转置和快速转置实现

行逻辑链接的顺序表----解决矩阵相乘

为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。于是可以将cpot固定在稀疏矩阵的存储结构中。
这种“带行链接信息”的三元组表为行逻辑链接的顺序表

typedef struct{
	Triple data[MAX+1];
	int rpos[MAXRC+1];//MAXRC为矩阵最大行数
	int mu,nu,tu;
}RLMatrix;
1
2
3
4
5

行逻辑连接的顺序表实现稀疏矩阵乘法

十字链表-----解决矩阵相加

当矩阵的非零元个数和位置在操作过程中变化较大时，采用链式存储结构表示三元组的线性表。
在链表中，每个非零元用一个含有5个域的节点表示。
i,j,e这三个域分别表示该非零元所在行、列和非零元的值。
向右域right用以链接同一行中下一个非零元
向下域down用以链接同一列中下一个非零元。
同一行的非零元通过right于链接成一个线性链表
同一列的非零元通过down域链接成一个线性链表。
整个矩阵构成一个十字交叉的链表。
可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。
十字链表压缩存储稀疏矩阵详解

广义表的定义

广义表是线性表的推广，也叫列表（lists）

别人整理地非常清晰明了，直接跳转过去看吧。
广义表 - 广义表概念，存储结构，深度/长度，复制算法