文档介绍：本章要点
数组的类型定义和表示方法
特殊矩阵和稀疏矩阵存储方法
及运算的实现
广义表的结构特点
第五章数组
数组可以看成是一种特殊的线性表,即线性表中数据元素本身也是一个线性表
多维数组组的定义
定义
数组特点
数组结构固定
数据元素同构
数组运算
给定一组下标,存取相应的数据元素
给定一组下标,修改数据元素的值
( )
( )
( )
( )
( )
( )
( )
( )
( )
数组的顺序存储结构
次序约定
以行序为主序
以列序为主序
a11 a12 …….. a1n
a21 a22 …….. a2n
am1 am2 …….. amn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
……..
am2
am1
……….
a2n
……..
a22
a21
a1n
…….
a12
a11
0
1
n-1
m*n-1
n
按列序为主序存放
0
1
m-1
m*n-1
m
amn
……..
a2n
a1n
……….
am2
……..
a22
a12
am1
…….
a21
a11
a11 a12 …….. a1n
a21 a22 …….. a2n
am1 am2 …….. amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
特殊矩阵
对称矩阵
a11 a12 …. …….. a1n
a21 a22 …….. ……. a2n
an1 an2 …….. ann
………………….
a11 a21 a22 a31 a32 an1 ann
…...
…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序:
三角矩阵
a11 0 0 …….. 0
a21 a22 0 …….. 0
an1 an2 an3…….. ann
…………………. 0
Loc(aij)=Loc(a11)+[( +(j-1)]*l
i(i-1)
2
a11 a21 a22 a31 a32 an1 ann
…...
…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序:
对角矩阵
a11 a12 0 ……………. 0
a21 a22 a23 0 …………… 0
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 ……an,n-1 ann.
0 a32 a33 a34 0 ……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
a11 a12 a21 a22 a23 ann-1 ann
…...
…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序:
M由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24),
(5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数(6,7)唯一确定

定义:非零元较零元少,且分布没有一定规律的矩阵
压缩存储原则:只存矩阵的行列维数和每个非零元的行列下标及其值
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表
#define M 20
typedef struct node
{ int i,j;
int v;
} TriTupleNode ;
TriTupleNode ma[M];
三元组表所需存储单元个数为3(t+1)
其中t为非零元个数
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
0 1 2 3 4 5 6 7 8
ma[0].i,ma[0].j,ma[0].v分别存放
矩阵行列维数和非零元个数
行列下标
非零元值
求转置矩阵
问题描述:已知一个稀疏矩阵的三元组表,求该矩阵转置矩阵的三元组表
问题分析
一般矩阵转置算法:
for(col=0;col<n;col++)
for(row=0;row<m;row++)
n[col][row]=m[row][col];
T(n)=O(mn)
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0 1 2 3 4 5 6 7 8
ma
i j v
7 6 8
1 3 -