目录

问题描述

数据结构

算法设计

算法流程图

 源代码

 运行结果     

​ 

---

 

问题描述

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

数据结构

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

算法设计

程序中设计了三个函数：

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

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

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

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

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

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

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

算法流程图

 源代码

/********
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);     //转置后 
}

  运行结果