-
2021-10-25 19:37:38
问题描述
输入矩阵的行数、列数和非零元素个数,以及所有非零元素,非零元素包括每个元素的行号、列号、元素值。 要求:1. 输入的非零元素个数必须满足稀疏矩阵要求,输入过程检测是否满足此要求,若不满足,则重新输入非零元素个数; 2. 非零元素按行号从小到大顺序输入,相同行号的元素,列号从小到大输入,输入过程检测是否满足此要求,若不满足,则重新输入当前非零元素的行号、列号和元素值
了解什么是稀疏矩阵
/** * 稀疏矩阵: 是指矩阵中大多数元素为 0 的矩阵。从直观上讲,当非零元素个数低于总元素的 30% * 时,这样的矩阵为稀疏矩阵 * 1. 稀疏矩阵的三元组存储表示 * 对于稀疏矩阵的存储压缩,采取只存储非零元素的方法。由于稀疏矩阵中非零元素 a_i_j 的分布没有 * 规律,因此再存储非零元素值的同时,还必须存储该非零元素在矩阵中所处的行号和列号的位置,这就是 * 稀疏矩阵的三元组表 表示法。 * * 三元组结构: * 该非零元素所在的行值 该非零元素所在的列值 该非零元素的值 * row col e * * 说明: 为处理方便,将稀疏矩阵中非零元素的三元组按照 "行序为主序" 的一维结构体数组进行存放, * 将矩阵的每一行(行由小到大)的全部非零元素的三元组按列号递增存放. * * 矩阵转置: * 指变换元素的位置,把位于(row,col) 位置上的元素转换到(col,row)位置上,即把元素的行列互换 * */
输入数据样例
第一组数据: 行 列 数据元素值 3 5 4 -------------------- 1 1 1 1 4 32 2 3 4 3 2 15 第二组数据: 行 列 数据元素值 3 5 4 -------------------- 1 1 1 1 4 32 2 3 4 2 1 15 3 2 15 第三组数据: 行 列 数据元素值 3 5 6 非零元素不满足条件重新输入: 4 -------------------- 1 1 1 1 4 32 2 3 4 3 2 15
解决方案
#include <stdio.h> /* 非零元素的个数最多为 255 */ #define MAX_SIZE 255 typedef int ElementType; typedef struct { /* 非零元素的行下标 */ int row; /* 非零元素的列下标 */ int col; /* 该非零元素的值 */ ElementType e; } Triple; typedef struct { /* 该非零元素的三元组表 MAX_SIZE+1: 表示 data[0] 为使用 */ Triple data[MAX_SIZE + 1]; /* 矩阵的行数 */ int rows; /* 矩阵的列数 */ int cols; /* 矩阵的非零元素个数 */ int length; } TSMatrix; /** * 稀疏矩阵列序递增转置算法 * @param A 原矩阵 * @param B 转置后 */ void TransposeTSMatrix(TSMatrix A, TSMatrix *B); void printT(TSMatrix B); void InputT(TSMatrix *A); int main() { TSMatrix A, B; InputT(&A); /* 转置前输出 */ printf("Before:\n"); printT(A); TransposeTSMatrix(A, &B); /* 转置后输出 */ printf("After:\n"); printT(B); return 0; } void TransposeTSMatrix(TSMatrix A, TSMatrix *B) { /* 把矩阵 A 转置到 B 所指向的矩阵中去。矩阵用三元组表示 */ int i, j, k; /* B的行 = A 的列 */ B->rows = A.cols; /* B的列 = A的行 */ B->cols = A.rows; /* 矩阵元素个数相同 */ B->length = A.length; /* 如果 B元素个数大于 0 */ if (B->length > 0) { /* j为辅助计数器,记录转置后的三元组在三元组表B中的下标值 */ j = 1; /* 扫描三元组表 A共 A.cols,每次寻找到列值为 k 的三元组进行转置 */ for (k = 1; k <= A.cols; k++) { for (i = 1; i <= A.length; i++) { /* 从头到尾扫描三元组表A,寻找 col 值为 k 的三元组进行转置 */ if (A.data[i].col == k) { B->data[j].row = A.data[i].col; B->data[j].col = A.data[i].row; B->data[j].e = A.data[i].e; /* 计数器 j 加 1,指向本行下一个转置后元素的位置下标 */ j++; } } /* inner for end */ } /* out for end */ } /* if end */ } /* TransposeTSMatrix end */ void printT(TSMatrix B) { int i, j; int t = 1; int zero = 0; for (i = 1; i <= B.rows; i++) { for (j = 1; j <= B.cols; j++) { if (B.data[t].row == i && B.data[t].col == j) { printf("%-4d", B.data[t].e); t++; } else printf("%-4d", zero); } printf("\n"); } } void InputT(TSMatrix *A) { int i; /* * 目标: * 存储一个三元组 * 1. 先满足输入的行列条件 * 2. 再满足非零元素个数 * 3. 实现三元组创建 * */ /* 第一次输入行列: 获取对应矩阵的行数和列数 */ scanf("%d%d", &A->rows, &A->cols); /* 输入的非零元素个数必须满足稀疏矩阵要求,输入过程检测是否满足此要求,若不满足,则重新输入非零元素个数 */ do { /* 输入非零元素个数 */ scanf("%d", &A->length); /* 如果非零元素个数大于 4,重新输入 => 矩阵大小为 3 行 5 列,6 个非零元素;(6 个非零元素,不是稀疏矩阵,输入错误) */ } while ((A->length > (A->rows * A->cols * 0.3))); /* 限制非零元素个数的 do...while end */ /* 非零元素个数满足后: 输入第一组矩阵表元素 */ scanf("%d%d%d", &A->data[1].row, &A->data[1].col, &A->data[1].e); /** * 非零元素按行号从小到大顺序输入,相同行号的元素,列号从小到大输入,输入过程检测是否满足此要求, * 若不满足,则重新输入当前非零元素的行号、列号和元素值 */ for (i = 2; i <= A->length; i++) { do { /* 输入三元组表: 获取对应位置下标的值 */ scanf("%d%d%d", &A->data[i].row, &A->data[i].col, &A->data[i].e); } while (A->data[i].row < A->data[i - 1].row || A->data[i].row == A->data[i - 1].row && A->data[i].col <= A->data[i - 1].col); } }
结果输出
更多相关内容 -
稀疏矩阵转置
2014-04-07 15:12:13稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号、值,建立稀疏矩阵的三元组存储结构,并将此矩阵转置,显示转置前后的三元组结构。 -
稀疏矩阵转置_clearlybgo_稀疏矩阵转置_稀疏矩阵_
2021-09-29 15:22:49稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号、值,建立稀疏矩阵的三元组存储结构,并将此矩阵转置,显示转置前后的三元组结构。 -
稀疏矩阵转置算法
2017-11-28 10:48:38在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵,并用三元组表存储。用C++ 扫描两遍三元组表实现稀疏矩阵转置 -
数据结构实验报告4-数组与广义表-基于十字链表的稀疏矩阵转置-实验内容及要求.docx
2019-07-06 20:45:49编写程序,从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构。其中,m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号。编写算法,实现矩阵转置,输出转置后的三元组到... -
数据结构课实验_稀疏矩阵转置.zip
2020-03-25 23:02:03数据结构课小实验,简单实现稀疏矩阵转置,终端显示 压缩包包含:xxjz.txt,一个cpp,可直接编译运行 -
稀疏矩阵转置算法(C语言)
2022-04-03 14:40:20稀疏矩阵的压缩:将矩阵中的值为零或者为常数C的某c个数,不做存储(或者共用同样的空间,本题转置对0不做存储),压缩后原本nxn的矩阵,存储只需要nxn-c的空间 下面以这样的M矩阵进行转置 1 2 3 4 0 0 0 5 1 转置后...(参考数据结构教材,严蔚敏,吴伟民版 p99,多谢阅读,望对您有帮助)
无论是几维的数组,在计算机中都是以一维数组的方式进行存储的。
矩阵:相当于二维数组,它的存储,依然是用一维数组的方式进行存储。
nxn的矩阵,在计算机空间上,需要nxn个空间。
稀疏矩阵的压缩:将矩阵中的值为零或者为常数C的某c个数,不做存储(或者共用同样的空间,本题转置对0不做存储),压缩后原本nxn的矩阵,存储只需要nxn-c的空间
下面以这样的M矩阵进行转置
1 2 3
4 0 0
0 5 1
转置后得N矩阵:
1 4 0
2 0 5
3 0 1
M矩阵的计算机三元组存储方式(此图为图1)
转置后T矩阵的计算机三元组存储方式(此图为图2)
转置过程的实现,实际上是从图一转化为图二的过程
因为图1是按照行储存(第一行储存完了,才储存第二行),转置后的T矩阵,同样是按照行进行存储。
故T矩阵再遍历矩阵M时,M的列就是T的行,把M的每列的数据,逐列,一一存到data中,完成转置运算先给出转置代码实现:
#include "stdio.h" #include "stdlib.h" #define Max_size 1000 typedef struct { int i;//矩阵中数据的行号 int j;//矩阵中数据的列号 int e;//i行j列,数据的值 }Triple;//三元组为一个节点 typedef struct { Triple data[Max_size + 1];//data[0]未用 int mu, nu, tu;//矩阵的行数,列数,非零元个数 }Matrix; void TransposeSMatrix(Matrix M,Matrix &T)//将矩阵M转置为T { T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu)//非零元不为0 { int q = 1;//用于逐项记录转置后矩阵T的值 int col, p;//矩阵M的col列号,p:指向当前值在M矩阵硬件的储存位置 for (col = 1; col < M.nu; col++) { for (p = 1; p < M.tu; p++) { if (M.data[p].j == col)//逐列进行遍历,并插入到T.data中 { T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i;//转置后i,j互换 T.data[q].e = M.data[p].e;//T的值获取到 q++;//T指针的数据后移 } } } } } int main() { Matrix M,T; M.mu = 3; M.nu = 3; M.tu = 6; M.data[1].i = 1; M.data[1].j = 1; M.data[1].e = 1; M.data[2].i = 1; M.data[2].j = 2; M.data[2].e = 2; M.data[3].i = 1; M.data[3].j = 3; M.data[3].e = 3; M.data[4].i = 2; M.data[4].j = 1; M.data[4].e = 4; M.data[5].i = 3; M.data[5].j = 2; M.data[5].e = 5; M.data[6].i = 3; M.data[6].j = 3; M.data[6].e = 1; TransposeSMatrix(M, T); printf("(%d,%d):%d", T.data[4].i, T.data[4].j, T.data[4].e);//求转置后T矩阵2行3列的值 return 0; }
运行结果
转置后T矩阵2行3列的值为5,如运行结果所示
-
稀疏矩阵转置(C语言)
2021-03-29 19:57:25最近有数据结构实验课了,还得学一学数据结构喽,以后就把学习经过贴上来了。 稀疏矩阵 ...稀疏矩阵转置 题目 (不得不说这个题输入数据的确坑。。) 有两种方法转置 话不多说,上代码: #include<stdi最近有数据结构实验课了,还得学一学数据结构喽,以后就把学习经过贴上来了。
稀疏矩阵
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组
稀疏数组的处理方法
1)记录数组一共有几行几列,有多少个不同的值(假设有sum个,则稀疏矩阵有sum+1行,3列)
2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
百度盗图(手动滑稽)稀疏矩阵转置
题目
(不得不说这个题输入数据的确坑。。)
有两种方法转置
话不多说,上代码:#include<stdio.h> #include<stdlib.h> #define MAXSIZE 1000 typedef struct{ int row;//第几行 int col;//第几列 int e;//存储的值 }Triple; typedef struct { Triple data[MAXSIZE]; int m,n,len;//稀疏矩阵的行,列,非零元素的个数 }TSMatrix; void createTSMatrix(TSMatrix *A)//创建矩阵 { int i=1; //data【0】未用 scanf("%d %d",&A->m,&A->n); int flag = 1; int a,b,c; char c1,c2; while(flag) { scanf("%d",&a); c1 = getchar(); scanf("%d",&b); c2 = getchar(); scanf("%d",&c); if(c1=='?'&&c2=='?') break; A->data[i].row=a; A->data[i].col=b; A->data[i].e=c; i++; } i--; A->len=i; } void TransMatrix(TSMatrix A,TSMatrix *B)//序列递增转置法 { int i,j,k; B->n=A.m; B->m=A.n; B->len=A.len; if(B->len) { j=1;//辅助计数器,记录转置后的三元组元素下标值 for(k=1;k<=A.n;k++)//扫描矩阵A的列次或B的行次 for(i=1;i<=A.len;i++) //扫描A找列为k的元素 { if(A.data[i].col==k) { B->data[j].row=A.data[i].col; B->data[j].col=A.data[i].row; B->data[j].e=A.data[i].e; j++; } } } } void FastTransMatrix(TSMatrix A,TSMatrix *B)//快速转置法 { int col,t,p,q; int num[MAXSIZE],position[MAXSIZE]; B->n=A.m; B->m=A.n; B->len=A.len; if(B->len) { for(col=1;col<=A.n;col++) num[col]=0; for(t=1;t<=A.len;t++) num[A.data[t].col]++; position[1]=1; for(col=2;col<=A.n;col++) { position[col]=position[col-1]+num[col-1]; } for(p=1;p<=A.len;p++) { col=A.data[p].col; q=position[col]; B->data[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; position[col]++; } } } void printMatrix(TSMatrix *B)//输出矩阵 { for(int i=1;i<=B->len;i++) { printf("%d %d %d\n",B->data[i].row,B->data[i].col,B->data[i].e); } } int main() { TSMatrix A,B;//A为初始矩阵,B为转置后的矩阵 createTSMatrix(&A); FastTransMatrix(A,&B); printMatrix(&B); return 0; }
-
【稀疏矩阵转置】线性时间复杂度实现稀疏矩阵转置
2017-10-20 16:43:251知识点:线性时间复杂度实现稀疏矩阵转置 2方法: (1):通过三元组记录初始输入信息 (2):记录每一列的元素个数 (3):求得记录每一列的第一个元素应放置的转置三元组的位置 3反思: (1):记录的...Think:
1知识点:线性时间复杂度实现稀疏矩阵转置
2方法:
(1):通过三元组记录初始输入信息
(2):记录每一列的元素个数
(3):求得记录每一列的第一个元素应放置的转置三元组的位置
(4):通过(3)所得到的记录数组和初始输入时记录的三元组遍历转置稀疏矩阵即可3反思:
(1):求解记录的是每一列的第一个元素应放置的转置三元组的位置,故遍历范围为[1, nu]而不是[1, tu]Problem Description
转置运算是一种最简单的矩阵运算,对于一个m*n的矩阵M( 1 = < m < = 10000,1 = < n < = 10000 ),它的转置矩阵T是一个n*m的矩阵,且T( i , j )=M( j , i )。显然,一个稀疏矩阵的转置仍然是稀疏矩阵。你的任务是对给定一个m*n的稀疏矩阵( m , n < = 10000 ),求该矩阵的转置矩阵并输出。矩阵M和转置后的矩阵T如下图示例所示。
稀疏矩阵M
稀疏矩阵TInput
连续输入多组数据,每组数据的第一行是三个整数mu, nu, tu(tu <= 50),分别表示稀疏矩阵的行数、列数和矩阵中非零元素的个数,随后tu行输入稀疏矩阵的非零元素所在的行、列值和非零元素的值,同一行数据之间用空格间隔。(矩阵以行序为主序)Output
输出转置后的稀疏矩阵的三元组顺序表表示。Example Input
3 5 5
1 2 14
1 5 -5
2 2 -7
3 1 36
3 4 28Example Output
1 3 36
2 1 14
2 2 -7
4 3 28
5 1 -5Hint
Author
xam以下为Accepted代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Node{ int x, y, num; }node1[104], node2[104]; int book[14014], cpot[14014]; int main(){ int mu, nu, tu; while(~scanf("%d %d %d", &mu, &nu, &tu)){ memset(book, 0, sizeof(book)); for(int i = 1; i <= tu; i++){ scanf("%d %d %d", &node1[i].x, &node1[i].y, &node1[i].num); book[node1[i].y]++; } cpot[1] = 1; for(int i = 2; i <= nu; i++){ cpot[i] = cpot[i-1] + book[i-1]; } for(int i = 1; i <= tu; i++){ int id = cpot[node1[i].y]; node2[id].x = node1[i].y; node2[id].y = node1[i].x; node2[id].num = node1[i].num; cpot[node1[i].y]++; } for(int i = 1; i <= tu; i++){ printf("%d %d %d\n", node2[i].x, node2[i].y, node2[i].num); } } return 0; }
-
三元组稀疏矩阵转置算法
2020-03-12 16:39:08三元组稀疏矩阵转置运算 1.关于稀疏矩阵的解释(定义) 矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素的分布没有规律,通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时,则称该... -
稀疏矩阵转置的三个算法(数据结构)
2020-10-24 21:24:15稀疏矩阵转置的三个算法 -
三元组顺序表表示的稀疏矩阵转置(10分)
2021-11-28 23:45:10三元组顺序表表示的稀疏矩阵转置(10分) 本题要求实现一个函数,实现三元组顺序表表示的稀疏矩阵转置。 函数接口定义: struct tripletable * trans(struct tripletable *t1); 其中 t1 是用户传入的参数。 函数须... -
西工大NOJ数据结构实验——2.1稀疏矩阵转置
2022-04-01 13:57:27西工大NOJ数据结构实验——2.1稀疏矩阵转置 -
数据结构实验:基于十字链表的稀疏矩阵转置
2021-11-20 15:30:13基于十字链表的稀疏矩阵转置 -
7-2 三元组顺序表表示的稀疏矩阵转置运算Ⅰ
2022-01-07 13:20:56三元组顺序表表示的稀疏矩阵转置。 输入格式: 输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行,每行3个数,分别表示非零元素的行标、列标和值。 输出格式: 输出转置后的三元组顺序表... -
6-2 三元组顺序表表示的稀疏矩阵转置
2021-11-03 14:26:296-2 三元组顺序表表示的稀疏矩阵转置 (10 分) 本题要求实现一个函数,实现三元组顺序表表示的稀疏矩阵转置。 函数接口定义: struct tripletable * trans(struct tripletable *t1); 其中 t1 是用户传入的参数。 函数... -
[NOJ]数据结构实验2.1 稀疏矩阵转置
2021-04-28 22:33:56[NOJ]数据结构实验2.1 稀疏矩阵转置 #include<stdio.h> #include<stdlib.h> typedef struct { int row,col; int e; }Triple; typedef struct { Triple *data; int m,n,len... -
NOJ数据结构实验003——稀疏矩阵转置
2021-04-17 23:06:17本题要求使用三元组进行矩阵转置,方法有两种,列序递增转置以及一次定位快速转置。 第一种方法思路简单,即将行列直接交换再进行排列,但占用空间较多,时间较慢。 第二种方法耗时较短,思路简述为记录每一列元素个... -
数据结构--稀疏矩阵转置(列序递增算法)的c语言实现(超详细注释/实验报告)
2021-10-24 23:39:57稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲,当非零元素个数低于总元素的30%时,这样的矩阵为稀疏矩阵。 -
6-42 稀疏矩阵转置
2021-12-02 15:18:49本题求稀疏矩阵的转置。 函数接口定义: void trans_mat(elem a[],int n,elem b[]); 其中b表示稀疏矩阵a的转置矩阵。 裁判测试程序样例: #include <stdio.h> #define N 5 //二维数组的行列值 #define ... -
【数据结构实验】NOJ003 实验2.1稀疏矩阵转置
2021-04-18 11:53:57参照书上使用的是一次定位快速转置法,连代码上的字母都没咋改哈哈。但是如果从1开始会WA,需要从0开始。 //4 4 //1 1 1 //2 1 2 //3 2 3 //0 0 0 #include <iostream> #include <string> #define ... -
【swjtu】数据结构实验5_基于十字链表的稀疏矩阵转置
2021-11-12 00:58:50编写算法,实现矩阵转置,输出转置后的三元组到另一字符文件中,检查你的转置结果是否正确。要求转置时不得新建元素结点(但允许新建行头/列头结点数组以及删除行头/列头结点数组,转置前后,总头结点不允许改变)。 ... -
7-5 三元组顺序表表示的稀疏矩阵转置Ⅱ (10 分)
2021-11-04 01:09:177-5 三元组顺序表表示的稀疏矩阵转置Ⅱ (10 分) 三元组顺序表表示的稀疏矩阵转置Ⅱ。设a和b为三元组顺序表变量,分别表示矩阵M和T。要求按照a中三元组的次序进行转置,并将转置后的三元组置入b中恰当的位置。 输入... -
python的scipy.sparse稀疏矩阵转置
2021-01-07 13:35:36python的scipy.sparse稀疏矩阵转置 由于scipy.sparse没有稀疏矩阵转置的函数,不能直接调用。要自己写一个函数,要是对sparse比较熟悉的话还是可以很快写出来的 def trans(D): x = find(D) return csc_matrix((x[2... -
数据结构【串与数组】——PTA:三元组顺序表表示的稀疏矩阵转置运算(含思路)
2021-11-13 19:53:26主题:三元组顺序表表示的稀疏矩阵转置。 问题: 输入格式: 输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行,每行3个数,分别表示非零元素的行标、列标和值。 输出格式: 输出转置后的三元组... -
稀疏矩阵转置以及输出
2020-12-06 09:52:32稀疏矩阵转置以及输出 代码实现: 1.稀疏矩阵的输入 2.稀疏矩阵转三元组 3.转置 4.三元组转稀疏矩阵 #include<iostream.h> #include<stdio.h> #define MAXSIZE 10000 typedef int ElemType; typedef int... -
基于十字链表存储的稀疏矩阵的转置
2019-04-28 14:29:32实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构(m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号)和十字链表的转置并将转置后的三元组到另一字符文件中 -
C++_稀疏矩阵转置
2018-10-24 20:49:14问题描述:稀疏矩阵转置 设计思路 设计思路:稀疏矩阵中存在大量非零元素,直接转置执行时间较高。因而采用三元组表示。按照压缩的概念,只存储稀疏矩阵中的非零元素,除了存储非零元素的值之外,还必须同时记下它...