数据结构(DATASTRUCTURE)第四章矩阵的压缩存储数组的定义及其基本操作二维数组同样满足数组的定义。一个二维数组可以被看成是特殊的一维数组，其中，每个元素又是一个一维数组。多维数组可以按同样的方法类推。2)数组的特点数组中的数据元素数目固定(结构固定)数组中的数据元素具有相同的数据类型(元素同构)数组中的每个数据元素都与一组唯一的下标值相对应；数组是一种随机存储结构。3)数组的基本运算数组的顺序存储1）存储方式计算机的存储结构是一维的，因而多维数组必须按某种次序排成一个线性序列加以存储。以二维数组行优先顺序存储为例：假设每个元素占用l单元。推广到n维数组将其中的每一个元素映射到一维数组的某一个位置，各维元素个数为m1,m2,m3,…,mn，下标为i1,i2,i3,…,in的数组元素的存储地址：特殊矩阵的压缩存储对称矩阵a11a21a22a31a32a33.......an,1........an,n为了便于访问方阵A中的元素，必须在aij和S[k]之间建立一个对应关系。若aij在下三角矩阵中(i≥j)，则有：}CrossList;Olink*rhead,*chead;/*行、列表指针向量基址*/if(!M.一个一维数组，一旦第一个元素a0的存储地址Loc(a0)确定，而每个元素所占用的存储空间大小为l,则第i个元素的地址可以由以下公式计算：以矩阵的转置为例说明这种压缩存储结构是如何实现矩阵运算的。()}SPMatrix;数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。j,data[0].元素的总数，则称这个矩阵为稀疏矩阵。()000000000voidTransposeSMtrix(TSMatrixa，TSMatrix&b)j]++;//求A中每列非0元个数()2）任意元素存储地址的计算稀疏矩阵的压缩存储{SPMatrixB;//寻找插入位置逻辑地址物理地址的计算；数组的顺序存储（行优先，列优先）chead[i]==NULL||M.returnOVERFLOW;2）任意元素存储地址的计算/*内存分配失败，返回溢出信息*/第四章矩阵的压缩存储64-7若aij在下三角矩阵中(i≥j)，则有：mu;/*行、列数互换*/j,data[0].修改数组元素值(给定一组下标，修改相应数据元素值)rhead[i]==NULL||M.//寻找插入位置LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*l数据类型定义：#defineSMax1024三元组结点：typedefintdatatypetypedefstruct{inti,j;datatypev;}SPNode;稀疏矩阵：typedefstruct{SPNodedata[SMax+1]];intmu,nu,tu;/*行、列、非零元素个数*/}SPMatrix;三元组表所需存储单元个数为3(t+1)其中t为非零元个数基本运算举例：以矩阵的转置为例说明这种压缩存储结构是如何实现矩阵运算的。问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。(一个m×n矩阵A，它的转置矩阵是一个n×m矩阵B，且A[i][j]=B[j][i]）一般矩阵转置算法：for(j=0;j<n;j++)for(i=0;i<m;i++)B[j][i]=A[i][j];T(n)=O(mn)从a.data的第一列开始转置(b.data的第一行），在转置完毕后，第二列的转置开始，程序的遍历同第一列相同，在此就不演示，仅把结果写出。方法一程序实现如下：voidTransposeSMtrix(TSMatrixa，TSMatrix&b){/*a，b分别表示两个稀疏矩阵，b是a的转置矩阵*//*程序中p、q分别指示b.data，a.data中三元组序号，col指示M的列号（即N的行号）*/intp,q,col;b.mu=a.nu;b.nu=a.mu;/*行、列数互换*/b.tu=a.tu;/*非零元数不变*/if（b.tu!=0）{/*若非零元不为零*/q=1;for（col=1;col<=a.nu;col++）方法二：快速转置算法扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查cpot表，按查到的位置直接将该项存入转置三元组表中。算法：P.84算法SPMatrixFast_TransMatrix(SPMatrixA){SPMatrixB;intp,q,col,k;intnum[n+1],cpot[n+1];=;//行数=;//列数=;//元素个数算法：P.84算法)//有非零元则转置