三元组结构实现稀疏矩阵转置算法的分析
三元组结构实现稀疏矩阵转置算法的分析
文章简要叙述了稀疏矩阵压缩存储的三元组表示法及其基于此种结构的矩阵的转置运算。探讨了基于三元组结构的矩阵转置算法的具体实现方法及其时空复杂度的问题。
【关键词】稀疏矩阵压缩存储三元组转置算法
在一些特殊矩阵中，如对称矩阵和上下三角矩阵，非零元素一般都有明显的规律，从而都可以压缩到一维数组里面，然而，实际应用中经常会遇到这样一些矩阵，它们非零元素少，且分布不均匀，且没有明显的规律，称之为稀疏矩阵。按照压缩存储的思想，只需存储矩阵中的非零元素。为了便于存取和检索，一般在存储的时候必须带有合适的辅助信息，即同时记录下它所在的行列的位置等等。在实际应用中，一般我们采取的是用三元组和十字链表两种表示方法来实现稀疏矩阵的存储及其运算。稀疏矩阵在数值计算、电力系统的潮流计算、天气预报、工程分析计算等方面都有着大量的应用，不少实际问题都可以转化为对稀疏矩阵的计算问题。了解稀疏矩阵的各种操作变得尤为重要。
1 基本概念
设矩阵中有t个非零元素，若t远远小于矩阵元素的总数，则称该矩阵为稀疏矩阵。通常，在m×n 的矩阵中，存在t个非零元素。设δ= t/（m*n），则称δ为矩阵的稀疏
因子，一般认为当δ≤0.05时为稀疏矩阵。在存储稀疏矩阵时，为了节约存储单元，很自然的压缩方法就是只存储非零元素，但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储相应的辅助信息，才能准确迅速确定一个非零元素是矩阵中的哪一个元素。最简单的办法就是将非零元素的值和它所在的行列号作为一个结点存放到一起，于是矩阵中的每一个非零元素就由一个三元组（i，j，aij）唯一确定。显然，稀疏矩阵的压缩存储方法会让其失去随机存取功能。
2 三元组表示稀疏矩阵转置算法的实现
用三元组来表示非零元素时稀疏矩阵的压缩存储方法的具体数据类型说明如下：
三元组表示的稀疏矩阵，如何实现转置算法呢？矩阵的转置是基本的矩阵运算，对于一个m×n 的矩阵M，它的转置N是一个n×m 的矩阵，且有N（i，j）=M（j，i）。设M和N互为转置矩阵，显然一个稀疏矩阵的转置亦是稀疏矩阵，假定a和b是此Stp类型的变量，分别表示矩阵M和N，接下来的问题就是如何实现由a到b。由于我们所用的存储方式一般都是按行存储，三元组表示的稀疏矩阵实现转置时具体做法是将每个三元组中的行列号互换，并按照新的行号排列三元组。实现转置操作主要有两步：第一步，在三元组表中，对i和j的值进行交换。第二步，重新排列三元组之
间的次序从而得到矩阵的转置。第一步实现起来很容易，第二步的实质就是如何实现使b.data三元组以矩阵N的行，也就是M的列为主序列来存储。按照M矩阵的列序进行转置操作，对M中的每一列col，通过从头到尾扫描三元组表a.data，找到所有列序号等于col的那些三元组，将它们的行号和列号交换后顺序依次放入b.data中，即可以得到N 的按行优先的压缩存储表示。具体代码实现过程比较简单，读者可自行完成，过程中需要注意的是参数之间利用地址传递比利用值传递容易实现很多。基于三元组的存储方式对稀疏矩阵的压缩存储，在对稀疏矩阵进行转置运算时，还有一种改进的的快速转置的算法，它的时间复杂度只有O（n+t），这种快速转置的算法还需引入两个数组作为辅助数据结构，其中一个表示矩阵M中某列的非零元素的个数；另一个数组初始值表示矩阵M中某列的第一个非零元素在N中的位置。它们之间具有一定的递归关系。利用附加的这种关系结构能够更精巧的完成稀疏矩阵基于三元组的转置运算，这里就不再敖述。
3 算法时空复杂度的分析
一般情况下，算法的时间效率和空间效率是一对矛盾体。有时算法的时间效率的提高是以使用了更多的存储空间为代价的，反之亦然。基于三元组的基本的矩阵转置算法的时间主要耗费在了此算法的二重循环上，若M的列数为n，
三元组表示稀疏矩阵的转置(一般算法和快速算法)
一、设计要求 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() //主函数
实现稀疏矩阵(采用三元组表示)的基本运算实验报告
实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组； （3）输出a + b 的三元组； （4）输出 a * b 的三元组； 三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={
CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在 操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在 操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在 操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在 操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在
数据结构稀疏矩阵转置,加法
《数据结构》实验报告 ◎实验题目:稀疏矩阵的转置、加法（行逻辑链接表） ◎实验目的：学习使用三元组顺序表表示稀疏矩阵，并进行简单的运算 ◎实验内容：以三元组表表示稀疏矩阵，并进行稀疏矩阵的转置和加法运算。 一、需求分析 该程序目的是为了用三元组表实现稀疏矩阵的转置和加法运算。 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);
数据结构三元组完成版
#include
if(m < 1 || m > (*M).mu || n < 1 || n > (*M).nu) k=1; if(m < (*M).data[i-1].i || m == (*M).data[i-1].i && n <= (*M).data[i-1].j) // 行或列的顺序有错 k=1; }while(k); (*M).data[i].i = m; //行下标 (*M).data[i].j = n; //列下标 (*M).data[i].e = e; //该下标所对应的值 } return 1; } // 销毁稀疏矩阵M，所有元素置空 void DestroySMatrix(TSMatrix *M) { (*M).mu=0; (*M).nu=0; (*M).tu=0; } // 输出稀疏矩阵M void PrintSMatrix(TSMatrix M) { int i; printf("\n%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu); printf("%4s%4s%8s\n", "行", "列", "元素值"); for(i=1;i<=M.tu;i++) printf("%4d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e); } // 由稀疏矩阵M复制得到T int CopySMatrix(TSMatrix M,TSMatrix *T) { (*T)=M; return 1; } // AddSMatrix函数要用到 int comp(int c1,int c2) { int i; if(c1 专业课程设计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( )实现。当用户选择该功能，系统提示输 常熟理工学院 《数据结构与算法》实验指导与报告书 _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 数据结构课程设计报告 题目：十字链表成为存储结构，实现稀疏矩阵的求和运算 学生姓名:张旋 班级:软件三班学号:201213040304 指导教师: 吴小平 一、需求分析 1.问题描述： 要求：十字链表下的稀疏矩阵的加、转、乘的实现。 2.基本功能 实现十字链表下的转置，乘法，加法运算。 3.输入输出 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （5）构造函数进行稀疏矩阵的转置，并输出结果。 （6）退出系统。 二、概要设计 1.设计思路： 本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。 2.数据结构设计： 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ 数据对象：D={aij | i=1,2,…,m; j=1,2,..,n; aij∈Elemset, m和n分别称为矩阵的行数和列数。} 数据关系：R={Row,Col} Row={ 数据结构---三元组顺序表------稀疏矩阵的转置和快速转置 #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.稀疏矩阵运算器 数据结构课程设计任务书 针对本课程设计，完成以下课程设计任务： 1、熟悉系统实现工具和上机环境。 2、根据课程设计任务，查阅相关资料。 3、针对所选课题完成以下工作： （1）需求分析 （2）概要分析 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4、书写上述文档和撰写课程设计报告。 3.课程设计报告目录 4.正文 （1）问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算频率。实现一个能进行稀疏矩阵基本运算的运算器。 （2）需求分析 本课程设计的稀疏矩阵运算器在visual studio 2013下运行调试成功，可以实现的功能有： 1.矩阵运算方式选择 2.根据提示输入相应数据 3.显示最终结果 使用的主要存储结构为三元组，并用三元组形式进行运算。所有参与运算数据类型为整形，因此输入的数据应为整形数据。为了节省存储空间使用三元组数据进行运算，可以通过多次扫描三元组数据来实现，即使用嵌套循环函数。输出结果为通常的阵列形式，因此使用了右对齐，保证输出形式的整齐。 （3）概要分析 本次课程设计中定义的结构体 typedef struct { int i, j;//矩阵元素所在行列 int v;//元素的值 }triple; typedef struct { triple data[MAXSIZE]; triple cop[MAXSIZE];//辅助数组 int m, n, t;//矩阵的行列数 }tripletable; Main函数调用子函数时输入1为调用 int Push_juzhen(int m, int n, int count)函数，可以实现矩阵相加功能 输入2为调用 int Dec_juzhen(int m, int n, int count)函数，可实现矩阵相减功能 输入3为调用 int Mul_juzhen()函数，可以实现矩阵相乘功能 （4）详细分析（流程图伪代码） 加法函数 int Push_juzhen(int m, int n, int count)//矩阵相加（行，列，矩阵数） { // p行，q列，s非零元素个数，v元素值 //ucount对数组下标计数的变量，与变量x实现多个矩阵相加 for (int c = 0; c < count; c++) { int x = 0; cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl; cin >> s; cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl; for (; x< s; x++)//传递行列及元素值 龙源期刊网 https://www.sodocs.net/doc/fe9953469.html, 基于十字链表与三元组表的稀疏矩阵压缩存储实例研究 作者：周张兰 来源：《软件导刊》2017年第11期 摘要：十字链表和带行链接信息的三元组表是稀疏矩阵的两种压缩存储方法。十字链表为链式存储结构，带行链接信息的三元组表为顺序存储结构。在MovieLens数据集上设计了分别采用十字链表和带行链接信息的三元组表对以用户为行、项目为列、用户评分为矩阵元的稀疏矩阵进行压缩存储，并在这两种存储结构上实现用户相似度计算算法。通过测试分析和比较了两种不同的压缩存储方法在创建及相似度计算上的执行效率，并探讨了各自的特点及适用条件。 关键词关键词：稀疏矩阵；十字链表；三元组表；压缩存储 DOIDOI：10.11907/rjdk.171845 中图分类号：TP302 文献标识码：A文章编号文章编号：16727800（2017）011002204 0引言 矩阵是科学与工程计算问题中研究的数学对象。在高阶矩阵中，可能存在很多相同值或零值的矩阵元，对这些矩阵元的存储造成存储空间的浪费。因此，可以对矩阵进行压缩存储，以节省存储空间，达到提高存储利用率的目的。在算法实现中，选择的存储结构不同，执行效率也将不同。对不同矩阵存储方法的特点进行分析和比较，有助于根据不同的实际应用，有针对性地选择更为合适的存储结构，以此提高矩阵运算及其它相关操作的运行效率。 1稀疏矩阵及存储 若一个m行n列矩阵中的零元素有t个，零元素个数t与矩阵元总数m×n的比值称为稀疏因子，一般认为若稀疏因子不大于0.05，则此矩阵为稀疏矩阵。设矩阵有10行10列，即总共100个元素，若其中零元素有95个，而非零元素仅有5个，则此矩阵为稀疏矩阵。在存储稀疏矩阵时，可以采用非压缩存储和压缩存储两种方式。非压缩存储使用二维数组，比如，设10 行10列的稀疏矩阵M的矩阵元均为整数，则可以使用二维数组存储该矩阵M，数组的定义用C语言[1]描述如下： int a[10][10]； 稀疏矩阵 一、问题描述 假若在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]; 专业课程设计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( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始 数据结构 课程设计实验报告 内容名称：稀疏矩阵的基本操作成员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 语言的特色。培养学生独立工作和创新思维的能力，取得设计与调试的实践经验。提高和加强计算机应用及软件开发能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定 课程设计任务书 学生姓名：专业班级： 指导教师：夏红霞工作单位：计算机科学与技术学院题目: 稀疏矩阵乘法的运算 课程设计要求: 1、熟练掌握基本的数据结构； 2、熟练掌握各种算法； 3、运用高级语言编写质量高、风格好的应用程序。 课程设计任务: 1、系统应具备的功能： （1）设计稀疏矩阵的存储结构 （2）建立稀疏矩阵 （3）实现稀疏矩阵的乘法 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排：2010年7月5日－9日（第19周） 7月5日查阅资料 7月6日系统设计，数据结构设计，算法设计 7月7日 -8日编程并上机调试 7月9日撰写报告 7月10日验收程序，提交设计报告书。 指导教师签名： 2010年7月4日系主任（或责任教师）签名： 2010年7月4日 目录 1.摘要 (1) 2.关键字 (1) 3.引言 (1) 4. 问题描述 (1) 5. 系统设计 (1) 6. 数据结构 (3) 7. 算法描述 (3) 8. 测试结果与分析 (4) 9. 源代码 (12) 10. 总结 (29) 11.参考文献 (29) 稀疏矩阵乘法的运算 1.摘要：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。因此需要采取其他的方法来解决这个问题，由于0在乘法中其结果总是0，所以可以考虑采用三元组的方式去存储稀疏矩阵中的非零元，这样在计算过程中不仅需要的内存空间减少了，而且运算的速率也提高了。 2.关键字：稀疏矩阵乘法二维矩阵算法复杂度 3.引言：随着科学技术的发展，人们对矩阵的运算的几率越来越大，特别是高新科技研究中对矩阵的运算更是常见。但是如何高效的并占内存少的进行矩阵运算就是一个急需解决的问题。本文主要对稀疏矩阵的存储以及稀疏矩阵的乘法运算进行了研究和探讨。 4.问题描述：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。为了减少空间和时间复杂度，可以根据给定的二维数组的数据设计稀疏矩阵的存储结构，然后根据设计的稀疏矩阵存储结构建立一个稀疏矩阵，最后获得两个二维数组得到他们各自的稀疏矩阵，计算这两个稀疏矩阵的乘积。 5.系统设计： 5.1 设计目标：通过一定的数据结构，存储含有少量数据的矩阵，把他们存入一个稀疏矩阵中，然后实现稀疏矩阵的乘法运算。[基本要求]设计稀疏矩阵的存储结构；建立稀疏矩阵；实现稀疏矩阵的乘法稀疏矩阵的运算(完美版)
数据结构与算法 特殊矩阵和稀疏矩阵
数据结构课程设计之稀疏矩阵实现与应用1
数据结构---三元组顺序表------稀疏矩阵的转置和快速转置
基于三元组表表示的稀疏矩阵的快速转置算法及其改进
三元组顺序表稀疏矩阵课程设计报告(不完整)
基于十字链表与三元组表的稀疏矩阵压缩存储实例研究
稀疏矩阵(算法与数据结构课程设计)
稀疏矩阵的运算(完美版)
数据结构C语言版-稀疏矩阵三元组的基本操作
稀疏矩阵乘法的运算
相关文档
- 稀疏矩阵快速转置 数据结构实验报告
- 稀疏矩阵转置
- 数据结构与算法 特殊矩阵和稀疏矩阵
- 稀疏矩阵的建立与转置
- 稀疏矩阵基本操作实验报告
- 稀疏矩阵的运算
- 4.3.1 稀疏矩阵-稀疏矩阵的抽象数据类型
- 稀疏矩阵(算法与数据结构课程设计)
- Java实现稀疏矩阵的转置
- 三元组表示稀疏矩阵的转置(般算法和快速算法)
- 三元组结构实现稀疏矩阵转置算法的分析
- 三元组表示稀疏矩阵的转置(一般算法和快速算法)
- 稀疏矩阵的运算(完美版)
- 稀疏矩阵的运算(完美版)
- 稀疏矩阵的运算(完美版)
- 基于三元组表表示的稀疏矩阵的快速转置算法及其改进
- 稀疏矩阵基本操作 实验报告
- 稀疏矩阵基本操作 实验报告
- 4.3.3 稀疏矩阵-快速转置算法
- 稀疏矩阵快速转置