第五章数组和广义表报告.ppt

第5章数组和广义表 数组和广义表：一种特殊的线性表 元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。 所有数据元素仍属同一数据类型 数组是一种常见的数据类型，几乎所有的程序设计语言都把数组设为固有类型。 本章从数据结构的角度讨论数组的定义和实现，使读者加深对数组类型的理解。 5.1 数组的定义 数组可以看做由一组名字相同、下标不同的变量构成的数据结构 ①数组中各元素具有统一的类型 ②数组元素的下标一般具有固定的上界和下界 ③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作 一维数组的特点：1个下标，ai 是ai+1的直接前驱 二维数组的特点：2个下标，每个元素aij受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组 N维数组的特点： n个下标，每个元素受到n个关系约束:一个n维数组可以看成是由若干个n－1维数组组成的线性表 5.2 数组的顺序存储表示和实现 多维数组的内存映像 事先约定按某种次序将数组元素排成一个序列，然后将这个线性序列存入存储器中。 例如：在二维数组中，既可以规定按行优先存储，也可以规定按列优先存储 若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式； BASIC、C和PASCAL采用行优先顺序；FORTRAN采用列优先 假设有二维数组A6*8 ，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）数组A的存储大小； （2）数组A的最后一个元素a57的第一个字节的地址； （3）按行存储时，元素a14的第一个字节的地址； （4）按列存储时，元素a47的第一个字节的地址； 5.3 矩阵的压缩存储 科学与工程计算问题中，将一个矩阵描述为一个二维数组 高阶矩阵中非零元素呈某种规律分布（特殊矩阵）或者矩阵中出现大量的零元素（稀疏矩阵）的情况下，会造成存储空间极大的浪费 为了节省空间，可以对这些矩阵进行压缩存储： 为多个相同的非零元素只分配一个存储空间 对零元素不分配空间 5.3.1特殊矩阵 对称矩阵 n阶方阵A中，aij=aji （0≦i, j≦n-1） 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素 一般按“行优先顺序”存储主对角线（包括对角线）以下的元素（ n(n+1)/2个） 将这些元素存放在一个向量S[n(n+1)/2] aij与其存储位置S[k]之间存在着对应关系： 三角矩阵 略 对角矩阵 略 5.3.2 稀疏矩阵 m*n的矩阵A中，有t个非零元素。令 e=t/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵 由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置 稀疏矩阵可由表示非零元的三元组(i,j,aij)及其行列数唯一确定 稀疏矩阵压缩存储的缺点：将失去随机存取功能 三元组顺序表 以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元组顺序表 解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序 算法1描述：P99 算法5.1 ** 算法1分析：T(n)=O(M的列数n*非零元个数t) 若 t 与m*n同数量级，则 算法2：快速转置，设两个辅助数组 算法2描述：P100 算法5.2 ** 算法分析：T(n)=O(M的列数n+非零元个数t)，若 t 与m*n同数量级，则T(n)=O(m*n) 5.4 广义表的定义 在广义表中约定： 第一个元素称为表头，而其余元素组成的表称为表尾； 用小写字母表示原子类型，用大写字母表示列表 广义表中元素既可以是单个元素(原子)，也可以是列表(子表)；每个元素都为原子且类型相同时，就是线性表 一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表 广义表的特性 有序性 一个直接前驱和一个直接后继 有长度 ＝表中元素个数 有深度 ＝表中括号的重数 可共享 可以为其他广义表所共享 可递归 自己可以作为自己的子表 ADT GList (P107-108) 5.5 广义表的存储结构 广义表的元素可以是不同结构（原子或列表），通常用链式结构，每个元素用一个结点表示 结点可能有两种形式 原子结点：表示原子，可设2个域或3个域，依习惯而选(标志域、值域、表尾指针) 表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针 1、假设按照行优先的方式进行存储整数数组A9*5，第一个元素的起始地址是100，每个整数占4个字节，求a32与a84的存储地址。