多维数组与广义表

对称矩阵：

对称矩阵的存储

在如下的对称数组中，可以只储存下三角中的元素。

存储方法：将下三角部分以行序为主序顺序存储到一个数组中去。在下三角中共有n(n+1)/2个元素，存储到一个数组SA[0]至SA[n(n+1)/2-1]中，存储顺序如下。

矩阵和数组的对应关系：

• 当i≥j时，下三角部分：数组数据=i(i+1)/2+j (i=行 j=列)
• 当i<j 时，上三角部分，因为aij=aji 访问和它对应的下三角中的aji即可，因此k=j(j +1)/2+i (0<=k<n(n+1)/2-1)

三角矩阵：

• 三角矩阵的特殊性是以主对角线划分矩阵。
• 主对角线任意一侧（不包括主对角线中）的元素均为常数，
• 三角矩阵又可以分为下三角矩阵（主对角线以上均为同一个常数和上三角矩阵（主对角线以下均为同一个常数）。

下三角矩阵的存储：**

类似于对称矩阵的下三角形存储，只需增加一个存储单元即可，需要n(n+1)/2+1个存储单元

• 存储图如下：

• 对应关系为：

上三角矩阵的存储：

对于上三角矩阵，其存储思想与下三角类似，也需要n(n+1)/2+1个存储单元

• 存储图与下三角矩阵一样：

• 对应关系为：

稀疏矩阵：

采用三元组表存储，将非零元素所在的行、列以及它的值构成一个三元组，然后再按某种规律存储这些三元组——三元组表，可以大大节约稀疏矩阵的存储空间。

• 存储图如下：

• 三元组表的定义：

  #define SMAX  100       // 定义一个足够大的三元组表
  typedef struct SPNode           // 定义三元组
  {    
   int i,j,v;           // 三元组非零元素的行、列和值
  } SPNode;
  typedef struct sparmatrix         // 定义稀疏矩阵
  {
   int rows,cols,terms; // 稀疏矩阵行、列和非零元素的个数
   SPNode data[SMAX];      // 三元组表
  } sparmatrix ;