稀疏矩阵的加法和乘法(三元组)

这篇具有很好参考价值的文章主要介绍了稀疏矩阵的加法和乘法(三元组)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基本思路:

三元组方法:主要的特点就是最后的结果矩阵均由三元组的形式来表达,调用函数再以矩阵形式输出

(1)稀疏矩阵加法

(下图参考懒猫老师《数据结构》课程相关笔记)

稀疏矩阵的乘法,数据结构初步,c语言,数据结构,算法

 这里与普通矩阵加法不同的是,稀疏矩阵的三元组在加法计算时,如果两个矩阵中的元素相加不为0时,才调用添加元素函数添加到和矩阵三元组中(最后的和矩阵也是一个三元组)

(2)稀疏矩阵乘法

稀疏矩阵的乘法,数据结构初步,c语言,数据结构,算法

 同样,在进行稀疏矩阵的乘法运算时,计算结果矩阵的元素时,要前两个矩阵在该位置的和不为0,才调用添加元素函数添加到结果矩阵三元组

完整代码:

(稀疏矩阵(顺序).h--用来实现稀疏矩阵的基本操作和加乘功能;稀疏矩阵加乘.c--用来对稀疏矩阵的加乘操作进行验证)

(1)稀疏矩阵(顺序).h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
typedef int DataType;

typedef struct Triple {
	int row, col; //行号,列号
	DataType item;//非零元素
} Triple;

typedef struct Matrix {
	int num;//非零元素的个数
	int mu;//矩阵的行数
	int nm;//矩阵的列数
} Matrix;

void TripleMatrix(Triple *data) { //初始化
	for (int i = 0; i < MAX; i++) {
		data[i].row = -1;
		data[i].col = -1;
	}
}

void printTriple(Triple *data) { //打印三元组
	int i = 0;
	printf("生成的三元组为:(行,列,非零元素)\n");
	while (data[i].row != -1) {
		printf("(%d,%d,%d)\n", data[i].row, data[i].col, data[i].item);
		i++;
	}
}

void printfMatrix(Triple *data, Matrix *datasum) { //打印矩阵
	printf("矩阵为:\n");
	int matirx[datasum->mu][datasum->nm];
	for (int i = 0; i < datasum->mu; i++) { //先将矩阵初始化为全0阵
		for (int j = 0; j < datasum->nm; j++) {
			matirx[i][j] = 0;
		}
	}
	for (int k = 0; k < datasum->num; k++) { //将稀疏矩阵中的值赋进去
		matirx[data[k].row - 1][data[k].col  - 1] = data[k].item; //行列值记得减1
	}
	for (int i = 0; i < datasum->mu; i++) { //打印
		for (int j = 0; j < datasum->nm; j++) {
			if (j == datasum->nm - 1)
				printf("%-5d\n", matirx[i][j]);
			else
				printf("%-5d ", matirx[i][j]);
		}
	}
}

void setItem(Triple *data, int row, int col, DataType item) { //添加元素
	Triple *str = data;
	Triple temp, temp1;
	int flag = 1; //控制两种储存交替进行
	int type = 0; //控制最后一个插入的是新元素还是原来存在temp和temp1中的元素
	while (str->row != -1 || str->col != -1) {
		if (str->row > row || (str->row == row && str->col > col)) { //插在前面
			temp = *str;
			str->row = row;
			str->col = col;
			str->item = item;
			str++;
			while (str->row != -1) {
				if (flag == 1) {
					temp1 = *str;
					*str = temp; //temp准备存储下一个
					str++;
					flag = 2;
				} else if (flag == 2) {
					temp = *str;
					*str = temp1; //temp1准备存储下一个
					str++;
					flag = 1;
				}
			}
			if (flag == 1) //最后一个元素在temp中
				type = 1;
			else if (flag == 2) //最后一个元素在temp1中
				type = 2;
		} else if (str->row < row || str->row == row) {
			str++;
		}
	}
	//前面都没有添加进去,就添加到末尾
	//或者存入temp或temp1中的需要在最后添加进去
	if (type == 0) {
		str->col = col;
		str->row = row;
		str->item = item;
	} else if (type == 1) {
		*str = temp;
	} else if (type == 2) {
		*str = temp1;
	}
}

DataType getItem(Triple *data, int row, int col, Matrix *datasum) { //根据行号列号获取矩阵元素
	if (row > datasum->mu || col > datasum->nm)
		printf("该坐标不在矩阵内!\n");
	for (int i = 0; i < datasum->num; i++) {
		if (data[i].row == row && data[i].col == col)
			return data[i].item;
	}
	return 0;
}

void addMatrix(Triple *data1, Triple *data2, Matrix *datasum1, Matrix *datasum2, Triple *add,
               Matrix *addsum) {//这个传参是真的无语
	if (datasum1->mu != datasum2->mu || datasum1->nm != datasum2->nm) {//不满足加法法则
		printf("violation of calculation rules!\n");
	}
	DataType item;
	addsum->num = 0;
	addsum->mu = datasum1->mu;
	addsum->nm = datasum1->nm;
	for (int i = 0; i < datasum1->mu; i++) {
		for (int j = 0; j < datasum1->nm; j++) {
			item = getItem(data1, i + 1, j + 1, datasum1) + getItem(data2, i + 1, j + 1, datasum2);
			if (item != 0) {//不是零就加入新的三元组中
				setItem(add, i + 1, j + 1, item);
				addsum->num++;
			}
		}
	}
}

void mulMatrix(Triple *data1, Triple *data2, Matrix *datasum1, Matrix *datasum2, Triple *mul, Matrix *mulsum) {
	if (datasum1->nm != datasum2->mu) { //不满足乘法法则
		printf("violation of calculation rules!\n");
	}
	mulsum->mu = datasum1->mu;
	mulsum->nm = datasum2->nm;
	mulsum->num = 0;
	int sum;
	for (int i = 0; i < datasum1->mu; i++) { //换第一个矩阵行
		for (int j = 0; j < datasum2->nm; j++) { //换第二个矩阵列
			sum = 0;
			for (int k = 0; k < datasum2->mu; k++) { //换第二个矩阵行
				sum += getItem(data1, i + 1, k + 1, datasum1) * getItem(data2, k + 1, j + 1, datasum2);
			}
			if (sum != 0) {//不是零就加入新的三元组中
				setItem(mul, i + 1, j + 1, sum);
				mulsum->num++;
			}
		}
	}
}

(2)稀疏矩阵加乘.c

#include "稀疏矩阵(顺序).h"

main() {
	Triple data1[MAX];
	TripleMatrix(data1);
	Triple data2[MAX];
	TripleMatrix(data2);
	Matrix datasum1;
	Matrix datasum2;
	printf("请输入第1个矩阵初始的行,列和非零元个数:");
	scanf("%d %d %d", &datasum1.mu, &datasum1.nm, &datasum1.num);
	initMatrix(data1, datasum1.num);
	printf("请输入第2个矩阵初始的行,列和非零元个数:");
	scanf("%d %d %d", &datasum2.mu, &datasum2.nm, &datasum2.num);
	initMatrix(data2, datasum2.num);
	printf("请确认您的输入:\n");
	printf("第1个");
	printfMatrix(data1, &datasum1);
	printf("第2个");
	printfMatrix(data2, &datasum2);
	printf("如果要进行相加操作,请输入1;如果要进行相乘操作,请输入2:");
	int type;
	scanf("%d", &type);
	if (type == 1) {
		Triple add[MAX];
		TripleMatrix(add);
		Matrix addsum;
		addMatrix(data1, data2, &datasum1, &datasum2, add, &addsum);
		printf("相加后矩阵为:\n");
		printfMatrix(add, &addsum);
	} else if (type == 2) {
		Triple mul[MAX];
		TripleMatrix(mul);
		Matrix mulsum;
		mulMatrix(data1, data2, &datasum1, &datasum2, mul, &mulsum);
		printf("相乘后矩阵为:\n");
		printfMatrix(mul, &mulsum);
	}
}

void initMatrix(Triple *data, int num) {
	int row, col;
	DataType item;
	for (int i = 0; i < num; i++) { //乱序的,不用从大到小
		printf("请依次输入行,列和非零元:");
		scanf("%d %d %d", &row, &col, &item);
		setItem(data, row, col, item);
	}
}

(3)测试输出

稀疏矩阵的乘法,数据结构初步,c语言,数据结构,算法

稀疏矩阵的乘法,数据结构初步,c语言,数据结构,算法

 (验证一下矩阵乘法~这里用的matlab)答案是一致的!

稀疏矩阵的乘法,数据结构初步,c语言,数据结构,算法

 初学小白,有错误欢迎指正喔!~文章来源地址https://www.toymoban.com/news/detail-797756.html

到了这里,关于稀疏矩阵的加法和乘法(三元组)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构·练习·三元组表法实现稀疏矩阵的转置

    一、问题描述 一个mxn的矩阵A,它的转置矩阵B是一个nxm矩阵,且A[i][j]=B[j][i],0=i=m-1,0=j=n-1,即A的行是B的列,A的列是B的行。 用三元组表对稀疏矩阵进行压缩存储,再进行时间复杂度O(n)的快速转置,最后输出稀疏矩阵。 其中m=4,n=5 二、算法概述 1、问题分析 1)压缩 2)转置

    2024年02月04日
    浏览(44)
  • 【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月05日
    浏览(44)
  • 数组:矩阵快速转置 矩阵相加 三元组顺序表/三元矩阵 随机生成稀疏矩阵 压缩矩阵【C语言,数据结构】(内含源代码)

    目录 题目: 题目分析: 概要设计: 二维矩阵数据结构: 三元数组三元顺序表顺序表结构: 详细设计: 三元矩阵相加: 三元矩阵快速转置: 调试分析: 用户手册: 测试结果:  源代码: 主程序:  头文件SparseMatrix.h:  头文件Triple.h: 总结: 稀疏矩阵A,B均采用 三元组

    2023年04月26日
    浏览(63)
  • 【数据结构】稀疏矩阵的压缩存储(三元组表、十字链表)(C语言)

    稀疏矩阵 是指矩阵中大多数元素为零的矩阵。从直观上讲,当非零元素个数低于总元素的30%时,这样的矩阵为稀疏矩阵。 1.1 三元组表的存储结构 稀疏矩阵的三元组表表示法是指只存储非零元素,同时存储该非零元素在矩阵中所处的行号和列号的位置信息。 为方便处理,将

    2023年04月16日
    浏览(42)
  • 【数据结构】稀疏矩阵存储的三种方法及三元组表示稀疏矩阵转置算法的两种实现 —— C++

    1. 三元组顺序表数据结构 注意:data[]中的元素是按行存储或者按列存储的,所以 在将三元组逆置时,不能简单地将行列下标对换,data[]数组中元素的顺序也需要重新排列 2. 三元组表示稀疏矩阵转置算法1 3. 三元组表示稀疏矩阵转置算法2:快速转置 为了 便于随机存取任意一

    2024年02月05日
    浏览(44)
  • 【数据结构与算法】 完成用十字链表存储的稀疏矩阵的加法运算

       Qestion:   完成用十字链表存储的稀疏矩阵的加法运算。 获取两个稀疏矩阵总有多少个非零元素,记作 cnt 。 当 cnt 不为零时一直循环,每循环一次 i++ ,也就是行循环,每循环一次就转移至下一行。 先从第一行开始循环,使得两个工作指针 p 、 q 分别指向两个稀疏矩阵

    2024年02月13日
    浏览(44)
  • [数据结构(C语言版本)上机实验]稀疏矩阵的三元组顺序表压缩存储以及转置实现(含快速转置)

    实现效果: 1、编写程序任意 输入 一个稀疏矩阵,用 三元组顺序表 压缩存储 稀疏矩阵 。 2、对稀疏矩阵进行 转置 , 输出 转置后的矩阵。 对应《数据结构(C语言版)》 第5章 数组与广义表 实验: 1、 掌握下三角矩阵的输入、输出、压缩存储算法; 2、 理解稀疏矩阵的三元

    2024年02月03日
    浏览(45)
  • 浙大数据结构第二周02-线性结构2 一元多项式的乘法与加法运算

    设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 输出分2行,分别以指数递降方式输出乘积多项式

    2024年02月13日
    浏览(51)
  • 数据结构— 数组、特殊矩阵、稀疏矩阵

    💟作者简介:大家好呀!我是 路遥叶子 ,大家可以叫我 叶子 哦! ❣️     📝个人主页:【路遥叶子的博客】 🏆博主信息: 四季轮换叶 , 一路招摇胜!      专栏 【数据结构-Java语言描述】  【安利Java零基础】 🐋希望大家多多支持😘一起进步呀!~❤️ 🌈若有帮助

    2024年02月02日
    浏览(53)
  • 【开卷数据结构 】稀疏矩阵

    🌺稀疏矩阵 🍁矩阵与稀疏矩阵的定义 🌺稀疏矩阵的转置 🍁详细思路 🍀思路一 🍀思路二 🌺稀疏矩阵的乘法 🍁详细思路 Q:什么是矩阵 A: 数学上,一个 矩阵 由 m 行 n 列的元素组成,是一个 m 行,n 列的表,m 和 n 是矩阵的 维度 。一般地,写作 mxn(读作“m乘n”)来指

    2024年01月19日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包