三元组表示稀疏矩阵并相加

一、实验题目：

要求稀疏矩阵用三元组结构存储，实现矩阵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");
    }
}

五、运行结果截图

内容:

        编写程序用三元组表示稀疏矩阵的案列转置操作。本设计使用三元组表来实现。

算法分析

        本题要完成的是三元组表实现稀疏矩阵按列转置操作。首先就是要设立三个函数。函数InitSPNode()用来建立一个稀疏矩阵的三元组表，就是要输入行数、列数和非零元的值，最后要用（-1，-1，-1）来结束输入；第二函数showMatrix()用来输出稀疏矩阵，算法中按矩阵a的列进行循环处理，对a的每一列扫描三元组，找出相应的元素，若找到了，则交换其行号与列号，并存储到矩阵b的三元组中。最后用函数TransposeSMatrix()用来完成稀疏矩阵的转置算法。算法主要的工作是在配合col的两重循环中完成，时间复杂度为（n*t）。如果非零元素个数t和m*n同数量级，则算法的时间复杂度变为O（m*n²）

概要设计

用三元组表实现系数矩阵的基本操作

程序运行流程图如下：

#include<stdio.h>
#include<string.h>
#define Ok 1
#define MAX 10//用户自定义三元组表最大长度
typedef struct//定义三元组表
{
	int i, j;//行，列
	int v;//非0数组中的值
}SPNode;
typedef struct//定义三元组表
{
	int m;//矩阵行
	int n;//矩阵列
	int t;//矩阵中的非零元素（三元组表的长度）
	SPNode date[MAX];
}SPMatrix;
void InitSPMatrix(SPMatrix* a)//输入三元列表
{
	int i, j, k, val, maxrow, maxcol;
	maxrow = 0;
	maxcol = 0;
	i = j = 0;
	k = 0;
	while (i != -1 && j != -1)//rol=-1&&col=-1结束输入
	{
		printf("输入（行 列 值）");
		scanf_s("%d,%d,%d", &i, &j, &val);
		a->date[k].i = i;
		a->date[k].j = j;
		a->date[k].v = val;
		if (maxrow < i) maxrow = i;//获得最大的列和行，以便于得到矩阵的列和行
		if (maxcol < j) maxcol = j;
		k++;
	}
	a->m = maxrow;
	a->n = maxcol;
	a->t = k-1;//矩阵中非零元素的数
}
void showMatrix(SPMatrix *a)
{
	int p, q;
	int t = 0;
	for (p = 0; p <= a->m; p++)//这个是行循环，p代表p+1行
	{
		for (q = 0; q <= a->n; q++)//这个是列循环，q代表q+1列
		{
			if (a->date[t].i== p && a->date[t].j == q)//遍历循环输出有v的元素
			{
					printf("%d", a->date[t].v);
					t++;
			}
			else printf("0");//if不成立说明该位置没有输入元素，则输出0
		}
		printf("\n");//一行结束以后进行换行处理
	}
}
void TransposeSMatrix(SPMatrix* a, SPMatrix* b)
{
	int q, col, p;
	b->m = a->n;//行列转换
	b->n = a->m;
	b->t = a->t;
	if (b->t)
	{
		q = 0;
		for(col=0;col<=a->n;++col)//遍历整个矩阵进行置换
			for(p=0;p<a->t;++p)
				if (a->date[p].j == col)
				{
					b->date[q].i = a->date[p].j;
					b->date[q].j = a->date[p].i;
					b->date[q].v = a->date[p].v;
					++q;
				}
	}
}
void main()
{
	SPMatrix a, b;
	printf("\n结束请输入（-1，-1，-1）\n");
	InitSPMatrix(&a);
	printf("输入矩阵为：\n");
	showMatrix(&a);
	TransposeSMatrix(&a, &b);
	printf("输出矩阵为：\n");
	showMatrix(&b);//转置后
}

1. 稀疏矩阵

  一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数 t 很小时，即$s < t$，称该矩阵为稀疏矩阵。

  比如：在一个100×100的矩阵中，其中只有100个非零元素，而非零元素相对于矩阵中的元素总个数10000很小，那么该矩阵为稀疏矩阵。

2. 稀疏矩阵的压缩存储方法

  对于稀疏矩阵来说，如果我们还是用100×100的方式来存储的话，显然是非常浪费的，因此我们可以采用一种稀疏矩阵的压缩存储方式，即三元组方式。

  三元组方式存储数据的策略是只存储非零元素。但是稀疏矩阵中非零元素的分布是没有任何规律的，在这种情况下，存储方案是：
1.存储非零元素

2.同时存储该非零元素所对应的行下标和列下标

3.稀疏矩阵中的每一个非零元素需由一个三元组(i, j, $a_{ij}$)唯一确定,稀疏矩阵中的所有非零元素构成三元组线性表，三元组中的i就是行下标，j是列下标，$a_{ij}$是对应的元素值。

图1-稀疏矩阵的压缩存储

  拿稀疏矩阵中的元素1来说，该元素的位置为第0行，第2列，在用三元组（i ，j ，aij）进行存储时，就是0 2 1，我们发现在这个三元组的线性表中，每个数据元素都是以三元组的方式组成的。

3. 定义存储结构

  当我们确定三元组的存储策略后，下一步我们要做的就是如何把这样的三元组存储下来。我们在进行保存时，需要把矩阵中的行数，列数，非零元素个数，矩阵中的数据都保存在data数据域（数组），在data数据域中的每个数据元素都是以三元组（行号，列号，元素值）形式存储，data域中表示的非零元素通常以行序为主序顺序排列，下标按行有序的存储结构。如图2所示：

