第五章数组和广义表 数组可以看成是一种特殊的线性表，即线性 表中数据元素本身也是一个线性表 §5.1数组的定义和特点 ★定义 a au) (a21 a22 (… n维数组中含有多 少个数据元素？ ★数组特点 数组结构固定 ?数据元素同构 ★数组运算 冬给定一组下标，存取相应的数据元素 必给定一组下标，修改数据元素的值
第五章 数组和广义表 数组可以看成是一种特殊的线性表，即线性 表中数据元素本身也是一个线性表 §5.1 数组的定义和特点 定义 = m m mn n n m n a a a a a a a a a A ... ... ... ... ... ... ... ... ... ... ... 1 2 21 22 2 11 12 1 数组特点 ❖数组结构固定 ❖数据元素同构 数组运算 ❖给定一组下标，存取相应的数据元素 ❖给定一组下标，修改数据元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) n维数组中含有多 少个数据元素？
§5.2数组的顺序存储结构和实现多维一)一维 ★次 a11 按列序为主序存放 a21 8量■级银■数 m- am1 m a12 11 a12 a22 a21 222 ●●●9●●●。 82n 量：道道。量日业 am2 ●●。。9●9●●e●。●。。●●。。。●o Aml am2… Amn ain a2n Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*I g8。g8年 m*n-】 a
§5.2 数组的顺序存储结构和实现 次序约定 ❖以行序为主序 ❖以列序为主序 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 0 a11 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 多维——〉一维
§5.3矩阵的压缩存储 ★对称矩阵 a11 a12. ●。。0●0 ain 221 a22……8a2n Anl an2 ●●●●●●●● Ann 按行序为主序： alla21a22a31a32 anl ann k=0 1234 n(n-1)/2 n(n+1)/2-1 [ii-1)/2+j-1,i≥j k= j(U-1)/2+i-1,i<j
§5.3 矩阵的压缩存储 − + − − + − = j j i i j i i j i j k ( 1)/ 2 1, ( 1)/ 2 1， 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… a21 a22 0.… ●●●●●●●。●。●●●●●●●。●●●。 0 Anl an2 an3… 8n0 按行序为主序： all a21a22a31a32 anl ann k=0 1234 n(n-1)/2 n(n+1)/2-1 Loc(ai--Loc(a)+KD+-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 按行序为主序：
5.3矩阵的压缩存储 ★稀疏矩阵 冬定义：非零元较零元少，且分布没有一定规律的矩阵 必压缩存储原则：只存矩阵的行列维数和每个非零元的 行列下标及其值 如何进行稀疏矩 0 12 9 阵的压缩存储？ 0 0 0 0 -3 00 0° 014 0 M= 0 024 0 00 0 0 180 0 0 0 0 表示非零元的 1500 -700 0J6x1 三元组 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)唯一确定
15 0 0 7 0 0 0 6 7 0 18 0 0 0 0 0 0 0 24 0 0 0 0 3 0 0 0 0 14 0 0 0 0 0 0 0 0 0 12 9 0 0 0 0 − − M = 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）唯一确定 5.3 矩阵的压缩存储 稀疏矩阵 ❖定义：非零元较零元少，且分布没有一定规律的矩阵 表示非零元的 三元组 ❖压缩存储原则：只存矩阵的行列维数和每个非零元的 行列下标及其值 如何进行稀疏矩 阵的压缩存储？