资源描述：
《第4章 矩阵的压缩存储.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构(DATASTRUCTURE)主讲教师：杨华莉第四章矩阵的压缩存储多维数组数组的定义及其基本操作数组的存储结构矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵的压缩存储24.1数组的定义及其基本操作1)数组的定义数组是n(n>=0)个相同数据类型数据元素构成的有限序列。数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。3二维数组同样满足数组的定义。一个二维数组可以被看成是特殊的一维数组，其中，每个元素又是一个一维数组。多维数组可以按同样的方法类推。()()()()()()()()()42)数组的特点数组中的数据元素数目固定
2、(结构固定)数组中的数据元素具有相同的数据类型(元素同构)数组中的每个数据元素都与一组唯一的下标值相对应；数组是一种随机存储结构。53)数组的基本运算构造n维数组销毁n维数组存取数组元素值(给定一组下标，存取相应数据元素值)修改数组元素值(给定一组下标，修改相应数据元素值)64.1.2数组的顺序存储一个一维数组，一旦第一个元素a0的存储地址Loc(a0)确定，而每个元素所占用的存储空间大小为l,则第i个元素的地址可以由以下公式计算：LOC(i)=LOC(i-1)+l=a+i*l71）存储方式计算机的存储结构是一维的，因而多维数组必须按某种次序
3、排成一个线性序列加以存储。二维数组与高维数组按行优先方式顺序存储a11,a12,…a1n,a21,…,a2n,…,am1,am2,…,amn按列优先方式顺序存储a11,a21,…am1,a12,…,am2,…,a1n,a2n,…,amn8以二维数组行优先顺序存储为例：假设每个元素占用l单元。2）任意元素存储地址的计算由于任一元素aij前面有i-1行,每行n个元素LOC(aij)=LOC(a11)+((i-1)*n+(j-1))*l按列优先顺序存储：LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*l9推广到n维数组将其中的每
4、一个元素映射到一维数组的某一个位置，各维元素个数为m1,m2,m3,…,mn，下标为i1,i2,i3,…,in的数组元素的存储地址：104.2特殊矩阵的压缩存储高级语言中一般用二维数组存储矩阵，当矩阵中存在大量相同的元素或零元素时，浪费空间。矩阵的压缩存储:为多个值相同的元素只分配一个存储空间,对零元素不分配空间。特殊矩阵：值相同的元素或零元素在矩阵中分布有一定规律。稀疏矩阵：零元素较多，分布无规律。114.2.1对称矩阵在一个n阶方阵A中，若元素满足下述性质：则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只需要存储矩阵的上三角或下三
5、角矩阵，这样可以节约大约一半的空间。12a11a21a22a31a32a33.......an,1........an,n在此下三角阵中,第i行恰有i个元素,元素总数为a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1因此可将这些元素存放在一个向量S[n(n+1)/2]中13为了便于访问方阵A中的元素，必须在aij和S[k]之间建立一个对应关系。若aij在下三角矩阵中(i≥j)，则有：若aij在上三角矩阵中(i6、下三角矩阵：在多数情况下，三角矩阵的常数c为0。154.3稀疏矩阵的压缩存储如果一个矩阵的非0元素个数远远小于矩阵元素的总数，则称这个矩阵为稀疏矩阵。一般来说，稀疏矩阵非0元素的分布是无规律的。因此，在存储非0元素的同时，还要存储适当的辅助信息。稀疏矩阵常用的压缩存储方式：三元组表十字链表164.3.1三元组表存储特点：对于矩阵中每个非0元素，用它的行号、列号、元素值，即（i,j,aij）表示。将表示稀疏矩阵的所有非0元素的三元组按行优先（列优先）顺序排列，则可得到一个其结点均是三元组的线性表，称为三元组表。要唯一确定一个稀疏矩阵，还必须存储
7、该矩阵的行数和列数。17数据类型定义：#defineSMax1024三元组结点：typedefintdatatypetypedefstruct{inti,j;datatypev;}SPNode;稀疏矩阵：typedefstruct{SPNodedata[SMax+1]];intmu,nu,tu;/*行、列、非零元素个数*/}SPMatrix;18三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7A.dataijv012345678data[0].i,data[0].j,
8、data[0].v分别存放矩阵行数、列数和非零元个数行列下标非零元值例：19基本运算举例：以矩阵的转置为例说明这种压缩存储结构是如何实现矩阵运算的。问题描述：已知一