图2-定义存储结构

  当定义好这样的存储结构后，我们可以使用计算机程序设计语言来实现这样的存储结构，如下所示：

#define MaxSize 100

//定义三元组线性表中的数据元素存储结构
typedef struct
{
    int row;        //行号
    int col;        //列号
    ElemType d;     //元素值，ElemType为数据元素类型

} TupNode; //三元组定义


//定义三元组线性表存储结构
typedef struct
{
    int rows;                   //行数值
    int cols;                   //列数值
    int nums;                   //非零元素个数
    TupNode data[MaxSize];      //data数据域

} TSMatrix; //三元组顺序表定义

4. 稀疏矩阵的三元组基本运算

算法：以行序方式扫描二维矩阵A，将其非零的元素加入到三元组t。
要求为data域以行序为主序顺序排列

图中是采用6行7列的稀疏矩阵作为说明，但是在下面的算法中以3行4列说明

//以行序方式扫描二维矩阵A，将其非零的元素加入到三元组t
//以3行4列的稀疏矩阵为例
void CreatMat(TSMatrix *t, int arr[3][4])
{
    int i;
    int j;
    t->rows = 3;
    t->cols = 4;
    t->nums = 0;

    //扫描矩阵中的非零元素
    for(i = 0; i < 3; i++)
    {
        for(j = 0; j < 4; j++)
        {
            //只存非零值，以三元组方式
            if(arr[i][j] != 0)
            {
                t->data[t->nums].row = i;
                t->data[t->nums].col = j;
                t->data[t->nums].d = arr[i][j];
                t->nums++;
            }
        }
    }
}

算法：将指定位置的元素值赋给变量x：执行x=arr[ i ] [ j ]

//将三元组线性表中指定位置的元素值赋值给变量x
void arr_Assign(TSMatrix t , int *data , int i , int j)
{
    int k = 0;
    //i和j是否合法
    if(i >= t.rows || j >= t.cols)
    {
        return;
    }

    //找到指定元素的行下标
    while(k < t.nums && i > t.data[k].row)
    {
        k++;
    }

    //当找到指定元素的行下标后，再找到指定元素的列下标
    while (k < t.nums && i == t.data[k].row && j > t.data[k].col)
    {
        k++;
    }
    //如果指定元素的行和列都相等，说明找到了
    if(t.data[k].row == i && t.data[k].col)
    {
        *data = t.data[k].d;
    }
    else
    {
        //说明没找到
        *data = 0;
    }
}

算法：三元组元素赋值：执行A[ i ] [ j ] = x
1. 将一个非0元素修改为非0值，如A[ 5 ] [ 6 ] = 8

将矩阵A中第5行，第6列的元素的值改为8，即修改三元组线性表中的数据元素的值。

2.将一个0元素修改为非0值，如A[ 3 ] [ 5 ] = 8

将矩阵A中第3行，第6列值为0的元素改为8，这时需要在三元组线性表数组中下标为3的位置往后插入一个数据元素

//修改三元组元素中的值：执行A[i][j]=x
void arr_Value(TSMatrix *t , int data , int i , int j)
{
    int k = 0;
    int k1;
    //指定的行和列是否合法
    if(i >= t->rows || j >= t->cols)
    {
        return;
    }
    //先查找行
    while(k < t->nums && i > t->data[k].row)
    {
        k++;
    }

    //查找列
    while(k < t->nums && i == t->data[k].row && j > t->data[k].col)
    {
        k++;
    }

    //当找到指定位置时直接修改
    if(i == t->data[k].row && j == t->data[k].col)
    {
        t->data[k].d = data;
    }
    else
    {
        //如果指定位置不存在，则说明该元素值为0，此时插入
        for(k1 = t->nums; k1 >= k; k1--)
        {
            t->data[k1+1].col = t->data[k1].col;
            t->data[k1+1].row = t->data[k1].row;
            t->data[k1+1].d = t->data[k1].d;
        }
        //插入数据
        t->data[k].row = i;
        t->data[k].col = j;
        t->data[k].d = data;
        t->nums++;
    }
}

输出三元组：从头到尾扫描三元组t,依次输出元素值

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(" ------------------\n");
    //输出所有的三元组
    for(i = 0; i < t->nums; i++)
    {
        printf("\t第%d行\t第%d列\t%d\n" , t->data[i].row , t->data[i].col, t->data[i].d);
    }
}

5. 测试

int main(void)
{
    //通过自定义3行4列的二维数组来表示稀疏矩阵
    int arr[3][4] = {
                    {0 , 1 , 0 , 0},
                    {0 , 0 , 0 , 2},
                    {3 , 0 , 0 , 4}
                    };

    int data = 0;
    TSMatrix t = {0};
    CreatMat(&t , arr);
    //输出三元组
    DispMat(&t);
    //获取稀疏矩阵指定位置的值,data的值应该为1才对
    arr_Assign(t, &data , 0 , 1);
    printf("---------------\n");
    printf("第0行第1列的数据元素值：%d\n\n" , data);
    printf("----------------\n");

    //将稀疏矩阵第0行第0列元素的值设置为1
    arr_Value(&t , data , 0 , 0);
    //输出三元组
    DispMat(&t);
    return 0;
}

运行结果：