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

《数据结构实验五矩阵的压缩存储与运算.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章 矩阵的压缩存储与运算【实验目的】1.熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2.掌握稀疏矩阵的加法、转置、乘法等基本运算；3.加深对线性表的顺序存储和链式结构的理解。第一节 知识准备    矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵

2、的压缩存储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

3、中找到元素m[k]= ；这里：k=i(i+1)/2+j   (i≥j) 图5-1 下三角矩阵a00a10a11a20…an-1,0…an-1,n-1k=  0        1      2        3     …     n(n-1)/2  …   n(n+1)/2-1                    图5-2下三角矩阵的压缩存储第五章 矩阵的压缩存储与运算【实验目的】1.熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2.掌握稀疏矩阵的加法、转置、乘法等基本运算；3.加深对线性表的顺序存储和链式结构的理解。第一节 知识准备    矩阵是由两个关

4、系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储1.对称矩阵和上、下三角阵若n阶矩阵A中的元素满足   =  （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零）

5、，都可以用一维数组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 下三角矩阵a00a10a11a20…an-1,0…an-1,n-1k=  0        1      2        3     …     n

6、(n-1)/2  …   n(n+1)/2-1                    图5-2下三角矩阵的压缩存储第五章 矩阵的压缩存储与运算【实验目的】1.熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2.掌握稀疏矩阵的加法、转置、乘法等基本运算；3.加深对线性表的顺序存储和链式结构的理解。第一节 知识准备    矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看

7、成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储1.对称矩阵和上、下三角阵若n阶矩阵A中的元素满足   =  （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二