河北大学：《数据结构》课程教学资源（PPT教案课件讲稿）第五章 数组和广义表

第五章数组和广义表 1教学内容:⊥多维数组 5.2特殊矩阵的压缩存储 5.3稀疏矩阵 5.4广义表 2教学目的:①)理解多维数组的结构特点和在内存中的两种顺序存储方式 (2)理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算 (3)领会稀疏矩阵的压缩方式和简单运算 (4)了解广义表的定义和基本运算 3教学重点:()多维数组的逻辑结构: (2)多维组的两种顺序存储方式,计算给定元素在存储区中的 (3)对称矩阵、三角矩阵的压缩存储方式 4)稀疏矩阵的三元组表表示方法 4,教学难点: 稀疏矩阵的压缩存储表示下的运算的实现 5学时安排:4学时 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 1 第五章 数组和广义表 ⒈教学内容：5.1 多维数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵 5.4 广义表 ⒉教学目的：⑴理解多维数组的结构特点和在内存中的两种顺序存储方式； ⑵理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算； ⑶领会稀疏矩阵的压缩方式和简单运算； ⑷了解广义表的定义和基本运算。 ⒊教学重点：⑴多维数组的逻辑结构； ⑵多维组的两种顺序存储方式，计算给定元素在存储区中的地址； ⑶对称矩阵、三角矩阵的压缩存储方式； ⑷稀疏矩阵的三元组表表示方法。 ⒋教学难点： 稀疏矩阵的压缩存储表示下的运算的实现 ⒌学时安排：4学时

5.1多维数组 ◆数组的逻辑结构 ◆数组的内存映象 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 2 5.1 多维数组 数组的逻辑结构 数组的内存映象

5.1.1数组的逻辑结构 ◆数组是我们熟悉的一种数据结构,可以看作线性表的 推广。数组作为一种数据结构其特点是结构中的元素本 身可以是具有某种结构的数据,但属于同一数据类型, 比如:一维数组可以看作一个线性表,二维数组可以看 作“数据元素是一维数组”的一维数组,三维数组可以 看作“数据元素是二维数组”的一维数组,依此类推。 m行n列的二维数组 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 3 5.1.1 数组的逻辑结构 数组是我们熟悉的一种数据结构，可以看作线性表的 推广。数组作为一种数据结构其特点是结构中的元素本 身可以是具有某种结构的数据，但属于同一数据类型， 比如：一维数组可以看作一个线性表，二维数组可以看 作“数据元素是一维数组”的一维数组，三维数组可以 看作“数据元素是二维数组”的一维数组，依此类推

