第四章数组 数组可以看成是一种特殊的线性表。即线性表中数 据元素本身也是一个线性表 §4.1数组的定义和特点 ★定义 mxn ( a ★数组特点 今数组结构固定 今数据元素同构 ★数组运算 心给定一组下标,存取相应的数据元素 今给定一组下标,修改数据元素的值
第四章 数组 数组可以看成是一种特殊的线性表，即线性表中数 据元素本身也是一个线性表 §4.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 数组特点 ❖数组结构固定 ❖数据元素同构 数组运算 ❖给定一组下标，存取相应的数据元素 ❖给定一组下标，修改数据元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
§4.2数组的顺序存储结构 ★次 a 今 按列序为主序存放 a 21 m1 a12 a 11a12 a a 22 a21a22 a 2n a 2 a m mn a a 2n 0c(aij)=Loc(a11)+(-1)m+(i-1)1 mn n
§4.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
§4.3矩阵的压缩存储 ★对称矩阵 a11a12 ●。●●0● 21 a 22······a2n n nn 按行序为主序: all a21 a22 a31 a32 ann 234 (n+1)2 kJ(-1)/2+/-1,i2J j(j-1)/2+i-1,i<j
§4.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 按行序为主序：
★三角矩阵 a100 21a 22 0 0 nlan2an3……a nn 按行序为主序 all a21 a22 a31 a32 anI n(n-1)/2n(n+1)2-1 Loc(aij)=Loc(a11+It+g-D)*I
三角矩阵 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 按行序为主序：
★对角矩阵 1a120 a 0 21a a 22a23 0 0a32a33a340 00 1,n-2 -1,n-1am-1,n 00 n,n-1 nn 按行序为主序 all a12 a21 a22 a23 ann-1 ann 34 (n-1)2n(n+1)/2 Loc(ai)=Loc(a1)+2(i-1)+(-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 按行序为主序：