当前位置:网站首页>C语言使用随机数生成矩阵,实现三元组的快速转置。
C语言使用随机数生成矩阵,实现三元组的快速转置。
2020-11-10 10:51:00 【osc_b9r67jnt】
稀疏矩阵压缩及转置
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");
}
}
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,下次加上流程图,创作不易,谢谢支持。
版权声明
本文为[osc_b9r67jnt]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4258260/blog/4710724
边栏推荐
- getIServiceManager() 源码分析
- SEO界,值得收藏的10条金玉良言有哪些?
- csdn bug9:待加
- GNU assembly language uses inline assembly to extend ASM
- 从大专生到蚂蚁金服CTO,他写下“支付宝”第一行代码:逆风的方向,更适合飞翔!...
- layer.prompt(options, yes) - 输入层
- 大专学历的我工作六年了,还有机会进大厂吗?
- Overview of the most complete anomaly detection algorithm in history
- What can I do if I can't register didi? How to deal with it?
- csdn bug1:待加
猜你喜欢
SEO界,值得收藏的10条金玉良言有哪些?
Understanding of learning to estimate 3D hand pose from single RGB images
[论文阅读笔记] RoSANE, Robust and scalable attributed network embedding for sparse networks
中央重点布局:未来 5 年,科技自立自强为先,这些行业被点名
CSDN bug5: to be added
Bartender2021实现安全远程标签打印,年终全新发布
史上最全异常检测算法概述
GNU assembly basic mathematical equations multiplication
What can I do if I can't register didi? How to deal with it?
从大专生到蚂蚁金服CTO,他写下“支付宝”第一行代码:逆风的方向,更适合飞翔!...
随机推荐
CCR coin robot: novel coronavirus pneumonia has accelerated the interest of regulators in CBDC.
ASP.NET Core框架揭秘[博文汇总
csdn bug11:待加
layer.prompt(options, yes) - 输入层
One of the 10 Greatest formulas in the world is well known
Swoole 如何使用 Xdebug 进行单步调试
OSChina 周二乱弹 —— 我养的绿植分别为土豆,生姜,蒜
编码风格:Mvc模式下SSM环境,代码分层管理
坚持追查7年,近10亿美元比特币终被美国政府没收充公
Mongodb index management of distributed document storage database
港股上市公司移卡收购创信众42.5%股权 谋划加快营销服务布局
LeetCode:二叉树(四)
【操作教程 】国标GB28181协议安防视频平台EasyGBS订阅功能介绍及开启步骤
What does the mremote variable in servicemanagerproxy refer to?
中央重点布局:未来 5 年,科技自立自强为先,这些行业被点名
selenium webdriver使用click一直失效问题的几种解决方法
csdn bug9:待加
一不小心画了 24 张图剖析计网应用层协议!
[论文阅读笔记] Network Embedding with Attribute Refinement
Farfetch、阿里巴巴集团和历峰集团结成全球合作伙伴关系,将加速奢侈品行业数字化进程