(10)稀疏矩阵的三元组表存储方法

5.3.2稀疏矩阵的压缩存储———三元组表一、什么是稀疏矩阵(sparsematrix)如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。012900000000000-3000014000240000018000001500-7000M=例如：一、什么是稀疏矩阵(sparsematrix)如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。用一个三元组（tupel3）存放矩阵中的一个非零元素的行号、列号及该非零元素的值。一个三元组的形式为：（i,j,e）二、三元组线性表存储结构一般情况下，一个稀疏矩阵中有若干个非零元素，所以要用一个“三元组线性表”来存放一个稀疏矩阵。1.中心思想：仅存储矩阵中的非零元素2.用顺序存储结构存放三元组线性表M=原矩阵:存放形式:（按行顺序存放）datapijedata11212data2139data331-3data43614data54324data65218data76115data864-7012900000000000-3000014000240000018000001500-7000mu=6nu=7tu=8注意：为了保存矩阵的行数、列数和非零元素个数，还需增设三个量：munutu3.三元组线性表的数据类型描述#defineMAXSIZE12500//非零元素个数的最大值typedefstruc{inti,j;ElemTypee;}Triple;typedefstruc{Tripledata[MAXSIZE+1];//三元组表，data[0]不用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.data[p].ia.data[p].ja.data[p].e例如x=a.data[6].j则x=2三、实现矩阵的运算:矩阵转置1.实例:求矩阵M的转置矩阵N:三、实现矩阵的运算:矩阵转置1.实例:求矩阵M的转置矩阵N:012900000000000-3000014000240000018000001500-7000M=00-3001512000180900240000000-70000000014000000000N=注意：用变量a和b分别存放矩阵M和N(TSMatrixa,b),既要从已知变量a来求得变量b的值。求解也既要完成如下求解工作：a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314b.mu=7b.nu=6b.tu=8求解2.求解步骤分析：p=1..8,q的值=1,2a.datapijea.data11212a.data2139a.data33-3a.data43614a.data54324a.data65218a.data7615a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data1b.data2b.data3b.data4b.data5b.data6b.data7b.data8求解1Col=1注:p=1..8,寻找a.data[p].j==col113-316152.求解步骤分析：p=1..8,q的值=3,4a.datapijea.data1112a.data2139a.data331-3a.data43614a.data54324a.data6518a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data3b.data4b.data5b.data6b.data7b.data8求解22注:p=1..8,寻找a.data[p].j==colCol=2211225182.求解步骤分析：p=1..8,q的值=5,6a.datapijea.data11212a.data219a.data331-3a.data43614a.data5424a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5b.data6b.data7b.data8求解33Col=3注:p=1..8,寻找a.data[p].j==col31934242.求解步骤分析：p=1..8,q的值=7a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data86-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data7b.data8求解Col=4注:p=1..8,寻找a.data[p].j==col446-72.求解步骤分析：p=1..8,q的值=7a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data8求解Col=5注:p=1..8,寻找a.data[p].j==col无!2.求解步骤分析：p=1..8,q的值=8a.datapijea.data11212a.data2139a.data331-3a.data4314a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data8求解Col=6注:p=1..8,寻找a.data[p].j==col663142.求解步骤分析：p=1..8,q的值=8a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314求解Col=7注:p=1..8,寻找a.data[p].j==col无!2.求解步骤分析：a.datapijea.data11212a.data2139a.data331-3a.data43614a.data54324a.data65218a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data32112b.data42518b.data5319b.data63424b.data746-7b.data86314求得b.mu=7b.nu=6b.tu=83.算法描述statusTransposeSMatrix(TSMatrixa,TSMatrixb){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.tu;++p)if(a.data[p].j==col){b.data[q].i:=a.data[p].j;b.data[q].j:=a.data[p].i;b.data[q].e:=a.data[p].e;++q;}returnOK;}//TransposeSMatrix四、实现矩阵的运算:矩阵相乘1.实例:求矩阵Q=M×NM=30050-1002000N=0210-2400Q=06-1004传统算法计算Q[i,j]的计算公式为：Q[i,j]=∑(M[i,k]×N[k,j])三元组表的计算过程分析：ije11314522-1312M.dataije12221131-2324N.dataije12621-1324Q.data×＝在经典算法中，无论M[i,k]和N[k,j]的值是否为0都要进行一次乘法运算；但此处只要考虑M.data和N.data中相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）的e值相乘即可得到结果矩阵中的一个三元组的e值，且该三元组的i值和j值分别取这两个相应的三元组的i值和j值。K=1m四、实现矩阵的运算:矩阵相乘1.实例:求矩阵Q=M×NM=30050-1002000N=30405260Q=06-1004传统算法计算Q[i,j]的计算公式为：三元组表的计算过程分析：ije11314522-1312M.dataije12221131-2324N.dataije12621-1324Q.data×＝Q[i,j]=∑(M[i,k]×N[k,j])K=1m在经典算法中，无论M[i,k]和N[k,j]的值是否为0都要进行一次乘法运算；但此处只要考虑M.data和N.data中相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）的e值相乘即可得到结果矩阵中的一个三元组的e值，且该三元组的i值和j值分别取这两个相应的三元组的i值和j值。四、实现矩阵的运算:矩阵相乘1.实例:求矩阵Q=M×NM=30050-1002000N=30405260Q=06-1004传统算法计算Q[i,j]的计算公式为：三元组表的计算过程分析：ije11314522-1312M.dataije12221131-2324N.dataije12621-1324Q.data×＝Q[i,j]=∑(M[i,k]×N[k,j])K=1m在经典算法中，无论M[i,k]和N[k,j]的值是否为0都要进行一次乘法运算；但此处只要考虑M.data和N.data中相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）的e值相乘即可得到结果矩阵中的一个三元组的e值，且该三元组的i值和j值分别取这两个相应的三元组的i值和j值。四、实现矩阵的运算:矩阵相乘1.实例:求矩阵Q=M×NM=30050-1002000N=30405260Q=06-1004传统算法计算Q[i,j]的计算公式为：三元组表的计算过程分析：ije11314522-1312M.dataije12221131-2324N.dataije12621-1324Q.data×＝Q[i,j]=∑(M[i,k]×N[k,j])K=1m在经典算法中，无论M[i,k]和N[k,j]的值是否为0都要进行一次乘法运算；但此处只要考虑M.data和N.data中相应的各对元素（即M.data中的j值和N.data中的