三元组表示稀疏矩阵并相加
一、实验题目：
要求稀疏矩阵用三元组结构存储，实现矩阵A+B=C,并采用矩阵形式显示结果。
二、实验思路：
定义两个结构体，Triple结构体用来存放每一个非零元素的信息（行标，列标，数值），Tripledata用来存放两个三元组矩阵的信息（行数，列数，非零元素的个数）。每一个三元组结构都需要调用这两个结构体，两个结构体共同组成一个稀疏矩阵的信息。定义两个二维数组将所有元素赋值为0，然后再在非零元素位置进行赋值操作，输出打印矩阵。最后用第三个数组存放前两个数组相加的结果。
三、流程图解析：
主函数：



打印矩阵



矩阵相加



实验代码:
#include <stdio.h>
#include <stdlib.h>

typedef struct threetuple{
    int x;//表示非零元素的行标
    int y;//表示非零元素的列标
    int value;//表示非零元的值
}Triple;//用来存放三元组中每一个非零元素的信息

typedef struct infor
{
    int col;//列数
    int row;//行数
    int counts;//存放非零元的个数
}Tripledata;//用来存放三元组矩阵的信息

void printtuple(Triple m[],Tripledata n,int A[n.col][n.row]);
void add_print(Tripledata n,int A[n.col][n.row],int B[n.col][n.row]);

int main()
{
    Tripledata t[2];//定义两个信息结构体来存放矩阵信息
    int i,j;
    for(i=0;i<=1;i++)//行列数信息
    {
        printf("请输入第%d个元组的信息：\n依次输入行数，列数，非零元个数\n",i+1);
        scanf("%d%d%d",&t[i].col,&t[i].row,&t[i].counts);//对非零元素进行赋值操作
    }
    if(t[0].col!=t[1].col||t[0].row!=t[1].row)
    {
        printf("该情况无法相加，程序退出");
        exit(0);
    }
    int a,b;
    a=t[0].counts;
    b=t[1].counts;
    Triple T1[a],T2[b];//定义两个非零元素信息结构体，前者对应A，后者是B
    printf("请输入每个三元组矩阵的非零元素的信息：\n");
    for(i=1,j=0;i<=t[0].counts;j++,i++)//每个三元组的信息；
    {
        printf("依次输入元组1第%d个非零元素行标,列标,数值",i);
        scanf("%d%d%d",&T1[j].x,&T1[j].y,&T1[j].value);
    }
    for(i=1,j=0;i<=t[0].counts;j++,i++)//每个三元组的信息；
    {
        printf("依次输入元组2第%d个非零元素行标,列标,数值",i);
        scanf("%d%d%d",&T2[j].x,&T2[j].y,&T2[j].value);
    }
    int A[t[0].col][t[0].row];//定义一个二维数组来存放矩阵信息
    int B[t[1].col][t[1].row];//同上
    printf("\nA的矩阵形式：");
    printtuple(T1,t[0],A);//以矩阵形式打印A
    printf("\nB的矩阵形式：");
    printtuple(T2,t[1],B);//以矩阵形式打印B
    add_print(t[0],A,B);//
    return 0;
}
void printtuple(Triple m[],Tripledata n,int A[n.col][n.row])//以矩阵形式输出两个三元祖
{
    int i,j;
    for(i=0;i<n.col;i++)
    {
        for(j=0;j<n.row;j++)
        {
           A[i][j]=0;//将所有元素赋值0
        }
    }
    for(i=0;i<n.counts;i++)
    {
        A[m[i].x-1][m[i].y-1]=m[i].value;//把三元组非零元素在对应位置赋值
    }
    for(i=0;i<n.col;i++)
    {
        printf("\n");
        for(j=0;j<n.row;j++)
        {
           printf("%2d",A[i][j]);//以矩阵形式打印
        }
    }
}
void add_print(Tripledata n,int A[n.col][n.row],int B[n.col][n.row])
{
    int i,j;
    int C[n.col][n.row];//定义一个新矩阵用来存储相加后的结果。
    printf("\n执行矩阵相加，并打印结果：\n");
    for(i=0;i<n.col;i++)
    {
        for(j=0;j<n.row;j++)
        {
            C[i][j]=A[i][j]+B[i][j];//进行矩阵相加运算
            printf("%-3d",C[i][j]);//相加和打印同时进行
        }
        printf("\n");
    }
}


五、运行结果截图

