廣義表實(shí)驗(yàn)報(bào)告

數(shù)據(jù)構(gòu)造試驗(yàn)匯報(bào) 題目：廣義表抽象數(shù)據(jù)類型的實(shí)現(xiàn)學(xué)院計(jì)算機(jī)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)班別級(jí)7班學(xué)號(hào)學(xué)生姓名指導(dǎo)教師成績____________________6月1.題目實(shí)現(xiàn)廣義表抽象數(shù)據(jù)類型GListADTGList{數(shù)據(jù)對(duì)象：D＝{ei|i=1,2,...,n;n≥0;ei∈AtomSet或ei∈GList，AtomSet為某個(gè)數(shù)據(jù)對(duì)象}數(shù)據(jù)關(guān)系：R1＝{<ei-1,ei>|ei-1,ei∈D,2<=i<=n}基本操作：InitGlist(&L);操作成果:創(chuàng)立空的廣義表LCreateGList(&L,S);初始條件:S是廣義表的書寫形式串操作成果:由S創(chuàng)立廣義表LDestroyGlist(&L);初始條件:廣義表L存在操作成果:銷毀廣義表LCopyGlist(&T,L);初始條件:廣義表L存在操作成果:由廣義表L復(fù)制得到廣義表TGListLength(L);初始條件:廣義表L存在操作成果:求廣義表L的長度,即元素個(gè)數(shù)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，用函數(shù)Visit處理每個(gè)元素}ADTGList2．存儲(chǔ)構(gòu)造定義由于廣義表中的數(shù)據(jù)元素可以具有不一樣的構(gòu)造（或是原子，或是列表），因此難以用次序存儲(chǔ)構(gòu)造表達(dá)，一般采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，每個(gè)數(shù)據(jù)元素可用一種節(jié)點(diǎn)表達(dá)。由于列表中的數(shù)據(jù)元素也許為原子或列表，由此需要兩種構(gòu)造的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，用以表達(dá)列表；一種是原子結(jié)點(diǎn)，用以表達(dá)原子。一種表結(jié)點(diǎn)可以由3個(gè)域構(gòu)成：標(biāo)志域，指示表頭的指針域和指示表尾的指針域；而原子結(jié)點(diǎn)只需兩個(gè)域：標(biāo)志域和值域。其形式定義闡明如下：-------廣義表的擴(kuò)展線性鏈表存儲(chǔ)表達(dá)------typedefenum{ATOM,LIST}ElemTag; //ATOM==0:原子,LIST==1:子表typedefstructGLNode{ ElemTagtag; //公共部分,用于辨別原子結(jié)點(diǎn)和表結(jié)點(diǎn)union{ //原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分AtomType atom; //atom是原子結(jié)點(diǎn)的值域AtomType由顧客定義struct{structGLNode*hp,*tp;}ptr; //ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾};}*GList； //廣義表類型voidvisit(GListL){ //visit函數(shù) printf("%c",L->atom);}voidGetGList(chars[]){ //接受建表元素--書寫形式串的函數(shù) inti; printf("\nInputGListtocreat:\n"); for(i=0;i<50;i++) { scanf("%c",&s[i]); if(s[i]=='\n') break; }}3.算法設(shè)計(jì)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) //復(fù)制廣義表{ 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請(qǐng)選擇功能\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("請(qǐng)輸入你想進(jìn)行的操作項(xiàng)的序號(hào)：\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("輸入要插入的元素：");