稀疏矩阵数据结构与算法.doc

稀疏矩阵数据结构与算法
稀疏矩阵的存储结构是三元组表，在运算算法中，用矩阵逻辑结构定位数据处理范围，选择算法主序，发现驱动元素或变量的数据映射范围，根据已知实体与目标实体间的映射关系和输出实体的逻辑结构，选择算法主序，输出结构与输出方法。在源程序分析中发现原子功能模块。说明：本文面对的是有一定计算机软件认识的大学生或者程序设计人员。
HYPERLINK"http://programdesign.baike.com/article-379697.html"\l"1#1"§1转置算法
稀疏矩阵在数据结构中不是重点，但是稀疏矩阵既是数据处理的大范围内，又具有一般程序设计与算法结构的基本特征。大学阶段遇到的科学计算类程序不多，稀疏矩阵运算（转置、乘法）的算法是应掌握的起步阶段HYPERLINK"http://programdesign.baike.com/article-379697.html"喜欢HYPERLINK"http://programdesign.baike.com/article-379697.html"分享

§1转置算法
算法对运算数据关联范围的设置不同，导致稀疏矩阵的转置算法的效率不同。
一．稀疏矩阵转置程序1的分析
1.什么是转置
Mmn-->Tnm，其中aij=bji
(1≤i≤m,1≤j≤n。i,j可看作与M,T无关的表示，也可以看作矩阵M为主动的下标表示方法)，而且aij∈M,bji∈T。
矩阵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的顺序为算法线索？）
转置矩阵的非0元个数相同，T.tu=M.tu
(3)对0元素多的稀疏矩阵的转置而言，与一般矩阵的转置不同。稀疏矩阵的非0元素aij，在程序中用三元组(i,j,aij)表示，i,j表示行数列数。因为不再按照矩阵的结构m行n列转置，不使用二维数组作为存储，所以必须记录每一个非0元素所在行列的位置。在规则的二维数组中，矩阵的行列通过元素的下标识别，元素在矩阵中的位置通过下标得到。因此一般矩阵用二维数组为存储结构。二维数组是物理存储结构的逻辑形式，可称为逻辑存储结构。
2.稀疏矩阵的一维数组存储结构
从操作系统可知，数据的存储方式有三种：连续（顺序）方式，链接方式，索引方式。矩阵不能直接用在计算机中，应选择顺序存储结构二维数组，存放元素。稀疏矩阵的非0元以矩阵行序为序存储在一维数组中，每一行元素的数目不同，可称为非规则数组。
从稀疏矩阵到一维数组是从矩阵结构到以元素次序为主序的逻辑结构变换。稀疏矩阵的一维数组的非0元素是记录(i,j,aij)。稀疏矩阵三元组表的顺序存储方式，称为三元组顺序表，选用一维数组。三元组表还可用链表表示。
****这里有两个转换或者两个关系。1.数学表示实体到计算机存储实体的转换。eg.矩阵到一维数组；2.数学逻辑结构到存储逻辑结构的转换。eg.矩阵的行列结构+稀疏矩阵非0元素到一维数组中非0元同行同列+顺序表示的转换。*****注释
数据结构：三元组顺序表
//----稀疏矩阵的三元组表顺序存储表示----//
#defineMAXSIZE12500
Typedefstruct{
inti,j;//该非0元的行下标row和列下标col
//有行下标或列下标相同的三元组
ElemTypee;
}Triple;//三元组元素

Typedefstruct{
Tripledata[MAXSIZE+1];//非0元三元组表，data[0]未用
intmu,nu,tu;//矩阵的行数，列数和非0元个数
}TSMatrix//三元组表
三元组表的顺序以矩阵行序为主序。非0元的三元组是以矩阵行序为主序排列的。这两个表述有区别。三元组表与三元组不同,用三元组元素好像没有必要。
3.稀疏矩阵转置运算程序-----一维数组存储结构
StatustransposeSMatrix(TSMatrixM，TSMatrix&T)
//稀疏矩阵从M到T转置
{
T.mu=M.nu;T.nu=M.nu;//矩阵行数列数互换
T.tu=M.tu;//转置矩阵非零元个数一样
if(T.tu){//矩阵非0元个数不为0
q=1;//q=1是行排列数组T.data[]工作游标
for(col=1;col<=M.nu;++col)//col是M的列，共循环列数nu次，
并不是整个矩阵次数
for(p=1;