数组是一个具有固定格式和数量的数据有序集,每一个 数据元素有唯一的一组下标来标识,因此,在数组上不能 做插入、删除数据元素的操作。通常在各种高级语言中数 组一旦被定义,每一维的大小及上下界都不能改变。在数 组中通常做下面两种操作: (1)取值操作:给定一组下标,读其对应的数据元素。 2)赋值操作:给定一组下标,存储或修改与其相对应 的数据元素。 我们着重研究二维和三维数组,因为它们的应用是广泛 的,尤其是二维数组 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 4 数组是一个具有固定格式和数量的数据有序集，每一个 数据元素有唯一的一组下标来标识，因此，在数组上不能 做插入、删除数据元素的操作。通常在各种高级语言中数 组一旦被定义，每一维的大小及上下界都不能改变。在数 组中通常做下面两种操作： (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应 的数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛 的，尤其是二维数组

5.1.2数组的内存映象 ◆通常,数组在内存被映象为向量,即用向量作为数组 的一种存储结构,这是因为内存的地址空间是一维的, 数组的行列固定后,通过一个映象函数,则可根据数组 元素的下标得到它的存储地址。 ◆对于一维数组按下标顺序分配即可。 ◆对多维数组分配时,要把它的元素映象存储在一维存 储器中,一般有两种存储方式:一是以行为主序(或先 行后列)的顺序存放,如 BASIC、 PASCAL、 COBOL、C等 程序设计语言中用的是以行为主的顺序分配,即一行分 配完了接着分配下一行。另一种是以列为主序(先列后 行)的顺序存放,如 FORTRAN语言中,用的是以列为主 序的分配顺序,即一列一列地分配。 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 5 5.1.2 数组的内存映象 通常，数组在内存被映象为向量，即用向量作为数组 的一种存储结构，这是因为内存的地址空间是一维的， 数组的行列固定后，通过一个映象函数，则可根据数组 元素的下标得到它的存储地址。 对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存 储器中，一般有两种存储方式：一是以行为主序（或先 行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等 程序设计语言中用的是以行为主的顺序分配，即一行分 配完了接着分配下一行。另一种是以列为主序（先列后 行）的顺序存放，如FORTRAN语言中，用的是以列为主 序的分配顺序，即一列一列地分配

以行为主序的分配规律是:最右边的下标先变化, 即最右下标从小到大,循环一遍后,右边第二个下标 再变,…,从右向左,最后是左下标。以列为主序分 配的规律恰好相反:最左边的下标先变化,即最左下 标从小到大,循环一遍后,左边第二个下标再变, 从左向右,最后是右下标。 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 6 以行为主序的分配规律是：最右边的下标先变化， 即最右下标从小到大，循环一遍后，右边第二个下标 再变，…，从右向左，最后是左下标。以列为主序分 配的规律恰好相反：最左边的下标先变化，即最左下 标从小到大，循环一遍后，左边第二个下标再变，… ，从左向右，最后是右下标

例如一个2×3二维数组,逻辑结构可以用左图表 中示。以行为主序的内存映象如右图(a)所示。分配 顺序为:a1,a12,a13,a21,a2,a23;以列为主序 的分配顺序为:a1,a21,a12,a2,a3,a23;它 的内存映象如右图(b)所示 a a a12 a21 l1 a12 a13 a12 21 av a a 2×3数组的逻辑状态 (a)以行为主序(b)以列为主序 2×3数组的物理状态 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 7 例如一个2×3二维数组，逻辑结构可以用左图表 示。以行为主序的内存映象如右图（a）所示。 分配 顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列为主序 的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它 的内存映象如右图（b）所示

设有m×n二维数组Amn,下面我们看按元素的下标求其 平地址的计算: 以“以行为主序”的分配为例:设数组的基址为 LOC(a1),每个数组元素占据个地址单元,那么a1的物理 地址可用一线性寻址函数计算 LOC(a1)=LOC(a1)+(-1)*n+y-1) 在C语言中,数组中每一维的下界定义为0,则 loc(ai=loc(aoo)+(i'n+j*I 推广到一般的二维数组:A[c1d][c2.d2l,则a;的物理地 址计算函数为: LOC(a)LOC(a1a2)+(-c)*(d2-c2+1)+(-c2) 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 8 设有m×n二维数组Amn，下面我们看按元素的下标求其 地址的计算： 以“以 行为 主序” 的分 配为 例：设 数组 的基 址为 LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理 地址可用一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推广到一般的二维数组：A[c1 ..d1 ] [c2 ..d2 ]，则aij的物理地 址计算函数为： LOC(aij)=LOC(a c1 c2 )+( (i- c1 ) *( d2 - c2 + 1)+ (j- c2 ) )*l

同理对于三维数组Amn,即 mXnXp数组,对于数组元 素a其物理地址为: LOC(aik=loc(a+((i-1)*n*p+(j-1*p+k-1)* 推广到一般的三维数组:A[1d[e2d】[e3d3],则a水k 的物理地址为: LOC(1)=LOC(ac1c2e3)+((i-c1)*(d2-C2+1)*(d3-c3+ 1)+(j-c2)*(d3-C3+1)+(k-c3) 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 9 同理对于三维数组Amnp，即m×n×p数组，对于数组元 素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推广到一般的三维数组：A[c1 ..d1 ] [c2 ..d2 ] [c3 ..d3 ]，则aijk 的物理地址为： LOC(i,j)=LOC(a c1 c2 c3 )+( (i- c1 ) *( d2 - c2 + 1)* (d3 - c3 + 1)+ (j- c2 ) *( d3 - c3 + 1)+(k- c3 ))*l

三维数组的逻辑结构和以行为主序的分配示意图如 图所示。 三维x 2 a131 4 a14 all al a2 ayl 24 续放示能图 a (a)一个3·42的三统放组的恩轻啪构 b)以行为主序的三致内存核象 2021年1月21日 数据结构讲义 10

2021年1月21日 数据结构讲义 10 •三维数组的逻辑结构和以行为主序的分配示意图如 图所示