Titan笔记

  • 首页
  • Java
  • 数据结构
  • C语言
  • Web
  • 杂谈
  • 移动开发
  • 逸笔挥墨
Titan笔记
分享学习,研究与开发的点滴记忆
  1. 首页
  2. 数据结构
  3. 正文

[数据结构] 稀疏矩阵的存储

2020年4月4日 950点热度 5人点赞 0条评论

【问题描述】

稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

【基本要求】

以三元组顺序表表示稀疏矩阵,实现两个矩阵相加、相减的运算。稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。

[数据结构] 稀疏矩阵的存储插图
稀疏矩阵加减法例子

【Talk is cheap, show you the code】

#include<iostream>
// By Titan 2020-03-30
using namespace std;
typedef struct TupNode TUP;
typedef struct Matrix *TSM;

struct TupNode {
	int col;
	int row;
	int data;
};
struct Matrix {
	int cols;
	int rows;
	int nums;
	TUP data[100];
};

TSM inputData(int rows,int cols) {
	int a[rows][cols];
	for(int i=0; i<rows; i++) {
		for(int j=0; j<cols; j++) {
			cin>>a[i][j];
		}
	}
	TSM T=new Matrix;
	T->rows=rows;
	T->cols=cols;
	T->nums=0;
	for(int i=0; i<rows; i++) {
		for(int j=0; j<cols; j++) {
			if(a[i][j]!=0) {
				T->data[T->nums].data=a[i][j];
				T->data[T->nums].row=i;
				T->data[T->nums].col=j;
				T->nums++;
			}
		}
	}
	return T;
}

void printTSM(TSM T) {
	if(!T) {
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	} else if(T->nums<=0) {
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	}
	cout<< "Total Rows:" << T->rows << endl<<"Total Columns: " << T->cols << endl;
	cout<< "Non-Zero Elements Count: "<<T->nums<<endl;
	cout<<"--------------------------------------------------------"<<endl;
	cout<<"Row\tColumn\tData"<<endl;
	for(int i=0; i<T->nums; i++) {
		cout<<T->data[i].row
		    <<"\t"<<T->data[i].col
		    <<"\t"<<T->data[i].data
		    <<endl;
	}
}
void printAsArray(TSM T){
	if(!T){
		cout<<"Invalid TSMatrix!"<<endl;
		return;
	}
	int a,b,col,row,data;
	a=T->cols;
	b=T->rows;
	int arr[a][b];
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			arr[i][j]=0;
		}
	}
	for(int i=0;i<T->nums;i++){
		col=T->data[i].col;
		row=T->data[i].row;
		data=T->data[i].data;
		arr[row][col]=data;
	}
	for(int i=0;i<b;i++){
		for(int j=0;j<a;j++){
			cout<<arr[i][j]<<"\t";
		}
		cout<<endl;
	}
}
void insertTSM(TSM T,int data,int row,int col){
	if(!T){
		return;
	}
	bool flag=true;
	for(int i=0;i<T->nums;i++){
		if(T->data[i].col==col && T->data[i].row == row){
			T->data[i].data+=data;
			if(T->data[i].data==0){
				for(int j=T->nums-1;j>i;j--){
					T->data[j-1]=T->data[j];
				}
				T->nums--;
			}
			flag=false;
			break;
		}
	}
	if(flag){
		T->data[T->nums].col=col;
		T->data[T->nums].row=row;
		T->data[T->nums].data=data;
		T->nums++;
	}

}
TSM addTSM(TSM T1,TSM T2){
	if(T1->cols!=T2->cols || T1->rows!=T2->rows){
		return NULL;
	}
	TSM NT=new Matrix();
	NT->cols=T1->cols;
	NT->rows=T1->rows;
	NT->nums=0;
	for(int i=0;i<T1->nums;i++){
		insertTSM(NT,T1->data[i].data,T1->data[i].row,T1->data[i].col);
	}
	for(int i=0;i<T2->nums;i++){
		insertTSM(NT,T2->data[i].data,T2->data[i].row,T2->data[i].col);
	}
	return NT;
}

TSM subTSM(TSM T1,TSM T2){
	for(int i=0;i<T2->nums;i++){
		T2->data[i].data=-T2->data[i].data;
	}
	return addTSM(T1,T2);
}

int main() {
	int a,b,choice=-1;
	cout<<"Please input the total rows and columns:"<<endl;
	cin>>a>>b;
	TSM T1=inputData(a,b);
	printTSM(T1);
	cout<<"Please input the total rows and columns:"<<endl;
	cin>>a>>b;
	TSM T2=inputData(a,b);
	printTSM(T2);
	TSM NewT;
	cout<<"Please select the action(0=Addition,1=Subtraction:)"<<endl;
	while(choice !=0 && choice!=1){
		cin>>choice;
		if(choice==0){
			NewT=addTSM(T1,T2);
		}else if(choice==1){
			NewT=subTSM(T1,T2);
		}else{
			cout<<"Invilid Choice!"<<endl;
		}
	}
	cout<<"The New TSMatrix is:"<<endl; 
	printTSM(NewT);
	cout<<"------------------------------------"<<endl;
	cout<<"The New Matrix is:"<<endl; 
	printAsArray(NewT);
}
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2022年12月9日

Titan

不为岁月流逝蹉跎,不为潮流的势头去附和

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论
最新 热点 随机
最新 热点 随机
Docker配置IPv6容器网络支持 什么是Elastic Stack,ELK的发展历程 K8s中Pod的基本概念 云原生 - 浅谈容器基础与K8S架构设计 腾讯Serverless体验,使用TypeScript编写并部署云函数 Go-Proxy-Checker,一款基于Go编写的高性能代理服务器验证工具
[Web] CSS 中 Display(显示) 与 Visibility(可见性)的区别与用法 [数据结构] 稀疏矩阵的存储 [PHP框架] ThinkPHP6 介绍、安装及配置 关于Hive使用的一些实例 Jetbrains(IDEA)免费教育订阅申请指南 Python爬虫获取豆瓣TOP250电影详情
分类
  • Android
  • C语言
  • Elasticsearch
  • Hadoop
  • Hive
  • Java
  • JavaWeb
  • Kubernetes
  • Linux运维之道
  • Mybatis学习笔记
  • Python
  • SpringCloud
  • Web
  • Web前端
  • Web后端
  • 云原生
  • 并发编程
  • 开发工具
  • 数据库
  • 数据结构
  • 杂谈
  • 移动开发
  • 移动测试
  • 诗词歌赋
  • 软件测试
  • 逸笔挥墨
  • 随摘
标签聚合
二叉树 Mybatis学习笔记 JavaWeb Python Java 数据结构 链式存储 Apache-Hive

COPYRIGHT © 2013-2021 Titan. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

豫ICP备20001822号-1

豫公网安备 41010502004418号