第2章数组(Array).pptVIP

内容提要 · 广义表的概念 · 广义表的存储结构 · 广义表的操作算法 递归表：允许递归的表。 表的长度: 表中直接元素的个数. 表的深度： 表中嵌套的最大层次数。 表头: 第一个元素. 表尾: 除表头外剩下部分组成的广义表 例如: A表的表头是( )，表尾是( )； B表的表头是a，表尾是(b, c)； C表的表头是a，表尾是( (b, c, d), e)； D表的表头是(a b)，表尾是(c, (d, (e, f), g) )； E表的表头是a，表尾是( ( ), (( ), ( )), b)。 广义表的基本操作 构造一个广义表 释放广义表空间 遍历广义表 复制广义表 求广义表的长度 求广义表的深度 求广义表的表头 求广义表的表尾 template class T GListT::GList(GListT head, GListT tail) { head=new GListNodeT; // 创建表头结点 head-type=LIST; head-next=NULL; // 将表头的头结点作为第一个数据结点 head-sublist= head.head; // 将表尾第一个数据结点作为第二个数据结点 head.head-next = tail.head-sublist; delete tail.head; // 释放表尾的头结点 head.head=tail.head=NULL; } 2. 遍历广义表(递归) template class T void GListT::Traverse(GListNodeT *p) { cout (; for (p=p-sublist; p; p=p-next) if (p-type==ATOM) cout p-data ; else Traverse(p); cout ); } template class T void GListT::Traverse( ) { Traverse(head ); } 3．复制广义表 (递归) template class T GListNodeT *GListT::Copy(GListNodeT* p) { head=new GListNodeT; // 创建头结点 head-type=LIST; head-next=head-sublist=NULL; // 复制原子结点、子表结点及其子表 for (p=p-sublist; p; p=p-next) { newp=new GListNodeT; newp-type = p-type; if (p-type==ATOM) newp-data =p-data; else newp-sublist=Copy(p); // 复制子表结点及其子表 if (head-sublist==NULL) head-sublist=tail=newp; else { tail-next=newp; tail=newp; } } tail-next=NULL; return head; } template class T GListT::GList(GListT gl) { head = Copy(gl.head); } 4．求广义表的长度 template class T int GListT::Length() { n=0; for (p=head-sublist; p; p=p-next) n++; return n; } 5. 求广义表的深度算法(递归) depth(p)的递归定义为: 1）递归终止条件： 当*p为原子时，depth(p)=0, 2）递归规律： depth(p) =1+ Max {depth(ai)} template class T int GListT::Depth(GListNodeT *p) { if (p-type==ATOM) re