数据结构课件CH5数组和广义表li幻灯片.ppt

例： L = ( a, ( x, y ), ((x))) 表头表尾分析法 1 L 1 1 (((x))) ((x,y),((x))) 1 (x,y) 1 ? ((x)) 1 (y) 0 x x 0 a a 0 y ? y (x) 1 ? 0 x ? x 1 1 1 ls … ? 2) 元素分析法: 若元素为原子，则为 空表 ls=NULL 非空表 指向元素1 的指针 tag=0 data 否则，依此类推。 指向元素2 的指针 指向元素n 的指针 例：LS=( a, (x,y), ((x)) ) 元素分析法 ? ls 1 1 1 1 x a 0 a x 0 x y 0 y x 0 x ((x)) (x, y) a 1 1 x y 1 (x) 作 业 1.广义表 F=((((a),b)),((( ),(d)),(e,f))) 画出其图形表示及存储结构。 2.广义表 G=(((a,b,( )),( ),(a,(b))),( )) 画出其图形表示及存储结构。 1 1 1 1 1 1 0 f 0 e 0 b 0 a 1 1 1 1 0 d 1 1 1 1.F 1 1 1 1 1 1 1 1 0 a 0 a 0 b 1 1 1 0 b 2. G 本章结束 * * * 树有度的概念,与广义表的长度对应 树的深度：树中叶子结点所在的最大层次 * 树有度的概念,与广义表的长度对应 树的深度：树中叶子结点所在的最大层次 * 仅从第一层看是一个线性结构. * 树有度的概念,与广义表的长度对应 树的深度：树中叶子结点所在的最大层次 * 表头可以是原子或表，表尾永远是表！ * 分析方法不同，构造结果是一样的 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 0 1 2 3 4 5 6 7 8 ma 7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v 0 1 2 3 4 5 6 7 8 mb k p p p p p p p p k k k k p p p p p p p p col=1 col=2 用“三元组”表示时如何实现？ 其时间复杂度为: O(nu ×tu ) 最坏情况为: O(nu2×mu) 快速转置算法 即按ma中三元组次序转置，转置结果放入mb中恰当位置。 算法关键是要预先确定M中每一列第一个非零元在mb中位置， 为确定这些位置，转置前应先求得M的每一列中非零元个数. 实现：设两个辅助数组 num[col]：表示矩阵M中第col列中非零元个数 cpot[col]：指示M中第col列第一个非零元在mb.data中的恰当位置 显然有： cpot[1]=1; cpot[col]=cpot[col-1]+num[col-