矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。所以，我们不研究矩阵及其运算等，而把精力放在如何将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。

• 数组的存储结构

  一个数组的所有元素在内存中占用一段连续的存储空间。

  • 以行优先方式存储
  • 以列优先方式存储

数组 A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5，5]的地址是( A )。
A. 1175 B. 1180 C. 1205 D. 1210

• 需要注意的是，当求出数组A[0,0]到特定元素A[5,5]的那部分时，不要着急着写出地址。
  因为我们所求出来的所占空间，是A[0,0]的首地址从1开始数（或者说 从A[0,0]的首地址开始到A[5,5]的尾地址（即A[6,1]的首地址））计算时的元素个数6*6=36（即 从A[0,0]到A[5,5]，包含A[5,5]有36个元素，但是题目的起始地址一般为0。
  所以应该A[0,0]的首地址从0开始数（或者说 从A[0,5]的首地址）计算的话，则是36-1=35（即 从A[0,5]，不包含A[5,5]有35个元素）。

  例如，首地址从0开始数，即意味着当首地址为5时，只存了一个元素的空间，但是地址却是第二个元素的（首）地址。

1 抽象数据类型数组的说明
2 数组的物理结构
3 特殊矩阵的压缩存储: 对称矩阵与三对角矩阵的压缩存储
4 稀疏矩阵的压缩存储：三元组顺序表与十字链表
5 稀疏矩阵的运算（转置算法）
6 广义表的概念：概念、物理结构、递归算法

• 计算数组中给顶元素的地址
  • 数组的存储方式（按行或按列优先存放）
  • 计算给定元素的前面的元素个数s
  • 每个元素的存储空间k
  • 该元素地址=起始元素地址+s*k

特殊矩阵

特殊矩阵压缩存储后仍然具有随机存储特性。（只用计算公式即可，无需查找时间）

二维数组→线性

注意：（因为一维数组下标是从0开始的，个数要-1，相当于减掉了自身，所以只用计算前面的元素个数，）（如果一位数组从1开始，就不用-1了，那么就不是前面了，就要加上本身aij，计算自身和前面的元素个数）（如果从1开始，那么下面的公式就要+1）

对称矩阵

对称矩阵：矩阵中的元素满足\(a_{i,j}\)=\(a_{j,i}\)，另外矩阵必须是方阵。

• 问题：假设有一个n*n的对称矩阵，第一个元素是\(a_{0,0}\)，请用一种存储效率较高的存储方式将其存储在一位数组中。
• 解答：将对称矩阵A[0...n-1,0...n-1]，存放在一维数据B[n(n+1)/2]中，即 元素\(a_{i,j}\)存放在\(b_k\)中。（只存放主对角线和下三角区的元素）
  

  

注意：（因为一维数组下标是从0开始的，个数要-1，相当于减掉了自身，所以只用计算前面的元素个数，）（如果一位数组从1开始，就不用-1了，那么就不是前面了，就要加上本身aij，计算自身和前面的元素个数）

• 在数组B中（下标从0开始），位于\(a_{i,j}\)(i≥j)前面的元素个数为：
  • 第0行：1个元素
  • 第1行：2个元素
  • ...

  • 第i-1行：i个元素

    注意：0到i-1是等差序列（都是完整的）

  • 第i行（不完整）：j个元素
  • 共计i(i+1)/2+j个元素
• 元素下标k与(i,j)之间的对应关系如下：
  \[k=\begin{cases} {{i(i+1)}\over{2}}+j & \text{i≥j,下三角区及对角线}\\ {{j(j+1)}\over{2}}+i & \text{i<j,上三角区}\\ \end{cases}\]

上三角矩阵

其中下三角元素均为常数C或0的n阶矩阵称为上三角矩阵。

• 问题：假设有一个n*n的上三角矩阵，第一个元素是\(a_{0,0...n-1]，存放在一位数据B[n(n+1)/2]中，即 元素\(a_{i,j}\)存放在b_k中。（只存放主对角线和下三角区的元素）
  

  

• 在数组B中（下标从0开始），位于\(a_{i,j}\)(i≥j)前面的元素个数为：
  • 第0行：n个元素
  • 第1行：n-1个元素
  • ...

  • 第i-1行：n-(i-1)=n-i+1个元素

    注意：0到i-1是等差序列（都是完整的）

  • 第i行（不完整）：(n-i)-(n-j)=j-i个元素

    注意：n-i为第i行总元素，n-j为j及j后面的元素个数，相减则为j前面的元素个数

  • 共计i(2n-i+1)/2+j-i个元素
• 元素下标k与(i,j)之间的对应关系如下：
  \[k=\begin{cases} {{i(2n-i+1)}\over{2}}+j-i & \text{i≤j,上三角区及对角线}\\ {{n(n+1)}\over{2}} & \text{i>j,下三角区（存放常量C）（放在最后一个位置）}\\ \end{cases}\]

下三角矩阵

其中上三角元素均为常数C或0的n阶矩阵称为下三角矩阵。

• 问题：假设有一个n*n的下三角矩阵，第一个元素是\(a_{0,j}\)存放在\(b_k\)中。（只存放主对角线和下三角区的元素）
  

  

• 在数组B中（下标从0开始），位于\(a_{i,j}\)(i≥j)前面的元素个数为：
  • 第0行：1个元素
  • 第1行：2个元素
  • ...
  • 第i-1行（0到i-1是等差序列）：i个元素
  • 第i行（不完整）：j个元素
  • 共计i(2n-i+1)/2+j-i个元素
• 元素下标k与(i,下三角区及对角线}\\ {{n(n+1)}\over{2}} & \text{i<j,上三角区（存放常量C）（放在最后一个位置）}\\ \end{cases}\]

typedef struct {
    float val;
    int i;
    int j;
}Trimat;    //三元组结构体

Trimat trimat[maxSize+1];