稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表

前几期期链接：

1. 【数据结构】栈与队列的概念和基本操作代码实现
2. 【数据结构】树与二叉树的概念与基本操作代码实现

1.数组

k维数组的定义：
k 维数组 D ＝ { a j 1 , j 2 , . . . , j k } k维数组D＝\{ a_{j_1, j_2, ..., j_k} \} k维数组D＝{aj1​,j2​,...,jk​​}
$$k>0称为数组的维数，b_i是数组第i维的长度，j_i是数组元素第i维的下标$$
$$a_{j_1,j_2,...,j_k}属于ElemSet(元素的性质相同)，Y_i=0,...,b_i-1(i=1,2,\dots ,k)$$

1. 数组可以看作是一种特殊的线性表，即线性表数据元素本身又是一个线性表
   

2. 数组特点
   数组结构固定，每一维的大小不可变
   数据元素同构(元素性质相同)

3. 数组运算
   给定一组下标，存取、修改相应的数据元素，一般不做插入、删除操作。

2.数组的顺序表示和实现

二维数组有两种顺序映象的方式

1. 以行序为主序:从数组的第一行开始依次存放每一行的数组元素;存放第i行时，从第一列开始顺次存放
   特点：有地址计算公式，可以随机访问
   二维数组任意元素的存储地址：
   $$Loc(a_{ij})=Loc(a_{11})+[(i-1)n+(j-1)]\ast L$$
   $$Loc(a_{11})称为基地址或基址$$
   

2. 以列序为主序:
   二维数组任意元素的存储地址：
   $$Loc(a_{ij})=Loc(a_{11})+[(j-1)m+(i-1)]\ast L$$
   $$Loc(a_{11})称为基地址或基址$$

可将二维数组的行为主序和列为主序的存储方式推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系

3.特殊矩阵的压缩存储

宗旨：为值相同的矩阵元素只分配一个空间，对零元不分配存储空间.

(1) 特殊矩阵：非零元在矩阵中的分布有一定规则

1. 上（下）三角矩阵
2. 对称矩阵
3. 对角矩阵

(2.)稀疏阵：零元多，分布无规律

（1）. 上三角矩阵—列为主序压缩存储

存储方式：列为主序压缩存储和行为主序压缩存储，存储空间是一维的，将二维数组以一维方式存储。
特点：均可以随机访问数组元素。

上三角矩阵—列为主序压缩存储–数组sa[M]

(1)下三角为0时：
当i≤j时，aij为非0元，存放地址Loc(aij)的计算公式：
$$Loc(a_{ij})=Loc(a_{11})+(\frac{(j-1)\cdot j}{2}+i-1)\cdot L,(condition:i\le j)$$

一维存储空间用一维数组sa[M]表示， Loc(aij)计算公式（a11存于sa[0],地址为0 ）：
$$Loc(a_{ij})=0+(\frac{(j-1)\cdot j}{2}+i-1)\cdot 1,(condition:i\le j)$$
数组sa的大小:$$M=\frac{(n+1)\cdot n}{2}$$

aij(i≤j)存于下标为k的一维数组元素中:
$$Loc(aij)=k=\frac{(j-1)\cdot j}{2}+i-1$$

(2)下三角为常数时：
常数的存放的位置为：$$\frac{(n+1)\cdot n}{2}$$
数组sa的大小:$$M=\frac{(n+1)\cdot n}{2}+1$$

（2）. 下三角矩阵—行为主序压缩存储

存储方式：列为主序压缩存储和行为主序压缩存储，存储空间是一维的，将二维数组以一维方式存储。
行为主序压缩存储：从第一行开始依次存放每一行的“非0（C）元”

特点：均可以随机访问数组元素。

下三角矩阵—行为主序压缩存储–数组sa[M]

(1)上三角为0时：
当 j≤i时，aij为非0元，存放地址Loc(aij)的计算公式：
$$Loc(a_{ij})=Loc(a_{11})+(\frac{(i-1)\cdot i}{2}+j-1)\cdot L,(condition:j\le i)$$

一维存储空间用一维数组sa[M]表示， Loc(aij)计算公式（a11存于sa[0],地址为0 ）：
$$Loc(a_{ij})=0+(\frac{(i-1)\cdot i}{2}+j-1)\cdot 1,(condition:j\le i)$$
数组sa的大小:$$M=\frac{(n+1)\cdot n}{2}$$

