第五章数组和广义表
第五章 数组和广义表
5.1数组的定义 52数组的顺序表示和实现 53矩阵的压缩存储
5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储
0一维数组具有线性表的结构,但操作简单,一般不 进行插入和删除操作,只定义给定下标读取元素和 修改元素的操作 0二维数组中,每个数据元素对应一对数组下标,在 行方向上和列方向上都存在一个线性关系,即存在 两个前驱(前件)和两个后继(后件)。也可看作 是以线性表为数据元素的线性表 n维数组中,每个数据元素对应n个下标,受n个关 系的制约,其中任一个关系都是线性关系。可看作 是数据元素为n-1维数组的一维数组。 0因此,多维数组和广义表是对线性表的扩展:线性 表中的数据元素本身又是一个多层次的线性表
一维数组具有线性表的结构，但操作简单，一般不 进行插入和删除操作，只定义给定下标读取元素和 修改元素的操作 二维数组中，每个数据元素对应一对数组下标，在 行方向上和列方向上都存在一个线性关系，即存在 两个前驱（前件）和两个后继（后件）。也可看作 是以线性表为数据元素的线性表。 n维数组中，每个数据元素对应n个下标，受n个关 系的制约，其中任一个关系都是线性关系。可看作 是数据元素为n-1维数组的一维数组。 因此，多维数组和广义表是对线性表的扩展：线性 表中的数据元素本身又是一个多层次的线性表
对于多维数组,有两种存储方式: 是以行为主序(或先行后列)的顺序存放,如 BASIC、 PASCAL、C等程序设计语言中用的是以行为 主的顺序分配,即一行分配完了接着分配下一行。 另一种是以列为主序(先列后行)的顺序存放, 如 FORTRAN语言中,用的是以列为主序的分配顺序 即一列一列地分配。 不论按何种方式存储,只要确定了数组的首地址以 及每个数组元素所占用的单元数,就可以将数组元素的 存储地址表示为其下标的线性函数。设有m×n二维数组 mn 以“以行为主序”的分配为例,按照元素的下标确 定其地址的计算方法如下
对于多维数组，有两种存储方式： 一是以行为主序（或先行后列）的顺序存放，如 BASIC、PASCAL、C等程序设计语言中用的是以行为 主的顺序分配，即一行分配完了接着分配下一行。 另一种是以列为主序（先列后行）的顺序存放， 如FORTRAN语言中，用的是以列为主序的分配顺序， 即一列一列地分配。 不论按何种方式存储，只要确定了数组的首地址以 及每个数组元素所占用的单元数，就可以将数组元素的 存储地址表示为其下标的线性函数。设有m×n二维数组 Amn，以“以行为主序”的分配为例，按照元素的下标确 定其地址的计算方法如下
设数组的基址为LOC(a1),每个数组元素占据L个地 址单元,计算a:的物理地址的函数为: LOC(ai)=LOC(a1)+((-1)*n+j-1)*L 同理,对于三维数组A-n,即m×n×p数组,对于数 组元素a1其物理地址为: LOC(aik=loc(a1+((i-1)*n*p+g-1)*p+k-1))L 注意: 在C语言中,数组中每一维的下界定义为0,则 LOC(aii=LOC(aoo)+(i*n+j)*L
设数组的基址为LOC(a11)，每个数组元素占据L个地 址单元，计算aij的物理地址的函数为： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L 同理，对于三维数组Amnp，即m×n×p数组，对于数 组元素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L 注意： 在C语言中，数组中每一维的下界定 义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * L