数据结构-稀疏矩阵的三元组表存储方法.ppt

稀疏矩阵的压缩存储三元组表,一、什么是稀疏矩阵(sparsematrix),如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。一般地，当非零元素个数只占矩阵元素总数的25%30%,或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。,012900000000000-3000014000240000018000001500-7000,M=,例如：,一、什么是稀疏矩阵(sparsematrix),如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。,用一个三元组（tupel3）存放矩阵中的一个非零元素的行号、列号及该非零元素的值。一个三元组的形式为：（i,j,e）,二、三元组线性表存储结构,一般情况下，一个稀疏矩阵中有若干个非零元素，所以要用一个“三元组线性表”来存放一个稀疏矩阵。,1.中心思想：仅存储矩阵中的非零元素,2.用顺序存储结构存放三元组线性表,M=,原矩阵:,存放形式:（按行顺序存放）,datapijedata11212data2139data331-3data43614data54324data65218data76115data864-7,012900000000000-3000014000240000018000001500-7000,mu=6nu=7tu=8,注意：为了保存矩阵的行数、列数和非零元素个数，还需增设三个量：munutu,3.三元组线性表的数据类型描述,#defineMAXSIZE12500/非零元素个数的最大值typedefstructinti,j;ElemTypee;Triple;,typedefstructTripledataMAXSIZE+1;/三元组表，data0不用intmu,nu,tu;/矩阵的行数、列数、非0元素个数TSMatrix/sparseness(稀疏),TSMatrixM；,用变量a存放矩阵M的形式如下：,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,注意：引用i,j,e时的格式应为：a.datap.ia.datap.ja.datap.e例如x=adata6.j则x=2,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,012900000000000-3000014000240000018000001500-7000,M=,00-3001512000180900240000000-70000000014000000000,N=,求解,注意:用变量a和b分别存放矩阵M和N(TSMatrixa,TSMatrixb),即要从已知变量a来求得变量b的值。,也既要完成如下求解工作：,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314b.mu=7b.nu=6b.tu=8,求解,2.求解步骤分析：p=1:8,q的值=1,2,a.datapijea.data11212a.data2139a.data33-3a.data43614a.data54324a.data65218a.data7615a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data1b.data2b.data3b.data4b.data5b.data6b.data7b.data8,求得,1,Col=1,注:p=1:8,寻找j=col的a.datap,1,13-3,1615,2.求解步骤分析：p=1:8,q的值=3,4,a.datapijea.data1112a.data2139a.data331-3a.data43614a.data54324a.data6518a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data3b.data4b.data5b.data6b.data7b.data8,求得,2,2,注:p=1:8,寻找j=col的a.datap,Col=2,2112,2518,2.求解步骤分析：p=1:8,q的值=5,6,a.datapijea.data11212a.data219a.data331-3a.data43614a.data5424a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5b.data6b.data7b.data8,求得,3,3,Col=3,注:p=1:8,寻找j=col的a.datap,319,3424,2.求解步骤分析：p=1:8,q的值=7,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data86-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data7b.data8,求得,Col=4,注:p=1:8,寻找j=col的a.datap,4,46-7,2.求解步骤分析：p=1:8,q的值=7,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data8,求得,Col=5,注:p=1:8,寻找j=col的a.datap,无!,2.求解步骤分析：p=1:8,q的值=8,a.datapijea.data11212a.data2139a.data331-3a.data4314a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data8,求得,Col=6,注:p=1:8,寻找j=col的a.datap,6,6314,2.求解步骤分析：p=1:8,q的值=8,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314,求得,Col=7,注:p=1:8,寻找j=col的a.datap,无!,2.求解步骤分析：,a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8,b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314,求得,b.Mu=7b.nu=6b.tu=8,3.算法描述,statusTransposeSMatrix(TSMatrixa,TSMatrix*b)(*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;if(*b).tu)q=1;for(col=1;col=a.nu;+col)for(p=1;p=a.