數(shù)據(jù)結(jié)構(gòu)實驗報告 題目：廣義表抽象數(shù)據(jù)類型的實現(xiàn)學(xué)院計算機(jī)學(xué)院專業(yè)計算機(jī)科學(xué)與技術(shù)年級班別2010級7班學(xué)號學(xué)生姓名指導(dǎo)教師成績____________________2012年6月1.題目實現(xiàn)廣義表抽象數(shù)據(jù)類型GListADTGList{數(shù)據(jù)對象：D＝{ei|i=1,2,...,n;n≥0;ei∈AtomSet或ei∈GList，AtomSet為某個數(shù)據(jù)對象}數(shù)據(jù)關(guān)系：R1＝{<ei-1,ei>|ei-1,ei∈D,2<=i<=n}基本操作：InitGlist(&L);操作結(jié)果:創(chuàng)建空的廣義表LCreateGList(&L,S);初始條件:S是廣義表的書寫形式串操作結(jié)果:由S創(chuàng)建廣義表LDestroyGlist(&L);初始條件:廣義表L存在操作結(jié)果:銷毀廣義表LCopyGlist(&T,L);初始條件:廣義表L存在操作結(jié)果:由廣義表L復(fù)制得到廣義表TGListLength(L);初始條件:廣義表L存在操作結(jié)果:求廣義表L的長度,即元素個數(shù)GListDepth(L);初始條件:廣義表L存在操作結(jié)果:求廣義表L的深度GlistEmpty(L);初始條件:廣義表L存在操作結(jié)果:判斷廣義表L是否為空GetHead(L);初始條件:廣義表L存在操作結(jié)果:取廣義表L的頭GetTail(L)初始條件:廣義表L存在操作結(jié)果:取廣義表L的尾InsertFirst_GL(&L,e)初始條件:廣義表L存在操作結(jié)果:插入元素e作為廣義表L的第一元素DeleteFirst_GL(GList&L,&e)初始條件:廣義表L存在操作結(jié)果:刪除廣義表L的第一元素，并用e返回其值Traverse_GL(GListL,void(*v)(AtomType))初始條件:廣義表L存在操作結(jié)果:遍歷廣義表L，用函數(shù)Visit處理每個元素 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創(chuàng)建廣義表\n");printf("2銷毀廣義表\n");printf("3復(fù)制廣義表\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("請輸入你想進(jìn)行的操作項的序號：\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復(fù)制所得的表是："); 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("輸入要插入的元素："); getchar(); GetGList(add); CreatGList(f,q); InsertFirst_GL(L,f); Traverse_GL(L,visit); break; case10:DeleteFirst_GL(L,d); printf("刪除后的廣義表是：\n"); Traverse_GL(L,visit); break; case11:Traverse_GL(L,visit); break; case12:return; default: printf("\nInputERROR!\n"); getchar();}//switch}while(1);}6．思考與小結(jié)通過本次廣義表的設(shè)計性實驗，加深了我對廣義表的存儲結(jié)構(gòu)和基本抽象數(shù)據(jù)類型的實現(xiàn)的理解。由于廣義表的操作涉及不少循環(huán)和遞歸的算法，所以本次實驗后，我對遞歸算法的調(diào)用有了進(jìn)一步的了解。廣義表的存儲結(jié)構(gòu)也是挺有意思的，很多情況