下载文档原格式
数据结构实验四稀疏矩阵运算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.链表转置法：该方法将稀疏矩阵的非零元素和对应的行列坐标存储在链表中。
教学单位计算机科学与技术学生学号************数据结构课程设计报告书题目稀疏矩阵运算器学生姓名秦豹专业名称软件工程指导教师李志敏实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。
需要分析：稀疏矩阵是指那些多数元素为零的矩阵。
利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。
实现一个能进行稀疏矩阵基本运算的运算器。
要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。
输入以三元组表示，输出以通常的阵列形式列出。
软件平台：Windows 2000，Visual C＋＋6.0或WINTC概要设计：ADT Array {数据对象:D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}数据关系:R = { ROW, COL }ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1}COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤j≤b2-2}基本操作：CreateSMatrix(&M); //操作结果:创建稀疏矩阵M.Print SMatrix(M);//初始化条件: 稀疏矩阵M存在.//操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M的列数等于N的行数.//操作结果:求稀疏矩阵的乘积Q=M*N.} ADT Array调试测试：初始界面矩阵的加法矩阵的减法矩阵的转置矩阵的乘法程序源码：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAXSIZE 40 //假设非零元素个数的最大值为40#define MAXRC 20 //假设矩阵的最大行数为20typedef int ElemType;typedef struct{int i,j; //非零元的行下标和列下标ElemType e; //非零元的值}Triple;typedef struct{Triple data[MAXSIZE+1];int rpos[MAXRC+1]; //各行第一个非零元在三元组的位置表int hs,ls,fls;}TSMatrix,*Matrix;void Creat(TSMatrix &M){int i,k;for(i=1;i<=MAXRC+1;i++)M.rpos[i]=0;printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");scanf("%d %d %d",&M.hs,&M.ls,&M.fls);for(i=1;i<=M.fls;i++){printf("请用三元组形式输入矩阵的元素(行列非零元素):");scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);}for(i=1,k=1;i<=M.hs;i++){M.rpos[i]=k;while(M.data[k].i<=i && k<=M.fls)k++;}}void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n){int a,b,temp,l;C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a<=A.fls && b<=B.fls){if(A.data[a].i==B.data[b].i){if(A.data[a].j<B.data[b].j)C.data[l++]=A.data[a++];else if(A.data[a].j>B.data[b].j){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}else{temp=A.data[a].e+n*B.data[b].e;if(temp){C.data[l]=A.data[a];C.data[l].e=temp;l++;}a++;b++;}}else if(A.data[a].i<B.data[b].i)C.data[l++]=A.data[a++];else {C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;} }while(a<=A.fls)C.data[l++]=A.data[a++];while(b<=B.fls){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}C.fls=l-1;}int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q){int arow,brow,ccol,tp,p,q,t;int ctemp[MAXRC+1];if(A.ls!=B.hs) return 0;Q.hs=A.hs;Q.ls=B.ls;Q.fls=0;if(A.fls*B.fls){for(arow=1;arow<=A.hs;arow++){for(ccol=1;ccol<=Q.ls;ccol++)ctemp[ccol]=0;Q.rpos[arow]=Q.fls+1;if(arow<A.hs) tp=A.rpos[arow+1];else tp=A.fls+1;for(p=A.rpos[arow];p<tp;p++){brow=A.data[p].j;if(brow<B.hs) t=B.rpos[brow+1];else t=B.fls+1;for(q=B.rpos[brow];q<t;q++){ccol=B.data[q].j;ctemp[ccol]+=A.data[p].e*B.data[q].e;}}for(ccol=1;ccol<=Q.ls;ccol++){if(ctemp[ccol]){if(++Q.fls>MAXSIZE) return 0;Q.data[Q.fls].i=arow;Q.data[Q.fls].j=ccol;Q.data[Q.fls].e=ctemp[ccol];}}}}return 1;}void Print_SMatrix(TSMatrix M){int k,l,n;Matrix p;p=&M;for(k=1,n=1;k<=p->hs;k++){for(l=1;l<=p->ls;l++){if(p->data[n].i==k && p->data[n].j==l){printf("%5d",p->data[n].e);n++;}elseprintf("%5d",0);}printf("\n");}printf("\n");}void Zhuanzhi(TSMatrix *a,TSMatrix *b){int q,col,p;b->hs=a->ls;b->ls=a->hs;b->fls=a->fls;if(b->fls){q=1;for(col=1;col<=a->ls;col++)for(p=1;p<=a->fls;p++)if(a->data[p].j==col){b->data[q].i=a->data[p].j;b->data[q].j=a->data[p].i;b->data[q].e=a->data[p].e;++q;}}}void Destory_SMatrix(TSMatrix &M){M.hs=M.ls=M.fls=0;}void main(){TSMatrix A,B,C;TSMatrix *p=&A,*q=&B;int flag,n;while(1){system("cls");printf("\n\n\n");printf("\t┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("\t┃*** 稀疏矩阵的加、减、转、乘*** ┃\n");printf("\t┣━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");printf("\t┃1、稀疏矩阵的加法┃\n");printf("\t┃2、稀疏矩阵的减法┃\n");printf("\t┃3、稀疏矩阵的转置┃\n");printf("\t┃4、稀疏矩阵的乘法┃\n");printf("\t┃5、退出该应用程序┃\n");printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf("输入要进行的项目的编号:");scanf("%d",&flag);if(flag==5) break;Creat(A);printf("矩阵A:\n"); Print_SMatrix(A);switch(flag){case 1: Creat(B);n=1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A+B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 2: Creat(B);n=-1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A-B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 3: printf("A->B:\n");Zhuanzhi(p,q);Print_SMatrix(B);break;case 4: Creat(B);printf("矩阵B:\n");Print_SMatrix(B);printf("A*B:\n");n=Xiangcheng(A,B,C);if(!n) printf("错误!行列不匹配\n");else Print_SMatrix(C);break;default: printf("输入错误!\n");}Destory_SMatrix(A);Destory_SMatrix(B);Destory_SMatrix(C);getchar();getchar();}printf("\n\t\t\t ***程序已经退出***\n");getchar();}小结：。
数据结构——稀疏矩阵运算器目录1. 简介1.1 概述1.2 稀疏矩阵的定义2. 数据结构设计2.1 稀疏矩阵的存储方式2.2 稀疏矩阵的数据结构设计3. 基本操作3.1 创建稀疏矩阵3.2 初始化稀疏矩阵的元素3.3 稀疏矩阵的加法3.4 稀疏矩阵的减法3.5 稀疏矩阵的乘法4. 高级操作4.1 稀疏矩阵的转置4.2 稀疏矩阵的快速乘法5. 示例应用5.1 矩阵乘法示例5.2 矩阵转置示例6. 总结与展望1. 简介1.1 概述稀疏矩阵是一种具有大量零元素的矩阵，对于大规模稀疏矩阵的运算，传统的矩阵运算方法效率较低。
本文档介绍了一种稀疏矩阵运算器的设计和实现。
1.2 稀疏矩阵的定义稀疏矩阵是指矩阵中大部分元素为零的矩阵。
相比于密集矩阵，稀疏矩阵的存储和运算可以进行有效的优化，提高运算效率。
2. 数据结构设计2.1 稀疏矩阵的存储方式稀疏矩阵可以使用多种方式进行存储，常见的方法有三元组表示法和十字链表表示法。
本文档使用三元组表示法进行存储。
2.2 稀疏矩阵的数据结构设计稀疏矩阵的数据结构设计包括矩阵的行数、列数和非零元素的个数等基本信息，以及按照行优先的方式存储稀疏矩阵的非零元素和对应的行列索引。
3. 基本操作3.1 创建稀疏矩阵创建稀疏矩阵的操作包括输入矩阵的行数和列数，以及非零元素的个数，以便为矩阵分配内存空间。
3.2 初始化稀疏矩阵的元素初始化稀疏矩阵的操作包括输入矩阵的非零元素及其对应的行列索引。
3.3 稀疏矩阵的加法实现稀疏矩阵的加法运算，包括对两个稀疏矩阵进行相应的遍历和运算操作。
3.4 稀疏矩阵的减法实现稀疏矩阵的减法运算，包括对两个稀疏矩阵进行相应的遍历和运算操作。
3.5 稀疏矩阵的乘法实现稀疏矩阵的乘法运算，包括对两个稀疏矩阵进行相应的遍历和运算操作。
4. 高级操作4.1 稀疏矩阵的转置实现稀疏矩阵的转置操作，包括对稀疏矩阵的行列索引进行互换。
4.2 稀疏矩阵的快速乘法通过对矩阵进行合并和切分等操作，实现稀疏矩阵的快速乘法运算，提高运算效率。
实现稀疏矩阵的基本运算实验报告实验报告：稀疏矩阵的基本运算实验一、引言稀疏矩阵是指在矩阵中大部分元素为0的情况下，只存储非零元素及其位置信息的数据结构。
由于稀疏矩阵节省空间，可以节约存储和计算时间，因此在科学计算和大规模矩阵运算中应用广泛。
本实验旨在实现稀疏矩阵的基本运算，包括矩阵加法、矩阵乘法和转置运算，并对其效率进行测试。
二、实验方法本实验使用C++语言实现稀疏矩阵的基本运算。
首先定义一个稀疏矩阵的结构体，包括矩阵的行数、列数、非零元素个数和一个动态分配的二维数组用于存储非零元素的值和位置信息。
然后根据实验要求，分别实现矩阵的加法、乘法和转置运算的函数。
1.矩阵加法：遍历两个矩阵的非零元素，将对应位置的元素相加存入结果矩阵。
2.矩阵乘法：遍历两个矩阵的非零元素，将对应位置的元素相乘并累加，存入结果矩阵。
3.转置运算：将矩阵的行列互换，同时调整非零元素的位置信息。
最后，通过随机生成不同大小的稀疏矩阵进行实验，并记录每种运算的运行时间，分析稀疏矩阵在不同运算中的效率差异。
三、实验结果1.矩阵加法运算：对两个1000*1000的稀疏矩阵进行加法运算，耗时0.05秒。
2.矩阵乘法运算：对一个1000*1000和一个1000*100的稀疏矩阵进行乘法运算，耗时0.1秒。
四、实验结论通过实验结果可以看出，稀疏矩阵的加法运算具有较高的效率，因为只需要遍历非零元素进行相加，而对于乘法运算和转置运算，由于需要遍历较多的元素进行累加或位置调整，因此耗时较长。
在矩阵转置运算中，由于矩阵规模较大，耗时最长。
总结而言，稀疏矩阵在处理大规模矩阵运算时具有一定的优势，可以节约存储空间和计算时间。
在实践中，可以根据应用的需求选择适当的数据结构和算法，进一步提升稀疏矩阵的运算效率。
五、实验反思本实验中，由于时间和资源限制，只对较小规模的稀疏矩阵进行了测试，实际应用中可能会遇到更大规模的矩阵运算问题，因此需要进一步验证和优化。
稀疏矩阵的存储和乘法操作⼀稀疏矩阵的存储1.三元组顺序表三元组表⽰法就是在存储⾮零元的同时，存储该元素所对应的⾏下标和列下标。
稀疏矩阵中的每⼀个⾮零元素由⼀个三元组(i,j,a ij)唯⼀确定。
矩阵中所有⾮零元素存放在由三元组组成的顺序表中(通常⽤数组)。
所以三元组的逻辑结构如下：//————稀疏矩阵的三元组表⽰法————//#define MAX_SIZE 1500 //表⽰稀疏矩阵的⾮零元素的最⼤个数class Triple{int i,j;//表⽰⾮零元素的⾏下表和列下标int val;//⾮零元素的值，此处以int类型为例};class TSMatrix{Triple data[MAX_SIZE];int row_num,col_num,cnt;//稀疏矩阵的⾏数、列数以及⾮零元素的个数};注意，此处的⾮零元素的三元组是以⾏序为主序顺序排列的。
2.⾏逻辑链接顺序表⾏逻辑链接顺序表的实质就是在三元组顺序表的基础上加了⼀个数组，这个数组⽤于存储稀疏矩阵中每⾏的第⼀个⾮零元素的在三元组顺序表中的位置(此处⼀定要理解对，是在三元组顺序表中的位置)。
所以其逻辑结构如下：//————稀疏矩阵的⾏逻辑链接表⽰法————//#define MAX_SIZE 1500 //表⽰稀疏矩阵的⾮零元素的最⼤个数#define MAX_ROW 1500 //表⽰稀疏矩阵的⾏数的最⼤个数class Triple{int i,j;//表⽰⾮零元素的⾏下表和列下标int val;//⾮零元素的值，此处以int类型为例};class RLSMatrix{Triple data[MAX_SIZE]; //⾮零元三元组表int rpos[MAX_ROW];//每⾏第⼀个⾮零元素的位置int row_num,col_num,cnt;//稀疏矩阵的⾏数、列数以及⾮零元素的个数};3.⼗字链表当稀疏矩阵的⾮零元个数和位置在操作过程中变化较⼤时，就不易采⽤顺序存储结构来表⽰三元组的线性表。
实验编号：4四川师大《数据结构》实验报告2016年11月12日实验四字符串、稀疏矩阵实验_一．实验目的及要求（1）熟悉字符串类型的实现方法，并完成串的一些基本操作；（2）掌握稀疏矩阵的三元组顺序表存储表示，并实现矩阵的转置运算。
二．实验内容（1）编程实现两个串S1和S2的比较。
（要求自己设计串的存储结构，并编写比较函数，不要调用系统提供的函数）（2）编程实现稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置等）。
（3）编程实现稀疏矩阵的十字链表存储表示及基本操作的实现（建立、输出等）。
注：（2）必做，（1）（3）选做。
三．主要仪器设备及软件（1）PC机（2）Dev C++ ,Visual C++, VS2010等四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现两个串S1和S2的比较。
（要求自己设计串的存储结构，并编写比较函数，不要调用系统提供的函数）➢代码部分：//Main.cpp:#include"SString.h"int main(){SString T1,T2;int i,n;T1[0]=T2[0]=0;cout<<"input T1 size:";cin>>n;T1[0]=n;cout<<"input T1 data:";for(i=1;i<=n;i++){cin>>T1[i];}cout<<"input T2 size:";cin>>n;T2[0]=n;cout<<"input T2 data:";for(i=1;i<=n;i++){cin>>T2[i];}cout<<"T1"<<Compare(T1,T2)<<"T2"<<endl;return 0;}//SString.cpp:#include"SString.h"char Compare(SString T1,SString T2){if(T1[0]>T2[0]){return '>';}else if(T1[0]<T2[0]){return '<';}else{for(int i=1;i<=T1[0];i++){if(T1[i]>T2[i]){return '>';}else if(T1[i]<T2[i]){return '<';}}}return '=';}//SString.h:#include<iostream>using namespace std;const int MAX=255;typedef unsigned char SString[MAX+1];char Compare(SString T1,SString T2);➢运行结果：（2）编程实现稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置等）。
实验名称稀疏矩阵的运算专业班级 10级计科（2）班学生姓名李永学号 10410902052 指导教师冯韵2012 至 2013学年第 1 学期第 3 至 4 周目录1 概述................................................................................................................................................. - 3 -2 系统分析......................................................................................................................................... -3 -2.2 设计分析.............................................................................................................................. - 3 -3 需求分析......................................................................................................................................... -4 -说明程序设计的任务，强调的是程序要做什么，明确规定： ..................................................... - 4 -1、输入的形式和输入值的范围；................................................................................................... - 4 -2、输出的形式；............................................................................................................................. - 4 -3、程序所能达到的功能；............................................................................................................... - 4 -4、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
实验四稀疏矩阵及其他特殊数组具体操作实验四稀疏矩阵及其他特殊数组操作一、实验目的1．掌握生成多维数组的方法及其标识2．掌握稀疏矩阵的创建及运算3．使用元胞数组和结构数组二、实验内容1．多维数组生成多维数组可以直接输入元素赋值生成，也可以由低维数组或由函数生成。
>>a=1:9>>b=reshape(a,3,3)>>c=cat(3,b,b)>>c(18)=[] %删除第18个元素查看三维数组c的元素存放顺序，可以看出三维数组是把第3维视做1页，先存放第1页的元素，在1页中先存放第1列的元素，再存放第2列的元素。
练习：1>通过“全下标”元素赋值方式创建一个3行2列3页的三维数组。
2>由函数ones,zeros,rand和randn直接创建2行3列2页的三维数组。
3>已知三维数组A。
A(:,:,1) =6 5 3 24 4 2 5A(:,:,2) =3 2 3 64 5 6 4（1）将三维数组A中第13个元素的重新赋值为1。
用单下标及全下标两种方式赋值。
A(13)=1 A(1,3,2)=1（2）将三维数组A中第2行第4列所有页的元素重新赋值为9。
A(2,4,:)=9（3）求数组A 各维的大小以及返回数组A 行数或列数的最大值。
[x,y,z]=size(A) length(A)（4）将该数组A 中第10个元素删除，观察数组A 的变化。
A(10)=[]4> 创建三维数组 B ，第一页为8764，第二页为0153，第三页为??3291。
重排生成数组C 为2行，3列，2页。
B(2,2,1)=[4 6;7 8]B(2,2,2)=[3 5;1 0]B(2,2,3)=[1 9;2 3]C=reshape(B,2,3,2)2、稀疏矩阵(1) 创建稀疏矩阵>>s=sparse([1 2 2 3 3 4],[1 1 2 2 3 3],[1 2 3 4 5 6])(2) 将稀疏矩阵与全元素矩阵转换>>f=full(s)>>k=f+s %稀疏矩阵与全元素矩阵的运算，注意结果的显示方式。
实验4：稀疏矩阵的基本操作
一、实验目的
1. 深入了解数组的存储表示和实现。
2．掌握稀疏矩阵的特点(三元组存储方法)。
3．掌握稀疏矩阵的三元组存储方法。
二、实验内容
1. 稀疏矩阵的存储及基本运算。
（1）针对给出的两个稀疏矩阵a和b，分别输出各自的三元组表示形式。
其中，a，b矩阵表示如下：
a，b矩阵三元组表示形式，预期结果下图所示：
图1 图2
（2）实现a，b稀疏矩阵的求和运算，并以三元组的形式表示，预期结果如下图所示：
图3
三、实验要求
1.独立完成实验程序的编写与调试；
2.实验完成后填写实验报告，学习委员按学号从小到大的顺序提交。
四、思考题
1.实现稀疏矩阵a，b的转置，并以三元组的形式表示。
图4 图5。
