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

《华北水利学院-数据结构-课件-第六章(陈波).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章的基本内容是：广义表的基本概念广义表的存储结构广义表的操作第六章广义表广义表的基本概念广义表：n（n≥0）个数据元素的有限序列，记作：GList＝(a1，a2，……，an)其中：GList是广义表的名称，ai（1≤i≤n）是GList的成员（或直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为GList的单元素（或原子）和子表。广义表的基本概念长度：广义表中直接元素的个数；深度：广义表中括号的最大嵌套层数。表头：广义表非空时，称第一个元素为表头；表尾：广义表中除表头外其余元素组成的广义表。表头、表尾概念的重要性体现在，它们既是广义表的元素存取方法、广义表的分解方法，

2、也暗示了广义表的构造方法。广义表()和广义表(())不同？A＝()B＝(a,b,c)C＝(a,(b,c,d),e)D＝((a,b),c,(d,(e,f),g))E＝(a,(),((),()),b)长度？深度？表头？表尾？广义表的示例广义表的存储结构广义表可以采用顺序存储结构吗？由于广义表的非线性特征，且定义中对各个子表的长度没有任何限制，因此若试图采用顺序存储结构，必将引入许多繁杂的人为约束，使广义表的存储、应用复杂化。所以广义表一般采用链式存储结构。广义表的存储结构如何采用链接存储结构存储广义表？若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。

3、采用头尾表示法存储广义表广义表中的数据元素既可以是广义表也可以是单元素头尾表示法中的结点结构？表结点——存储广义表；元素结点——存储单元素广义表的存储结构——头尾表示法enumGListNodeType{ATOM,LIST};templatestructGListNode{GListNodeTypetype;//结点类型union{Tdata;GListNode*sublist;};GListNode*next;//存储后继结点指针};定义结点结构type=1sublistnexttype=0datanext广义表的存储结构——头尾表示法画出广义表G=(()，x

4、，(a，(b，c)))的存储结构。templateclassGList{GListNode*head;public:GList();GList(GListhead,GListtail);//利用表头、表尾构造对象GList(GList&gl);//拷贝构造函数~GList();voidTraverse();//遍历算法intLength();//计算表的长度intDepth();//计算表的深度……};广义表的存储结构——头尾表示法