-
2020-12-21 16:41:05
一、设计要求
1
.
1
问题描述
稀疏矩阵是指那些多数元素为零的矩阵。
利用稀疏特点进行存储和计算可以大大节省存
储空间,提高计算效率。求一个稀疏矩阵
A
的转置矩阵
B
。
1
.
2
需求分析
(
1
)以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现稀疏矩阵的转置运算。
(
2
)稀疏矩阵的输入形式采用三元组表示,运算结果则以通常的阵列形式列出。
(
3
)
首先提示用户输入矩阵的行数、
列数、
非零元个数,
再采用三元组表示方法输入矩阵,
然后进行转置运算,该系统可以采用两种方法,一种为一般算法,另一种为快速转置算法。
(
4
)程序需要给出菜单项,用户按照菜单提示进行相应的操作。
二、概要设计
2
.
1
存储结构设计
采用“带行逻辑链接信息”的三元组顺序表表示矩阵的存储结构。三元组定义为:
typedef struct
{
int i
;
//
非零元的行下标
int j
;
//
非零元的列下标
ElemType e;
//
非零元素值
}Triple;
矩阵定义为:
Typedef struct
{
Triple data[MAXSIZE+1];
//
非零元三元组表
int rpos[MAXRC+1];
//
各行第一个非零元的位置表
int mu,nu,tu;
//
矩阵的行数、列数和非零元个数
}RLSMatrix;
例如有矩阵
A
,它与其三元组表的对应关系如图
更多相关内容 -
三元组表示稀疏矩阵并相加
2020-06-27 08:53:47数据结构实验设计:三元组稀疏矩阵相加三元组表示稀疏矩阵并相加
一、实验题目:
要求稀疏矩阵用三元组结构存储,实现矩阵A+B=C,并采用矩阵形式显示结果。
二、实验思路:
定义两个结构体,Triple结构体用来存放每一个非零元素的信息(行标,列标,数值),Tripledata用来存放两个三元组矩阵的信息(行数,列数,非零元素的个数)。每一个三元组结构都需要调用这两个结构体,两个结构体共同组成一个稀疏矩阵的信息。定义两个二维数组将所有元素赋值为0,然后再在非零元素位置进行赋值操作,输出打印矩阵。最后用第三个数组存放前两个数组相加的结果。
三、流程图解析:
主函数:
打印矩阵
矩阵相加
实验代码:#include <stdio.h> #include <stdlib.h> typedef struct threetuple{ int x;//表示非零元素的行标 int y;//表示非零元素的列标 int value;//表示非零元的值 }Triple;//用来存放三元组中每一个非零元素的信息 typedef struct infor { int col;//列数 int row;//行数 int counts;//存放非零元的个数 }Tripledata;//用来存放三元组矩阵的信息 void printtuple(Triple m[],Tripledata n,int A[n.col][n.row]); void add_print(Tripledata n,int A[n.col][n.row],int B[n.col][n.row]); int main() { Tripledata t[2];//定义两个信息结构体来存放矩阵信息 int i,j; for(i=0;i<=1;i++)//行列数信息 { printf("请输入第%d个元组的信息:\n依次输入行数,列数,非零元个数\n",i+1); scanf("%d%d%d",&t[i].col,&t[i].row,&t[i].counts);//对非零元素进行赋值操作 } if(t[0].col!=t[1].col||t[0].row!=t[1].row) { printf("该情况无法相加,程序退出"); exit(0); } int a,b; a=t[0].counts; b=t[1].counts; Triple T1[a],T2[b];//定义两个非零元素信息结构体,前者对应A,后者是B printf("请输入每个三元组矩阵的非零元素的信息:\n"); for(i=1,j=0;i<=t[0].counts;j++,i++)//每个三元组的信息; { printf("依次输入元组1第%d个非零元素行标,列标,数值",i); scanf("%d%d%d",&T1[j].x,&T1[j].y,&T1[j].value); } for(i=1,j=0;i<=t[0].counts;j++,i++)//每个三元组的信息; { printf("依次输入元组2第%d个非零元素行标,列标,数值",i); scanf("%d%d%d",&T2[j].x,&T2[j].y,&T2[j].value); } int A[t[0].col][t[0].row];//定义一个二维数组来存放矩阵信息 int B[t[1].col][t[1].row];//同上 printf("\nA的矩阵形式:"); printtuple(T1,t[0],A);//以矩阵形式打印A printf("\nB的矩阵形式:"); printtuple(T2,t[1],B);//以矩阵形式打印B add_print(t[0],A,B);// return 0; } void printtuple(Triple m[],Tripledata n,int A[n.col][n.row])//以矩阵形式输出两个三元祖 { int i,j; for(i=0;i<n.col;i++) { for(j=0;j<n.row;j++) { A[i][j]=0;//将所有元素赋值0 } } for(i=0;i<n.counts;i++) { A[m[i].x-1][m[i].y-1]=m[i].value;//把三元组非零元素在对应位置赋值 } for(i=0;i<n.col;i++) { printf("\n"); for(j=0;j<n.row;j++) { printf("%2d",A[i][j]);//以矩阵形式打印 } } } void add_print(Tripledata n,int A[n.col][n.row],int B[n.col][n.row]) { int i,j; int C[n.col][n.row];//定义一个新矩阵用来存储相加后的结果。 printf("\n执行矩阵相加,并打印结果:\n"); for(i=0;i<n.col;i++) { for(j=0;j<n.row;j++) { C[i][j]=A[i][j]+B[i][j];//进行矩阵相加运算 printf("%-3d",C[i][j]);//相加和打印同时进行 } printf("\n"); } }
五、运行结果截图
-
三元组实现稀疏矩阵的加法
2018-12-18 15:49:07用三元组表示稀疏矩阵M与N,设计算法实现两个稀疏矩阵的加法Q=M+N -
编写程序用三元组表示稀疏矩阵的案列转置操作。
2021-10-31 08:51:56编写程序用三元组表示稀疏矩阵的案列转置操作。本设计使用三元组表来实现。 算法分析 本题要完成的是三元组表实现稀疏矩阵按列转置操作。首先就是要设立三个函数。函数InitSPNode()用来建立一个稀疏矩阵的三元组表...内容:
编写程序用三元组表示稀疏矩阵的案列转置操作。本设计使用三元组表来实现。
算法分析
本题要完成的是三元组表实现稀疏矩阵按列转置操作。首先就是要设立三个函数。函数InitSPNode()用来建立一个稀疏矩阵的三元组表,就是要输入行数、列数和非零元的值,最后要用(-1,-1,-1)来结束输入;第二函数showMatrix()用来输出稀疏矩阵,算法中按矩阵a的列进行循环处理,对a的每一列扫描三元组,找出相应的元素,若找到了,则交换其行号与列号,并存储到矩阵b的三元组中。最后用函数TransposeSMatrix()用来完成稀疏矩阵的转置算法。算法主要的工作是在配合col的两重循环中完成,时间复杂度为(n*t)。如果非零元素个数t和m*n同数量级,则算法的时间复杂度变为O(m*n²)
概要设计
用三元组表实现系数矩阵的基本操作
函数
void InitSPMatrix(SPMatrix* a)
void showMatrix(SPMatrix *a)
void TransposeSMatrix(SPMatrix* a, SPMatrix* b)
程序运行流程图如下:
#include<stdio.h> #include<string.h> #define Ok 1 #define MAX 10//用户自定义三元组表最大长度 typedef struct//定义三元组表 { int i, j;//行,列 int v;//非0数组中的值 }SPNode; typedef struct//定义三元组表 { int m;//矩阵行 int n;//矩阵列 int t;//矩阵中的非零元素(三元组表的长度) SPNode date[MAX]; }SPMatrix; void InitSPMatrix(SPMatrix* a)//输入三元列表 { int i, j, k, val, maxrow, maxcol; maxrow = 0; maxcol = 0; i = j = 0; k = 0; while (i != -1 && j != -1)//rol=-1&&col=-1结束输入 { printf("输入(行 列 值)"); scanf_s("%d,%d,%d", &i, &j, &val); a->date[k].i = i; a->date[k].j = j; a->date[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++)//这个是行循环,p代表p+1行 { for (q = 0; q <= a->n; q++)//这个是列循环,q代表q+1列 { if (a->date[t].i== p && a->date[t].j == q)//遍历循环输出有v的元素 { printf("%d", a->date[t].v); t++; } else printf("0");//if不成立说明该位置没有输入元素,则输出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)//遍历整个矩阵进行置换 for(p=0;p<a->t;++p) if (a->date[p].j == col) { b->date[q].i = a->date[p].j; b->date[q].j = a->date[p].i; b->date[q].v = a->date[p].v; ++q; } } } void main() { SPMatrix a, b; printf("\n结束请输入(-1,-1,-1)\n"); InitSPMatrix(&a); printf("输入矩阵为:\n"); showMatrix(&a); TransposeSMatrix(&a, &b); printf("输出矩阵为:\n"); showMatrix(&b);//转置后 }
-
用三元组表示稀疏矩阵的乘法.ppt
2021-09-18 17:11:39用三元组表示稀疏矩阵的乘法.ppt -
用三元组表示稀疏矩阵的乘法PPT学习教案.pptx
2021-10-05 19:30:25用三元组表示稀疏矩阵的乘法PPT学习教案.pptx -
数据结构三元组稀疏矩阵_稀疏矩阵三元组顺序表表示
2019-12-05 00:54:52培养解决综合性实际问题的能力 二课程设计任务 题目稀疏矩阵AB的和 题目要求稀疏矩阵A,B用三元组顺序表存储 三元组表C存放结果矩阵 AB的和存到C中 题目用三元组C存放以三元组顺序表做存储结构的稀疏矩阵AB的和 一 ... -
35-稀疏矩阵的三元组表示方式
2018-06-28 18:00:44对于稀疏矩阵来说,如果我们还是用100×100的方式来存储的话,显然是非常浪费的,因此我们可以采用一种稀疏矩阵的压缩存储方式,即三元组方式。 三元组方式存储数据的策略是只存储非零元素。但是稀疏矩阵...1. 稀疏矩阵
一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数 t 很小时,即 s<t s < t ,称该矩阵为稀疏矩阵。
比如:在一个100×100的矩阵中,其中只有100个非零元素,而非零元素相对于矩阵中的元素总个数10000很小,那么该矩阵为稀疏矩阵。
2. 稀疏矩阵的压缩存储方法
对于稀疏矩阵来说,如果我们还是用100×100的方式来存储的话,显然是非常浪费的,因此我们可以采用一种稀疏矩阵的压缩存储方式,即三元组方式。
三元组方式存储数据的策略是只存储非零元素。但是稀疏矩阵中非零元素的分布是没有任何规律的,在这种情况下,存储方案是:
1.存储非零元素2.同时存储该非零元素所对应的行下标和列下标
3.稀疏矩阵中的每一个非零元素需由一个三元组(i, j, aij a i j )唯一确定,稀疏矩阵中的所有非零元素构成三元组线性表,三元组中的i就是行下标,j是列下标, aij a i j 是对应的元素值。
图1-稀疏矩阵的压缩存储拿稀疏矩阵中的元素1来说,该元素的位置为第0行,第2列,在用三元组(i ,j ,aij)进行存储时,就是0 2 1,我们发现在这个三元组的线性表中,每个数据元素都是以三元组的方式组成的。
3. 定义存储结构
当我们确定三元组的存储策略后,下一步我们要做的就是如何把这样的三元组存储下来。我们在进行保存时,需要把矩阵中的行数,列数,非零元素个数,矩阵中的数据都保存在data数据域(数组),在data数据域中的每个数据元素都是以三元组(行号,列号,元素值)形式存储,data域中表示的非零元素通常以行序为主序顺序排列,下标按行有序的存储结构。如图2所示:
图2-定义存储结构当定义好这样的存储结构后,我们可以使用计算机程序设计语言来实现这样的存储结构,如下所示:
#define MaxSize 100 //定义三元组线性表中的数据元素存储结构 typedef struct { int row; //行号 int col; //列号 ElemType d; //元素值,ElemType为数据元素类型 } TupNode; //三元组定义 //定义三元组线性表存储结构 typedef struct { int rows; //行数值 int cols; //列数值 int nums; //非零元素个数 TupNode data[MaxSize]; //data数据域 } TSMatrix; //三元组顺序表定义
4. 稀疏矩阵的三元组基本运算
算法:以行序方式扫描二维矩阵A,将其非零的元素加入到三元组t。
要求为data域以行序为主序顺序排列
图中是采用6行7列的稀疏矩阵作为说明,但是在下面的算法中以3行4列说明
//以行序方式扫描二维矩阵A,将其非零的元素加入到三元组t //以3行4列的稀疏矩阵为例 void CreatMat(TSMatrix *t, int arr[3][4]) { int i; int j; t->rows = 3; t->cols = 4; t->nums = 0; //扫描矩阵中的非零元素 for(i = 0; i < 3; i++) { for(j = 0; j < 4; j++) { //只存非零值,以三元组方式 if(arr[i][j] != 0) { t->data[t->nums].row = i; t->data[t->nums].col = j; t->data[t->nums].d = arr[i][j]; t->nums++; } } } }
算法:将指定位置的元素值赋给变量x:执行x=arr[ i ] [ j ]//将三元组线性表中指定位置的元素值赋值给变量x void arr_Assign(TSMatrix t , int *data , int i , int j) { int k = 0; //i和j是否合法 if(i >= t.rows || j >= t.cols) { return; } //找到指定元素的行下标 while(k < t.nums && i > t.data[k].row) { k++; } //当找到指定元素的行下标后,再找到指定元素的列下标 while (k < t.nums && i == t.data[k].row && j > t.data[k].col) { k++; } //如果指定元素的行和列都相等,说明找到了 if(t.data[k].row == i && t.data[k].col) { *data = t.data[k].d; } else { //说明没找到 *data = 0; } }
算法:三元组元素赋值:执行A[ i ] [ j ] = x
1. 将一个非0元素修改为非0值,如A[ 5 ] [ 6 ] = 8
将矩阵A中第5行,第6列的元素的值改为8,即修改三元组线性表中的数据元素的值。
2.将一个0元素修改为非0值,如A[ 3 ] [ 5 ] = 8
将矩阵A中第3行,第6列值为0的元素改为8,这时需要在三元组线性表数组中下标为3的位置往后插入一个数据元素
//修改三元组元素中的值:执行A[i][j]=x void arr_Value(TSMatrix *t , int data , int i , int j) { int k = 0; int k1; //指定的行和列是否合法 if(i >= t->rows || j >= t->cols) { return; } //先查找行 while(k < t->nums && i > t->data[k].row) { k++; } //查找列 while(k < t->nums && i == t->data[k].row && j > t->data[k].col) { k++; } //当找到指定位置时直接修改 if(i == t->data[k].row && j == t->data[k].col) { t->data[k].d = data; } else { //如果指定位置不存在,则说明该元素值为0,此时插入 for(k1 = t->nums; k1 >= k; k1--) { t->data[k1+1].col = t->data[k1].col; t->data[k1+1].row = t->data[k1].row; t->data[k1+1].d = t->data[k1].d; } //插入数据 t->data[k].row = i; t->data[k].col = j; t->data[k].d = data; t->nums++; } }
输出三元组:从头到尾扫描三元组t,依次输出元素值void DispMat(TSMatrix *t) { int i; if(t->nums <= 0) { return; } printf("\t行数:%d\t列数:%d\t元素个数:%d\n", t->rows , t->cols , t->nums); printf(" ------------------\n"); //输出所有的三元组 for(i = 0; i < t->nums; i++) { printf("\t第%d行\t第%d列\t%d\n" , t->data[i].row , t->data[i].col, t->data[i].d); } }
5. 测试
int main(void) { //通过自定义3行4列的二维数组来表示稀疏矩阵 int arr[3][4] = { {0 , 1 , 0 , 0}, {0 , 0 , 0 , 2}, {3 , 0 , 0 , 4} }; int data = 0; TSMatrix t = {0}; CreatMat(&t , arr); //输出三元组 DispMat(&t); //获取稀疏矩阵指定位置的值,data的值应该为1才对 arr_Assign(t, &data , 0 , 1); printf("---------------\n"); printf("第0行第1列的数据元素值:%d\n\n" , data); printf("----------------\n"); //将稀疏矩阵第0行第0列元素的值设置为1 arr_Value(&t , data , 0 , 0); //输出三元组 DispMat(&t); return 0; }
运行结果:
-
三元组实现稀疏矩阵的乘法
2019-10-25 21:39:38#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <...//定义三元组 typedef struct { int i, j;//行数、列数 int val;//非零值 }Node; typedef struct { Node data[Max... -
用三元组表示的稀疏矩阵的相乘和转置
2021-03-14 16:15:12#include#define MAX 40 /*非零元个数的最大值*/typedef struct{int i,j;/*非零元的行下标和列下标*/int e;.../*非零元三元组表,data[0]未用*/int mu,nu,tu;/*矩阵的行数,列数,非零元的个数*/int rpos[MAX+1... -
用三元组实现稀疏矩阵的转置
2021-10-30 12:35:29内容: 设m*n的矩阵中有t个非零元素且t<<m*n,这样的矩阵成为稀疏矩阵,在存储稀疏矩阵时,按照常规方法存储时相当浪费内存,因此提出...编写程序用三元组表实现稀疏矩阵的按列转置操作。 步骤: 算法分析 本 -
C/C++利用三元组实现稀疏矩阵运算
2018-12-23 16:57:42三元组((x,y),z)其中(x,y)表示非零元位置,z...三元组稀疏矩阵表示一些图也是很不错的选择 这样就很浪费空间,三元组直接 ((0,1),1) ((1,2),1) ((3,4),1) ((5,6),1) ((7,8),1) 下面是稀疏矩阵代码: #... -
用三元组实现稀疏矩阵的乘法!
2021-03-14 16:14:49已结贴√问题点数:20回复次数:2 用三元组实现稀疏矩阵的乘法!#include#include#define MAXSIZE 12500typedef struct{int i,j;int e;} Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;} TSMatrix;int... -
稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
2020-12-21 16:41:08问题:稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。答案:对更多相关问题(本小题满分10分)已知抛物线的焦点坐标是F(0,-2), 求它的标准方程。I bought a dress for only 10 dollars in a ... -
三元组转置稀疏矩阵
2018-04-21 03:38:07当一个矩阵中非零元素远小于矩阵中元素的个数时,如果用简单的二维数组来表示矩阵就会造成大量的空间占用, 所以引进三元组来表示稀疏矩阵。如下:typedef struct{ int i , j;//表示非零元素的行列 int v;//矩阵... -
三元组求稀疏矩阵的转置
2018-02-04 10:22:08直接按照稀疏矩阵A的三元组表A.value的次序依次顺序转换,并将转换后的三元组放置于三元组表B.value的恰当位置。 为了算出每个三元组的具体位置,设两个辅助向量num[ ]和cpot[ ] 。 ◆ num[col]:统计稀疏矩阵A中... -
三元组表形式表示稀疏矩阵,实现两个矩阵的加法、减法
2021-12-05 12:58:41/*三元组表*/ } TSMatrix; void inputMatrix(TSMatrix &m) { printf("输入矩阵的行数,列数和非零元素的个数:(行数,列数,非零元素个数)"); scanf("%d,%d,%d", &m.rows,&m.cols, &m.nums ); printf("输入稀疏矩阵... -
三元组表与稀疏矩阵怎么转换?
2020-12-21 16:41:07展开全部非转载,知乎本人用python将三元组转化为稀疏矩阵我的问题是arcgis输出的空间e69da5e887aa3231313335323631343130323136353331333431376638权重矩阵是三元组类型,需要转化成方阵,即将图一中的【1,2,0.... -
利用三元组实现稀疏矩阵的操作
2018-06-09 10:37:05生成三元组辅助向量; 返回到三元组的某一位; 修改三元组的某一位;快速转置; 求最大值; 求最小值; 打印结果 -
C/C++利用三元组实现稀疏矩阵的压缩存储
2021-06-24 11:02:24对于稀疏矩阵有两种存储方式:三元组和十字链表法。本文介绍用三元组存储。 代码 【注】: 稀疏矩阵的下标从1开始,而一维数组下标从0开始 #include <iostream> using namespace std; //定义结点 ... -
数据结构严蔚敏----稀疏矩阵的三元组表示
2019-01-02 20:21:52题目:输入稀疏矩阵,建立稀疏矩阵三元组顺序结构,实现转置 先来了解一下稀疏矩阵和三元组的关系: 稀疏矩阵的概念是:一个m行n列的矩阵,若它的非零元个数特别少,即可称它为稀疏矩阵 如何进行稀疏矩阵的压缩... -
稀疏矩阵的三元组表示方式代码模板(C++表示)
2019-05-04 10:59:01稀疏矩阵的三元组表示方式代码模板 #include <iostream> #define MaxSize 100 //定义三元组线性表中的数据元素存储结构 typedef struct { int row; //行号 int col; //列号 ElemType d; //元素值,... -
三元组稀疏矩阵的转置,用C++实现
2021-05-23 12:35:17书上不是有吗?把我的给你看看,没关系,要下下礼拜才交#includeusing namespace std;class matrix{public:int data[100][100];int m,n;...//稀疏矩阵初始化void SpmDisplay(spmatrix spm);//显... -
稀疏矩阵的三元组表示法和稀疏矩阵的转置
2018-12-24 19:27:34首先我们需要了解什么是稀疏矩阵? 矩阵中非零元素的个数远远...正因为这样,我们对稀疏矩阵进行存储选择的方法不是平常的直接存储,因为要存储好多非零元素,太浪费空间,所以我们选择采用三元组进行存储。对于... -
考研数据结构之数组(5.3)——使用三元组法表示稀疏矩阵(C表示)
2020-05-24 17:43:32使用三元组表示法来表示稀疏矩阵。 三元组数据结构是一个长度为n,表内每个元素都有3个分量的线性表,其3个分量分别为行下标和列下标。元素结构体定义如下: /* 三元组的结构体 */ typedef struct { int val;// ... -
数据结构实现稀疏矩阵(采用三元组表示)的基本运算
2019-11-19 16:51:32数据结构实现稀疏矩阵(采用三元组表示)的基本运算 目的 领会稀疏矩阵三元组存储结构及基本算计运算 内容 假设n*n的稀疏矩阵A采用三元组表示,设计一个程序实现以下功能 生成以下两个稀疏矩阵的三元组a和b 输出a... -
用三元组表实现稀疏矩阵的基本操作
2021-10-31 12:33:14函数 InitSPNode()用来建立一个稀疏矩阵的三元组表。 首先输入行数、列数和非零元的值,输入(-1,-1,-1)结束输入。 >函数showMatrix()用来输出稀疏矩阵 算法中按矩阵a的列进行循环处理,对a的每一列扫描三元组... -
用三元组存储稀疏矩阵及其快速转置
2020-07-27 10:32:42稀疏矩阵可以用一个三元组数组表示,数组每个元素是一个三元组,三元组形式为 (矩阵行号,矩阵列号,元素值) 三元组个数,即数组长度,为稀疏矩阵的非零元素个数。 三元组元素按照行号递增,列号递增的方式排序。 ... -
三元组稀疏矩阵转置算法
2020-03-12 16:39:08三元组稀疏矩阵转置运算 1.关于稀疏矩阵的解释(定义) 矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素的分布没有规律,通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时,则称该...