数据结构（四）---稀疏矩阵转三元组的相关操作_稀疏矩阵如何转换成三元组表

稀疏矩阵转三元矩阵的相关操作

最近学完数据结构里面的矩阵的相关操作，在之前的矩阵的存储和操作中，就是简单的用多维数组进行存储，然后进行相关的操作。但是，这样如果一个矩阵面的有效元素只是占25%-30%或者低于这个数的时候，这样的矩阵就会被称为稀疏矩阵，如果按照以前的套路进行矩阵的操作，这样的话就比较浪费空间和时间了，所以我们需要三元组。

什么叫三元组

定义：将稀疏矩阵非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。

简单的来说，就是把稀疏矩阵里面的非0元素的行和列，还有数值这三个值记录下来，弄个表。

三元组的数据结构的定义

就是建立一个三元组的元素数据类型的结构体
然后建立一个三元组的结构体

typedef struct
{
    int r;                  //行号
    int c;                  //列号
    int d;             //元素值
} TupNode;                  //三元组定义

typedef struct
{
    int rows;               //行数
    int cols;               //列数
    int nums;               //非零元素个数
    TupNode data[MaxSize];
} TSMatrix;                 //三元组顺序表定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14

稀疏矩阵转三元组

思路蛮简单的就是遍历矩阵的数组，只要碰到非0的元素，就把它的行，列，值记载下来。

void CreatMat(TSMatrix &t,int A[M][N])  //从一个二维稀疏矩阵创建其三元组表示
{
    int i,j;
    t.rows=M;
    t.cols=N;
    t.nums=0;
    for (i=0; i<M; i++)
    {
        for (j=0; j<N; j++)
            if (A[i][j]!=0)     //只存储非零元素
            {
                t.data[t.nums].r=i;
                t.data[t.nums].c=j;
                t.data[t.nums].d=A[i][j];
                t.nums++;
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三元组的输出

这个更简单，先判断三元组里面非0元素的个数是否为0，如果是0的话，直接就返回，否的话，就输出呗

void DispMat(TSMatrix t)        //输出三元组
{
    int i;
    if (t.nums<=0)          //没有非零元素时返回
        return;
    printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
    printf("\t------------------\n");
    for (i=0; i<t.nums; i++)
        printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
}
1
2
3
4
5
6
7
8
9
10
11

矩阵的转置

矩阵的转置定义蛮简单的，就是行换成列，列换成行。

void TranTat(TSMatrix t,TSMatrix &tb)       //矩阵转置
{
    int p,q=0,v;                    //q为tb.data的下标
    tb.rows=t.cols;
    tb.cols=t.rows;
    tb.nums=t.nums;
    if (t.nums!=0)                  //当存在非零元素时执行转置
    {
        for (v=0; v<t.cols; v++)        //tb.data[q]中的记录以c域的次序排列
            for (p=0; p<t.nums; p++)    //p为t.data的下标
                if (t.data[p].c==v)
                {
                    tb.data[q].r=t.data[p].c;
                    tb.data[q].c=t.data[p].r;
                    tb.data[q].d=t.data[p].d;
                    q++;
                }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三元组指定位置的赋值和取出

在三元组里面查找，只要找到这个元素，就可以进行操作

bool Value(TSMatrix &t,int x,int i,int j)  //三元组元素赋值
{
    int k=0,k1;
    if (i>=t.rows || j>=t.cols)
        return false;               //失败时返回false
    while (k<t.nums && i>t.data[k].r) k++;                  //查找行
    while (k<t.nums && i==t.data[k].r && j>t.data[k].c) k++;//查找列
    if (t.data[k].r==i && t.data[k].c==j)   //存在这样的元素
        t.data[k].d=x;
    else                                    //不存在这样的元素时插入一个元素
    {
        for (k1=t.nums-1; k1>=k; k1--)
        {
            t.data[k1+1].r=t.data[k1].r;
            t.data[k1+1].c=t.data[k1].c;
            t.data[k1+1].d=t.data[k1].d;
        }
        t.data[k].r=i;
        t.data[k].c=j;
        t.data[k].d=x;
        t.nums++;
    }
    return true;                   `
    //成功时返回true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

bool Assign(TSMatrix t,int &x,int i,int j)  //将指定位置的元素值赋给变量
{
    int k=0;
    if (i>=t.rows || j>=t.cols)
        return false;           //失败时返回false
    while (k<t.nums && i>t.data[k].r) k++;                  //查找行
    while (k<t.nums && i==t.data[k].r && j>t.data[k].c) k++;//查找列
    if (t.data[k].r==i && t.data[k].c==j)
        x=t.data[k].d;
    else
        x=0;                //在三元组中没有找到表示是零元素
    return true;            //成功时返回true
}
1
2
3
4
5
6
7
8
9
10
11
12
13

矩阵的加减

矩阵的加减操作首先先看两个矩阵行列是否相等，如果相等才能进行操作。不然无法进行计算。
加减的思路都是一样的，下面是讲下加的算法
现在有两个三元组a,b现在可以进行加法运算，准备一个空的三元组c
遍历a,b里面所以的元素
1.当a和b的行号相等的时候，如果a的列数小于b的列数，就把a的元素加在c中，如果a的列数大于b的列数，就把b的元素加在c中，如果行号和列号都相等的时候，就把a和b的元素进行加法运算，不为0的话，就把它结果加入c中
2.当a行号大于b的行号的时候，把b的元素添加到C中
3.当a行号小于b的行号的时候，把a的元素添加到C中

bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i=0,j=0,k=0;
    int v;
    if (a.rows!=b.rows || a.cols!=b.cols)
        return 0;        //行数或列数不等时不能进行相加运算
    c.rows=a.rows;
    c.cols=a.cols;       //c的行列数与a的相同
    while (i<a.nums && j<b.nums)         //处理a和b中的每个元素
    {
        if (a.data[i].r==b.data[j].r)    //行号相等时
        {
            if(a.data[i].c<b.data[j].c)  //a元素的列号小于b元素的列号
            {
                c.data[k].r=a.data[i].r;//将a元素添加到c中
                c.data[k].c=a.data[i].c;
                c.data[k].d=a.data[i].d;
                k++;
                i++;
            }
            else if (a.data[i].c>b.data[j].c)//a元素的列号大于b元素的列号
            {
                c.data[k].r=b.data[j].r;      //将b元素添加到c中
                c.data[k].c=b.data[j].c;
                c.data[k].d=b.data[j].d;
                k++;
                j++;
            }
            else                    //a元素的列号等于b元素的列号
            {
                v=a.data[i].d+b.data[j].d;
                if (v!=0)           //只将不为0的结果添加到c中
                {
                    c.data[k].r=a.data[i].r;
                    c.data[k].c=a.data[i].c;
                    c.data[k].d=v;
                    k++;
                }
                i++;
                j++;
            }
        }
        else if (a.data[i].r<b.data[j].r) //a元素的行号小于b元素的行号
        {
            c.data[k].r=a.data[i].r;      //将a元素添加到c中
            c.data[k].c=a.data[i].c;
            c.data[k].d=a.data[i].d;
            k++;
            i++;
        }
        else                              //a元素的行号大于b元素的行号
        {
            c.data[k].r=b.data[j].r;      //将b元素添加到c中
            c.data[k].c=b.data[j].c;
            c.data[k].d=b.data[j].d;
            k++;
            j++;
`
        }
        c.nums=k;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

总结

稀疏矩阵和转三元组的操作主要想明白如何转换的，其他操作都蛮简单的。