三元组稀疏矩阵快速转置Ｃ语言算法
徐光联
摘要：三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点，这里给出三元组稀疏矩阵的转置算法详细讲解，并给出Ｃ语言算法的源程序。
关键词：三元组；稀疏矩阵；快速转置
｛ｉｎｔ　ｍ，ｎ，ｔ；　　　　　　　　　　　　　　／＊　　ｍ　表示行数，　ｎ　表示列数，ｔ　表示非零元素个数　　＊／
Ｍａｔ　　ｄａｔａ［ＭＡＸＳＩＺＥ］；　　／＊　　所存储元素的最大个数　＊／)Ｓｐｍａｔｒｉｘ；
Ｓｐｍａｔｒｉｘ　ａ，ｂ；
要假定结构中ｄａｔａ域表示非零元素的三元组是以行为主顺序排列的。(算式１)表示了稀疏矩阵Ｍ和Ｎ中ｄａｔａ域的排列情况。这种表示方法，在矩阵足够稀疏的情况下，对存储空间的需求量比通常的方法少得多。
一、前　言
三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点，处理这个知识点很费时间，在教学过程中，往往受课时限制，采取略过不讲的办法，有的教材就干脆把它省去不提。日常生产和科研过程中，数字计算中大量使用了矩阵，为了减少运算量，提高运算效率，这个算法很有用处。这里给出三元组稀疏矩阵的快速转置算法详细过程，并给出Ｃ语言描述的实例。
矩阵转置定义为：　ｍ行ｎ列矩阵Ｍ(ｍ，ｎ)　转换为ｎ行ｍ列Ｎ
矩阵，即行列互换。例如：(ｎ，ｍ)
如Ｍ(３，４)转置为Ｎ(４，３)。如图－１矩阵转置。
二、数组的三元组表示与稀疏矩阵
在实际应用中，往往会遇到一种大多数元素的值为零的矩阵，只有少部分为非零元素，这些非零元素在矩阵中的分布又没有一定的规律，我们把它记作“零元素个数＞＞非零元素个数”，即零元素个数远远大于非零元素个数。这种矩阵称为稀疏矩阵(ｓｐａｒｓｅ　ｍａｔｒｉｘ)。例如，下面所示的矩阵Ｍ和它的转置矩阵Ｎ，在３０个元素中只有８个非零元素，显然是个稀疏矩阵。如图－２，稀疏矩阵Ｍ转置成Ｎ的示意图。
为了节省空间，可以
进行压缩存储，只需存储稀疏矩阵的非零元素。但是，为了实现矩阵的各种运算，除了存储非零元素的值外，还必须同时记下它所在的行和列。可以用一个三元组(ｉ，　ｊ，　ａｉｊ)唯一地确定矩阵中的一个非零元素，其中ｉ，　ｊ分别表示非零元素的行号和列号，ａｉｊ表示非零元素的值。
下面就是(算式１)式中矩阵Ｍ的(５行６列共有)８个非零元素的三元组表示：
｛　(１，１，　８)，　(１，３，　９)　，　(２，２，２)　，　(３，４，３)　，　(３，６，７)，　(４，１，６)　，　(４，３，４)　，　(５，４，５)｝
若以某种方式(以行为主或以列为主的顺序)将８个三元组排列起来，再加上一个表示矩阵Ｍ的行数，列数及非零元素的个数的特殊的三元组(５，６，８)，则所形成的表就能唯一地确定稀疏矩阵。
三元组表：　假设以顺序存储结构来表示三元组表(ｔｒｉｐｌｅｔａｂｌｅ)，则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。其结构描述如下：
ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛ｉｎｔ　Ｉ，ｊ；
ＥｌｅｍＴｙｐｅ　　ｖ；｝Ｍａｔ；
ｔｙｐｅｄｅｆ　　ｓｔｒｕｃｔ2008.No5９２
例如，　我们所说的５×６的矩阵Ｍ，若用三元组表来表示，在每个元素占一个存储单元的情况下，则只需要２７个存储单元(包括特殊三元组所占的３个单元，可以使用数组［０］单元)；若直接用二维数组，按通常办法表示，则需３０个单元。矩阵越大，越稀疏，其优越性越明显。
三、稀疏矩阵的转置算法。
矩阵的转置运算是变换元素的位置，把位于(ｉ，　　ｊ)的元素换到(ｊ，　ｉ)位置上。也就是说，把元素的行和列对换。所以一个ｍ×ｎ的矩阵Ｍ，它的转置矩阵是一个ｎ×ｍ的矩阵，且Ｎ［ｉ，ｊ］＝Ｍ［ｊ，ｉ］，其中，１≤ｉ≤ｎ，１≤ｊ≤ｍ。例如，　(算式１)中的矩阵Ｎ就是矩阵Ｍ的转置矩阵，矩阵Ｎ也是一个稀疏矩阵，其非零元素的排列情况如表－１(ｂ)所示。求矩阵Ｍ的转置矩阵Ｎ，实际上就是由表－１(ａ)求表－１(ｂ)。
从表－１可以看出，对每个非零元素而言，从Ｍ转置到Ｎ，分两步，第一步，把ａ．ｄａｔａ的第一列数和第二列数对换，得到的ｂ＇．ｄａｔａ。因为ｂ’．ｄａｔａ是按非零元素在Ｎ中的列序排列的，又因为我们已约定，ｂ．ｄａｔａ中的非零元素应按照在矩阵Ｎ中的行序排列。第二步，将ｂ’．ｄａｔａ转换成按非零元素在矩阵Ｎ中的行序排列的ｂ．ｄａｔａ。转换方法如下：
普通算法分析：按ｂ．ｄａｔａ中三元组的次序进行转置。也就是说，按照矩阵Ｍ的列序进行转置。显然，为了找到Ｍ中的每一列的所有的非零元素，需要对ａ．ｄａｔａ从第１行起整个扫描一遍。由于ａ．ｄａｔａ是以Ｍ的行序来存放每一个非零元素的，因此，这样得到的顺序恰好是ｂ．ｄａｔａ应有的顺序。其具体算法描述如下：
＃ｄｅｆｉｎｅ　　ＭａｘＳｉｚｅ　１００＃ｄｅｆｉｎｅ　　ＥｌｅｍＴｙｐｅ　ｉｎｔｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛ｉｎｔ　ｉ，ｊ；ＥｌｅｍＴｙｐｅ　ｖ；｝Ｍａｔ；
ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ

