资源描述：
《数据结构-稀疏矩阵的三元组表存储方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、稀疏矩阵的压缩存储———三元组表一、什么是稀疏矩阵(sparsematrix)如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。一般地，当非零元素个数只占矩阵元素总数的25%—30%,或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。012900000000000-3000014000240000018000001500-7000M=例如：一、什么是稀疏矩阵(sparsematrix)如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。用一个三元组（tupel3）存放矩阵中的一个非零元素的行号、列号及该非零元素的值。一个三元组的形式为：（i,j,e）二、三元组线性表存储结
2、构一般情况下，一个稀疏矩阵中有若干个非零元素，所以要用一个“三元组线性表”来存放一个稀疏矩阵。1.中心思想：仅存储矩阵中的非零元素2.用顺序存储结构存放三元组线性表M=原矩阵:存放形式:（按行顺序存放）datapijedata11212data2139data331-3data43614data54324data65218data76115data864-7012900000000000-3000014000240000018000001500-7000mu=6nu=7tu=8注意：为了保存矩阵的行数、列数和非零元素个数，还需增设三个量：munutu3.三元组线性表的数据类型描述#d
3、efineMAXSIZE12500//非零元素个数的最大值typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{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-
4、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,TSMatrixb),即要从
5、已知变量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.dat
6、a11212a.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,寻找j=col的a.data[p]113-316152.求解步骤分析：p=1:8,q的值=3,4a.datapijea.data1112a.data2139a.data331-3a.data43614a.data54324a.da
7、ta6518a.data76115a.data864-7a.mu=6a.nu=7a.tu=8b.dataqijeb.data113-3b.data21615b.data3b.data4b.data5b.data6b.data7b.data8求得22注:p=1:8,寻找j=col的a.data[p]Col=2211225182.求解步骤分析：p=1:8,q的值=5,6a.datapijea.data11212a.data219a.data331-3a.dat
