稀疏矩阵数据构造与算法.docx

《稀疏矩阵数据构造与算法.docx》由会员分享，可在线阅读，更多相关《稀疏矩阵数据构造与算法.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、稀疏矩阵数据构造与算法1.什么是转置Mmn-Tnm，其中aij=bji(1im,1jn。i,j可看作与M,T无关的表示，可以以看作矩阵M为主动的下标表示方法)，而且aijM,bjiT。矩阵M已知，矩阵T未知。因而在编程时，应考虑以哪个矩阵为算法主序，这是一个出发点。(1)M，T的行列互换两个矩阵的行数mu列数nu互换，T.mu=M.nu=n，T.nu=M.mu=m，以T为主动。(2)矩阵元素T(i,j)=M(j,i)，矩阵T的第i行第j列元素与矩阵M的第j行第i列元素相等。以T的元素为驱动，由于能从M的元素得到T的元素，所以建立表达式就能得到T元素的值。在程序中，能否用矩阵T的顺序为算法线索？

2、转置矩阵的非0元个数一样，T.tu=M.tu(3)对0元素多的稀疏矩阵的转置而言，与一般矩阵的转置不同。稀疏矩阵的非0元素aij，在程序中用三元组(i,j,aij)表示，i,j表示行数列数。由于不再根据矩阵的构造m行n列转置，不使用二维数组作为存储，所以必须记录每一个非0元素所在行列的位置。在规则的二维数组中，矩阵的行列通过元素的下标识别，元素在矩阵中的位置通过下标得到。因此一般矩阵用二维数组为存储构造。二维数组是物理存储构造的逻辑形式，可称为逻辑存储构造。2.稀疏矩阵的一维数组存储构造从操作系统可知，数据的存储方式有三种：连续顺序方式，链接方式，索引方式。矩阵不能直接用在计算机中，应选择顺序

3、存储构造二维数组，存放元素。稀疏矩阵的非0元以矩阵行序为序存储在一维数组中，每一行元素的数目不同，可称为非规则数组。从稀疏矩阵到一维数组是从矩阵构造到以元素次序为主序的逻辑构造变换。稀疏矩阵的一维数组的非0元素是记录(i,j,aij)。稀疏矩阵三元组表的顺序存储方式，称为三元组顺序表，选用一维数组。三元组表还可用链表表示。*这里有两个转换或者两个关系。1.数学表示实体到计算机存储实体的转换。eg.矩阵到一维数组；2.数学逻辑构造到存储逻辑构造的转换。eg.矩阵的行列构造+稀疏矩阵非0元素到一维数组中非0元同行同列+顺序表示的转换。*注释数据构造：三元组顺序表/-稀疏矩阵的三元组表顺序存储表示-

4、/#defineMAXSIZE12500Typedefstructinti,j;/该非0元的行下标row和列下标col/有行下标或列下标一样的三元组ElemTypee;Triple;/三元组元素TypedefstructTripledataMAXSIZE+1;/非0元三元组表，data0未用intmu,nu,tu;/矩阵的行数，列数和非0元个数TSMatrix/三元组表三元组表的顺序以矩阵行序为主序。非0元的三元组是以矩阵行序为主序排列的。这两个表述有区别。三元组表与三元组不同,用三元组元素好似没有必要。3.稀疏矩阵转置运算程序-一维数组存储构造StatustransposeSMatrix(T

5、SMatrixM，TSMatrix&T)/稀疏矩阵从M到T转置T.mu=M.nu;T.nu=M.nu;/矩阵行数列数互换T.tu=M.tu;/转置矩阵非零元个数一样if(T.tu)/矩阵非0元个数不为0q=1;/q=1是行排列数组T.data工作游标for(col=1;col为何q时，Tq=Mp?T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;/q增加,循环返回到p的for循环；当一次遍历M.data数组结束，循环返回col的for循环。/if(T.tu)/TransposeSMatrix稀疏矩阵转置算法4.算法的解释：根据M的列的顺序，在M.data中寻

6、找M的每一列的全部元素，这一列元素正是T的一样行值的全部元素。共有nu次列数循环，每次循环遍历一次M.data。将M.data从M的行排列数组重排到M的列排列数组，这个数组等于T的行排列数组。data以矩阵的行序为主序.为何是M的列序，由于以T的行序为一维数组的主序。比拟M,T之间的差异，可知重排三元组表元素之间的次序可实现矩阵转置。T.data是M.data中元素次序的重排，这个次序的重排不是随意的重排。而是以T的行序为序，T的行序就是M的列序。将T的行序，作为重排M.data中元素的主序。稀疏矩阵的转置算法，对要重排的矩阵数据，是以目的矩阵T的行序(M的列序)做为算法主序。这是编程的出发点

7、。将M同一列的数据有序存放在T的一维数组中。M的列序从1到N，而且M同一列的数据仍然是按从上到下的行序1,m，作为部分离散有序形式，存在在一维数组M.data中，符合T.data按T的行序排列的要求。1)什么是算法主序？目的实体元素求解的顺序。T.data递增序，只要一个方向，称为求解线索方向。求解线索是算法线索集合的一个元素。T.data根据矩阵行排列一维数组的序是矩阵行排列，因而对应已知矩阵M列序。所以M的列序作为算法主序，使M成为驱动数据。2)目的T与已知M的映射关系形的对应：行数，列数，非零元个数。序的对应：行序列序。层次的对应：每一行每一列非0元的个数，每一行每一列第一个非0元的位置

8、。对转置运算而言：T每一行非0元个数与M每一列非0元个数一样。T每一行第一个非0元位置与M每一列第一个非0元位置的关系。T的行序等于M的列序。3)算法的关键是矩阵数据根据谁的序，进行程序处理。根据已知矩阵，还是目的矩阵。根据目的矩阵的序即行序，从矩阵数据M.data中进行选择。矩阵有两个性质：1.层次构造2.顺序，可以为是元素的顺序。这个转置算法用递增序，因而还可从用矩阵层次构造编程。用M矩阵的行序，或者用准确定位见第二节的方法。4矩阵的一维数组可看做mu个行数组。稀疏矩阵的行数组并不规则，一样行的三元组元素的行下标域一样。从相邻的特性可知，根据data1与行元素的个数，可知下一行的第一个元素的位置下标。这与基址存储器与段长存储器的做用一样。注意：用行下标变换的方法，求行数组的边界似乎不优美。