数据结构讲义第5章-数组与广义表.pptVIP

以行为主序： LOC(aij)=LOC(a00)+(i*n+j)*l 以列为主序： LOC(aij)=LOC(a00)+(j*m+n)*l 一般地，对A[c1..d1,c2..d2] 则：以行为主序有： LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*l 以列为主序： LOC(aij)=LOC(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*l 5.3.1特殊矩阵的压缩存储 1、对称矩阵 （1） 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。 （2）压缩存储方法： 由于对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，则可将n2个元素存储到n(n-1)/2个元素空间中。 不失一般性，以行序为主序存储其下三角的元素。 一般地，设对称矩阵A的下三角部分以行为主序顺序存储到一个向量SA[n(n+1)/2]中，如图所示。 下三角矩阵 与对称矩阵类似，设存入向量：SA[n*(n+1)+1]中，sa[k] 与aij 的对应关系为： 上三角矩阵 设存入向量：SA[n*(n+1)+1]中，sa[k] 与aij 的对应关系为： 5．4 广义表 5．4 广义表 习题五 5.1 假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址时１００，每个整数占４个字节。问下列元素的存储地址是什么。 (1) a0000 (2)a1111 (3)a3125 5.2 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（ (1) ），若该数组按行存放时，元素A[8][5]的起始地址是( (2) ），若该数组按列存放时，元素A[8][5]的起始地址是（ (3) ）。 (1)A. 80 B.100 C.240 D.270 (2)A.SA+141 B.SA+144 C.SA+222 D.SA+225 (3)A.SA+117 B.SA+180 C.SA+222 D.SA+225 5.3求下列广义表的操作结果 GetHead[((a),a)] GetTail[((a),a)] GetTail[GetHead[((a,b),(c,d))]] GetHead[GetHead[((a,b),(c,d))]] * * 5.1 数组的定义和运算 1、n维数组：n维数组是由∏bi个元素组成，每个元素受着n个关系的约束。在每个关系中，元素aj1j2…jn（0≤ji≤bi-2）都有一个后继。故这n 个关系是线性关系。 数组中的所有元素必须属于同一数据类型。每个元素都对应一组下标（j1，j2，…jn），每个下标的范围0≤ji≤bi-1 ， bi称为第i维的长度。 ∏bi为n维数组的长度。 当n=1时，n维数组退化为定长的线性表。 一、数组的概念 以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 Am?n= a00 a01 a0 n-1 a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1 在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1 在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j Am×n= a11 a12 ┅ a1j ┅ a1n a21 a22 ┅ a2j ┅ a2n ┇ ┇ ai1 ai2 ┅ aij ┅ ain ┇ ┇ am1 am2 ┅ amj ┅ amn A=（? 1 ? 2 ┅ ?j ┅ ?n) 我们可以把二维数组看成一个线性表： A=(? 1 ? 2 … ?j … ?n)，其中?j（1≤j ≤n）本身也是一个线性表，称为列向量。 矩