矩阵的快速转置与乘法 数据结构课程设计
矩阵快速转置和乘法
（一）课程设计的目的
本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用VC
上机调试的基本方法。
利用三元组实现稀疏矩阵的有关算法
（二）需求分析
●问题描述：
1.稀疏矩阵采用三元组表示方法，可得一种以顺序存储结构的压缩存储
结构，后得B(n×m)并对矩阵B输出。
2.矩阵的乘法即一个矩阵与另一个的行数与前者的列数相同的矩阵相
乘。这里就用上述的矩阵A与B相乘得到C(m×m)并对矩阵C输出。
●基本要求：
1．功能要求--稀疏矩阵是指那些多数元素为零的矩阵，一般来说，当非零元素个数只占矩阵元素的总数的25%-30%或者低于这个百分数。利“稀
疏“特点进行存储和计算可以大大节省存储空间，提高计算效率。实现
一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三
元组顺序表表示稀疏矩阵，实现矩阵的转置和两个矩阵相乘的运算
2．首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。
3. 稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列
形式列出；乘积矩阵也用二维数组存放。
4. 程序可以对三元组的输入顺序加以限制，以行优先，以便提高计算的效
率。
5. 本程序中，按提示入相应的数据，由用户在键盘上输入演示程序中规定
的输入数据。这里输入的数据值为整型。
（三）概念设计
1、抽象数据类型稀疏矩阵的定义如下：
ADT SparseMatrix{
数据对象：D={aij|i=1,2,3……..,m; j=1,2,3…….,n;
Aij属于Elemset,m和n分别称为矩阵的行数和列数} 数据关系：R={Row,Col}
Row={
Col={
基本操作；
CreateSMatrix(&M);
操作结果：创建稀疏矩阵M;
PrintSMatrix(M);
初始条件：稀疏矩阵M存在。
操作结果：输出稀疏矩阵M;
TransposeSmatrix(M,N) ;
初始条件：稀疏矩阵M存在。
操作结果：输出稀疏矩阵N
MultSMatrix(M,N,&Q);
初始条件：稀疏矩阵M的行数等于N的列数。
操作结果：求稀疏矩阵的和Q=M*N.
}ADT SparseMatrix
2.数据结构：
三元组的结构
3.程序模块：
1）主程序模块：
Int main()
{
初始化；
While(1)
{
接受命令；
处理命令；
}
}
2）创建稀疏矩阵模块；
3）对已创建好的稀疏矩阵进行快速矩阵转置；
4）求稀疏矩阵的乘积Q=M*N模块；
5）输出稀疏矩阵模块；
4.各模块的调用关系及算法设计如下流程图所示
（四）详细设计
1．三元组数据结构算法
typedef struct{
int i,j; /*行下标,列下标*/
ElemType e; /*非零元值*/
}Triple;
typedef struct {
Triple data[MAXSIZE+1]; /*零元三元组表,data[0]未用*/ int rpos[MAXRC+1];
int mu,nu,tu; /*阵的行数、列数和非零元个数*/ }TSMatrix;
2．稀疏矩阵的创建算法
Status CreateSMatrix(TSMatrix &M) /*创建一个稀疏矩阵*/
{
printf("请输入稀疏矩阵的行数,列数,非零元数(请小于20个,用空格
隔开各数据):");
scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
if(M.tu>MAXSIZE||M.tu<=0||M.tu>M.mu*M.nu)
{printf("-----出错啦,非零元个数超过最大值!!\n");return ERROR;}
while(p<=M.tu)
{printf("请输入第 %d 个非零元素的行,列,元素值(用空格隔
开):",p);
scanf("%d %d %d",&a,&b,&c);
M.data[0].i=0;M.data[0].j=0;
if(a<=M.mu&&b<=M.nu&&c!=0)
{if(a>M.data[p-1].i||(a==M.data[p-1].i&&b>M.data[p-1].j))
{M.data[p].i=a;M.data[p].j=b;M.data[p].e=c;p++;}
else printf("-----出错啦,请从行到列,从小到大输入!!\n");
}
else printf("-----出错啦,所输入数据超出范围!!\n");
if(a==M.mu&&b==M.nu&&p<=M.tu){printf("-----出错啦,输入顺
序有误,请认真核查,从头输入!!\n");p=1;}
}
printf("-----输入成功!!\n");
return OK;
}
3．稀疏矩阵的输出算法
Status PrintMatrix(TSMatrix M) /*输出一个矩阵*/
{int i,j,p=1;
if(M.tu==0){printf("-----找不到此矩阵或为空矩阵!!\n" );return
ERROR;}
printf("---%d行 %d列 %d个非零元素---\n以阵列方式输出
为:\n",M.mu,M.nu,M.tu);
for(i=1;i<=M.mu;i++)
{for(j=1;j {if(i==M.data[p].i&&j==M.data[p].j) {printf("%d ",M.data[p].e);p++;} else printf("%d ",0); } if(i==M.data[p].i&&j==M.data[p].j) {printf("%d\n",M.data[p].e);p++;} else printf("%d\n",0); } return OK; } 4．稀疏矩阵的转置算法 Status TransposeSMatrix(TSMatrix M,TSMatrix &T) /*求快速稀疏矩阵M的转置矩阵T*/ {if(M.tu==0){printf("-----找不到所需矩阵!!\n" );return ERROR;} T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; for(p=1;p<=M.nu;++p) num[p]=0; for(q=1;q<=M.tu;++q) ++num[M.data[q].j]; cpot[1]=1; for(p=2;p<=M.nu;++p) cpot[p]=cpot[p-1]+num[p-1]; for(q=1;q<=M.tu;++q) { p=M.data[q].j; k=cpot[p]; T.data[k].i=M.data[q].j; T.data[k].j=M.data[q].i; T.data[k].e=M.data[q].e; ++cpot[p]; } printf("-----转置成功!!\n"); return OK; } 5．两个稀疏矩阵的乘法算法 Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) /*求稀疏矩阵的积Q=M*N */ { if(M.tu==0||N.tu==0){printf("-----找不到所需矩阵!!\n" );return ERROR;} if(M.nu!=N.mu) {printf("-----此矩阵不能被运算,请核查行列 数!!\n" );return ERROR;} for(p=1;p<=M.tu;p++) /*为M.rpos[] 赋值*/ {if(M.data[p].i==k) {M.rpos[k]=p; k++;} else if(M.data[p].i>k) {M.rpos[k]=p--; k++;} } for(;k<=M.mu;k++)M.rpos[k]=M.tu; k=1; for(q=1;q<=N.tu;q++) /* 为N.rpos[]赋值*/ {if(N.data[q].i==k) {N.rpos[k]=q;k++;} else if(N.data[q].i>k) {N.rpos[k]=p--;k++;} } for(;k<=N.mu;k++)N.rpos[k]=N.tu; Q.mu=M.mu; /*初始化Q*/ Q.nu=N.nu; Q.tu=0; for(arow=1;arow<=M.mu;++arow) {for(ccol=1;ccol<=N.nu;ccol++) ctemp[ccol]=0; if(arow tp=M.rpos[arow+1]; else tp=M.tu+1; for(p=M.rpos[arow];p {brow=M.data[p].j; if(brow t=N.rpos[brow+1]; else t=N.tu+1; for(q=N.rpos[brow];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]!=0) {Q.tu++; if(Q.tu>MAXSIZE) {printf("-----出错啦,非零元个数超出最大 值!!\n");return ERROR;} Q.data[Q.tu].i=arow; Q.data[Q.tu].j=ccol; Q.data[Q.tu].e=ctemp[ccol];} } } printf("-----运算成功!!\n"); return OK; } 6．函数及其函数调用关系 (五)测试与分析 （六）总结 通过一个学期的数据结构课程学习,使我对这门课程有了个大致的了解,这是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，老师就为我们阐述了它的重要性。它对我们 来说具有一定的难度。它是其它编程语言的一门基本学科。此次的程序设计能够成功，是我们小组的同学共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计都有了明显的提高。但是我在动手能力上还是薄弱,我会在今后的时间里勤加练习,使自己不断进步! （七）附录 源代码清单： #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 /*稀疏矩阵的三元组顺序表类型TSMatrix的定义*/ #define MAXSIZE 20 /*非零元个数最大值*/ #define MAXRC 10 typedef int Status; typedef int ElemType; typedef struct{ int i,j; /*行下标,列下标*/ ElemType e; /*非零元值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /*零元三元组表,data[0]未用*/ int rpos[MAXRC+1]; int mu,nu,tu; /*阵的行数、列数和非零元个数*/ }TSMatrix; Status CreateSMatrix(TSMatrix &M) /*创建一个稀疏矩阵*/ {int p=1,a,b,c; printf("请输入稀疏矩阵的行数,列数,非零元数(请小于20个,用空格隔开各数据):"); scanf("%d %d %d",&M.mu,&M.nu,&M.tu); if(M.tu>MAXSIZE||M.tu<=0||M.tu>M.mu*M.nu) {printf("-----出错啦,非零元个数超过最大值!!\n");return ERROR;} while(p<=M.tu) {printf("请输入第 %d 个非零元素的行,列,元素值(用空格隔开):",p); scanf("%d %d %d",&a,&b,&c); M.data[0].i=0;M.data[0].j=0; if(a<=M.mu&&b<=M.nu&&c!=0) {if(a>M.data[p-1].i||(a==M.data[p-1].i&&b>M.data[p-1].j)) {M.data[p].i=a;M.data[p].j=b;M.data[p].e=c;p++;} else printf("-----出错啦,请从行到列,从小到大输入!!\n"); } else printf("-----出错啦,所输入数据超出范围!!\n"); if(a==M.mu&&b==M.nu&&p<=M.tu){printf("-----出错啦,输入顺序有误,请认真核查,从头输入!!\n");p=1;} } printf("-----输入成功!!\n"); return OK; } Status PrintMatrix(TSMatrix M) /*输出一个矩阵*/ {int i,j,p=1; if(M.tu==0){printf("-----找不到此矩阵或为空矩阵!!\n" );return ERROR;} printf("---%d行%d列%d个非零元素---\n以阵列方式输出为:\n",M.mu,M.nu,M.tu); for(i=1;i<=M.mu;i++) {for(j=1;j {if(i==M.data[p].i&&j==M.data[p].j) {printf("%d ",M.data[p].e);p++;} else printf("%d ",0); } if(i==M.data[p].i&&j==M.data[p].j) {printf("%d\n",M.data[p].e);p++;} else printf("%d\n",0); } return OK; } Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) /*求稀疏矩阵的积Q=M*N */ { int arow,brow,p,q,ccol,ctemp[MAXRC+1],t,tp,k=1; if(M.tu==0||N.tu==0){printf("-----找不到所需矩阵!!\n" );return ERROR;} if(M.nu!=N.mu) {printf("-----此矩阵不能被运算,请核查行列数!!\n" );return ERROR;} for(p=1;p<=M.tu;p++) /*为M.rpos[] 赋值*/ {if(M.data[p].i==k) {M.rpos[k]=p; k++;} else if(M.data[p].i>k) {M.rpos[k]=p--; k++;} } for(;k<=M.mu;k++)M.rpos[k]=M.tu; k=1; for(q=1;q<=N.tu;q++) /* 为N.rpos[]赋值*/ {if(N.data[q].i==k) {N.rpos[k]=q;k++;} else if(N.data[q].i>k) {N.rpos[k]=p--;k++;} } for(;k<=N.mu;k++)N.rpos[k]=N.tu; Q.mu=M.mu; /*初始化Q*/ Q.nu=N.nu; Q.tu=0; for(arow=1;arow<=M.mu;++arow) {for(ccol=1;ccol<=N.nu;ccol++) ctemp[ccol]=0; if(arow tp=M.rpos[arow+1]; else tp=M.tu+1; for(p=M.rpos[arow];p {brow=M.data[p].j; if(brow t=N.rpos[brow+1]; else t=N.tu+1; for(q=N.rpos[brow];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]!=0) {Q.tu++; if(Q.tu>MAXSIZE) {printf("-----出错啦,非零元个数超出最大值!!\n");return ERROR;} Q.data[Q.tu].i=arow; Q.data[Q.tu].j=ccol; Q.data[Q.tu].e=ctemp[ccol];} } } printf("-----运算成功!!\n"); return OK; } Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T) /*求快速稀疏矩阵M的转置矩阵T*/ {int p,q,k=1; int cpot[MAXSIZE],num[MAXSIZE]; if(M.tu==0){printf("-----找不到所需矩阵!!\n" );return ERROR;} T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; for(p=1;p<=M.nu;++p) num[p]=0; for(q=1;q<=M.tu;++q) ++num[M.data[q].j]; cpot[1]=1; for(p=2;p<=M.nu;++p) cpot[p]=cpot[p-1]+num[p-1]; for(q=1;q<=M.tu;++q) { p=M.data[q].j; k=cpot[p]; T.data[k].i=M.data[q].j; T.data[k].j=M.data[q].i; T.data[k].e=M.data[q].e; ++cpot[p]; } printf("-----转置成功!!\n"); return OK; } void Show() {printf("****************************************************** ***********\n"); printf("============>>0.退出程序\n"); printf("\n"); printf("============>>1.创建矩阵 A\n"); printf("\n"); printf("============>>2.输出矩阵 A\n"); printf("============>>3.输出矩阵 B\n"); printf("============>>4.输出矩阵 C\n"); printf("\n"); printf("============>>5.转置矩阵 A->B\n"); printf("============>>6.矩阵相乘 A*B=C\n"); printf("\n"); printf("******************************************************* **********\n"); } void main() { int select; TSMatrix A,B,C; A.tu=0; B.tu=0; C.tu=0; Show(); while(1) { printf("请选择: "); scanf("%d",&select); if(select==0)break; switch(select) { case 1: CreateSMatrix(A); break; case 2: PrintMatrix(A); break; case 3: PrintMatrix(B); break; case 4: PrintMatrix(C); break; case 5: FastTransposeSMatrix(A,B); break; case 6: MultSMatrix(A,B,C); break; default:printf("输入错误,请认真核查!!\n"); break; } } } 一、设计要求 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，它与其三元组表的对应关系如图 2．2 系统功能设计 本系统通过菜单提示用户首先选择稀疏矩阵转置方法，然后提示用户采用三元组表示法输入数据创建一个稀疏矩阵，再进行矩阵的转置操作，并以通常的阵列形式输出结果。主要实现以下功能。 （1）创建稀疏矩阵。采用带行逻辑连接信息的三元组表表示法，提示用户输入矩阵的行数、列数、非零元个数以及各非零元所在的行、列、值。 （2）矩阵转置。<1>采用一般算法进行矩阵的转置操作，再以阵列形式输出转置矩阵B。 <2>采用快速转置的方法完成此操作，并以阵列形式输出转置矩阵B。 三、模块设计 3．1 模块设计 程序包括两个模块：主程序模块、矩阵运算模块。 3．2 系统子程序及其功能设计 系统共设置了8个子程序，各子程序的函数名及功能说明如下。 （1）CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵 （2）void DestroySMatrix(RLSMatrix &M) //销毁稀疏矩阵 （3）void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵 （4）void print(RLSMatrix A) //打印矩阵函数，输出以阵列形式表示的矩阵 （5）TransposeSMatrix(RLSMatrix M,RLSMatrix &T) //求稀疏矩阵的转置的一般算法（6）FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) //快速转置算法 （7）void showtip() //工作区函数，显示程序菜单 （8）void main() //主函数 计 算 机 系 统 应 用 https://www.sodocs.net/doc/d62808006.html, 2011 年 第20卷 第 1期 178 经验交流 Experiences Exchange GPU 上的矩阵乘法的设计与实现① 梁娟娟，任开新，郭利财，刘燕君 (中国科学技术大学 计算机科学与技术学院，合肥 230027) 摘 要: 矩阵乘法是科学计算中最基本的操作，高效实现矩阵乘法可以加速许多应用。本文使用NVIDIA 的CUDA 在GPU 上实现了一个高效的矩阵乘法。测试结果表明，在Geforce GTX 260上，本文提出的矩阵乘法的速度是理论峰值的97%，跟CUBLAS 库中的矩阵乘法相当。 关键词: 矩阵乘法；GPU ；CUDA Design and Implementation of Matrix Multiplication on GPU LIANG Juan-Juan, REN Kai-Xin, GUO Li-Cai, LIU Yan-Jun (School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) Abstract: Matrix multiplication is a basic operation in scientific computing. Efficient implementation of matrix multiplication can speed up many applications. In this paper, we implement an efficient matrix multiplication on GPU using NVIDIA’s CUDA. The experiment shows that our implementation is as fast as the implementation in CUBLAS, and the speed of our implementation can reach the peak speed’s 97%, on Geforce GTX260. Keywords: matrix multiplication; GPU; CUDA GPU 是一种高性能的众核处理器，可以用来加速许多应用。CUDA 是NVIDIA 公司为NVIDIA 的GPU 开发的一个并行计算架构和一门基于C 的编程语言。在CUDA 中程序可以直接操作数据而无需借助于图形系统的API 。现在已经有许多应用和典型算法使用CUDA 在GPU 上实现出来。 1 引言 矩阵乘法是科学计算中的最基本的操作，在许多领域中有广泛的应用。对于矩阵乘法的研究有几个方向。一个是研究矩阵乘法的计算复杂度，研究矩阵乘法的时间复杂度的下界，这方面的工作有strassen 算法[1]等。另外一个方向是根据不同的处理器体系结构，将经典的矩阵乘法高效的实现出来，这方面的结果体现在许多高效的BLAS 库。许多高效的BLAS 库都根据体系结构的特点高效的实现了矩阵乘法，比如GotoBLAS [2], ATLAS [3]等。Fatahalian [4]等人使 用着色语言设计了在GPU 上的矩阵乘法。CUBLAS 库是使用CUDA 实现的BLAS 库，里面包含了高性能的矩阵乘法。 本文剩下的部分组织如下，第2节介绍了CUDA 的编程模型，简单描述了CUDA 上编程的特点。第3节讨论了数据已经拷贝到显存上的矩阵乘法，首先根据矩阵分块的公式给出了一个朴素的矩阵乘法实现，分析朴素的矩阵乘法的资源利用情况，然后提出了一种新的高效的矩阵乘法。第4节讨论了大规模的矩阵乘法的设计和实现，着重讨论了数据在显存中的调度。第5节是实验结果。第6节是总结和展望。 2 CUDA 编程模型和矩阵乘法回顾 2.1 CUDA 编程模型 NVIDIA 的GPU 是由N 个多核处理器和一块显存构成的。每个多核处理器由M 个处理器核，1个指令部件，一个非常大的寄存器堆，一小块片上的共享内 ① 基金项目:国家自然科学基金(60833004);国家高技术研究发展计划(863)(2008AA010902) 收稿时间:2010-04-26;收到修改稿时间:2010-05-21 c++课程设计-矩阵的转置与乘法计算 C++课程设计实验报告 姓名学号班级 任课教师时间 9月 教师指定题目4-4 矩阵的转置与乘法计算评定难易级别 A 实验报告成绩 1.实验内容: 1.1 程序功能介绍 该程序定义了一个向量类，里面的元素是模板形式，定义了有关向量了类的各种属性、方法及运算符重载函数。 1.2 程序设计要求 （1）利用已知的向量类对象定义一个矩阵类，矩阵类的数据是向量子对象，同样定义矩阵类的各种属性、方法及运算符重载函数。 （2）完善成员函数，使矩阵可以由文件输入，具体的输入格式自己规定。 （3）完成矩阵的赋值、转置、乘法等运算，要求用整形矩阵和浮点型矩阵分别演算。 （4）更改main函数结构，可由用户选择输入矩阵数据的方法，程序可以连续运行，直到选择退出为止。 2. 源程序结构流程框图与说明(含新增子函数的结构框图) 作者：喻皓学号：0511590125 3. 基本数据结构 定义的类模板，将函数用链表将一些功能函数连接起来。其中定义了构造函数，析构函数，重载赋值、乘法、数乘、输入、输出，矩阵转置等函数，实现矩阵的矩阵的赋值、转置、乘法等运算。 template 《数据结构》实验报告 ◎实验题目:稀疏矩阵的转置、加法（行逻辑链接表） ◎实验目的：学习使用三元组顺序表表示稀疏矩阵，并进行简单的运算 ◎实验内容：以三元组表表示稀疏矩阵，并进行稀疏矩阵的转置和加法运算。 一、需求分析 该程序目的是为了用三元组表实现稀疏矩阵的转置和加法运算。 1、输入时都是以三元组表的形式输入； 2、输出时包含两种输出形式：运算后得到的三元组表和运算后得到的矩阵； 3、测试数据： （1）转置运算时输入三元组表：1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 得到转置后的三元组表：1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 （2）进行加法运算时先输入矩阵A（以三元组表形式）：1 1 1 2 2 2 2 3 4 3 1 -4 输入矩阵B（以三元组表形式）：1 3 -2 2 3 -5 3 1 8 3 2 -6 A与B的和矩阵以矩阵形式输出为：1 0 -2 0 2 -1 4 -6 0 (二) 概要设计 为了实现上述操作首先要定义三元组表，稀疏矩阵： typedef struct { int i,j; int e; }Triple;//三元组 typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }Matrix;//稀疏矩阵 1.基本操作 void CreatMatrix(Matrix *m) 操作结果：创建一个稀疏矩阵。 void PrintMatrix(Matrix m) 初始条件：矩阵m已存在。 操作结果：将矩阵m以矩阵的形式输出。 void FastTransposeMatrix(Matrix a,Matrix *b) 初始条件：稀疏矩阵a已存在； 操作结果：将矩阵a进行快速转置后存入b中。 void AddMatrix(Matrix a,Matrix b,Matrix *c) 初始条件：稀疏矩阵a和b都已存在； 操作结果：将矩阵a和b的和矩阵存入c中。 2.本程序包含了两个模块： （1）头文件模块； 其中包括定义三元组表Triple和稀疏矩阵Matrix，以及创建矩阵void CreatMatrix(Matrix *m)和输出矩阵void PrintMatrix(Matrix m)两个函数； （2）主程序模块； 包括主函数main()，快速转置函数void FastTransposeMatrix(Matrix a,Matrix *b)和实现矩阵相加函数void AddMatrix(Matrix a,Matrix b,Matrix *c) (三) 详细设计 定义三元组和稀疏矩阵类型： typedef struct { int i,j; int e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }Matrix; 创建头文件:“Matrix.h” void CreatMatrix(Matrix *m)//矩阵的初始化 { int p=1,a,b,c; printf("请输入矩阵的行数、列数、非零元的个数（数据用空格隔开）:"); scanf("%d %d %d",&(*m).mu,&(*m).nu,&(*m).tu); 实验2 稀疏矩阵的建立与转置 一、实验目的 掌握特殊矩阵的存储和操作算法。 二、实验内容及问题描述 实现用三元组保存稀疏矩阵并实现矩阵转置的算法。 三、实验步骤 1. 定义稀疏矩阵的三元组形式的存储结构。 2. 实现三元组矩阵的传统转置算法。 3. 实现三元组矩阵的快速转置算法。 4. 输入矩阵非零元素，测试自己完成的算法。 四、程序流程图 五、概要设计 矩阵是很多的科学与工程计算中研究的数学对象。在此，我们感兴趣的是，从数学结构这门学科着眼，如何存储矩阵的元从而使矩阵的各种运算有效的进行。本来，用二维数组存储矩阵，在逻辑上意义是很明确的，也很容易理解，操作也很容易和方便。但是在数值分析中经常出现一些阶数很高的矩阵，同时，在矩阵中又有很多值相同或者都为零的元素，可以对这种矩阵进行压缩存储：对多个值相同的元素只分配一个存储空间；对零元素不分配空间。稀疏矩阵的定义是一个模糊的定义：即非零元个数较零元个数较少的矩阵。例如下图所示的矩阵 为一个稀疏矩阵。为了实现稀疏矩阵的这种存储结构，引入三元组这种数据结构。三元组的线性表顺存储形式如下图： 六、详细设计 sanyuanzu.h 头文件 #define max 100 typedef struct { int row,col; int e; }Triple;//定义三元组 typedef struct { Triple data[max]; int mu,nu,tu; }TSMatrix;///*定义三元组的稀疏矩阵*/ void creat( TSMatrix &M) ; void fasttrans(TSMatrix A,TSMatrix &B); 三元组顺序表实现矩阵的转置： /*-------------------------------------------------------------- ----------------用三元组顺序表实现对稀疏矩阵的转置----------------- ------------------------编译环境：VS 2013------------------------ --------------------------------------------------------------*/ #define_CRT_SECURE_NO_WARNINGS//用于取消VS 2013对printf、scanf等函数的警告#include 常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期 专业：物联网工程 实验名称：特殊矩阵和稀疏矩阵 实验地点： N6-210 指导教师：聂盼红 计算机科学与工程学院 2017 实验五特殊矩阵和稀疏矩阵 【实验目的】 1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址； 2、掌握对称矩阵的压缩存储表示； 3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。 若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。 sa[k]与矩阵元素a ij之间存在着一一对应的关系： 若i>=j，k=i*(i+1)/2+j; 若i 的关系。（注意C程序中，i，j，k均从0开始） （2）调试程序与运行。对称矩阵存储下三角部分即i>=j。 对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下： #include<> #define N 5 int main() { int upper[N][N]= {{3,9,1,4,7}, {9,5,2,5,8}, {1,2,5,2,4}, {4,5,2,1,7}, {7,8,4,7,9} }; /*对称矩阵*/ int rowMajor[15]; /*存储转换数据后以行为主的数组*/ int Index; /*数组的索引值*/ int i,j; printf("Two dimensional upper triangular array:\n"); for (i=0; i 一种用于通用处理器结构优化的矩阵乘法性能模型 朱海涛１，２李玲２陈云霁２钱诚２ １中国科学技术大学计算机科学与技术学院，合肥２３００２７ ２中国科学院计算技术研究所微处理器中心，北京１００１９０ Ｅ－ｍａｉｌ： ｚｈｕｈｔ＠ ｍａｉｌ． ｕｓｔｃ． ｅｄｕ． ｃｎ 摘要：矩阵乘法作为高性能计算中的关键组成部分，是一种具有计算和访存密集特点的典型应用，因此优化矩阵乘法的性能对通用处理器是非常重要的．为了提高矩阵乘法的性能，本文提出了一种性能模型，用于预测通用处理器上矩阵乘法的执行时间．该模型反映了矩阵乘法执行时间与通用处理器的运算部件、访存带宽、寄存器个数等结构参数之间的关系，可以指导处理器结构的优化来平衡计算和访存能力、提高执行速度．基于该模型本文给出了在一个优化的通用处理器结构中，寄存器个数和访存带宽应满足的理论下界．本文在Ｇｏｄｓｏｎ－３Ｂ处理器平台上对该性能模型进行了验证，实验结果表明矩阵乘法执行时间的预测精确度达到９５％以上．基于该模型，本文还提出了一种对Ｇｏｄｓｏｎ－３Ｂ结构进行优化的方法，使矩阵乘法的执行时间减少了５０％左右． 矩阵乘法；性能模型；通用处理器；结构优化 ＴＰ３０１Ａ１０００－１２２０ （ ２０１２ ） ０５－０９８１－０６ Ｍａｔｒｉｘ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｐｅｒｆｏｒｍａｎｃｅ Ｍｏｄｅｌ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ Ｇｅｎｅｒａｌ－ｐｕｒｐｏｓｅ Ｐｒｏｃｅｓｓｏｒ ＡｒｃｈｉｔｅｃｔｕｒｅＺＨＵ Ｈａｉ－ｔａｏＬＩ ＬｉｎｇＣＨＥＮ Ｙｕｎ－ｊｉＱＩＡＮ Ｃｈｅｎｇ ２０１０－１２－２８国家科技重大专项项目（ ２００９ＺＸ０１０２８－００２－００３，２００９ＺＸ０１０２９－００１－００３）资助．朱海涛，男，１９８２年生，博士研究生，研究方向为计算机体系结构和高性能计算：李玲，女，１９８２年生，博士，研究方向为图像／视频处理、高性能计算；陈云霁，男，１９８３年生，博士，副研究员，研究方向为并行计算、微体系结构、硬件验证；钱诚，男，１９８５年生，博士，研究方向为微体系结构、硬件验证． 万方数据 数据结构---三元组顺序表------稀疏矩阵的转置和快速转置 #include<> #include<> #include<> #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INEEASLIBE -1 #define OVERFLOW -2 #define maxsize 100 typedef int status; typedef int elemtype; typedef struct { int i,j; elemtype e; }elem; typedef struct { elem data[maxsize+1]; int mu,mn,tu; }matrix; status showmatrix(matrix M) { int i,j,k=1; for(i=1;i<=;i++) { for(j=1;j<=;j++) { if(i==[k].i&&j==[k].j) { printf("%d\t",[k].e); k++; } else printf("0\t"); } printf("\n"); } return OK; } status trans(matrix M,matrix &T) { int i=1,j=1,k=1; =; =; =; while(i<= { for(;k<=;k++) if[k].j==i) { [j].e=[k].e; [j].i=[k].j; [j].j=[k].i; j++; } k=1; i++; } return OK; } status initmatrix(matrix &M) { printf("请输入该矩阵行数mu和列数mn和非零元个数tu\nmu="); scanf("%d",&; getchar(); printf("\nmn="); scanf("%d",&; getchar(); printf("\ntu="); scanf("%d",&; getchar(); if>maxsize) { printf("非零元个数已超过定义的值\n请重新输入tu="); scanf("%d",&; getchar(); 基于三元组表表示的稀疏矩阵的快速转置算法及其改进 摘要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。 需求分析：矩阵作为许多科学与工程计算的数据对象,必然是计算机处理的数据对象之 一。在实际应用中,常会遇到一些阶数很高,同时又有许多值相同的元素或零元素的矩阵,在这类矩阵中,如果值相同的元素或零元素在矩阵中的分配没有规律,则称之为稀疏矩阵。为了节省存储空间,常对稀疏矩阵进行压缩存储。压缩存储的基本思想就是:对多个值相同的元素只分配1个存储空间,对零元素不分配存储空间。换句话说,就是只存储稀疏矩阵中的非零元素。稀疏矩阵可以采取不同的压缩存储方法,对于不同的压缩存储方法,矩阵运算的实现也就不同。 1．稀疏矩阵的三元组表表示法 根据压缩存储的基本思想,这里只存储稀疏矩阵中的非零元素,因此,除了存储非零元的值以外,还必须同时记下它所在行和列的位置(i,j),即矩阵中的1个非零元aij由1个三元组(i,j,aij)惟一确定。由此可知,稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定。对于稀疏矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法,用三元组数组(三元组顺序表)来表示稀疏矩阵即为稀疏矩阵的三元组表表示法。三元组数组中的元素按照三元组对应的矩阵元素在原矩阵中的位置,以行优先的顺序依次存放。 三元组表的类型说明如下: # define MAXSIZE 1000 /*非零元素的个数最多为 1000*/ typedef struct { int row,col; /*该非零元素的行下标和列下标*/ ElementType e; /*该非零元素的值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /*非零元素的三元组表, data[0]未用*/ int m,n,len; /*矩阵的行数、列数和非零元素的个数*/ }TSMatrix; 2．稀疏矩阵的快速转置算法 待转置矩阵source和转置后矩阵dest分别用三元组表A和B表示,依次按三元组表A中三元组的次序进行转置,转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上,需要预先计算以下数据: 1)待转置矩阵source每一列中非零元素的个数(即转置后矩阵dest每一行中非零元素的个 数)。 一、实验内容和要求 1、稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相 加得到矩阵C的算法。 （1）从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。 （2）设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。 （3）设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。 （4）输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。 二、实验过程及结果 一、需求分析 1、将随机生成的数定义为int型（为方便起见设定范围为-20至20（不含0），可 修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。 2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列 排列形式输出）。 3、程序能实现的功能包括： ①随机产生稀疏矩阵；②输出阵列形式的矩阵；③输出三元组顺序 表；④将矩阵快速转置；⑤将两个稀疏矩阵相加生成新的矩阵。 二、概要设计 1、稀疏矩阵的抽象数据类型定义： ADT TSMatrix{ 数据对象：D={ aij|i=1,2,…,m,j=1,2,…,n; Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}数据关系：R={Row，Col} Row={ 稀疏矩阵 一、问题描述 假若在n m ?阶中，有t 个元素不为零，令n m t ?=δ称为矩阵的稀疏因子。通常认为≤δ0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。 二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。 三、测试数据 1、转置操作的测试数据： ??????? ? ?00200013000010020100 2、相加操作的测试数据： ??????? ? ?002000130000100 20100 ??????? ??00200010000210030300 3、相乘操作的测试数据： ?????? ? ??000000030040 0021 ??????? ??001002000021 四、算法思想 1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。 2、稀疏矩阵转置的算法思想 将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。 为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想 两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v 的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。 五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。 六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1]; —7— 基于CUDA 的矩阵乘法和FFT 性能测试 肖 江，胡柯良，邓元勇 (中国科学院国家天文台，北京 100012) 摘 要：针对NVIDIA 公司的CUDA 技术用Geforce8800GT 在Visual Studio2008环境下进行测试，从程序运行时间比较判断CUBLAS 库、CUDA 内核程序、CUDA 驱动API 、C 循环程序与Intel MKL 库以及FFTW 库与CUFFT 库运行响应的差异。测试结果表明，在大规模矩阵乘法和快速傅里叶变换的应用方面，相对于CPU ，利用GPU 运算性能可提高25倍以上。 关键词：矩阵乘法；快速傅里叶变换；并行计算；GPU 通用计算 Ability Test for Matrix-Multiplication and FFT Based on CUDA XIAO Jiang, HU Ke-liang, DENG Yuan-yong (National Astronomical Observatories, Chinese Academy of Sciences, Beijing 100012) 【Abstract 】This paper introduces the result of a test that evaluates the effectiveness of Compute Unified Device Architecture(CUDA) using NVDIA GeForce8800GT and the compiler Visual Studio 2008. It tests the speed of NVIDIA CUBLAS, CUDA kernel, common C program, Intel MKL BLAS, CUDA driver API program, FFTW and CUFFT Library in matrix-multiplication and Fast Fourier Transform(FFT). Test result of the large scale data shows that the computing ability of GPU is 25 times better than that of CPU. 【Key words 】matrix-multiplication; Fast Fourier Transform(FFT); parallel computation; GPGPU 计 算 机 工 程 Computer Engineering 第35卷 第10期 Vol.35 No.10 2009年5月 May 2009 ·博士论文· 文章编号：1000—3428(2009)10—0007—04 文献标识码：A 中图分类号：TP312 1 概述 长期以来，人们对并行计算的需求是无止境的，如在气象、天文，资源以及时系跟踪等领域，它们对程序处理速度的要求都相当高，否则将导致结果出现偏差或失去其意义。文献[1]全面地综述了并行计算在各个方面的最新进展，包括并行计算机体系结构、并行算法、并行性能优化与评价、并行编程等。提高并行运算的速度一般采用以下3个方面的改进措施： (1)处理速度更快的新的硬件设备，如更快的超级计算机、更大的内存以及更快的I/O 设备。这是从根本上提升并行计算能力的途径。 (2)更优化的程序设计方法和函数库，如在程序中引入多线程、并行等处理方法。 (3)采用优化的软件，这也是一种简便有效且成本相对较低的方法。 采用基于CUDA(Compute Unified Device Architecture)的GPU 并行计算属于第(1)种和第(2)种方法的结合。CUDA 是一个新的基础架构，是一个软硬件协同的完整的解决方案。这种架构可以使用GPU 处理复杂的科学计算问题，特别是极大数据量的并行计算问题。它提供了硬件的直接访问接口，而不必像传统GPU 方式那样依赖图形API 接口实现GPU 的访问[2]。CUDA 在GPU 架构上将晶体管更多地投入到数据处理，减少数据缓存和流量控制对晶体管资源的消耗。图1是最近几年GPU 与CPU 每秒浮点运算能力的增长情况[3]。CUDA 采用C 语言作为编程语言，进行了适度的扩展，提供大量的高性能计算指令开发能力， 使开发者能够在GPU 强大计算能力的基础上建立起一种效率更高的密集数据计算解决 方案[4]。 图1 CPU 与GPU 的浮点运算速度[3] 本文主要通过79 MB 的数据量对NVIDIA 的GPU 核心芯片(G92)和Intel Pentium D830芯片进行矩阵乘法和快速傅里叶变换测试，通过编程评估两者在最优化函数库下的并行运算能力。 2 基于CUDA 的GPU 软硬件测试环境 2.1 CUDA 测试硬件的选择 CUDA 支持的GPU(CUDA-enabled GPU)包括NVIDIA 公司的Geforce, Quadro 和Tesla 3个产品线。其中，Geforce 和Quadro 系列显示芯片可以直接插入普通PCI-Express×16插槽中，最大理论带宽为8 GB/s [5]，为了便于将CPU 与GPU 进行性 基金项目：国家“973”计划基金资助项目(2006CB806301)；国家自然科学基金资助项目(10473016, 10673016)；中国科学院知识创新工程基金资助项目(KJCX2-YW-T04) 作者简介：肖 江(1982－)，男，博士研究生，主研方向：并行计算，嵌入式软件环境，图像处理；胡柯良，副研究员；邓元勇，研究员、博士生导师 收稿日期：2008-10-20 E-mail ：xj@https://www.sodocs.net/doc/d62808006.html, 专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主 控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输 数据结构 课程设计实验报告 内容名称：稀疏矩阵的基本操作成员1：09213020-陈东 成员2：09213040-蔡丹 班级：09数31 教师：李晓翠 江苏师范大学 数学科学学院 目录 1.序言 (3) 1.1数据结构背景 (3) 1.2课程设计目的 (3) 1.3 课程名称 (3) 1.4设计要求 (3) 1.5设计说明 (3) 2．课程任务设计说明书 (5) 3.需求分析 (6) 3.1题目名称 (6) 3.2题目内容 (6) 3.3题目分析 (6) 4．概要设计 (7) 4.1稀疏矩阵存储结构 (7) 4.2.稀疏矩阵的基本操作 (7) 4.3各模块设计要求 (8) 4.4总体功能流程图 (9) 4.4.1存储结构流程图 (9) 4.4.2稀疏矩阵基本操作流程图 (10) 5．详细设计 (11) 5.1设计原理 (11) 5.2基本函数实现流程图 (13) 6．主要函数代码 (21) 7．调试与操作说明 (27) 7.1操作说明 (27) 7.2调试结果………………………………………………………………………………. ..28 7.3结果分析 (31) 8.设计体会 (32) 9.参考文献 (32) 10.分工说明 (33) 1.序言 1.1数据结构背景 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。 数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 基于此原因，我们开设了数据结构课程设计。针对数据结构课程的特点，着眼于培养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。 1.2课程设计的目的 巩固和深刻理解―数据结构（C语言版）‖课程所讲解的C语言作为数据结构的算法的描述，掌握对数据的存储结构和算法进行描述时，尽量考虑C 语言的特色。培养学生独立工作和创新思维的能力，取得设计与调试的实践经验。提高和加强计算机应用及软件开发能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定三元组表示稀疏矩阵的转置(一般算法和快速算法)
GPU上的矩阵乘法的设计与实现
c++课程设计-矩阵的转置与乘法计算
数据结构稀疏矩阵转置,加法
稀疏矩阵的建立与转置
三元组顺序表实现矩阵的转置
数据结构与算法 特殊矩阵和稀疏矩阵
一种用于通用处理器结构优化的矩阵乘法性能模型
数据结构---三元组顺序表------稀疏矩阵的转置和快速转置
基于三元组表表示的稀疏矩阵的快速转置算法及其改进
矩阵转置及相加实验报告
稀疏矩阵(算法与数据结构课程设计)
(相当不错还得再看很多遍)基于CUDA的矩阵乘法和FFT性能测试
稀疏矩阵的运算(完美版)
数据结构C语言版-稀疏矩阵三元组的基本操作
相关文档
- 数据结构---三元组顺序表------稀疏矩阵的转置和快速转置
- 4.3.3 稀疏矩阵-快速转置算法
- 数据结构与算法 特殊矩阵和稀疏矩阵
- 稀疏矩阵的操作
- 稀疏矩阵快速转置 数据结构实验报告
- 矩阵快速转置和乘法
- 数据结构与算法 特殊矩阵和稀疏矩阵
- 数据结构C语言版-稀疏矩阵三元组的基本操作
- 数据结构—三元组表法实现稀疏矩阵的转置
- 第三章 稀疏矩阵
- 4.3.1 稀疏矩阵-稀疏矩阵的抽象数据类型
- 稀疏矩阵的建立与转置
- 稀疏矩阵的存储和快速转换
- 稀疏矩阵快速转置 数据结构实验报告
- 稀疏矩阵转置
- 三元组结构实现稀疏矩阵转置算法的分析
- 数据结构---三元组顺序表------稀疏矩阵的转置和快速转置
- 利用三元组表对稀疏矩阵实现加法减法及转置
- 数据结构---三元组顺序表------稀疏矩阵的转置和快速转置
- 稀疏矩阵三元组实现矩阵转置算法实验报告