DS数组和广义表1.PPTVIP

第5章要点 数组的类型定义和表示方法 特殊矩阵和稀疏矩阵存储方法 及运算的实现 广义表的结构特点 第5章 数组 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。 5.1.1 多维数组组的定义 定义 5.1.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序 5.2.1 特殊矩阵 对称矩阵（只记录对角线及其下面的部分） 三角矩阵（下三角矩阵） 稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法： 5.3 广义表 广义表(Lists)也称为列表，它是线性表的推广。大家知道，线性表是n（n≥0）个元素a1，a2，…，ai，…，an的有限序列。其中，线性表的元素仅限于原子项，所谓原子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。 广义表是n（n≥0）个元素a1，a2，…，ai，…，an的有限序列，其中ai或者是原子，或者是一个广义表。通常，广义表可记作LS=(a1,a2,…,ai,…,an)。LS是广义表的名字，n为广义表LS的长度。若ai本身也是广义表，则称它为LS的子表。不包含任何元素（即n=0）的广义表称为空表。 需要注意的是： 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。 若广义表LS非空(n≥1)，则a1称为LS的表头，其余元素组成的表(a2,…,ai,…,an)称为LS的表尾。显然，表尾一定是子表，但表头可以是原子，也可以是子表。 广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。 广义表是一个多层次的线性结构。例如: 有A、B、C、D、E五个广义表的描述如下： A=( ) A是一个空表,它的长度为零 B=(e) 列表B只有一个原子e,B的长度为1. C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d) D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d))) E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...))) 广义表的结构特点: 1) 广义表中的数据元素有相对次序; 2) 广义表的长度定义为最外层包含的元素个数; 3) 广义表的深度定义为所含括弧的重数; 注意: “原子”的深度为“0”; “空表”的深度为1 4) 表头可以是原子或列表;表尾必定是列表。 5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。 6) 任何一个非空广义表 LS = ( ?1, ?2, …, ?n) 均可分解为： 表头 Head(LS) = ?1 和 表尾 Tail(LS) = ( ?2, …, ?n) 两部分。 例如： Head( (( b, c)) ) = (( b, c)) Tail( (( b, c)) ) = ( ) Head( a,( b, c) ) = a Tail( a,( b, c) ) = (( b,c )) Head( ( c ) ) =(c) Tail( ( c ) ) = ( ) 广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分支结点（即叶子）对应原子或者空表。 * 北京联合大学信息学院《数据结构》 * 数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) a00