用三元组表实现稀疏矩阵的基本操作-Toy模板网

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

问题描述

数据结构

算法设计

算法流程图

源代码

运行结果

问题描述

编写程序用三元组表实现稀疏矩阵的按列转置操作。

数据结构

本设计使用三元组表实现。

算法设计

程序中设计了三个函数：

1.函数InitSPNode()用来建立一个稀疏矩阵的三元组表。

首先输入行数、列数和非零元的值，输入（-1 ，-1，-1）结束输入。

2.函数showMatrix()用来输出稀疏矩阵。

算法中按矩阵a的列进行循环处理，对a的每一列扫描三元组，找出相应的元素，若找到，则交换其行号和列好，并存储到矩阵b的三元组中。

3.函数TransposeSMatrix()用来完成稀疏矩阵的转置算法。

算法的主要工作是在p和col的两重循环中完成，时间复杂度为O(n*t)。如果

非零元素个数t和m*n同数量级，则算法的时间复杂度变为O(m*n^2)。

算法流程图

用三元组表实现稀疏矩阵的基本操作文章来源地址https://www.toymoban.com/news/detail-435919.html

源代码

/********
date:2021-10-28
author:sy
version:1.0
Description:用三元组表实现稀疏矩阵的按列转置操作 
*********/
#include<stdio.h>
#include<string.h>
#define OK 1
#define Maxsize 10   //用户自定义三元组最大长度

/*定义三元组表*/
typedef struct  
{
	 int i,j;  //非零元素的行列 
	 int v;    //非零元素值 
 }SPNode;
/*定义三元组表*/
typedef struct  
{
 	SPNode data[Maxsize];  //三元组表 
 	int m,n,t;             //矩阵行，列及三元组表长度 
}SPMatrix;                 //三元组表的存储类型 

/*输入三元组表*/
void InitSPNode(SPMatrix*a)  
{
    int i,j,k,val,maxrow,maxcol;
	     maxrow=0;
	     maxcol=0;
	     i=j=0;
	     k=0;
    while(i!=-1&&j!=-1)  //row=-1&&col=-1结束输入
	{
	  	printf("输入（行列值）：");
	  	scanf("%d%d%d",&i,&j,&val);
	  	a->data[k].i=i;
	  	a->data[k].j=j;
	  	a->data[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++)
   	{
   		for(q=0;q<=a->n;q++)
   		{
   			if(a->data[t].i==p&&a->data[t].j==q)
   			{
   				printf(" %d  ",a->data[t].v);
   				t++;
			}
	    else printf(" 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)   /*按a的列序转置*/
		     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;
			 } 
	}
}
int main()
{
	SPMatrix a,b;
 	printf("\n 结束请输入(-1-1-1)\n"  );
 	InitSPNode(&a);
 	printf(" 输入矩阵为：\n"  );
 	showMatrix(&a);     //转置前
  	TransposeSMatrix(&a,&b);
 	printf(" 输出矩阵为: \n"  );
 	showMatrix(&b);     //转置后 
}