- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Am×n
i行，每行 n个元素
LOC(aij)=LOC(ac1,c2)+[(d2-c2+1)*(i-c1)+(j-c2)]* l
j个元素
◆ 三维数组
A[c1:d1,c2:d2,c3:d3]，求LOC(akij)
◆ n维数组
A[c1:d1，c2:d2，…，ci:di，…，cn:dn]
可以看成由d1-c1+1个行表所组成的线性表，而每个 行表本身又是一个二维数组。 A=( [ ]c1, [ ]c1+1, …, [ ]k-1, [ ]k, …, [ ]d1 )
⎡ a11 ⎢a ⎢ 21 A = ⎢ a31 ⎢ ⎢ M ⎢ ⎣ a n1
a12 a 22 a32 M an 2
a13 a 23 a33 M an 3
L a1n ⎤ L a2 n ⎥ ⎥ L a3 n ⎥ ⎥ M ⎥ L a nn ⎥ ⎦
⎧ i ( i − 1) + j −1 ⎪ ⎪ k =⎨ 2 ⎪ j ( j − 1) + i − 1 ⎪ 2 ⎩
i 1 1 2 4 5 5
j 1 4 2 3 1 2
d 5 4 3 -1 4 2 0 1 2 3 4 5
sa.data[sa.td]
sb->data[sb->td]
算法执行过程示意图
算法： void trantup(TSMatrix sa,TSMatrix *sb) { int p,q,v; sb->md=sa.nd; sb->nd=sa.md; sb->td=sa.td; if(sb->td!=0) { q=0; /*q指示sb->data的下标*/ for(v=1;v<=sa.nd;v++) /*扫描遍数*/ for(p=0;p<sa.td;p++) if(sa.data[p].j==v) { sb->data[q].i=sa.data[p].j; sb->data[q].j=sa.data[p].i; sb->data[q].d=sa.data[p].d; q++; } } }
每个一维数组有 (d2-c2+1)个元素 (i-c1)个 一维数组 aij是第i个一维数组中的 元素，在它之前有j-c2个 元素
以C语言为例：A[m][n] ，求LOC(aij) LOC(aij)=LOC(a00)+( i*n+j)* l
a01 ⎡ a00 ⎢ a a11 10 ⎢ M ⎢ M = ⎢ ai −1, 0 ai −1,1 ⎢ ai 0 ai1 ⎢ M M ⎢a ⎣ m −1,0 am −1,1 L L M L L M L a0, j −1 a0 j a1, j −1 a1 j M M ai −1, j −1 ai −1, j ai , j −1 aij M M am −1, j −1 am −1, j L L M L L M L a0,n −1 ⎤ a1,n −1 ⎥ ⎥ M ⎥ ai −1,n −1 ⎥ ai ,n −1 ⎥ M ⎥ am −1,n −1 ⎥ ⎦
a a
1n
2n
思考：数组中能否进行插入和删除元素的操作？
为什么？
二、数组的运算
初始化 ArrayInitiate(A, n, c1, d1, c2, d2, …, cn, dn) 销毁 ArrayDestroy(A) 存数组元素 Storage(A, j1, j2, …, jn, x) 取数组元素 Get(A, j1, j2, …, jn, x )
可将n2个元压缩到n(n+1)/2个元的一维数组va中。 若以行优先进行存储，则aij在一维数组中的地址为： k=0+(1+2+3+…+(i-1))+j-1 =i(i-1)/2+j-1
i≥j
0 0 L 0⎤ ⎡ a11 ⎢a a22 0 L 0⎥ ⎢ 21 ⎥ M ⎥ A= ⎢ M ⎢ ⎥ ⎢an−1,1 an−1, 2 L an−1, n−1 0 ⎥ ⎢ an1 an 2 L an,n−1 ann ⎥ ⎣ ⎦
LOC(akij)=LOC(ac1,c2 ,c3) +[(d3-c3+1)(d2-c2+1)(k-c1) +(d3-c3+1)(i-c2)+(j-c3)] * l
=LOC(ac1,c2,…,cn) +[
∑
i=1
n−1
( ji − ci )
k =i+1
∏
n
5.3 矩阵的压缩存储
压缩存储：为多个值相同的元只分配一个存储空间；
(dk − ck +1) + ( jn − cn ) ]×l
或者写成：
LOC ( a j1, j 2,L, j n ) = LOC ( a c1, c 2,L,cn ) +
n ⎧ ( d k − ck + 1) 其中 ⎪α i = l k Π = i +1 ⎨ ⎪ ⎩α n = l
∑α ( j
i i =1
a12 a13 a23
当i ≥ j 当i < j
va： a11 a21 a22 a31 k= 0 1 2 3
a32 a33 4 5
…
ann
… n(n+1)/2-1
5.3.2 稀疏矩阵
一、定义
大量矩阵元素的值为0，且分布没有一定规律的矩阵。 例：矩阵M4×6如下：
每个非零元必须用一个三元组（i,j,d）来表示，所有 三元组构成一个线性表。 例：上述的M矩阵，可由下列7个三元组 i j 1 5 4 2 6 1 5 d 3 4 -1 1 2 5 4 以及（4, 6, 7） 作为它的描述。
i
1 1 2 2 3 4
j
1 5 2 5 4 1
d
5 4 3 2 -1 4
i
1 1 2 4 5 5
j
1 4 2 3 1 2
d
5 4 3 -1 4 2
sa.data[sa.td]
sb->data[sb->td]
i p 1 1 2 2 3 4
j 1 5 2 5 4 1
d 5 4 3 2 -1 4 0 1 2 3 4 5 q
例：一个二维数组Amxn 的逻辑状态如下：
⎡ a 11 ⎢ ⎢ a 21 ⎢ M =⎢ ⎢ a i1 ⎢ M ⎢ ⎢ ⎣ a m1
a a a a
12 22
K K M K M K
a a
1j 2j
K K M K M K
Am × n
M
i2
M
a
M
ij
M
m2
a
m⎦
2.求转置矩阵
对于一个m×n的矩阵A，它的转置矩阵B是一个n×m 的矩阵，且满足bij=aji，1≤i≤n，1≤j≤m。 例：
A4×5
⎡5 ⎢0 =⎢ ⎢0 ⎢ ⎣4
0 3 0 0
0 0 0 0 0 −1 0 0
4⎤ 2⎥ ⎥ 0⎥ ⎥ 0⎦
其转置矩阵为: B 5× 4
⎡5 ⎢0 ⎢ = ⎢0 ⎢ ⎢0 ⎢4 ⎣
Chapter 5 数组
5.1 数组的定义和运算 5.2 数组的顺序存储结构 5.3 矩阵的压缩存储
5.3.1 特殊矩阵 5.3.2 稀疏矩阵
5.1 数组的定义和运算
一、定义
数组（Array）是n（n>1）个相同数据类型的数 据元素所构成的有限序列。 数组可看成线性表的推广。从本质上讲，数组是 下标-值偶对的集合，其中每个元素都由一个值和一 组下标组成，记为： A[c1:d1, c2:d2, …, ci:di, …, cn:dn] 每个数据元素都对应一组下标A[j1, j2, …, ji, …, jn] 其中，ci, di分别为每个下标ji的界偶，( i=1, 2, …, n )， ci称下界偶，di称上界偶。
4
算法分析： *空间： 经典（二维数组）：2×m×n 改进（三元组顺序表）：2×(3×td+3)=6(td+1) 只有当 6(td+1) < 2×m×n
*时间： 经典方法：for(col=1;col＜=n;col++) for(row=1;row＜=m;row++) b[col][row]=a[row][col]； 时间为 O(m×n) 反复扫描法：O(sa.nd×sa.td)=O(n×td) 当td→m时，反复扫描法与经典方法相近。 当td→m×n时，反复扫描法时间为O(m×n2)，反 而比经典方法多。所以，此方法只适用于稀疏矩阵， 即 td << m×n时，才可能既节省空间，又不耗费太多 的时间。
0 3 0 0 2
0 0 0 −1 0
4⎤ 0⎥ ⎥ 0⎥ ⎥ 0⎥ 0⎥ ⎦
若说明TSMatrix sa, TSMatrix *sb，分别表示矩阵A和B， 则sa.data，sb->data如下：
转置方法——反复扫描法
思想：对sa.data中三元组的列值进行反复扫描 （共扫描sa.nd遍）。 设二重循环： 外循环：v：1→sa.nd （扫描遍数） 内循环：p：0→sa.td-1 对所有的非零元素进行检查，下标为p的 元素的列值若为v（即sa.data[p].j==v）， 则交换行、列值后顺序存到sb->data中； 否则，不交换，继续检查。
va： a11 k= 0
a21 a22 a31 a32 a33 1 2 3 4 5
…
ann
c
… n(n+1)/2-1
二、对称矩阵
若一个n阶方阵A中的元满足下述性质： aij=aji (1≤i, j≤n)，则称A为n阶对称矩阵。
将n2个元压缩到n(n+1)/2个元的一维数组va中。 若以行优先进行存储，则va[k]与矩阵元aij之间存在着 一一对应关系：