/*    
*Copyright (c) 2015 , 烟台大学计算机学院    
*All right resvered .    
*文件名称: 稀疏矩阵.cpp    
*作    者: 郑兆涵    
*稀疏矩阵的三元组表示的实现及应用（2） 
*/


问题：稀疏矩阵的三元组表示的实现及应用
（2）采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法
提示1：两个行数、列数相同的矩阵可以相加
提示2：充分利用已经建立好的算法库解决问题
提示3：教材例6.3已经给出两个稀疏矩阵相加的运算的算法，但未利用基本运算。请比较这两种方案
 
编程代码：①针对提示1，两个行数，列数相同的矩阵相加的方法

 
//头文件：tup.h，包含定义稀疏矩阵的三元组表示数据结构的代码、宏定义、要实现算法的函数的声明；
#ifndef TUP_H_INCLUDED
#define TUP_H_INCLUDED
#define M 6
#define N 7
#define MaxSize  100         //矩阵中非零元素最多个数
typedef int ElemType;
typedef struct
{
    int r;                  //行号
    int c;                  //列号
    ElemType d;             //元素值
} TupNode;                  //三元组定义
typedef struct
{
    int rows;               //行数
    int cols;               //列数
    int nums;               //非零元素个数
    TupNode data[MaxSize];
} TSMatrix;                 //三元组顺序表定义
void CreatMat(TSMatrix &t,ElemType A[M][N]);  //从一个二维稀疏矩阵创建其三元组表示
bool Value(TSMatrix &t,ElemType x,int i,int j);  //三元组元素赋值
bool Assign(TSMatrix t,ElemType &x,int i,int j); //将指定位置的元素值赋给变量
void DispMat(TSMatrix t);//输出三元组
void TranTat(TSMatrix t,TSMatrix &tb);//矩阵转置
#endif // TUP_H_INCLUDED


//源文件：tup.cpp，包含实现各种算法的函数的定义 
#include "stdio.h"
#include "tup.h"
void CreatMat(TSMatrix &t,ElemType 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++)//源文件：tup.cpp，包含实现各种算法的函数的定义 
            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++;
            }
    }
}
bool Value(TSMatrix &t,ElemType 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
}
bool Assign(TSMatrix t,ElemType &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
}
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);
}
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++;
                }
    }
}


