广义表实验报告

数据构造试验汇报 题目：广义表抽象数据类型的实现学院计算机学院专业计算机科学与技术年级班别级7班学号学生姓名指导教师成绩____________________6月1.题目实现广义表抽象数据类型GListADTGList{数据对象：D＝{ei|i=1,2,...,n;n≥0;ei∈AtomSet或ei∈GList，AtomSet为某个数据对象}数据关系：R1＝{<ei-1,ei>|ei-1,ei∈D,2<=i<=n}基本操作：InitGlist(&L);操作成果:创立空的广义表LCreateGList(&L,S);初始条件:S是广义表的书写形式串操作成果:由S创立广义表LDestroyGlist(&L);初始条件:广义表L存在操作成果:销毁广义表LCopyGlist(&T,L);初始条件:广义表L存在操作成果:由广义表L复制得到广义表TGListLength(L);初始条件:广义表L存在操作成果:求广义表L的长度,即元素个数GListDepth(L);初始条件:广义表L存在操作成果:求广义表L的深度GlistEmpty(L);初始条件:广义表L存在操作成果:判断广义表L与否为空GetHead(L);初始条件:广义表L存在操作成果:取广义表L的头GetTail(L)初始条件:广义表L存在操作成果:取广义表L的尾InsertFirst_GL(&L,e)初始条件:广义表L存在操作成果:插入元素e作为广义表L的第一元素DeleteFirst_GL(GList&L,&e)初始条件:广义表L存在操作成果:删除广义表L的第一元素，并用e返回其值Traverse_GL(GListL,void(*v)(AtomType))初始条件:广义表L存在操作成果:遍历广义表L，用函数Visit处理每个元素}ADTGList2．存储构造定义由于广义表中的数据元素可以具有不一样的构造（或是原子，或是列表），因此难以用次序存储构造表达，一般采用链式存储构造，每个数据元素可用一种节点表达。由于列表中的数据元素也许为原子或列表，由此需要两种构造的结点：一种是表结点，用以表达列表；一种是原子结点，用以表达原子。一种表结点可以由3个域构成：标志域，指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。其形式定义阐明如下：-------广义表的扩展线性链表存储表达------typedefenum{ATOM,LIST}ElemTag; //ATOM==0:原子,LIST==1:子表typedefstructGLNode{ ElemTagtag; //公共部分,用于辨别原子结点和表结点union{ //原子结点和表结点的联合部分AtomType atom; //atom是原子结点的值域AtomType由顾客定义struct{structGLNode*hp,*tp;}ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾};}*GList； //广义表类型voidvisit(GListL){ //visit函数 printf("%c",L->atom);}voidGetGList(chars[]){ //接受建表元素--书写形式串的函数 inti; printf("\nInputGListtocreat:\n"); for(i=0;i<50;i++) { scanf("%c",&s[i]); if(s[i]=='\n') break; }}3.算法设计intInitGList(GList&L) //建空广义表{L=(GList)malloc(sizeof(structGLNode));if(!L)returnERROR;L->tag=LIST;L->ptr.hp=NULL;L->ptr.tp=NULL;returnOK;}GListCreatGList(GList&L,char*s){ //由书写形式串建广义表 GListq; charx; x=*s; s++; if(x!='\n'){ q=(GList)malloc(sizeof(structGLNode)); if(x=='('){ q->tag=LIST; q->ptr.hp=CreatGList(L,s); } elseif(x==')'){ q->tag=LIST; if(*s!=',') q=NULL; x=*s; s++; if(x==','){ q=(GList)malloc(sizeof(structGLNode)); q->ptr.tp=CreatGList(L,s); } } else{ q->tag=ATOM; q->atom=x; } }//if elseq=NULL; x=*s; s++; if(q!=NULL) if(x==',') q->ptr.tp=CreatGList(L,s); else q->ptr.tp=NULL; L=q; returnL;}intDestroyGList(GList&L)//销毁广义表{GListph,pt;if(L){if(L->tag)ph=L->ptr.hp;else ph=NULL;pt=L->ptr.tp;free(L); L=NULL;DestroyGList(ph);DestroyGList(pt); }returnOK;}GListCopyGList(GList&T,GListL) //复制广义表{ if(!L)T=NULL; else{ T=(GList)malloc(sizeof(structGLNode)); T->tag=L->tag; if(L->tag==ATOM) T->atom=L->atom; else CopyGList(T->ptr.hp,L->ptr.hp); CopyGList(T->ptr.tp,L->ptr.tp); } returnT;}intGListLength(GListL) //求广义表长度{ inti=0; GListp; p=L; if(p->tag==LIST&&!p->ptr.hp) return0; elseif(p->tag==ATOM) return1; else{ p=L->ptr.hp; for(i=0;p;p=p->ptr.tp,i++); returni; }}-intGListDepth(GListL) //求广义表深度{intmax,dep;GListp;p=L;if(!L||p->tag==LIST&&p->ptr.hp==NULL)return1;elseif(p->tag==ATOM)return0;else{for(max=0,p=L->ptr.hp;p;p=p->ptr.tp) { dep=GListDepth(p); if(dep>max) max=dep; }}returnmax+1;}intGListEmpty(GListL) //判断广义表与否为空 { if(!L||L->tag==LIST&&!L->ptr.hp) return1; return0; }GListGetHead(GListL) //取广义表表头{GListp,h;if(!L||L->tag==LIST&&!L->ptr.hp) {printf("\nEmptyGList-NoGListhead!\n"); returnNULL; }p=(GList)malloc(sizeof(structGLNode));h=L->ptr.hp;p->tag=h->tag;p->ptr.tp=NULL;if(p->tag==ATOM)p->atom=L->ptr.hp->atom;elseCopyGList(p->ptr.hp,L->ptr.hp->ptr.hp);returnp;}GListGetTail(GListL) //取广义表表尾{GListp; if(!L) { printf("\nEmptyGList-NoGListtail!\n"); returnNULL; } p=(GList)malloc(sizeof(structGLNode)); p->tag=LIST; p->ptr.tp=NULL; CopyGList(p->ptr.hp,L->ptr.hp->ptr.tp); returnp;}intInsertFirst_GL(GListL,GListe) //插入一种元素作为广义表的第一元素{ GListp; p=L->ptr.hp; L->ptr.hp=e; e->ptr.tp=p; return1;}intDeleteFirst_GL(GList&L,GList&e) //删除广义表的第一元素{ if(L){ e=L->ptr.hp; L->ptr.hp=e->ptr.tp; e->ptr.tp=NULL; } else e=L; return1; }voidTraverse_GL(GList&L,voidvisit(GListL)) //遍历广义表{ if(L!=NULL){ if(L->tag==LIST){ printf("("); if(!L->ptr.hp) printf(""); else Traverse_GL(L->ptr.hp,visit); } else visit(L); if(L->tag==LIST) printf(")"); if(L->ptr.tp!=NULL){ printf(","); Traverse_GL(L->ptr.tp,visit); } } else printf("\nEmptyGList!\n");}4．测试voidmain(){GListL,T,d,f,head,tail; inta; chars[50],add[50],*p,*q; p=s; q=add; if(!InitGList(L)&&!InitGList(T)){ printf("FailtoinitGList!\n"); return; }do{ //操作界面printf("\n\n请选择功能\n");printf("------------------------------------\n");printf("1创立广义表\n");printf("2销毁广义表\n");printf("3复制广义表\n");printf("4求广义表长度\n");printf("5求广义表深度\n");printf("6判断广义表与否为空\n");printf("7取广义表表头\n");printf("8取广义表表尾\n");printf("9插入一种元素\n");printf("10删除一种元素\n");printf("11遍历广义表\n");printf("12退出程序\n");printf("------------------------------------\n");printf("请输入你想进行的操作项的序号：\n"); scanf("%d",&a); printf("\n"); switch(a){ case1:getchar(); GetGList(s); CreatGList(L,p); break; case2:if(DestroyGList(L)) printf("Succeedtodestroy.\n"); break; case3:CopyGList(T,L); printf("\n原表是："); Traverse_GL(L,visit); printf("\n复制所得的表是："); Traverse_GL(T,visit); break; case4:printf("表的长度是%d\n",GListLength(L)); break; case5:printf("表的深度是%d\n",GListDepth(L)); break; case6:if(GListEmpty(L)) printf("EmptyGList!\n"); else printf("NotEmptyGList!\n"); break; case7:printf("表头是：\n"); head=GetHead(L); Traverse_GL(head,visit); break; case8:printf("表尾是：\n"); tail=GetTail(L); Traverse_GL(tail,visit); break; case9:printf("输入要插入的元素：");