第5章 广义表,5.1 广义表的定义 5.2 广义表操作的实现,5.1 广义表的定义 5.1.1 定义,广义表（Lists）简称表，它是线性表的推广 一个广义表是n（n≥0）个元素的序列，当n=0时称为空表在一个非空的广义表中，其元素可以是某一确定类型的对象（这种元素被称作单元素），也可以是由单元素构成的表（这种元素可相对地被称作子表或表元素）显然，广义表的定义是递归的，广义表是一种递归的数据结构设ai为广义表的第i个元素，广义表LS可表示为： LS=（a1，a2，…， an） 其中： ①LS——广义表的名字； ②n——广义表的长度； ③ ； ④n=0 空表； ⑤当广义表非空时，称a1为表头（head），其余元素组成的表（a2，a3， …， an）为表尾（tail）； 广义表的抽象数据类型：P107,,5.1.2 举例,分别用圆圈和方框表示表（表元素）和单元素 ①A=（） 空表，其长度为零 ②B=（e） B中只有一个单元素，长度为1，表头为'e'，表尾为空③C=（a，（b，c，d）） 长度为2，表头为‘a’，表尾为子表（（b，c，d））。
④D=（A，B，C） 长度为3，表头为A, 表尾为（B，C） ⑤E=（a，E） 长度为2，表头为a，表尾为（E）--表头为E，表尾为（）E相当于无穷表（a，（a,（a，（…））））5.1.3广义表的几个性质,①有次序性： 广义表中的数据元素有固定的相对次序 线性排列 --线性表的推广 层次结构 --树的推广 ②有长度： 广义表的长度定义为最外层括弧中包含的数据元素个数 表元素个数一定，不能无限，可以是空表③有深度： 广义表的深度（多少层）定义为广义表书写形式中括弧的最大重数，因此空表的深度为1，因为一个“单原子“不是广义表，所以没有“深度“可言，但可以认为它的深度为0 如：A，B：1；C：2；D：3； E：无穷大 ④可递归： 如E ⑤可共享： 子表可共享5.1.4 广义表的存储结构,由于广义表中的数据元素可以是原子，也可以是广义表，显然难以用顺序存储结构表示 由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子为了在存储结构中便于分辩原子和子表，令表示广义表的链表中的结点为“异构“结点，如图所示， 结点中设有一个“标志域tag“， 并约定 tag=0 表示原子结点，tag=1 表示表结点。
原子结点中的 data 域存储原子，表结点中指针域的两个值分别指向表头和表尾原子结点,表结点,广义表的头尾链表存储表示：,enum ElemTag {ATOM,LIST}; typedef char AtomType; struct GLNode{ ElemTag tag; union { AtomType atom; struct { GLNode *hp,*tp; } ptr; }; }; typedef GLNode* GList;,例：广义表 L=(a,(x,y),((z))) 的存储结构可由对L进行表头和表尾的分析得到--若列表不空，则可分解成表头和表尾（采用头尾链表存储结构） 分析： ①L为一非空列表,②L的表头为原子a,③L的表尾为列表((x,y),((z))),④((x,y),((z)))的表头为列表(x,y),其余分析同上5.2 广义表操作的实现,基于广义表是递归定义的结构，因此实现广义表操作的算法均为递归函数5.2.1 分治法与递归求解,分治法是进行算法设计的一种方法，其严格定义为： 对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1k≤n) 个子集，从而产生m个子问题，分别求解这m个问题，得出m个问题的子解，再用某种方法把它们组合成原来问题的解。
若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止 在利用分治法求解时，若所得子问题的性质和原问题相同，则可递归求解何谓“递归函数“？,一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件： ①在每一次调用自己时，必须是(在某种意义上)更接近于解； ②函数中必须有一个终止处理或计算的准则5.2.2 广义表的头尾链表存储表示 glist.h,#include #include using namespace std; enum ElemTag {ATOM,LIST}; typedef char AtomType;,struct GLNode{ ElemTag tag; union { //匿名共用体 AtomType atom; struct { GLNode *hp,*tp; } ptr; }; }; typedef GLNode* GList;,void initGList(GList,5.2.3 操作的实现 glist.cpp,#include “glist.h“ ⑴ 初始化 void initGList(GList },⑶ 求广义表的深度 int getDepth(GList L) //采用头尾链表存储结构，求广义表L的深度 { int max=0,dep; GList p; if(!L) return 1; //空表深度为1 if(L-tag==ATOM) return 0; //原子深度为0 for(p=L; p; p=p-ptr.tp) { dep=getDepth(p-ptr.hp); //求以p-a.ptr.hp为头指针的子表深度 if(depmax) max=dep; } return max+1; // 非空表的深度是各元素的深度的最大值加1 },⑷ 建立广义表 以广义表字符串S建立广义表。
从前面的讨论可知，非空广义表可分解成表头和表尾两个部分建表时，可分别建立（分解为两个子问题）： 表头有两种情况，为单原子或为列表，当为列表时与原问题相同； 表尾必为列表，与原问题相同 设string sever(string& S )函数的功能为: 从广义表字符串S中提取表头串返回，并将S置成表尾串// 将非空串str分割成两部分： // hsub为最外层第一个','之前的子串，str为之后的子串 string sever(string },if(in) { hstr=str.substr(1,i-2); str=“(“+str.substr(i,n-i); } else { hstr=str.substr(1,n-2); str=““; } return hstr; },S的值有三种情况： ①“( )“--空表 ②单字符串--原子结点 ③多字符串--列表 算法： ①当S=“( )“，广义表L为空--L=NULL； ②否则，L为列表--创建表结点； A. 当S为单字符串时，为原子结点--建原子结点的子表； B. 否则，S为列表字符串--创建表结点； a. 从S中提取表头串hsub及表尾串tsub； b. 以hsub建表头--与原问题相同，递归； c. 如表尾串tsub为空--置表尾为NULL； 否则，以tsub建表尾， 递归。
//由广义表的书写形式串S创建广义表L void creatGList(GList //创建单原子广义表 },else { L-tag=LIST; hsub=sever(S); //从sub中分离出表头串hsub creatGList(L-ptr.hp,hsub); if(S.empty()) //表尾串为空 L-ptr.tp=NULL; else creatGList(L-ptr.tp,S); } } },⑸ 以字符串形式输出广义表 void printGList(GList,if(L-ptr.tp) { coutptr.tp,1); } if(k==0) coutatom; } },5.2.4 应用 main.cpp,#include “glist.h“ int main(){ string S1=“((),(e),(a,(b,c,d)))“; string S2=“(a,(x,y),((z)))“; string S3=“(a,b)“; string S4=“()“; GList L; initGList(L); creatGList(L,S2); coutgetLength(L)endl; coutgetDepth(L)endl; printGList(L); },。