数据结构第11讲 稀疏矩阵与广义表 c.ppt

第5章数组和广义表
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
特殊矩阵
稀疏矩阵
广义表的类型定义
广义表的存储表示和实现
稀疏矩阵
假设 m 行 n 列的矩阵含 t 个非零元素,则称 d= t/(m×n)为稀疏因子,通常认为d≤。
以常规方法,即以二维数组表示高阶的稀疏矩阵时产生的问题:
(1)零值元素占的空间很大
(2)计算中进行了很多和零值的运算
解决问题的原则:
尽可能少存或不存零值元素
尽可能减少没有实际意义的运算
运算方便
即:
尽可能快地找到下标值(i,j)对应的非零值元
尽可能快地找到同一行或同一列的非零值元
抽象数据类型稀疏矩阵的定义:
ADT SparseMatrix {
数据对象:D={ ai,j | i=1,2,…,m;j=1,2,……n;
ai,j∈ElemSet,m和n分别称为矩阵的行数和列数
数据关系:R={Row,Col}
Row = { <ai,j,ai,j+1> | 1≤i≤m,1≤j≤n-1 }
Col = { <ai,j,ai+1,j> | 1≤i≤m-1,1≤j≤n }
基本操作:
} ADT SparseMatrix
稀疏矩阵的表示方法:
(1)顺序存储结构——三元组表示法
(2)行逻辑链接的顺序表
(3)数组的链接存储结构——十字链表表示法
7 0 0 0 15 0
0 -4 0 0 0 0
0 0 0 -1 0 0
-2 0 0 0 0 21
M=
21
6
4
-2
1
4
-1
4
3
-4
2
2
15
5
1
7
1
1
列
行
值

行数mu=4, 列数nu=6, 非零元个数tu=6
0
0
三元组顺序表存储表示
#define MAXSIZE 12500
// 假设非零元个数的最大值为12500
typedef struct {
int i, j; // 该非零元的行下标和列下标
ElemType e;
} Triple;
typedef struct {
Triple data[MAXSIZE + 1];
// 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
} TSMatrix;
如何求转置矩阵?
转置运算是一种简单的矩阵运算。对于一个 m×n 的矩阵 M,它的转置矩阵 T 是个 n×m 的矩阵,且T(i,j) = M(j,i),1≤i≤n,1≤j≤m。
7 0 0 0 15 0
0 -4 0 0 0 0
-2 0 0 0 0 21
0 0 0 -1 0 0
21
6
4
-1
4
3
-4
2
2
15
5
1
7
1
1
-2
1
4
7 0 0 -2
0 -4 0 0
0 0 -1 0
0 0 0 0
15 0 0 0
0 0 0 21
-1
3
4
7
1
1
-2
4
1
-4
2
2
15
1
5
21
4
6
?
M
T
用常规的二维数组表示时的算法
其时间复杂度为: O(mu×nu)
for (col=1; col<=nu; ++col)
for (row=1; row<=mu; ++row)
T[col][row] = M[row][col];