第04章广义线性表.ppt

A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) 由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。 按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式: 头尾链表存储表示 扩展线性链表存储表示 A ＝( ) B ＝(e) C ＝(a, (b，c，d)) A ＝( ) B ＝(e) C ＝(a, (b，c，d)) D ＝(A, B, C) E ＝(a, E) F ＝(( )) 同构：表结点和原子结点结构相同,广义表同层上的各个元素互为“兄弟” 同构示例（孩子兄弟结点法） 广义线性表——广义表 若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。 采用头尾表示法存储广义表 如何采用链接存储结构存储广义表？ 广义表的存储结构——头尾表示法 广义线性表——广义表 广义表中的数据元素既可以是广义表也可以是单元素 头尾表示法中的结点结构？ 表结点——存储广义表；元素结点——存储单元素 tag=1 hp tp tag=0 data 表结点 元素结点 tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：数据域，存放单元素。 广义表的头尾表示法（异构表示） 广义线性表——广义表 结点结构 特点：（把头尾都看成一个表，重点是怎么理解这种结构） 1)除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点； 2)容易分清列表中原子和子表所在的层次； 3)最高层表结点个数即为列表的长度； 4)异构：表结点和原子结点结构不同 广义表的头尾表示法（异构表示） 广义线性表——广义表 enum Elemtag {Atom, List}; template class T struct GLNode { Elemtag tag; union { T data; struct { GLNode *hp, *tp; } ptr; }; }; 广义线性表——广义表 广义表的存储结构——头尾表示法 定义结点结构 tag=1 hp tp tag=0 data 广义线性表——广义表 广义表的异构示例（头尾链表存储） NULL A 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d 广义线性表——广义表 广义表的存储结构——头尾表示法 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d 1 D ∧ 1 1 ∧ 广义线性表——广义表 广义表的存储结构——头尾表示法 1 E 0 a 1 ∧ 1 F ∧ ∧ 三元组顺序表转置算法——算法Ⅰ 基本思想：直接取，顺序存。即在A的三元组顺序表中依次找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。 矩阵的压缩存储 矩阵的压缩存储 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 row col item 0 1 2 3 4 5 6 MaxTerm-1 5（矩阵的行数） 6（矩阵的列数） 7（非零元个数） row col item 0 1 2 3 4 5 6 MaxTerm-1 6（矩阵的行数） 5（矩阵的列数） 7（非零元个数） 设置矩阵B的行数、列数、非零元个数 矩阵的压缩存储 0 0 15 0 3 22 0