aij(i≤j)存于下标为k的一维数组元素中:
$$Loc(aij)=k=\frac{(i-1)\cdot i}{2}+j-1$$

上三角为常数时：
常数的存放的位置为：$$\frac{(n+1)\cdot n}{2}$$
数组sa的大小:$$M=\frac{(n+1)\cdot n}{2}+1$$

（3）. 对称矩阵

存放方式：只存上三角阵或只存下三角阵都可以

地址计算公式 : 参考上三角和下三角矩阵的地址计算公式

（4）. 对角矩阵

对角矩阵 –2d+1对角阵：主对角线和主对角线上面d条对角线、主对角线下面d条对角线上的数据元素分布不规律，非0（C）.

2d+1 对角阵特点：**第一行和最后一行每行有d+1个数据元素**，余下每行**最多**2d+1个数据元素

压缩存储方法：第一行和最后一行每行存 d+1 个数据元素，余下每行存 2d+1 个数据元素

2d+1-对角阵行为主序压缩存储地址计算公式：
矩阵元素下标从0开始的地址计算公式：
$$Loc(a_{ij})=Loc(a_{00})+(2d+1)\ast i-d+j-(i-d)=Loc(a_{00})+(2d+1)\ast i+j-i$$
$$0\le i,j<n,|i-j|\le d$$

§矩阵元素下标从1开始的地址计算公式：
$$Loc(a_{ij})=Loc(a_{11})+(2d+1)\ast (i-1)-d+j-i+d=Loc(a_{11})+(2d+1)\ast (i-1)+j-i$$
$$1\le i,j\le n,|i-j|\le d$$

4. 稀疏矩阵

稀疏矩阵: 矩阵元素零元多，在矩阵中随机出现
假设 m行 n列的矩阵含 t个非零元素,则稀疏因子：$$\delta =\frac{t}{m\cdot n}$$
通常认为 δ ≤ 0.05 的矩阵为稀疏矩阵。

压缩存储原则：只存储每个非零元的行、列下标及其值和矩阵的行列维数

常规存储方法缺点:

(1) 零值元素占了很大空间;
(2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。

解决问题的原则:

(1) 尽可能少存或不存零值元素；
(2) 尽可能减少没有实际意义的运算；
(3) 操作方便。 即：尽可能快地找到与下标值(i,j)对应的元素，尽可能快地找到同一行或同一列的非零值元。

5. 稀疏矩阵的压缩

稀疏矩阵的压缩存储方法:

1. 三元组顺序表
2. 行逻辑联接的顺序表
3. 十字链表

（1）. 三元组顺序表

三元表结构：

//三元表结构：
typedef struct{  
    int i, j;       //非零元的行、列下标 
    int e;   //非零元的值
} Triple;

//稀疏矩阵的结构
#define MAXSIZE 100  //非零元最大个数
typedef struct{  
    Triple data[MAXSIZE + 1];       //三元组表，data[0]未用
    int mu, nu, tu; //矩阵行、列数、非零元个数
} TSMatrix;

特点：
有序的双下标法行序有序存储
便于进行依行顺序处理的矩阵运算
若需存取某一行中的非零元，需**从头开始查找**。

压缩存储后，元素aij的存储位置与其下标无关，而取决于之前的非零元个数
非零元以行为主序顺序存放

（2）. 行逻辑联接的顺序表

#define MAXRC 500 
//行逻辑联接的顺序表
typedef struct {
    Triple data[MAXSIZE + 1];
    int  rpos[MAXRC + 1]; // 每一行非0元存放的起始位置
    int  mu, nu, tu;
} RLSMatrix; // 行逻辑链接顺序表类型

（3）. 十字链表

用三元组表存储稀疏矩阵，在单纯的存储和做类似转置之类的运算时可以节约存储空间，且运算速度较快;
但当进行矩阵相加等运算时，稀疏矩阵的非零元位置和个数都会发生变化。使用三元组表必然会引起数组元素的大量移动。

1. 采用链表存放稀疏矩阵的非0元
2. 将稀疏矩阵每行的非0元按照列升序的顺序放在一个单链表中
3. 将稀疏矩阵每列的非0元按照行升序的顺序放在一个单链表中

即：
稀疏矩阵的每个非0元即位于一个行单链表，也同时位于一个列单链表
用一维数组保存每行非0元的单链表的头指针
用一维数组保存每列非0元的单链表的头指针

十字链表 ：每个非零元用含有五个域的结点表示（非零元的所在行、列、值，及同行、同列的下一个非零元）

//十字链表
typedef struct OLNode{ 

    int row, col; //非零元所在行、列
    int val; //非零元的值
    struct OLNode*right, *down;//同行、同列的下一个非零元
}OLNode,* OLink;

typedef struct{ 
    OLink rhead[M],chead[N]; //行、列指针数组
    int mu, nu, tu; //行、列数及非零元个数
}CrossList;

6. 稀疏矩阵的转置（普通转置 和 快速转置）

解决思路：

1. 将矩阵行、列维数互换，非零元个数不变
2. 将每个三元组中的i和j相互调换，非零元值不变
3. 重排次序，使T.data中元素以T的行(M的列)为主序
   

方法一（普通转置）复杂度为O(T.mu×T.nu)

按矩阵T中三元组表T.data的次序依次在矩阵M的三元组表M.data中找到相应三元组进行转置
为找到M.data中第i列所有非零元素，需对M.data扫描一遍
由于M.data以M行序为主序，所以得到的恰是T.data中应有的顺序

//复杂度为O(T.mu×T.nu)
Status TransposeSMatrix(TSMatrix M, TSMatrix &T){ 
    int col, p, k;
    T.mu=M.nu;  
    T.nu=M.mu; 
    T.tu=M.tu; 
    if(T.tu){ //有非零元，转置
        k=1;//k为T.data表下标
        for(col=1;col<=M.nu;col++)//查找M每一列的非零元
            for( p=1;p<=M.tu;p++)//扫描M的所有非零元
                if( M.data[p].j==col ){ 
                    T.data[k].i=M.data[p].j;
                    T.data[k].j=M.data[p].i;
                    T.data[k].e=M.data[p].e; 
                    k++;
                }
        return OK;
    }
    return ERROR;
}

//T(n)=O(M.nu×M.tu)
//若M.tu与M.mu×M.nu同数量级则 T(n)=O(M.mu×M.nu^2)

方法二：快速转置 复杂度O(S.nu+S.tu)

//复杂度O(S.nu+S.tu) 
//若S.tu与S.mu×S.nu同数量级则 T(n)=O(S.mu×S.nu)
void TransPose_F(TSMatrix S,TSMatrix &Transpose_S){
    //S为原来矩阵
    //Transpose_S为转置后矩阵
    Transpose_S.mu=S.nu;
    Transpose_S.nu=S.mu;
    Transpose_S.tu=S.tu;
    if(S.tu){
        //判断是否为空
        int col;//列
        int num[MAXSIZE]={0};// 记录原三元组中列号为 col 的项的数目。 辅助数组
        int cpot[MAXSIZE]={0};// 记录原三元组中列号为 col 的项在新三元组中的首位置。 辅助数组
        
        //扫描第一次 记录元素矩阵S中列数为j的个数
        for(int i=1;i<=S.tu;i++){
            //记录元素矩阵S中列数为j的个数
            num[S.data[i].j]++;
        }

        cpot[1]=1;//初始化第一个元素的地址

        //扫描第二次 记录原三元组中列号为 col 的项在新三元组中的首位置
        for(col=2;col<=S.nu;col++){
            //列号为 col 的项在新三元组中的首位置
            cpot[col]=cpot[col-1]+num[col-1];
        }

        //扫描第三次 转置
        for(int t=1;t<=S.tu;t++){
            col=S.data[t].j;//列数
            int s=cpot[col];//地址  下标

            Transpose_S.data[s].e=S.data[t].e;
            Transpose_S.data[s].i=S.data[t].j;
            Transpose_S.data[s].j=S.data[t].i;

            cpot[col]++;//下标 后移
        }
    }
}

感谢阅读！
前几期期链接：

1. 【数据结构】栈与队列的概念和基本操作代码实现
2. 【数据结构】树与二叉树的概念与基本操作代码实现