《数据结构》(c语言版)第五章 数组和广义表.ppt

6) 任何一个非空广义表 LS = ( ?1, ?2, …, ?n) 均可分解为 表头 Head(LS) = ?1 和 表尾 Tail(LS) = ( ?2, …, ?n) 两部分。 例如: D = ( E, F ) = ((a, (b, c))，F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) ? 结构的创建和销毁 InitGList(L); DestroyGList(L); CreateGList(L, S); CopyGList(T, L); 基本操作 ? 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); ? 插入和删除操作 InsertFirst_GL(L, e); DeleteFirst_GL(L, e); ? 遍历 Traverse_GL(L, Visit()); §5.5 广义表的表示方法 通常采用头、尾指针的链表结构 表结点: 原子结点： tag=1 hp tp tag=0 data （1） 表头、表尾分析法： 构造存储结构的两种分析方法: 若表头为原子，则为 空表 ls=NIL 非空表 ls tag=1 指向表头的指针 指向表尾的指针 tag=0 data 否则，依次类推。 L = ( a, ( x, y ), ( ( x ) ) ) a ( x, y ) ( ) 1 L L = ( ) 0 a 1 1 1 1 1 0 x ? ? ? ( ) x （2） 子表分析法： 若子表为原子，则为 空表 ls=NIL 非空表 指向子表1 的指针 tag=0 atom 否则，依次类推。 指向子表2 的指针 指向子表n 的指针 1 1 1 ls … ? 1 ? tag=1 hp tp 例如: ? LS=( a, (x,y), ((x)) ) 0 a 1 1 ls 1 ? 0 x 0 y ? 1 ? 0 ? x 第五章 作 业 5.1 假设有二维数组A 6?8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）数组A的体积（即存储量）； （2）数组A的最后一个元素a57的第一个字节的地址； （3）按行存储时，元素a14的第一个字节的地址； （4）按列存储时，元素a47的第一个字节的地址。 第五章 作 业 5.10 求下列广义表操作的结果： （1）GetHead( (p, h, w) ); （4） GetTail( ((a ,b) ,(c ,d)) ); （5） GetHead ( GetTail ( ((a,b),(c,d)) ) )。 5.12 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。 （1）( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , ( ( ( e ) ) ) ) （2 ( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) ) * 我们仅讨论三对角矩阵的压缩存储，五对角矩阵，七对角矩阵等读者可以作类似分析。 另外: s[k]与a[i][j]的对应关系还有如下表示： 3i或 3j 当 i=j k= 3i+1或3j-2 当i=j-1 3i-1 或3j+2 当 i=j+1 对角矩阵 a1