ch5数组和广义表.pptVIP

第5章 数组和广义表（Arrays Lists） 第5章 数组和广义表 第5章 数组和广义表 若是N维数组，其中任一元素的地址该如何计算？ Loc (j1, j2,… jn)=LOC(0,0,…0)＋ 例2：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K 按列存储的公式是？ Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K （尽管是方阵，但公式仍不同） N维数组的顺序存储表示（见教材P93） stdarg.h ：利用宏va_start、va_arg和va_end提供 遍历未知数目和类型的函数参数表的功能。 5.3 矩阵的压缩存储 5.3 矩阵的压缩存储 二、稀疏矩阵的压缩存储 方法1：压缩转置 方法2 快速转置 设计思路： 令：M中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数， cpot[ col ]：存放M中第col列的第一个非0元素的位置， （即b.data中待计算的“恰当”位置所需参考点） 5.4 广义表的定义 2.特点： 有次序性 有长度 有深度 可递归 可共享 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 ＝(( )) 一个直接前驱和一个直接后继 表中直接元素的个数； 表中括号的最大嵌套层数 自己可以作为自己的子表 可以为其他广义表所共享 特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。 5.4 广义表的定义 广义表的示例 长度？深度？表头？表尾？ n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 n=3，3个元素都是子表 n=2，a 为原子，E为子表 n=1, 表中元素为空表( ) 5.4 广义表的定义 广义表的图形表示 A B e C a b c d D E a E的长度为2，深度为∞ 5.4 广义表的定义 介绍两种特殊的基本操作： GetHead( L) ——取表头(可能是原子或列表); GetTail(L ) ——取表尾(一定是列表) 。 广义表的抽象数据类型定义见教材P107-108 5.4 广义表的定义 1. GetTail(b, k, p, h)＝ ; 2. GetHead( (a,b), (c,d) )＝ ; 3. GetTail( (a,b), (c,d) )＝ ; 4. GetTail ( GetHead ((a,b),(c,d)) )＝ ; 例：求下列广义表操作的结果 (k, p, h) （b） (a,b) 5. GetTail（e）＝ ; 6. GetHead ( ( ) )＝ . 7. GetTail ( ( ) ) ＝ . ( ) (a,b) ( ) ( ) ((c,d)) 5.4 广义表的定义 广义表可以采用顺序存储结构吗？ 由于广义表中的数据元素的类型不统一，因此难以采用顺序存储结构来存储。 若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。 采用头尾表示法存储广义表 如何采用链接存储结构存储广义表？ 5.5 广义表的存储结构 广义表的存储结构——头尾表示法 广义表中的数据元素既可以是广义表也可以是单元素 头尾表示法中的结点结构？ 表结点——存储广义表；原子结点——存储单元素 5.5 广义表的存储结构 tag=1 hp tp tag=0 data 表结点 原子结点 tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：数据域，存放单元素。 广义表的存储结构——头尾表示法 结点结构 5.5