华北水利学院 数据结构 课件 第六章(陈波).pptVIP

第六章 广义表 本章的基本内容是： 广义表的基本概念 广义表的存储结构 广义表的操作 广义表的基本概念 广义表：n（n≥0）个数据元素的有限序列，记作：GList＝(a1，a2，……，an) 其中： GList是广义表的名称，ai（1≤i≤n）是GList的成员（或直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为GList的单元素（或原子）和子表。 广义表的基本概念 长度：广义表中直接元素的个数； 深度：广义表中括号的最大嵌套层数。 表头：广义表非空时，称第一个元素为表头； 表尾：广义表中除表头外其余元素组成的广义表。 表头、表尾概念的重要性体现在，它们既是广义表的元素存取方法、广义表的分解方法，也暗示了广义表的构造方法。 广义表的示例 A ＝( ) B ＝(a, b,c) C ＝(a, (b,c,d),e) D ＝( (a,b),c,(d,(e,f),g)) E ＝(a, (), ((), ()),b) 广义表的存储结构 广义表可以采用顺序存储结构吗？ 由于广义表的非线性特征，且定义中对各个子表的长度没有任何限制，因此若试图采用顺序存储结构，必将引入许多繁杂的人为约束，使广义表的存储、应用复杂化。所以广义表一般采用链式存储结构。 广义表的存储结构 如何采用链接存储结构存储广义表？ 广义表的存储结构——头尾表示法 广义表的存储结构——头尾表示法 画出广义表G=(( )，x，(a，(b，c)))的存储结构。 * * 广义表( )和广义表(( ))不同？ 长度？深度？表头？表尾？ 若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。 采用头尾表示法存储广义表 广义表中的数据元素既可以是广义表也可以是单元素 头尾表示法中的结点结构？ 表结点——存储广义表；元素结点——存储单元素 enum GListNodeType{ATOM,LIST}; template class T struct GListNode { GListNodeType type; // 结点类型 union { T data; GListNode *sublist; }; GListNodeT * next; // 存储后继结点指针 }; 定义结点结构 type=1 sublist next type=0 data next