【精品数据结构】多维数组与广义表.pptVIP

第5章 多维数组与广义表 5.1 数组的存储结构与寻址 看待N维数组的两种不同角度： 数组的寻址操作： 根据所给的下标定位相应的元素。 方法： 根据一定的映射规则，将多维数组的“多维”结构映射到计算机中“一维”的物理存储单元中去。 映射规则： 1. 行主序（主要） 2. 列主序 以二维数组arr[2][3]为例： 以行序为主序（按行存储）的方法： “左”下标优先 以列序为主序（按列存储）的方法： “右”下标优先 5.2 特殊矩阵的压缩存储方式 矩阵的存储问题： 普通矩阵：二维数组 特殊矩阵：采用二维数组相对低效，需要采用特殊方法。 5.2.1 对称矩阵（下/上三角矩阵）的压缩存储 对称矩阵 ： 矩阵AN×N，其元素ai,j满足特性： ai,j=aj,i（1≤i≤N，1≤j≤N） 对角矩阵： 所有的非零元素都集中在以主对角线为中心的带状区域内。 5.2.2 稀疏矩阵的三元组顺序表存储方式 稀疏矩阵： 含有“较多”零元素,通常指零元素数目占整个矩阵元素数目的95％或者更高的矩阵。 “三元组顺序表” 5.3 广义表 广义表（Generalized Lists）是线性表的推广，有时也称为列表（Lists）。 当线性表中的元素类型不一致（即某些元素是原子类型的数据，而另一些元素却是原子类型构成的一个线性表）时，会使元素之间在原有线性关系的基础上，加入层次关系的新特性。 5.3.1 广义表的定义、特性与基本操作 广义表的定义 ： 可以把含有n（n≥0）个元素，名称为L的广义表记为： L =（ε1 ,ε2,…,εn） 其他术语： n=0，则该广义表为空表。 n0时， 对于广义表的每个元素，如果其类型仍为广义表，那么可以称这个元素为广义表L的“子表”。 如果其类型只是单个元素，那么可以称其为广义表L的“原子”。 第一个元素为广义表L的“表头”，而其余元素组成的表被称为广义表L的“表尾”。 L4=（a，（b，c，d）），L4包含2个元素，一个是原子a，一个是子表（b，c，d），子表表长为3，L4表表长为2； L5=（L1，L2，L4），L5包含3个元素，三个元素都是列表。将子表的值带入后，我们可以得到L5=（（），（a），（a，（b，c，d）））； L6=（a，L6），L6只包含2个元素，但由于L6是包含自己的递归表，所以L6相当于是一个无限的列表：L6=（a，（a，（a，（a，…））））。 广义表的基本操作： 对广义表L执行取表头的操作： getHead(L) 对广义表L执行表尾的操作： getTail(L) 广义表的基本特性：线性表 广义表兼具线性与层次双重关系特性。 5.3.2 广义表的存储结构与广义表的递归算法 广义表的存储结构 链式存储结构 广义表的递归算法 思路一： 对于原子类型的数据，直接操作；对于列表型的数据，将其分解成表头与表尾两部分，再分别进行递归调用。（分而治之） 思路二： 对于原子型数据，直接操作；对于列表型数据，可以把列表中各项看成是并列的，依次对各项进行递归处理。 5.4 本章小结 基本要求： 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 掌握对特殊矩阵进行压缩存储时的下标变换公式。 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 掌握广义表的结构特点及其存储表示方法，熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。 学会利用分治法的算法设计思想编制递归算法的方法。 借用字符串来存储广义表的“逻辑”表示形式； 以“分治”思想为基础递归将各项广义表信息填入具体存储结构。 根据广义表的“逻辑”表示形式完成广义表的“物理”构造： 基本内容： 1. 数组与线性表的关系 2. 行主序寻址与列主序寻址 3. 特殊矩阵的存储策略 4. 兼具线性关系与层次关系的复杂结构：广义表 * 5.1 数组的存储结构与寻址 5.2 特殊