资源描述：
《数据结构(严蔚敏)C语言版课件第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表7/22/202110:16PM第页【课前思考】1.在你的认识中，"数组"是什么？在学习了C语言之后，同学们可能会误认为“数组”是一组地址连续的内存，数组也是一种线性的数据结构，它可以看成是线性表的一种扩充。2.为什么顺序表以及其它线性结构的顺序存储结构都可以用"一维数组"来描述？因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。7/22/202110:16PM第页【学习目标】1.理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法。 2.掌握特殊矩阵的存储压
2、缩表示方法。 3.理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。7/22/202110:16PM第页【重点和难点】本章重点是学习数组类型的定义及其存储表示。【知识点】数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。广义表的类型定义、广义表的存储表示、广义表操作的实现。7/22/202110:16PM第页【学习指南】从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前几章讨论的线性结构的顺序
3、存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。但由于广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固。本章算法设计题，完成5.21，
4、5.23。7/22/202110:16PM第页5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的存储结构5.6广义表操作的递归函数7/22/202110:16PM第页一、数组的概念1．一维数组一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。2．二维数组二维数组可以看成是向量的推广。5.1数组的定义7/22/202110:16PM第页例如，设A是一个有m行n列的二维数组，则A可以表示为：在
5、此，可以将二维数组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的二维数组7/22/202110:16PM第页图5.2矩阵Am×n看成n个列向量的线性表7/22/202110:16PM第页图5.3矩阵Am×n看成m个行向量的线性表由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型
6、的非线性结构。7/22/202110:16PM第页以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。例如二维数组A3×4，它有3行、4列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：(1）获得特定位置的元素值；(2）修改特定位置的元素值。3．多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三
7、维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。7/22/202110:16PM第页数组的抽象类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn
8、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{
9、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:7/22/202110:16PM第页二维数组的定义:数据对象
10、:D={aij
11、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={
