特殊矩阵的压缩存储

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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可以看到，通过三元组带状矩阵的存储方式，我们只需要存储非零元素的信息，而零元素则可以省略不存储。

这样就大大减少了存储空间的使用。

而带状矩阵是指矩阵中非零元素所在的行和列的分布呈带状结构。

带状矩阵可以用来表示一些具有特定规律的矩阵，比如对角线元素较多的矩阵。

在带状矩阵中，非零元素分布在主对角线及其附近的带状区域内，其宽度可以根据实际情况确定。

通过使用带状矩阵的特性，我们可以进一步优化三元组带状矩阵的存储方式。

在存储非零元素的值、行和列的数组中，我们可以按照带状矩阵的分布规律来存储元素的信息，这样可以进一步减少存储空间的使用。