北京邮电大学计算机学院05级数据结构5数组和广义表.pptVIP

数据结构---第五章 数组和广义表 第五章 数组和广义表 5.1 数组和线性表的关系以及数组的运算 5.2 数组的顺序存储结构 5.3 矩阵的压缩存储 5.4 广义表的定义和表示方法 5.5 广义表的存储结构 5.6 广义表的递归算法 本章学习要点、习题与上机作业 5.1 数组和线性表的关系以及数组的运算 任何数组A都可以看作一个线性表 A=(a1, a2, …, ai , …an ) 二维数组m?n时， ai是数组中第i行所有元素，0?i?m-1，表中每一个元素是一个一维数组； 三维数组时， 表中每一个元素是一个二维数组； n维数组时， 表中每一个元素是一个(n-1)维数组 数组与线性表之间的关系 线性表的扩展，其数据元素本身也是线性表 数组的特点 数组中各元素都具有统一的类型 可以认为，d维数组的非边界元素具有d个直接前趋和d个直接后继 数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储 每组有定义的下标都存在一个与其相对应的值 在数组上的基本操作 给定一组下标，取得相应的数据元素值 给定一组下标，修改相应的数据元素值 5.2 数组的顺序存储结构 一维数组 二维数组 a00 a01 a02 ... a0,n-1 a10 a11 a12 ... a1,n-1 : : : : am-1,0 am-1,1 am-1,2 ... am-1,n-1 n维数组 LOC[j1, j2, ..., jn]=c0+c1?j1 +c2?j2 +...+cn?jn =c0+ ci?ji cn=L; ci-1=ci?bi (1i?n) c0=b =LOC[0,0,...,0] 数组是一种随机存取结构:对任一元素定位时间相等. 5.3 矩阵的压缩存储 目的是节省空间。 5.3.1 对称矩阵 [特点] 在n?n的矩阵a中，满足如下性质： aij=aji (1 ? i, j ? n) [存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。 k= i(i-1)/2+j-1 当i?j j(j-1)/2+i-1 当ij 5.3.2 三角矩阵 [特点] 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。 [存储方法] 重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间: sa[0.. n(n+1)/2]。sa[0]=C 上三角矩阵 下三角矩阵 k= (i-1)?(2n-i+2)/2+j-i+1 i?j k= i?(i-1)/2+j i?j 0 ij 0 ij 5.3.3 带状矩阵（对角矩阵） [特点] 在n?n的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 — L对角矩阵。 [存储方法] 只存储带状区内的元素。 1）以对角线的顺序存储,共n*L个元素。 1 2 3 4 5 6 1 8 2 3 0 0 0 2 4 2 0 3 0 0 3 5 7 7 6 8 0 4 0 9 6 9 1 5 5 0 0 6 1 4 2 6 0 0 0 2 8 3 2）只存储带状区内的元素。除首行和末行，按每行 L个元素，共(n-2)L+(L+1)个元素。sa[0..(n-1)L] 存储地址计算： k=(i-1)L+(j-i) 1? i, j ? n |i-j|?(L-1)/2 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0