5.2数组的顺序表示和实现 >按行序为主序存放 a00 a01 第1行 800 a01 a0,n-1 30.n-1 810 811 ai.n-1 a10 an ●0● 第2行 2m-1,0 am-1,1 … m-1,n-1 a1,1 ●年e L0c(aj)=L0c(ao)+(? )XL am-10 am-11 第n行 。◆· a m-1,n-1 -11 1945
— 11 — 5.2 数组的顺序表示和实现 按行序为主序存放 Loc( aij )= Loc( a00 ) + ( i×n + j )× L a00 a01 … a0,n-1 a10 a11 … a1,n-1 … am-1,0 am-1,1 … am-1,n-1 ? a00 a01 … a0,n-1 a10 a11 … a1,n-1 … … …… am-1,0 am-1,1 … am-1,n-1 第1行 第2行 第n行 a00 a01 … a0,n-1 a10 a11 … a1,n-1 … am-1,0 am-1,1 … am-1,n-1
5.2数组的顺序表示和实现 例：假设有二维数组AM,N,设A[0,0在644处， A[2,2]在676处。每个元素占一个存储空间， 则A[4,5的地址为多少？以行序为主序存储。 .L0c(2,2)=L0c(0,0)+2*n+2 =644+2*n+2=676. .n=(676-2-644)/2=15 .0c(4,5)=L0c(0,0)+4*15+5 =644+60+5=709. -12- 145
— 12 — 5.2 数组的顺序表示和实现 例：假设有二维数组A[M,N]，设A[0,0]在644处， A[2,2] 在676处。每个元素占一个存储空间， 则A[4,5]的地址为多少？以行序为主序存储。 ∵ Loc( 2, 2 ) = Loc( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc( 4, 5 ) = Loc( 0, 0 ) + 4 * 15 + 5 = 644 + 60 + 5 = 709
5.2 数组的顺序表示和实现 例：设有二维数组A[10,20],其每个元素占两个字 节，A[0][0]存储地址为100，若按行优先顺 序存储，则元素A[6,6的存储地址为352 按列优先顺序存储，元素A[6,61的存储地址 为232 100+(6*20+6)*2=352 100+(6*10+6)*2=232 -13- 145
— 13 — 5.2 数组的顺序表示和实现 例：设有二维数组A[10,20]，其每个元素占两个字 节， A[0][0]存储地址为100，若按行优先顺 序存储，则元素A[6,6]的存储地址为 ， 按列优先顺序存储，元素A[6,6]的存储地址 为 。 352 232 100+(6*20+6)*2=352 100+(6*10+6)*2=232
目录页 Contents Page 数组的定义 第五章数组 数组的顺序表示和实现 和广义表 矩阵的压缩存储 广义表的定义 广义表的存储结构 -14 1945
— 14 — — 14 — Contents Page 目录页 数组的顺序表示和实现 数组的定义 广义表的定义 广义表的存储结构 矩阵的压缩存储
5.3矩阵的压缩存储 在某些矩阵中，往往会出现许多值相同的元素或 零元素，为了节省存储空间，可对这类矩阵进行压 缩存储。压缩存储的原则是：对多个值相同的元素 只分配一个存储空间，对零元不分配空间。 我们把相同的元素或零元素在矩阵中的有一定的 规律分布称为特殊矩阵，如果矩阵中零元素占绝大 部分的称为稀疏矩阵。 -15- 1945
— 15 — 5.3 矩阵的压缩存储 在某些矩阵中，往往会出现许多值相同的元素或 零元素，为了节省存储空间，可对这类矩阵进行压 缩存储。压缩存储的原则是：对多个值相同的元素 只分配一个存储空间，对零元不分配空间。 我们把相同的元素或零元素在矩阵中的有一定的 规律分布称为特殊矩阵，如果矩阵中零元素占绝大 部分的称为稀疏矩阵