数据结构-实验四讲义-稀疏矩阵的基本操作

数据结构实验四稀疏矩阵运算1、实验目的掌握三元组法存储稀疏矩阵的方法及相关的基本操作。

2、实验内容∙用三元组法存放稀疏矩阵∙求出矩阵转置结果∙求出矩阵相乘结果∙输出结果矩阵3、实验要求∙用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入∙要求采用稀疏矩阵快速转置算法∙若两个矩阵不能相乘则输出“Error”4、试验参考程序typedef s tr uct { // 定义三元组的元素int i, j;int e;} Tr iple;typedef s tr uct { // 定义矩阵Tr iple data[MA XSI ZE + 1];int mu, nu, tu;} TSMa tr ix;typedef s tr uct { // 定义行逻辑连接矩阵Tr iple data[MA XSI ZE + 2];int rpos[MA XROW + 1];int mu, nu, tu;} RLSMatr ix;矩阵输入函数bool InPutT SMat r ix(T SMatr ix & T) {cout << "输入矩阵的行，列和非零元素个数:" << e ndl;cin >> T.mu >> T.nu >> T.tu;cout << "请输出非零元素的位置和值:" << e ndl;for (int k = 1;; k <= T.t u; k++)cin >> T.data[k].i >> T.da ta[k].j >> T.data[k].e;retur n t rue;}请补充完成下列矩阵转置函数、矩阵乘法函数与矩阵输出函数Bool Trans poseSMa tr ix(T SMa t r ix M, T SMat r ix & T){TSMatrix M,T; //定义预转置的矩阵InPutTSMatrix(M, 0); //输入矩阵int num[MAXROW+1];int cpot[MAXROW+1]; // 构建辅助数组int q,p,t;T.tu=M.tu; T.mu=M.nu; T.nu=M.mu;if(T.tu){for(int col=1;col<=M.nu;col++) num[col]=0;for(t=1;t<=M.tu;t++) ++num[M.data[t].j];cpot[1]=1;for(int i=2;i<=M.nu;i++) cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元组中出现的位置for(p=1;p<=M.tu;p++){col=M.data[p].j; q=cpot[col];T.data[q].i=col; T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e; ++cpot[col];}}cout<<"输入矩阵的转置矩阵为"<<endl;OutPutSMatrix(T);return true;}Bool MultSMatr ix(RLSMatr ix M, RL SMatr ix N，RL SMat r ix & T){RLSMatrix M,N,Q; // 构建三个带“链接信息”的三元组表示的数组InPutTSMatrix(M,1); // 用普通三元组形式输入数组InPutTSMatrix(N,1);Count(M); Count(N);if(M.nu!=N.mu) return false;Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; // Q初始化int ctemp[MAXROW+1]; // 辅助数组int arow,tp,p,brow,t,q,ccol;if(M.tu*N.tu){ // Q是非零矩阵for( arow=1;arow<=M.mu;arow++){///memset(ctemp,0,N.nu);for(int x=1;x<=N.nu;x++) // 当前行各元素累加器清零ctemp[x]=0;Q.rpos[arow]=Q.tu+1; // 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1 if(arow<M.mu) tp=M.rpos[arow+1];else tp=M.tu+1;for(p=M.rpos[arow];p<tp;p++){ // 对当前行每个非零元素进行操作brow=M.data[p].j; // 在N中找到i值也操作元素的j值相等的行if(brow<N.mu) t=N.rpos[brow+1];else t=N.tu+1;for(q=N.rpos[brow];q<t;q++){ // 对找出的行当每个非零元素进行操作ccol=N.data[q].j;ctemp[ccol] += M.data[p].e*N.data[q].e; // 将乘得到对应值放在相应的元素累加器里面}}for(ccol=1;ccol<=Q.nu;ccol++) // 对已经求出的累加器中的值压缩到Q中if(ctemp[ccol]){if(++Q.tu>MAXSIZE) return false;Q.data[Q.tu].e=ctemp[ccol];Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;}}OutPutSMatrix(Q);return true;}}boo l O utP utSMatrix(T SMat r ix T){// 输出矩阵，按标准格式输出int m,n,k=1;fo r(m=0;m<T.mu;m++){fo r(n=0;n<T.nu;n++){if((T.d a ta[k].i-1)==m&&(T.d a ta[k].j-1)==n){co ut.w id th(4);co ut<<T.d a ta[k++].e;}e ls e{co ut.w id th(4); co ut<<"0"; }}co ut<<e nd l;}re turn true;}}并建立ma in（）函数对上述函数进行测试。

稀疏矩阵基本操作实验报告一、实验内容稀疏矩阵得压缩储存结构,以及稀疏矩阵得三元组表表示方法下得转置、相加、相乘等算法二、实验目得1.熟悉数组、矩阵得定义与基本操作2.熟悉稀疏矩阵得储存方式与基本运算3.理解稀疏矩阵得三元组表类型定义,掌握稀疏矩阵得输入、输出与转置算法三、实验原理1.使用三元组储存矩阵中得非零元素(三元组分别储存非零元素得行下标,列下标与元素值)。

除了三元组表本身,储存一个稀疏矩阵还需要额外得三个变量,分别储存矩阵得非零元个数,矩阵得行数与矩阵得列数。

2.稀疏矩阵得创建算法:第一步:根据矩阵创建一个二维数组,表示原始矩阵第二步:取出二维数组中得元素(从第一个元素开始取),判断取出元素就是否为非零元素,如果为非零元素,把该非零元素得数值以及行下标与列下表储存到三元数组表里,否则取出下一个元素,重复该步骤。

第三步:重复第二步,知道二维数组中所有得元素已经取出。

3.稀疏矩阵倒置算法:第一步:判断进行倒置得矩阵就是否为空矩阵,如果就是,则直接返回错误信息、第二步:计算要倒置得矩阵每列非零元素得数量,存入到ｎum数组(其中nｕm［ｉ］代表矩阵中第i列非零元素得个数)、以及倒置后矩阵每行首非零元得位置,存入ｃp ｏt数组中(其中cpｏt表示倒置后矩阵每行非零元得位置,对应表示原矩阵每列中第一个非零元得位置)。

第三步:确定倒置后矩阵得行数与列数。

第四步:取出表示要导致矩阵中三元组表元素{e, I, j｝(第一次取出第一个,依次取出下一个元素),从第二步ｃpot数组中确定该元素倒置后存放得位置(ｃpot［j］),把该元素得行下标与列下标倒置以后放入新表得指定位置中。

cpot［j］变量加一。

第五步:重复第四步,直到三元组表中所有得元素都完成倒置。

第六步:把完成倒置运算得三元组表输出、4.稀疏矩阵加法算法:第一步:检查相加两个矩阵得行数与列数就是否相同,如果相同,则进入第二步,否则输出错误信息。

第二步:定义变量i与j,用于控制三元组表得遍历。

数据结构之稀疏矩阵稀疏矩阵的存储方式和操作分析稀疏矩阵是指矩阵中大部分元素为零的特殊矩阵。

在实际应用中，稀疏矩阵经常出现，如图像处理、网络分析和科学计算等领域。

对于稀疏矩阵的存储和操作是数据结构中的重要内容。

本文将介绍稀疏矩阵的存储方式和相关操作的分析。

一、稀疏矩阵存储方式稀疏矩阵的存储方式有多种，其中三元组顺序表和二维数组是比较常用的方法。

1. 三元组顺序表三元组顺序表是一种基于行优先存储的方式，可以将稀疏矩阵以非零元素的形式存储起来。

主要包括行号、列号和元素值三个信息。

以一个4x5的稀疏矩阵为例，其中有三个非零元素分别为A[1][2]=3, A[2][3]=4, A[3][4]=5。

可以使用三元组顺序表来存储：```行号列号元素值1 2 32 3 43 4 5```三元组顺序表的优点是可以节省存储空间，同时也方便进行矩阵的操作。

但是在进行元素的查找和修改时，效率较低。

2. 二维数组二维数组是一种常见的矩阵表示方法，可以直接使用二维数组来表示稀疏矩阵。

其中非零元素的位置用实际的值表示，其余位置用零值表示。

以同样的4x5的稀疏矩阵为例，使用二维数组存储如下：```0 0 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5```二维数组的优点是简单直观，并且可以快速进行元素的查找和修改。

但当稀疏矩阵的规模较大时，会造成较高的存储资源浪费。

二、稀疏矩阵的操作分析对于稀疏矩阵的操作，主要包括矩阵的转置、相加、相乘等。

1. 转置操作稀疏矩阵的转置是指将原始矩阵的行与列对调。

对于三元组顺序表来说，转置操作主要涉及到行号和列号的交换。

而对于二维数组来说，可以直接在取值的时候将行号和列号对调即可。

2. 相加操作稀疏矩阵的相加操作是指将两个矩阵对应位置的元素相加。

对于三元组顺序表来说，可以通过遍历两个矩阵的非零元素，并将其对应位置的元素相加。

而对于二维数组来说，可以直接将对应位置的元素相加即可。

3. 相乘操作稀疏矩阵的相乘操作是指将两个矩阵相乘得到一个新的矩阵。

稀疏矩阵的操作--课程设计重点讲义资料攀枝花学院学⽣课程设计（论⽂）题⽬：稀疏矩阵的操作学⽣姓名：学号：所在院(系)：数学与计算机学院专业：计算机科学与技术班级： 1班指导教师：职称：讲师2016年6 ⽉24 ⽇攀枝花学院教务处制攀枝花学院本科学⽣课程设计任务书注：任务书由指导教师填写。

摘要本课程设计主要实现在三元组存储结构与⼗字链表存储结构下输⼊稀疏矩阵，并对稀疏矩阵进⾏转置，相加，相乘操作，最后输出运算后的结果。

在程序设计中，考虑到⽅法的难易程度，采⽤了先⽤三元组实现稀疏矩阵的输⼊，输出，及其转置，相加，相乘操作的⽅法，再在⼗字链表下实现。

程序通过调试运⾏，结果与预期⼀样，初步实现了设计⽬标。

关键词程序设计，稀疏矩阵，三元组，⼗字链表⽬录摘要 (II)1课程设计题⽬与要求 (1)1.1课程设计的⽬的 (1)1.2题⽬要求 (1)2.2设计思路 (2)2.3数据结构设计 (2)2.4软件结构设计 (3)3详细设计 (5)3.1稀疏矩阵的定义 (5)3.2主程序模块 (6)3.3稀疏矩阵模块 (7)3.4⼗字链表模块 (15)3.4.1创建⼗字链表 (15)3.4.2⼗字链表的输出 (16)4程序测试及运⾏ (18)5 总结 (21)参考⽂献 (22)1 课程设计题⽬与要求1.1课程设计的⽬的1．掌握多维数组的逻辑结构和存储结构。

2．掌握稀疏矩阵的压缩存储及基本操作。

1.2题⽬要求（1）稀疏矩阵采⽤三元组表⽰，求两个具有相同⾏列数的稀疏矩阵A和B的相加矩阵C，并输出C。

（2）求出A的转置矩阵D，输出D（⽤两种⽅法实现，原始算法和改进的算法）。

（3）求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

2.1模块⽰意图如图2.1所⽰。

图 2.1主程序模块主要进⾏命令操作，接收命令，处理命令，退出操作等。

稀疏矩阵模块实现矩阵的相加，矩阵的相乘和矩阵的转置。

⼗字链表模块主要是创建⼗字链表和输出⼗字链表2.2设计思路本实验要求是使⽤C语⾔设计三元组，⼗字链表实现稀疏矩阵的加、转、乘。

数据结构实验报告稀疏矩阵运算实验目的：1.学习并理解稀疏矩阵的概念、特点以及存储方式。

2.掌握稀疏矩阵加法、乘法运算的基本思想和算法。

3.实现稀疏矩阵加法、乘法的算法，并进行性能测试和分析。

实验原理：稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。

在实际问题中，有许多矩阵具有稀疏性，例如文本矩阵、图像矩阵等。

由于存储稀疏矩阵时，对于大量的零元素进行存储是一种浪费空间的行为，因此需要采用一种特殊的存储方式。

常见的稀疏矩阵的存储方式有三元组顺序表、十字链表、行逻辑链接表等。

其中，三元组顺序表是最简单直观的一种方式，它是将非零元素按行优先的顺序存储起来，每个元素由三个参数组成：行号、列号和元素值。

此外，还需要记录稀疏矩阵的行数、列数和非零元素个数。

稀疏矩阵加法的原理是将两个稀疏矩阵按照相同的行、列顺序进行遍历，对于相同位置的元素进行相加，得到结果矩阵。

稀疏矩阵乘法的原理是将两个稀疏矩阵按照乘法的定义进行计算，即行乘以列的和。

实验步骤：1.实现稀疏矩阵的三元组顺序表存储方式，并完成稀疏矩阵的初始化、转置、打印等基本操作。

2.实现稀疏矩阵的加法运算，并进行性能测试和分析。

3.实现稀疏矩阵的乘法运算，并进行性能测试和分析。

4.编写实验报告。

实验结果：经过实验测试，稀疏矩阵的加法和乘法算法都能正确运行，并且在处理稀疏矩阵时能够有效节省存储空间。

性能测试结果表明，稀疏矩阵加法、乘法的运行时间与非零元素个数有关，当非零元素个数较少时，运算速度较快；当非零元素个数较多时，运算速度较慢。

实验分析：稀疏矩阵的运算相对于普通矩阵的运算有明显的优势，可以节省存储空间和运算时间。

在实际应用中，稀疏矩阵的存储方式和运算算法都可以进行优化。

例如，可以采用行逻辑链接表的方式存储稀疏矩阵，进一步减少存储空间的占用；可以采用并行计算的策略加快稀疏矩阵的运算速度。

总结：通过本次实验，我深入学习了稀疏矩阵的概念、特点和存储方式，掌握了稀疏矩阵加法、乘法的基本思想和算法，并通过实验实现了稀疏矩阵的加法、乘法运算。

数据结构实验报告实验四稀疏矩阵的表示和转置一、实验目的1. 掌握稀疏矩阵的三元组顺序表存储结构2. 掌握稀疏矩阵的转置算法。

二、实验内容采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。

（算法5.1）三、实验步骤：1. 构建稀疏矩阵M。

2. 求稀疏矩阵M的转置矩阵T。

3. 输出稀疏矩阵M和稀疏矩阵T。

四、算法说明首先要创建稀疏矩阵的三元组顺序表存储表示，定义mu,nu,tu分别表示矩阵的行数、列数和非零元个数。

在进行稀疏矩阵的转置时要做到(1)：将矩阵的行列值相互交换；（2）：将每个三元组的i，j相互调换；（3）：重排三元组之间的次序便可实现矩阵的转置。

五、测试结果六、分析与探讨在此次程序中转置的方法称为快速转置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元的位置。

七、附录：源代码数据结构实验报告源代码列在附录中，要求程序风格清晰易理解，有充分的注释。

有意义的注释行不少于30%。

#include <stdio.h>#define MAXSIZE 5#define MAXMN 200typedef struct{int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE];int rpos[MAXMN];int mu,nu,tu;//矩阵的行数、列数和非零元个数}TSMatrix; //行逻辑连接的顺序表int main(){printf("矩阵M\n");TSMatrix M,T;printf("i j v\n");int i;for(i=0;i<MAXSIZE;i++)scanf("%d %d %d",&M.data[i].i, &M.data[i].j, &M.data[i].e); printf("请输入矩阵M的行数mu,列数nu,及非零元的个数tu\n"); scanf("%d %d %d",&M.mu, &M.nu, &M.tu);//求稀疏矩阵M的转置矩阵TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu){int t, column, num[MAXMN]={0}; //用来统计M中每列非零元的个数for(t=0;t<M.tu;t++)++num[M.data[t].j];T.rpos[0]=0; for(column=1;column<T.mu;column++)T.rpos[column]=T.rpos[column-1]+num[column-1]; int p, q;for(p=0;p<M.tu;p++){column=M.data[p].j;q=T.rpos[column];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;数据结构实验报告T.data[q].e=M.data[p].e;T.rpos[column]++; //转置矩阵T中同一行的非零元的起始位置自增1 } }//输出矩阵M及转置矩阵Tprintf("\n矩阵T：\n");printf("i j v\n");for(i=0;i<T.tu;i++)printf("%d %d %d\n",T.data[i].i, T.data[i].j, T.data[i].e); printf("\n");return 0;}欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求。

稀疏矩阵存储和操作稀疏矩阵的数据结构与算法稀疏矩阵是指具有大量零元素和少量非零元素的矩阵。

在实际场景中，由于矩阵中大部分元素为零，传统的矩阵存储方式会造成大量的存储空间的浪费以及数据操作的低效性。

因此，为了节省存储空间和提高数据操作的效率，稀疏矩阵的存储和操作需要借助于特定的数据结构和算法。

一、稀疏矩阵存储的数据结构1.1. 压缩存储方法压缩存储方法是一种常用的稀疏矩阵存储方法。

常见的压缩存储方法有三种：行压缩法（CSR）、列压缩法（CSC）和十字链表法。

1.1.1. 行压缩法（CSR）行压缩法是通过两个数组来存储稀疏矩阵的非零元素。

第一个数组存储非零元素的值，第二个数组存储非零元素在矩阵中的位置信息。

1.1.2. 列压缩法（CSC）列压缩法与行压缩法相似，只是存储方式不同。

列压缩法是通过两个数组来存储稀疏矩阵的非零元素。

第一个数组存储非零元素的值，第二个数组存储非零元素在矩阵中的位置信息。

1.1.3. 十字链表法十字链表法是一种更加灵活的稀疏矩阵存储方法。

通过使用链表的方式，将非零元素存储在链表中，并且每个非零元素还具有行和列的指针，方便进行数据操作。

1.2. 坐标存储法坐标存储法是一种简单直观的稀疏矩阵存储方法。

每个非零元素包括行列坐标和元素值，通过三元组的方式进行存储。

二、稀疏矩阵的操作算法2.1. 矩阵转置矩阵转置是指将原矩阵的行变为列，列变为行的操作。

对于稀疏矩阵，常用的转置算法为快速转置算法。

该算法通过统计每列非零元素的个数，并根据列的非零元素个数确定每个非零元素转置后的位置。

2.2. 矩阵相加矩阵相加是指将两个矩阵对应位置上的元素相加得到一个新的矩阵。

对于稀疏矩阵的相加，可以遍历两个矩阵的非零元素，对相同位置上的元素进行相加。

2.3. 矩阵相乘矩阵相乘是指将两个矩阵相乘得到一个新的矩阵。

对于稀疏矩阵的相乘，常用的算法为稀疏矩阵乘法算法。

该算法通过遍历两个矩阵的非零元素，按照矩阵乘法的规则计算得到新矩阵的非零元素。

浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验四稀疏矩阵的基本操作--用链接存储结构实验成绩指导老师（签名）日期一.实验目的和要求1．了解稀疏矩阵的三元组线性表存储方法。

2．掌握稀疏矩阵采用链式存储结构时基本操作的实现。

二. 实验内容1．编写稀疏矩阵采用带行指针向量的链接存储结构时基本操作的实现函数。

基本操作包括：①初始化稀疏矩阵；②输入稀疏矩阵；③输出稀疏矩阵；④稀疏矩阵的转置运算。

要求把稀疏矩阵的存储结构定义及基本操作实现函数存放在头文件LinkMatrix.h中，主函数main() 存放在主文件test7_2.cpp中，在主函数中通过调用LinkMatrix.h中的函数进行测试。

2．选做：编写稀疏矩阵的相乘运算实现函数，要求把该函数添加到头文件LinkMatrix.h中，并在主文件test7_2.cpp中添加相应语句进行测试。

3．填写实验报告，实验报告文件取名为report4.doc。

4．上传实验报告文件report4.doc与源程序文件LinkMatrix.h及test7_2.cpp到Ftp服务器上你自己的文件夹下。

三. 函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路函数：void InitMatrix(LMatrix &M)功能：初始化稀疏矩阵思路：将稀疏矩阵的行、列、元素个数均置为0，元素指针数组全部置为NULL函数：void InputMatrix(LMatrix &M, int m, int n)功能：输入稀疏矩阵思路：以行、列、值的方式输入稀疏矩阵的每个元素函数：void OutputMatrix(LMatrix M)功能：输出稀疏矩阵思路：以行、列、值的方式输出稀疏矩阵的每个元素函数：void MyTranspose(LMatrix & M)功能：稀疏矩阵的转置运算思路：主要是通过添加一个指针数组，对M进行一次遍历，完全使用其原有的空间来进行转置。

稀疏矩阵的相关操作稀疏矩阵是指在一个矩阵中，大部分元素为0的矩阵。

由于大部分元素为0，而非零元素相对较少，稀疏矩阵的存储和处理具有一定的特殊性。

在实际应用中，经常需要对稀疏矩阵进行各种操作，如创建、存储、加法操作等。

本文将从这些方面详细介绍稀疏矩阵的相关操作。

首先，创建稀疏矩阵需要考虑两个关键因素：矩阵的大小和矩阵的稀疏性。

对于稀疏矩阵的大小，一般可以使用行数和列数来描述。

而对于稀疏矩阵的稀疏性，可以使用一个矩阵的非零元素个数与总元素个数的比值来衡量，一般使用稀疏度来表示，即非零元素个数与总元素个数的比值。

创建稀疏矩阵的方法有多种，下面介绍两种常见的方法。

1.压缩矩阵存储法：该方法将稀疏矩阵的非零元素和对应的行列坐标存储在一个矩阵中。

其中，矩阵的每一行存储一个非零元素的值、行和列坐标。

这种方法虽然节约了存储空间，但是在进行矩阵操作时，需要通过遍历矩阵找到对应的非零元素，因此操作效率较低。

2.链表存储法：该方法将稀疏矩阵的非零元素和对应的行列坐标存储在一个链表中。

链表的每个节点包含一个非零元素的值、行和列坐标，以及下一个非零元素的指针。

这种方法在插入和删除操作时比较方便，并且节约了存储空间。

但是，链表存储法在进行矩阵操作时，也需要通过遍历链表找到对应的非零元素，因此操作效率较低。

除了创建稀疏矩阵，还需要进行其他各种操作，如稀疏矩阵的加法、乘法、转置等。

稀疏矩阵的乘法操作较为复杂。

对于两个稀疏矩阵相乘，需要根据矩阵乘法的定义，将一个矩阵的行与另一个矩阵的列进行乘法运算，然后将结果相加得到最终的乘积矩阵。

由于稀疏矩阵的特殊性，可以采用稀疏矩阵乘法算法进行计算，提高乘法操作的效率。

1.三元组转置法：该方法将稀疏矩阵的非零元素和对应的行列坐标存储在三个数组中，分别是非零元素数组、行坐标数组和列坐标数组。

将这三个数组的元素进行转置，并重新组合成转置后的稀疏矩阵。

2.链表转置法：该方法将稀疏矩阵的非零元素和对应的行列坐标存储在链表中。