求解
b .data 4 b .data 5 b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=7 求解步骤分析 的值
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7 Col=3 b . data q b .data 1 b .data 2 b .data 3 i 1 1 2 2 3 3 j 3 6 1 5 1 4 e -3 15 12 18 9 24
注意： 注意：
引用i 引用 , j ,e 时的格 式应为： 式应为： a . data[p] . i a . data[p] . j a . data[p] . e 例如 x=a . data[6] . j 则 x=2
a. mu=6 a. nu=7 a. tu=8
三、实现矩阵的运算:矩阵转置 实现矩阵的运算 矩阵转置
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7 Col=4 b . data q b .data 1 b .data 2 b .data 3 i 1 1 2 2 3 3 4 j 3 6 1 5 1 4 6 e -3 15 12 18 9 24 -7
求解
b .data 4 b .data 5 b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=5,6 求解步骤分析 的值
求解
b .data 4 b .data 5
无!
b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=8 求解步骤分析 的值
求解
b .data 4 b .data 5 b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=3,4 求解步骤分析 的值
的形式如下： 用变量 a 存放矩阵 M 的形式如下：
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7
求解
b .data 4 b .data 5 b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
b. mu=7 b. nu=6 b. tu=8
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=1,2 求解步骤分析 的值
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7 Col=1 b . data q b .data 1 b .data 2 b .data 3 i 1 1 j e 3 -3 6 15
如果矩阵M中的大多数元素均 如果矩阵 中的大多数元素均 为零元素，则称矩阵M为稀疏矩阵 为稀疏矩阵。 为零元素，则称矩阵 为稀疏矩阵。
例如： 例如：
0 0 -3 0 0 15 12 9 0 0 0 0 0 0 0 0 24 0 18 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0
5.3.2 稀疏矩阵的压缩存储 ———三元组表 三元组表
一、什么是稀疏矩阵(sparse matrix) 什么是稀疏矩阵
如果矩阵M中的大多数元素均 如果矩阵 中的大多数元素均 为零元素，则称矩阵M为稀疏矩阵 为稀疏矩阵。 为零元素，则称矩阵 为稀疏矩阵。
一、什么是稀疏矩阵(sparse matrix) 什么是稀疏矩阵
注意： 注意：
为了保存矩阵的行数、 为了保存矩阵的行数、列 数和非零元素个数， 数和非零元素个数，还需 增设三个量： 增设三个量：mu nu tu
mu=6 nu=7 tu=8
3.三元组线性表的数据类型描述 3.三元组线性表的数据类型描述
#define MAXSIZE 12500 typedef struc{ int ElemType }Triple; typedef struc{ Triple data [MAXSIZE+1]; //三元组表，data[0]不用 三元组表， 三元组表 不用 int mu , nu , tu ; }TSMatrix TSMatrix M ； //矩阵的行数、列数、非0元素个数 矩阵的行数、列数、 矩阵的行数 元素个数 //sparseness(稀疏 稀疏) 稀疏 i, j; e; //非零元素个数的最大值 非零元素个数的最大值
1.实例 求矩阵 的转置矩阵 实例:求矩阵 的转置矩阵N: 实例 求矩阵M的转置矩阵
三、实现矩阵的运算:矩阵转置 实现矩阵的运算 矩阵转置
1.实例 求矩阵 的转置矩阵 实例:求矩阵 的转置矩阵N: 实例 求矩阵M的转置矩阵
0 0 -3 0 0 15 12 9 0 0 0 0 0 0 0 0 24 0 18 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 12 9 N= 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 18 0 24 0 0 0 0 0 0 0 14 0 0 0 0 0 15 0 0 -7 0 0 0
3 14
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=8 求解步骤分析 的值
a . data p a .data 1 a .data 2 a .data 3 a 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7 Col=7 b . data q b .data 1 b .data 2 b .data 3 i 1 1 2 2 3 3 4 6 j 3 6 1 5 1 4 6 3 e -3 15 12 18 9 24 -7 14
M=
二、三元组线性表存储结构
1.中心思想：仅存储矩阵中的非零元素 中心思想： 中心思想 用一个三元组（ 用一个三元组（tupel3）存放矩阵中的 ） 一个非零元素的行号、列号及该 一个非零元素的行号、列号及该非零元素 的值。 一个三元组的形式为：（ ：（i 的值。 一个三元组的形式为：（ , j, e） ） 一般情况下， 一般情况下，一个稀疏矩阵中有若干个 非零元素，所以要用一个“三元组线性表” 非零元素，所以要用一个“三元组线性表” 来存放一个稀疏矩阵。 来存放一个稀疏矩阵。
求解
b .data 4 b .data 5 b .data 6 b .data 7 b .data 8
a. mu=6 a. nu=7 a. tu=8
注:p=1..8,寻找 a.data[ p].j==col 寻找
2.求解步骤分析：p=1..8, q的值 求解步骤分析： 的值=7 求解步骤分析 的值
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 Col=6 -3 14 求解 24 18 15 -7 b . data q b .data 1 b .data 2 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8 i 1 1 2 2 3 3 4 6 j 3 6 1 5 1 4 6 e -3 15 12 18 9 24 -7
M=
求解
注意：用变量 和 分别存放矩阵 注意：用变量a和 b分别存放矩阵 M和N (TSMatrix a,b),既要从已 和 既要从已 知变量a来求得变量 的值。 来求得变量b的值 知变量 来求得变量 的值。
也既要完成如下求解工作： 也既要完成如下求解工作：
a . data p a .data 1 a .data 2 a .data 3 a .data 4 a .data 5 a .data 6 a .data 7 a .data 8 i 1 1 3 3 4 5 6 6 j 2 3 1 6 3 2 1 4 e 12 9 -3 14 24 18 15 -7 b . data q b .data 1 b .data 2 b .data 3 i 1 1 2 2 3 3 4 6 j 3 6 1 5 1 4 6 3 e -3 15 12 18 9 24 -7 14