[工学]数据结构数组和广义表演示.ppt

第五章? ? 数组和广义表 第五章 ??? 数组和广义表 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 第五章 习 题 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 第五章 习 题 ? 结构的创建和销毁 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.3.2 广义表的存储结构 由于广义表中的数据元素可以具有不同的类型，（或是原子，可是广义表）因此难以用顺序存储结构表示，通常采用链式存储结构，书上介绍了两种链式存储结构，一种是首尾链表，另一种是扩展线性链表，本课程只介绍首尾链表存储方式。 如何设定首尾链表结点的结构？由于广义表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示广义表；一种是原子结点，用以表示原子。从上节得知：若广义表不空，则可分成表头和表尾，反之，一对确定的表头和表尾可唯一确定广义表。由此，一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域，如下图所示： tag ptr 表结点 1 0 tag atom hp tp 原子结点 通常采用头、尾指针的链表结构 表结点: 原子结点： tag=1 hp tp tag=0 data 首尾链表结点的类型定义如下： Typedef enum{ ATOM,LIST}ElemTag; //ATOM==0:原子,LIST==1: 列表 Typedef struct GLNode { ElemTag tag; //标志域：用于区分原子结点和表结点 union { AtomType atom; //原子结点的值域 struct {struct GLNode *hp,*tp;}ptr; //表结点的指针域， //由两个指针域构成：ptr.hp指向表头， ptr.tp指向表尾 }; }*Glist; tag ptr 表结点 1 0 tag atom hp tp 原子结点 1) 表头、表尾分析法: 构造存储结构的两种分析方法: 若表头为原子，则为 空表 ls=NIL 非空表 ls tag=1 指向表头的指针 指向表尾的指针 tag=0 data 否则，依次类推。 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6