当前位置：文档之家› 01 稀疏矩阵压缩存储与转置

01 稀疏矩阵压缩存储与转置

河北工业大学计算机软件技术基础（VC）

课程设计任务书

一、题目：01稀疏矩阵压缩存储与转置

二、目的与要求

1．目的：

（1）通过该题目的设计，培养学生综合利用C++语言解决问题的能力，使学生理解和掌握C++语言的结构体，自定义函数等设计方法，将所学知识转化为分析和设计简单实际问题的能力，并学会查资料和工具书,进行创新设计。

（2）提高学生建立程序文档、归纳总结的能力。

（3）继续和深化软件技术基础课程的学习，初步了解数据结构中对于稀疏矩阵的存储与操作。

2．基本要求：

（1）要求用C++语言编程，在Visual C++环境下调试完成；

（2）要求使用C++的结构体和自定义函数完成设计；

（3）在VC++6.0环境中，学会调试程序的方法，及时查究错误，独立调试完成。

（4）程序调试通过后，完成程序文档的整理,加必要的注释。

三、设计方法和基本原理

1．课题功能描述

本题目的功能是对稀疏矩阵采用三元组的形式进行压缩存储，并能够对压缩存储的矩阵还原显示和转置。

2．基本原理和关键字

1）. 稀疏矩阵

矩阵中非零元素的个数较少（一般小于5%）。

2）. 压缩存储

只存储稀疏矩阵中的非零元素，同时存储这些元素的位置信息。

3）. 三元组

将每一个非零元素用（i，j，value）来表示，i表示非零元素所在的行，j表示非零元素所在的列，value是非零元素的值，这种方式表示称为三元组。

例如矩阵：

三元组形式的存储为：

其中每行表示一个三元组，其中第0个元素表示矩阵的总行数、列数、非零元素的个数；从第1行到第8行表示矩阵中的非零元素，每行的值分别表示非零元素所在的行数、列数和值。

3．问题解决方案（编程要求）：

1）编写程序，实现压缩矩阵的还原显示；

2）编写程序，实现压缩矩阵的转置，并将转置的矩阵以压缩矩阵的形式存储。

四、主要技术问题的描述：

1、定义三元组

使用结构体的形式定义三元组，结构体的分量包括非零元素所在的行、列和值。

struct Triple {

int i; //元素行号

int j; //元素列号

ElemType e; //元素值

};

使用结构体的形式定义稀疏矩阵，其分量包括三元组数组，矩阵总行数、总列数和非零元素总个数。

struct TsMatrix {

Triple data[MAXSIZE+1]; //三元组表，以行为主序存入一维向量data[ ]中

int mu; //矩阵总行数

int nu; //矩阵总列数

int tu; //矩阵中非零元素总个数

};

2、压缩矩阵还原显示

自定义函数，将三元组中非零元素在矩阵中相应的位置显示出来，其余的位置显示0。

3、压缩矩阵转置

如下图所示，自定义函数，直接将原始矩阵三元组的存储形式，转化为转置矩阵的三元组存储形式。

具体方法：依次扫面原始矩阵三元组存储形式中的列数据，按扫描到的列号从小到大的顺序存入到转置后矩阵的三元组形式，因为原始矩阵的行就是转置后矩阵的列。

1518 0 0 0-7(6, 4, -7)(6, 1, 15)(5, 2, 18)(5, 3, 14)(4, 6, -7)

(3, 4, 24)

三元组表b.data

五、创新要求

快速转置

压缩矩阵，利用带辅助向量的三元组表，辅助向量的内容包括每列的非零元素个数 NUM(i)以及每列的第一个非零元素在三元组表中的位置POS(i) 。

如下表所示：

利用此表直接找到原始矩阵三元组的元素在转置矩阵三元组中的存储位置，不需逐个扫描．．．．．．

从而节省系统时间。

六、课程设计的考核方式及评分方法

1．考核方式

（1）学生要提交书面课程设计报告（A4纸打印）；并将设计报告的电子文档、.cpp 源文件和.h 头

文件放到一个文件夹里（如果是基于MFC 的编程，另外还包括源程序的压缩包）上传到所对

应班级的学生名称相应文件夹中。

（2）课程设计结束时，在机房当场验收。教师提供测试数据，由学生运行所设计的系统，检查运

行结果是否正确，并回答教师提出的有关问题。

2．评分方法

根据出勤率、课程设计期间纪律、课程设计运行结果、课程设计报告及答辩情况综合评分。

七、书写设计报告的要求（详细内容见“设计报告模板”）

八、说明：课程设计的有关文档，“设计报告模板”和“课程设计要求”请在下载任务书处下载。

出师表

两汉：诸葛亮

先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。

宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。

侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。

将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。

亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。

臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。

先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽忠言，则攸之、祎、允之任也。

愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。臣不胜受恩感激。

今当远离，临表涕零，不知所言。

数据结构实验五矩阵的压缩存储与运算学习资料

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1

k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系：公式中采用了C语言的符号，int()表示取整，‘%’表示求余。

三元组表示稀疏矩阵的转置(一般算法和快速算法)

一、设计要求 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() //主函数

稀疏矩阵的建立与转置

实验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);

稀疏矩阵的运算(完美版)

专业课程设计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. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足 = （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 … n(n-1)/2 … n(n+1)/2-1 图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵

数据结构与算法特殊矩阵和稀疏矩阵

