数据结构(第5章)ppt课件.ppt

《数据结构(第5章)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、结构数组的内存映象9/16/20212数据结构讲义5.1.1数组的逻辑结构数组是我们熟悉的一种数据结构，可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。9/16/20213数据结构讲义数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及

3、上下界都不能改变。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。9/16/20214数据结构讲义5.1.2数组的内存映象通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。对于一维数组按下标顺序分配即可。对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为

4、主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。9/16/20215数据结构讲义以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。9/16/20216数据结

5、构讲义例如一个2×3二维数组，逻辑结构可以用左图表示。以行为主序的内存映象如右图（a）所示。分配顺序为：a11，a12，a13，a21，a22，a23；以列为主序的分配顺序为：a11，a21，a12，a22，a13，a23；它的内存映象如右图（b）所示。9/16/20217数据结构讲义设有m×n二维数组Amn，下面我们看按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*l在C语言中，数组中

6、每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*l推广到一般的二维数组：A[c1..d1][c2..d2]，则aij的物理地址计算函数为：LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2))*l9/16/20218数据结构讲义同理对于三维数组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(

7、i,j)=LOC(ac1c2c3)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*l9/16/20219数据结构讲义三维数组的逻辑结构和以行为主序的分配示意图如图所示。9/16/202110数据结构讲义例5.1若矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。9/16

8、/202111数据结构讲