<>稀疏矩阵压缩及转置

1、随机数生成矩阵算法思想:使用time()函数给随机数播种,获得矩阵的总行数,总列数,非零元个数。总行数与总列数的值可直接存入三元组。每次生成一个非零元的行与列之后,由键盘输入非零元的大小e;并将其先存入二维数组a[][]。

2、压缩矩阵至三元组的算法思想:获得矩阵之后,将其压缩进三元组表当中,三元组的非零元个数初始中为0,因在生成随机矩阵的过程中可能会出现相同的行、列,导致矩阵非零元被覆盖,所以具体的非零元个数以矩阵当中的为准。遍历矩阵,如果存在非零元,则将该元素的行标i与列标j,存入三元组,同时非零元个数+1。

3、打印矩阵的算法思想:先打印每一行的元素,如果i,j与三元组表里的i,j相匹配,则打印元素,否则打印0。

4、三元组快速转置的算法思想:求得被转置矩阵M的每一列的非零元个数,进而求得每一列的第一个非零元在T.data中应有的位置,故需要两个辅助向量:num与copt。先使T.mu=M.nu、T.nu=M.mu、T.tu=M.tu。如果T.tu不等于0,则先求每一列中的非零元个数num[col],col从1到M.nu;再求位置copt[col],copt[col]=copt[col-1]+num[col-1]
,col从2到M.nu,copt[1]=1;最后进行转置操作,令M的i,j互换,每次互换一个元素则++copt[col]。

5、具体实现代码如下:
#include<stdio.h> #include<stdlib.h> #include<time.h> #define MAXSIZE 200 #
define OK 1 #define FALSE 0 #define OVERFLOW -2 #define ERROR 0 typedef int
Status; typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple;
typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }TSMatrix; Status
CreateMatrix(TSMatrix *M) { int i,j,n,k; //行,列,非零元个数 int a[50][50]={0};
//存放矩阵,初始值为0 ElemType e; printf("本次稀疏矩阵的行数与列数均由随机数产生!\n"); srand((unsigned)time(
NULL) + (unsigned)rand()); //以time()为种子生成随机数 (*M).mu=rand()%10+6;
//随机行大小,取余是确定范围,mu在(6~15)之间 (*M).nu=rand()%10+7; //随机列大小 k=rand()%10+6;
//随机非零元个数 printf("该稀疏矩阵的行数为%d,列数为%d,非零元个数为%d。",(*M).mu,(*M).nu,k); (*M).data[0].
i=0; for(n = 1; n <= k; n++) //生成随机数矩阵 { i=rand()%(*M).mu+1; j=rand()%(*M).nu+1;
printf("请按行序输入第 %d 个非零元素,行%d,列%d,元素值:\n",n,i,j); scanf("%d",&e); a[i][j]=e; } (*
M).tu=1; for(i=1;i<=(*M).mu;i++) //以行为主序存入三元组 { for(j=1;j<=(*M).nu;j++) { if(a[i
][j]!=0) { (*M).data[M->tu].i = i; //行下标 (*M).data[M->tu].j = j; //列下标 (*M).data
[M->tu].e = a[i][j]; //该下标所对应的值 M->tu++; } } } M->tu--; return OK; } Status
PrintMatrix(TSMatrix M) { int i,j,n=1; printf("\n\n"); for(i=1;i<=M.mu;i++) {
for(j=1;j<=M.nu;j++) { if(M.data[n].i==i&&M.data[n].j==j) { printf("%4d",M.data[
n].e); n++; } else printf("%4d",0); } printf("\n"); } return OK; } Status
FastTransposeSMatrix(TSMatrix M,TSMatrix *T) { int col,t,p,q; int *num,*copt;
num=(int*)malloc((M.nu+1)*sizeof(int)); //给num分配内存空间;大小为M的列数+1,num[1]开始 copt=(
int*)malloc((M.nu+1)*sizeof(int)); //copt表示该列的第一个非零元在T.data中的位置,copt大小与num相等 T->
mu=M.nu; T->nu=M.mu; T->tu=M.tu; //T的行数等于M的列数,列数等于行数,非零元个数相等 if(T->tu) //非空 {
for(col=1;col<=M.nu;++col) num[col]=0; //清零操作 for(t=1;t<=M.tu;++t) ++num[M.data[
t].j]; //求M中每一列含非零元个数 copt[1]=1; //M的第一列的第一个非零元在T的第一个位置 for(col=2;col<=M.nu;++
col) copt[col]=copt[col-1]+num[col-1]; //累加操作,比较复杂,求每一列的第一个非零元在T.data中的位置 for(p=
1;p<=M.tu;++p) { col=M.data[p].j; q=copt[col]; T->data[q].i=M.data[p].j; //转置操作
T->data[q].j=M.data[p].i; T->data[q].e=M.data[p].e; ++copt[col]; //位置已用,计数加一 } }
return OK; } void main() { TSMatrix M,T; CreateMatrix(&M); printf("原始矩阵如下:\n");
PrintMatrix(M); //打印M FastTransposeSMatrix(M,&T); printf("转置矩阵如下:\n");
PrintMatrix(T); //打印T }
6、粉丝数上50,下次加上流程图,创作不易,谢谢支持。

技术
©2019-2020 Toolsou All rights reserved,
智慧屏和智能穿戴开发:组件方法汽车运动学模型的线性化推导过程【源码分析设计模式 4】JDK中的原型模式二进制模2除法(CRC循环冗余检验)python闭包Python 列表、元祖数据库实验4 SQL语言-SELECT查询操作MTCNN原理介绍vue项目中element-ui的分页器(组件封装)【数据结构与算法 9】谁发明的八皇后,本宫赐你一丈红