常熟理工学院《数据结构与算法》实验指导与报告书 _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 #define max 20 #define zero 0 typedef struct{ int i,j,v; }node; typedef struct{ node data[max]; int m; }TSmatrix; TSmatrix *Setmatrix(){ //建三对角矩阵TSmatrix *T; T=(TSmatrix *)malloc(sizeof(TSmatrix)); printf("请输入矩阵行数或列数:\n"); scanf("%d",&T->m); printf("建立三对角矩阵:\n"); for(int n=0;n<3*T->m-2;n++) scanf("%d%d%d",&T->data[n].i,&T->dat a[n].j,&T->data[n].v); return T; } TSmatrix *Trabsmatrix(TSmatrix *T){ //三对角矩阵转置 int n,k,temp; TSmatrix *F; F=(TSmatrix *)malloc(sizeof(TSmatrix)); F->m=T->m; for(n=0;n<3*T->m-2;n++){ //将结点信息存入新三元组表中 temp=2*T->data[n].j+T->data[n].i; //计算待存入三元数组下标 F->data[temp].i=T->data[n].j; F->data[temp].j=T->data[n].i; F->data[temp].v=T->data[n].v; } return F; } void TSmatrixout(TSmatrix *T){ //三对角矩阵输出 int a,b,n; n=0; for(a=0;am;a++){ for(b=0;bm;b++){ if(T->data[n].i==a&&T->data[n].j==b){ printf("%-5d",T->data[n].v); n++; } else printf("%-5d",zero); } printf("\n"); } } void main(){ TSmatrix *T; T=Setmatrix(); printf("三对角矩阵:\n"); TSmatrixout(T); T=Trabsmatrix(T); printf("转置后三对角矩阵:\n"); TSmatrixout(T); } 问题分析：本程序要求实现对压缩存储下的三对角矩阵进行转置，为实现上述功能，需要解决的关键问题是三对角矩阵压缩存储及转置过程。概要设计：利用三元组表以行序为主序压缩存储三对角矩阵。转置时，先利用三元数组中的行标i 和列标j计算出待放入新三元数组的下标temp。由于转置时需要将行标和列标交换，所以temp=2*j+i。找出待存入的下标后，将相应的信息存入下标为temp的三元数组中。详细设计：

稀疏矩阵及其压缩存储方法

稀疏矩阵及其压缩存储方法 1.基本概念稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。设m行n列的矩阵含t个非零元素，则称以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。如下三角阵、三对角阵、稀疏矩阵。压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。目的是节省大量存储空间。 n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。 2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构）三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。（1）稀疏矩阵的三元组顺序表存储表示方法 #define MAXSIZE 12500 // 假设非零元个数的最大值为12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; //非零元素的值 } Triple; // 三元组类型 typedef union { //共用体 Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型（2）求转置矩阵的操作 ◆用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) ◆用三元组顺序表表示时的快速转置算法 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];// 求M 中每一列所含非零元的个数

矩阵压缩1

为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。一、相关概念㈠特殊矩阵：矩阵中存在大多数值相同的元,或非0元，且在矩阵中的分布有一定规律。 ⒈对称矩阵：矩阵中的元素满足 a ij=a ji 1≤i,j≤n ⒉三角矩阵：上（下）三角矩阵指矩阵的下（上）三角（不包括对角线）中的元素均为常数c或0的n阶矩阵。 ⒊对角矩阵（带状矩阵）：矩阵中所有非0元素集中在主对角线为中心的区域中。㈡稀疏矩阵：非0元素很少（≤ 5%）且分布无规律。二、存储结构及算法思想 1、对称矩阵存储分配策略：每一对对称元只分配一个存储单元,即只存储下三角（包括对角线）的元, 所需空间数为: n(n+1)/2。存储分配方法：用一维数组sa[n(n+1)/2]作为存储结构。 sa[k]与a ij之间的对应关系为: 2、三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素b i,j和sb[k]之间仍然有如上的对应关系，只是还需要再加一个存储常数c的存储空间即可。如在下三角矩阵中，用n(n+1)/2的位置来存储常数。

对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案 2、稀疏矩阵常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。 1）、三元组表示法三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,a ij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。

基于三元组表表示的稀疏矩阵的快速转置算法及其改进

基于三元组表表示的稀疏矩阵的快速转置算法及其改进摘要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用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.熟悉数组、矩阵的定义和基本操作 2.熟悉稀疏矩阵的储存方式和基本运算 3.理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法三、实验原理 1.使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数。 2.稀疏矩阵的创建算法：第一步：根据矩阵创建一个二维数组，表示原始矩阵第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，重复该步骤。第三步：重复第二步，知道二维数组中所有的元素已经取出。 3.稀疏矩阵倒置算法：第一步：判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。第二步：计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i] 代表矩阵中第i列非零元素的个数）。以及倒置后矩阵每行首非零元的位置，存入cpot 数组中（其中cpot表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第一个非零元的位置）。第三步：确定倒置后矩阵的行数和列数。第四步：取出表示要导致矩阵中三元组表元素{e, I, j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中确定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中。cpot[j] 变量加一。第五步：重复第四步，直到三元组表中所有的元素都完成倒置。第六步：把完成倒置运算的三元组表输出。 4.稀疏矩阵加法算法：第一步：检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否则输出错误信息。第二步：定义变量i和j，用于控制三元组表的遍历。第三步：比较变量矩阵M中第i个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。进入第五步第四步：如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第

稀疏矩阵(算法与数据结构课程设计)

稀疏矩阵一、问题描述假若在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];