下载文档原格式
数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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-1k= 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。
特殊矩阵的压缩存储所谓特殊矩阵：是指矩阵中值相同的元素或者零元素的分布有⼀定的规律。
常见的特殊矩阵有：对称矩阵、三⾓矩阵、对⾓矩阵。
注意：它们都是⽅阵，即⾏数和列数相同。
主对⾓线：在矩阵中每个元素的⾏标等于纵标（i==j）。
上三⾓：在矩阵中每个元素的⾏标⼩于纵标（i<j）。
下三⾓：在矩阵中每个元素的⾏标⼤于纵标（i>j）。
⼀、对称矩阵的压缩存储⼀个n阶⽅阵A[n][n]中的元素满⾜ai,j=aj,i(0<=i,j<=n-1),则称其为n阶对称矩阵。
压缩存储：由于元素关于主对⾓线对称，在存储时只存储对称矩阵的上三⾓或下三⾓元素，使得对称的元素共享⼀个存储空间。
（以⾏序为主序存储其下三⾓+主对⾓线的元素，⼀共要存储n*(n+1)/2个元素）由于k的序号=所有它前⾯元素的个数=所在⾏前⾯⾏的所有元素+所在⾏它前⾯的元素（包括本⾝）。
⼀维数组k与与⼆维数组元素的i、j之间的关系：当i>=j时，k=i*(i+1)/2 + j;//本例都是以0为开始的下标，以下也是类同。
当i<j时，k=j*(j+1)/2+i;⼆、三⾓矩阵的压缩矩阵上三⾓矩阵：当⼀个⽅阵的主⾓线以下的所有元素皆为零；当i<=j时，k=(i-1)*(2n-i+2)/2+j-2;(以下公式为了⽅便理解，i,j,k都是从1开始)矩阵元素压缩放在⼀维数组上，可以理解为：如5*5矩阵上三⾓矩阵第⼀⾏为5个元素，第⼆⾏为4个元素...最后⼀⾏为1个元素（也就是元素个数逐减的等差数列an=n-i+1，an代表每⾏的个数，i代表的是第⼏项（第⼏⾏），所以a1=n-1+1=n,当前⾏的前⾯所有⾏的元素和：s(i-1)=n(a1+an)/2=(i-1)*[n+(n-（i-1)+1)]=(i-1)*(2n-i+2)/2）如：a[3][3]=b[10],s2=5+4=9，所以k=s2+j-2=10。
下三⾓矩阵：当⼀个⽅阵的主⾓线以上的所有元素皆为零；当i>=j时，k=i*(i+1)/2+j-2;。
三对角矩阵压缩存储三对角矩阵是一种特殊类型的矩阵，在存储和计算上具有一定的优势。
本文将从三对角矩阵的定义、特性、压缩存储方法以及相应的计算算法等方面进行介绍。
一、三对角矩阵的定义三对角矩阵是指除了主对角线上的元素外，只有上下相邻对角线上的元素不为零，其余元素都为零的矩阵。
例如，一个n阶的三对角矩阵可以表示为：\[ A = \begin{bmatrix}b_1 & c_1 & 0 & \cdots & \cdots & \cdots & 0 \\a_2 & b_2 & c_2 & 0 & \cdots & \cdots & 0 \\0 & a_3 & b_3 & c_3 & 0 & \cdots & 0 \\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\0 & \cdots & \cdots & \cdots & \cdots & a_{n-1} & b_{n-1} \\ 0 & \cdots & \cdots & \cdots & \cdots & 0 & a_n \\\end{bmatrix} \]其中，b1, b2, ..., bn为主对角线上的元素；a2, a3, ..., an为下对角线上的元素；c1, c2, ..., cn-1为上对角线上的元素。
二、三对角矩阵的特性1. 三对角矩阵是一种稀疏矩阵，大部分元素都为零，只有O(n)个非零元素。
2. 三对角矩阵可以用来表示一些特定问题的线性方程组，如一维热传导方程、抛物线偏微分方程等。
一、实验目的1. 理解并掌握矩阵压缩存储的基本原理和方法。
2. 学习针对不同类型矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储技术。
3. 通过编程实现矩阵压缩存储，并验证其正确性和效率。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 实验数据：随机生成的矩阵数据三、实验内容本次实验主要针对以下三种特殊矩阵的压缩存储进行实验：1. 对称矩阵2. 三角矩阵（上三角矩阵和下三角矩阵）3. 稀疏矩阵四、实验步骤1. 对称矩阵压缩存储- 设计一个对称矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。
- 实现一个函数，将输入的对称矩阵压缩存储到一维数组中。
- 实现一个函数，根据一维数组中的元素索引还原对称矩阵。
2. 三角矩阵压缩存储- 设计一个三角矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。
- 实现两个函数，分别用于将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中。
- 实现两个函数，分别用于根据一维数组中的元素索引还原上三角矩阵和下三角矩阵。
3. 稀疏矩阵压缩存储- 设计一个稀疏矩阵的结构体，包含矩阵的行数、列数、非零元素个数以及压缩后的数组。
- 实现一个函数，将输入的稀疏矩阵压缩存储到一维数组中。
- 实现一个函数，根据一维数组中的元素索引还原稀疏矩阵。
五、实验结果与分析1. 对称矩阵压缩存储- 实验结果：成功将输入的对称矩阵压缩存储到一维数组中，并可以正确还原。
- 分析：对称矩阵压缩存储可以节省约50%的存储空间。
2. 三角矩阵压缩存储- 实验结果：成功将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中，并可以正确还原。
- 分析：三角矩阵压缩存储可以节省约75%的存储空间。
3. 稀疏矩阵压缩存储- 实验结果：成功将输入的稀疏矩阵压缩存储到一维数组中，并可以正确还原。
- 分析：稀疏矩阵压缩存储可以大大节省存储空间，提高矩阵运算的效率。
精品资料数据结构实验五矩阵的压缩存储与运算........................................第五章矩阵的压缩存储与运算【实验目的】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-1k= 0 1 23 …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= 。
template<class Type>SparseMatrix<Type>SparseMatrix<Type>::FastTranspos ( ) ...{//对稀疏矩阵a(*this指示)做快速转置，结果放在b中，时间代价为O(Terms+Columns)。
int *rowSize = new int[Cols];//辅助数组，统计各列非零元素个数int *rowStart = new int[Cols];//辅助数组，预计转置后各行存放位置SparseMatrix<Type> b ( Cols, Rows );//存放转置结果b.Rows = Cols; b.Cols = Rows;b.Terms = Terms;if ( Terms > 0 ) ...{for (int i = 0; i < Cols; i++) rowSize[i] = 0;//统计矩阵b中第i行非零元素个数for ( i = 0; i < Terms; i++ )//根据矩阵a中第i个非零元素的列号，将rowSize相当该列的计数加1rowSize[smArray[i].col]++;rowStart[0] = 0;//计算矩阵b第i行非零元素的开始存放位置for ( i = 1; i < Cols; i++ ) //rowStart[i]=矩阵b的第i行的开始存放位置rowStart[i] = rowStart[i-1]+rowSize[i-1];for ( i = 0; i < Terms; i++ ) ...{//从a向b传送int j = rowStart[smArray[i].col];//j为第i个非零元素在b中应存放的位置b.smArray[j].row = smArray[i].col;b.smArray[j].col = smArray[i].row;b.smArray[j].value = smArray[i].value;rowStart[smArray[i].col]++;}}delete[ ] rowSize;delete [ ] rowStart; return b;}。
矩阵压缩储存三元组带状矩阵矩阵压缩储存是一种常用的数据结构，用于减少存储空间和提高数据处理效率。
在某些特殊类型的矩阵中，存在大量的零元素，这些零元素会占据大量的存储空间，并且对于计算和处理时也会造成浪费。
因此，为了更高效地存储和处理这些特殊类型的矩阵，我们可以使用三元组带状矩阵的方法。
三元组带状矩阵是一种压缩储存矩阵的方法，它通过记录矩阵中非零元素的值、所在行和列的信息，来表示整个矩阵。
与普通的矩阵相比，三元组带状矩阵可以大大减少存储空间的使用。
三元组带状矩阵的存储方式如下：首先，我们需要记录矩阵的行数和列数，以及非零元素的个数。
然后，我们使用一个数组来存储非零元素的值，另外还需要两个数组来存储非零元素所在的行和列的信息。
这样，我们就可以通过这三个数组来表示整个矩阵了。
举个例子来说明三元组带状矩阵的存储方式。
假设有一个5x5的矩阵，其中只有4个非零元素，分别是2、4、6和8。
那么我们可以使用如下的三个数组来表示这个矩阵：值数组：[2, 4, 6, 8]行数组：[1, 2, 3, 4]列数组：[1, 2, 3, 4]通过这三个数组，我们就可以还原出原始的矩阵。
在这个例子中，我们可以得到如下的矩阵：2 0 0 0 00 4 0 0 00 0 6 0 00 0 0 8 00 0 0 0 0可以看到，通过三元组带状矩阵的存储方式，我们只需要存储非零元素的信息，而零元素则可以省略不存储。
这样就大大减少了存储空间的使用。
而带状矩阵是指矩阵中非零元素所在的行和列的分布呈带状结构。
带状矩阵可以用来表示一些具有特定规律的矩阵，比如对角线元素较多的矩阵。
在带状矩阵中，非零元素分布在主对角线及其附近的带状区域内，其宽度可以根据实际情况确定。
通过使用带状矩阵的特性，我们可以进一步优化三元组带状矩阵的存储方式。
在存储非零元素的值、行和列的数组中，我们可以按照带状矩阵的分布规律来存储元素的信息，这样可以进一步减少存储空间的使用。
稀疏矩阵的压缩存储方法与应用场景稀疏矩阵指的是矩阵中绝大部分元素为0的情况下，只保存非零元素及其对应的坐标的一种存储方式。
相比于一般的矩阵存储方式，稀疏矩阵的压缩存储方法可以有效节省存储空间，并提高运算效率。
本文将介绍一些常见的稀疏矩阵的压缩存储方法以及其应用场景。
一、行压缩存储法(CRS)行压缩存储法(CRS，Compressed Row Storage)是一种经典的稀疏矩阵压缩存储方法。
在CRS中，矩阵的非零元素按行优先的顺序存储，并记录每行非零元素的开始位置及其列号。
由于CRS只存储非零元素及其对应的行列坐标，因此可以大大减少存储空间。
CRS适用于行操作较多的场景，比如图像处理、有限元分析等。
在这些场景下，常常需要对稀疏矩阵进行行操作，例如行相加、行相减、行乘以常数等。
CRS可以通过迅速定位非零元素所在的行并对其进行操作，提高计算效率。
二、列压缩存储法(CCS)列压缩存储法(CCS，Compressed Column Storage)是另一种常见的稀疏矩阵压缩存储方法。
在CCS中，矩阵的非零元素按列优先的顺序存储，并记录每列非零元素的开始位置及其行号。
与CRS相比，CCS可以更加高效地进行列操作，如列相加、列相减、列乘以常数等。
CCS常用于图论、网络分析等领域。
例如，在图论中，常常需要对邻接矩阵进行列操作，如计算图的邻接节点、计算图的度数等。
CCS 可以快速对非零元素所在的列进行操作，提高计算效率。
三、对角线压缩存储法(Diagonal Storage)对角线压缩存储法是一种适用于具有特殊结构的稀疏矩阵的压缩存储方法。
在对角线压缩存储法中，只存储矩阵的非零主对角线元素以及非零副对角线元素，其余元素均为0。
通过存储非零对角线元素及其位置，可以进一步减少存储空间。
对角线压缩存储法适用于具有对称或反对称性质的矩阵。
在数值计算、网络传输等领域，经常需要处理对称或反对称矩阵。
对角线压缩存储法可以有效存储这类特殊结构的矩阵，并提高运算效率。
特殊矩阵的压缩存储简介矩阵是数学和计算机科学中的基本数据结构之一，广泛应用于各个领域。
在某些情况下，矩阵的数据量十分庞大，导致存储和处理的效率低下。
为解决这一问题，特殊矩阵的压缩存储方法应运而生。
什么是特殊矩阵特殊矩阵是指具有一定特征或性质的矩阵。
常见的特殊矩阵包括对角矩阵、三角矩阵、稀疏矩阵等。
这些矩阵在实际应用中具有普遍性和重要性，因为它们往往可以提供更高效的存储和运算方式。
1. 对角矩阵对角矩阵是指所有的非对角元素都为零的矩阵。
由于对角矩阵的特殊属性，可以使用一维数组来存储矩阵的主对角线元素，从而减少存储空间的占用。
2. 三角矩阵三角矩阵是指所有主对角线以下或以上的元素都为零的矩阵。
同样地，三角矩阵可以使用一维数组来压缩存储，只存储非零元素即可。
3. 稀疏矩阵稀疏矩阵是指元素中绝大多数为零的矩阵。
对于稀疏矩阵，传统的二维数组存储方式存在很大的空间浪费。
因此，压缩存储方法可以大幅减少稀疏矩阵的存储空间。
压缩存储方法特殊矩阵的压缩存储方法旨在减少存储空间的占用，并提高对矩阵的操作效率。
常见的压缩存储方法包括对角线压缩法、三角矩阵压缩法和行逻辑链接法等。
1. 对角线压缩法对于对角矩阵和三角矩阵，可以使用对角线压缩法来进行存储。
对角线压缩法是指只存储矩阵的主对角线元素或其他非零对角线元素，并用一维数组来表示。
通过这种方式，可以大幅减少矩阵的存储空间，并方便对矩阵进行操作。
对角矩阵的压缩存储对角矩阵的对角线元素存储在一维数组中，数组的长度等于矩阵的行数或列数。
例如，对于一个3x3的对角矩阵：1 0 00 2 00 0 3可以使用一维数组[1, 2, 3]来表示。
三角矩阵的压缩存储三角矩阵的非零元素存储在一维数组中，数组的长度等于矩阵的行数或列数。
对于下三角矩阵，可以使用一维数组来存储矩阵的下三角部分（不包含主对角线），而上三角矩阵可以使用一维数组来存储矩阵的上三角部分。
例如，对于一个3x3的下三角矩阵：1 0 02 3 04 5 6可以使用一维数组[2, 4, 5]来表示。
特殊矩阵的压缩存储特殊矩阵的压缩存储是一种将矩阵中的零元素省略掉，只存储非零元素及其位置信息的存储方式。
这种存储方式可以大大减少矩阵在内存中所占用的空间，提高计算效率和存储效率。
一、特殊矩阵的定义特殊矩阵是指具有某些特定性质的矩阵。
常见的特殊矩阵有三角矩阵、对称矩阵、对角线矩阵、稀疏矩阵等。
1. 三角矩阵：当一个上三角（下三角）矩阵中除了主对角线和下（上）方所有元素都为零时，称之为上（下）三角矩阵。
2. 对称矩阵：当一个方阵A满足A[i][j]=A[j][i]时，称之为对称矩阵。
3. 对角线矩阵：当一个方形n×n的稠密（dense）或稀松（sparse）实数或复数方针中非对角线元素都为0时，该方针被称为对角线方针。
4. 稀松（sparse）或稀有（sparsest）系数或系数矩阵（sparse matrix）：在数学中，一个矩阵如果大部分元素为零，那么这个矩阵就被称为稀疏矩阵。
二、特殊矩阵的压缩存储方式特殊矩阵的压缩存储方式是一种将矩阵中的零元素省略掉，只存储非零元素及其位置信息的存储方式。
这种存储方式可以大大减少矩阵在内存中所占用的空间，提高计算效率和存储效率。
1. 三角矩阵的压缩存储对于上三角（下三角）矩阵A，只需要把主对角线以下（以上）的元素按行优先顺序排列成一个一维数组B即可。
由于上（下）三角形中有n(n-1)/2个零元素，因此B数组长度为n(n+1)/2。
例如：A = [ 1 2 3 ][ 0 4 5 ][ 0 0 6 ]B = [ 1, 2, 3, 4, 5, 6 ]2. 对称矩阵的压缩存储对于对称方针A，只需要把其中任意一个三角形（上或下）中的非零元素按行优先顺序排列成一个一维数组B即可。
由于对称方针中有n(n+1)/2个零元素，因此B数组长度为n(n+1)/2。
例如：A = [ 1 2 3 ][ 2 4 5 ][ 3 5 6 ]B = [ 1, 2, 3, 4, 5, 6 ]3. 对角线矩阵的压缩存储对于对角线方针A，只需要把其对角线上的元素按行优先顺序排列成一个一维数组B即可。
软件综合课程设计特殊矩阵的压缩存储算法的实现二叉排序树的实现二〇一四年六月一、特殊矩阵的压缩存储算法的实现1.问题陈述对于特殊矩阵可以通过压缩存储减少存储空间。
基本要求：1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值；2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值；2.程序代码#include<stdio.h>#include <stdlib.h>#include<iostream.h>static shangsanjiao(int n){int i,j,k,z,g;int L[100][100],SA[100];cout<<"请输入您要压缩矩阵的行列数"<<endl;cin>>n;cout<<"请输入您的矩阵内元素："<<endl;for(i=1;i<n+1;i++)for(j=1;j<n+1;j++){cin>>L[i][j];if(i<=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;SA[k]=L[i][j];}cout<<"您输入的矩阵为："<<endl;for(i=1;i<n+1;i++){for(j=1;j<n+1;j++)cout<<L[i][j]<<" ";cout<<endl;}cout<<"压缩存储后："<<endl;for(k=0;k<n*(n+1)/2+1;k++)cout<<k<<" "<<SA[k];cout<<"若要读取矩阵的值请输入'100'退出输入'000'。