//编制main函数，完成相关的测试工作 
#include <stdio.h>
#include "tup.h"
bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
    int i,j;
    ElemType va,vb,vc;
    if (a.rows!=b.rows || a.cols!=b.cols)
        return false;                        //行数或列数不等时不能进行相加运算
    c.rows=a.rows;
    c.cols=a.cols;       //c的行列数与a的相同
    c.nums=0;
    for(i=0; i<M; i++)
        for(j=0; j<N; j++)
        {
            Assign(a,va,i,j);
            Assign(b,vb,i,j);
            vc=va+vb;
            if(vc)
                Value(c,vc,i,j);
        }
    return true;
}

int main()
{
    TSMatrix ta,tb,tc;
    int A[M][N]=
    {
        {0,0,1,0,0,0,0},
        {0,2,0,0,0,0,0},
        {3,0,0,0,0,0,0},
        {0,0,0,5,0,0,0},
        {0,0,0,0,6,0,0},
        {0,0,0,0,0,7,4}
    };
    int B[M][N]=
    {
        {0,0,10,0,0,0,0},
        {0,0,0,20,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,50,0,0,0},
        {0,0,20,0,0,0,0},
        {0,0,0,10,0,0,4}
    };
    CreatMat(ta,A);
    CreatMat(tb,B);
    printf("A:\n");
    DispMat(ta);
    printf("B:\n");
    DispMat(tb);
    if(MatAdd(ta, tb, tc))
    {
        printf("A+B:\n");
        DispMat(tc);
    }
    else
    {
        printf("相加失败\n");
    }
    return 0;
}


输出结果：


当一个矩阵中非零元素远小于矩阵中元素的个数时，如果用简单的二维数组来表示矩阵就会造成大量的空间占用, 所以引进三元组来表示稀疏矩阵。
如下：
typedef struct{
	int i , j;//表示非零元素的行列 
	int v;//矩阵的非零元素 
}SPNode;
 
typedef struct{
	int m , n , t;//表示矩阵的行，列及非零元素的个数 
	SPNode data[SMAX];//三元组表 
}SPMatrix;
 
即三元组。
以下我们就用三元组来实现矩阵的基本运算：转置
一般算法
将原三元组a的行、列、元素值装换为b的列、行、元素值；
按a的行或b的列进行循环处理：对a的每一列进行扫描，找出相应的元素，交换行号和列号。
代码：
void TransposeSMatrix(SPMatrix *a , SPMatrix *b)//转置
{
	int q , col , p;//将原三元组a的行、列、元素值装换为b的列、行、元素值；
	b -> m = a -> n;
	b -> n = a -> m;
	b -> t = a -> t;
	if(b -> t)//按a的行或b的列进行循环处理：对a的每一列进行扫描，找出相应的元素，交换行号和列号。
 
	{
		q = 0;
		for(col = 1 ; col <= a -> n ; ++col)
		{
			for(p = 0 ; p < a -> t ; ++p)
			{
				if(a-> data[p].j == col)
				{
					b-> data[q].i = a-> data[p].j;
					b-> data[q].j = a-> data[p].i;
					b-> data[q].v = a-> data[p].v;
					++q;
				}
			}
		}
	}
}
快速算法
主要思想：a中第二列的第一个非零元素等于第一列的第一个元素位置加上第一列的非零元素。
引入两个向量：num[col]和cpot[col]。
前者表示：第col列的非零元素的个数
后者表示：第col列的第一个非零元素的位置
Cpot[1] =1
      Cpot[col] = cpot[col - 1] +num[col-1]     2<=col<=n
4 将原三元组a的行、列、元素值装换为b的列、行、元素值；
5 代码：
SPMatrix *Trans(SPMatrix *a)//转置
{
	SPMatrix *b;
	int i , j ,k;
	int num[SMAX], cpot[SMAX];
	b = (SPMatrix  *)malloc(sizeof(SPMatrix));
	b->m = a -> n;
	b->n = a -> m; 
	b->t = a -> t;
	if(b -> t>0)
	{
		for(i = 1 ; i <= a-> n;i++)
		num[i] = 0;
		for(i =1 ; i <= a->t;i++)
		{
			j = a-> data[i].j;
			num[j]++;
		}
		cpot[1]=1;
for(i=2; i<=a->t;i++)
		{
			cpot[i]= cpot[i-1] + num[i-1];
		}
		for(i=1;i<=a->t;i++)
		{
			j=a->data[i].j;
			k=cpot[j];
			b->data[k].i=b->data[i].j;
			b->data[k].j=b->data[i].i;
			b->data[k].v=b->data[i].v;
			cpot[j]++;
		}
	} 
	return b;
}