数据结构(严蔚敏)C语言版课件第5章

2020年2月11日2时26分第1页第五章数组和广义表2020年2月11日2时26分第2页【课前思考】1.在你的认识中，数组是什么？在学习了C语言之后，同学们可能会误认为“数组”是一组地址连续的内存，数组也是一种线性的数据结构，它可以看成是线性表的一种扩充。2.为什么顺序表以及其它线性结构的顺序存储结构都可以用一维数组来描述？因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。2020年2月11日2时26分第3页【学习目标】1.理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法。2.掌握特殊矩阵的存储压缩表示方法。3.理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。2020年2月11日2时26分第4页【重点和难点】本章重点是学习数组类型的定义及其存储表示。【知识点】数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。广义表的类型定义、广义表的存储表示、广义表操作的实现。2020年2月11日2时26分第5页【学习指南】从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前几章讨论的线性结构的顺序存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。但由于广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固。本章算法设计题，完成5.21，5.23。2020年2月11日2时26分第6页5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的存储结构5.6广义表操作的递归函数2020年2月11日2时26分第7页一、数组的概念1．一维数组一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。2．二维数组二维数组可以看成是向量的推广。5.1数组的定义2020年2月11日2时26分第8页例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由n个列向量A=[α1,α2,……,αn]组成，其中αi=(a1i,a2i,…..,ami)，0≤i≤n（图5.2）；也可以将二维数组A看成是由m个行向量B=[β1，β2，…，βm]T组成，其中，βi=(ai1,ai2,….,ain)，0≤i≤m（图5.3）。图5.1Am×n的二维数组2020年2月11日2时26分第9页图5.2矩阵Am×n看成n个列向量的线性表2020年2月11日2时26分第10页图5.3矩阵Am×n看成m个行向量的线性表由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。2020年2月11日2时26分第11页以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。例如二维数组A3×4，它有3行、4列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：(1）获得特定位置的元素值；(2）修改特定位置的元素值。3．多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。2020年2月11日2时26分第12页数组的抽象类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{aj1,...ji,...jn,aj1,...ji+1,...jn|0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:2020年2月11日2时26分第13页二维数组的定义:数据对象:D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={ai,j,ai+1,j|0≤i≤b1-2,0≤j≤b2-1}COL={ai,j,ai,j+1|0≤i≤b1-1,0≤j≤b2-2}2020年2月11日2时26分第14页基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)2020年2月11日2时26分第15页InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK2020年2月11日2时26分第16页DestroyArray(&A)操作结果：销毁数组A。2020年2月11日2时26分第17页Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。2020年2月11日2时26分第18页Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。2020年2月11日2时26分第19页5.2数组的顺序表示和实现由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。怎样将多维数组中元素存入到计算机内存中呢？由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。2020年2月11日2时26分第20页一、行优先顺序1．存放规则行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如下形式存放到内存：a00，a01,…a0n-1，a10，a11，...，a1n-1，…，am-10，am-11，…，am-1n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和PASCAL语言都是以行序为主；另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主显然。2020年2月11日2时26分第21页因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。2．地址计算由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其它元素的内存地址？我们可以将它们的地址排列看成是一个等差数列，假设每个元素占l个字节，元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij的前面有i行(0~i-1)共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+（i×n+j）×l。同理，三维数组Am×n×p按行优先存放的地址计算公式为：LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×l。2020年2月11日2时26分第22页二、列优先顺序1．存放规则列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时，按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元素，第三列元素，依次类推……在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前面提到的Am×n二维数组，可以按如下的形式存放到内存：a00，a10…，am-10，a01，a11，…，am-11，…，a0m-1，a1m-1，...，am-1n-1。即二维数组按列优先存放到内存后，也变成了一个线性序列（线性表）。2020年2月11日2时26分第23页因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。2．地址计算同样与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素aij的地址。对二维数组有：LOC(aij)=LOC(a00)+(j×m+i)×l对三维数组有：LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×l2020年2月11日2时26分第24页三、3维数组存储实例假设有一个3×4×2的三维数组A，共有24个元素，其逻辑结构如图5.4所示。图5.4三维数组的逻辑结构图列行纵a311a321a331a341a211a221a231a241a111a121a131a141a112a122a132a142a242a3422020年2月11日2时26分第25页三维数组元素的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A3×4×2（下标从1开始）采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：a111，a112，a121，a122，…，a331，a332，a341，a342采用以列为主序的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a3422020年2月11日2时26分第26页以上的存放规则可推广到多维数组的情况。总之，知道了多维数组的维数，以及每维的上下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出其在存储器中的位置。因此，数组的顺序存储是一种随机存取的结构。四、多维数组地址计算以二维数组Am×n为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc［1,1］，求任意元素aij的地址。aij是排在第i行，第j列，并且前面的第i-1行有n×（i-1）个元素，第ｉ行第j个元素前面还有ｊ-１个元素。由此得到如下地址计算公式：Loc［i,j］=Loc［1,1］+n×(i-1)+(j-1)2020年2月11日2时26分第27页根据计算公式，可以方便地求得aij的地址是Loc［i,j］。如果每个元素占size个存储单元，则任意元素aij的地址计算公式为：Loc［i,j］=Loc［1,1］+(n×(i-1)+j-1)×size三