数据结构课件 第5章广义表.pptVIP

第5章 广义表;5.1 广义表的定义5.1.1 定义;设ai为广义表的第i个元素，广义表LS可表示为： LS=（a1，a2，…， an） 其中： ①LS——广义表的名字； ②n——广义表的长度； ③ ； ④n=0 空表； ⑤当广义表非空时，称a1为表头（head），其余元素组成的表（a2，a3， …， an）为表尾（tail）； 广义表的抽象数据类型：P107 ;5.1.2 举例;③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 域存储原子，表结点中指针域的两个值分别指向表头和表尾。;广义表的头尾链表存储表示：;例：广义表 L=(a,(x,y),((z))) 的存储结构。;②L的表头为原子a;③L的表尾为列表((x,y),((z)));④((x,y),((z)))的表头为列表(x,y);其余分析同上。;5.2 广义表操作的实现;5.2.1 分治法与递归求解;何谓递归函数？;5.2.2 广义表的头尾链表存储表示glist.h;struct GLNode{ ElemTag tag; union { //匿名共用体 AtomType atom; struct { GLNode *hp,*tp; } ptr; }; }; typedef GLNode* GList; ;void initGList(GList L); // 创建空的广义表L int getLength(GList L); int getDepth(GList L); void creatGList(GList L,string s); void printGList(GList L,int k=0);;5.2.3 操作的实现glist.cpp;⑶ 求广义表的深度 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 str) { int n,k,i; // k记录尚未配对的左括号个数 string ch,hstr; n=str.length(); for(i=0,k=-1; in(ch!=,||k!=0); ++i) { // 搜索最外层的第一个逗号 ch=str.substr(i,1); //从第i个位置起，取1个字符 if(ch==() ++k;