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

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

。題目：廣義表抽象數(shù)據(jù)類型的實(shí)現(xiàn)

學(xué)院計(jì)算機(jī)學(xué)院

專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)

年級(jí)班別2023級(jí)7班

學(xué)號(hào)_________________________

學(xué)生姓名____________________________

指導(dǎo)教師_________________________

成績(jī)____________________

2023年6月

1.題目

實(shí)現(xiàn)廣義表抽象數(shù)據(jù)類型GList

ADTGList{

數(shù)據(jù)對(duì)象：D={ei|i=l,2,...,n；0；eiSAtomSet或ei.e

GList,AtomSet為某個(gè)數(shù)據(jù)對(duì)象}

數(shù)據(jù)關(guān)系：RI={<ei-i,ei>Iei-i,eieD,2<=i<=n}

基本操作：

InitG1ist(&L);

操作結(jié)果：創(chuàng)建空的廣義表L

CreateGList(&L,S);

初始條件:S是廣義表的書寫形式串

操作結(jié)果：由S創(chuàng)建廣義表L

DestroyGlist(&L);

初始條件:廣義表L存在

操作結(jié)果：銷毀廣義表L

CopyGlist(&T,L);

初始條件:廣義表L存在

操作結(jié)果：由廣義表L復(fù)制得到廣義表T

GListLength(L);

初始條件:廣義表L存在

操作結(jié)果:求廣義表L的長(zhǎng)度，即元素個(gè)數(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的第一元素

De1eteFirst_GL(GList&L,&e)

初始條件：廣義表L存在

操作結(jié)果：刪除廣義表L的第一元素,并用e返回其值

Traverse_GL(GListL,void(*v)(AtomType))

初始條件:廣義表L存在

操作結(jié)果:遍歷廣義表L,用函數(shù)Visit解決每個(gè)元素

}ADTGList

2.存儲(chǔ)結(jié)構(gòu)定義

由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)(或是原子,或是列表)，因此難以用順序存

儲(chǔ)結(jié)構(gòu)表達(dá)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),每個(gè)數(shù)據(jù)元素可用一個(gè)節(jié)點(diǎn)表達(dá)。

由于列表中的數(shù)據(jù)元素也許為原子或列表，由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn):一種是表結(jié)點(diǎn)，用

以表達(dá)列表;一種是原子結(jié)點(diǎn)，用以表達(dá)原子。一個(gè)表結(jié)點(diǎn)可以由3個(gè)域組成：標(biāo)志域，指示表

頭的指針域和指示表尾的指針域;而原子結(jié)點(diǎn)只需兩個(gè)域:標(biāo)志域和值域。其形式定義說(shuō)明如

下:

一一廣義表的擴(kuò)展線性鏈表存儲(chǔ)表達(dá)

typedefenum{ATOM,LIST}E1emTag;//AT0M=0:原子,LIST==1:子表

typedefstructGLNode{。

ElemTagtag;。//公共部分,用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;。//atom是原子結(jié)點(diǎn)的值域AtomType由

用戶定義

struct{structGLNode*hp,*tp；}ptr；

//Ptr是表結(jié)點(diǎn)的指針域,ptr.hp和ptr.tp分別指向表頭和

表尾

}；

}*GList;o?！◤V義表類型

voidvisit(GListL){。。//visit函數(shù)

oprintf("%cn,L->atom)；

)

voidGetGList(chars[])

?！ń邮芙ū碓?-書寫形式串的函數(shù)

inti;

printf("\nInputGListtocreat：\nu);

for(i=0;i<50;i++)

?{

。scanf(u%cM,&s[i])；

oif(s[i]==An')

o??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;

吹=*s;

°s++；

if(x!=,\n,){

f=(GList)malloc(sizeof(structGLNode));

。if(x=='('){

gq->tag=LIST;

bq->ptr.hp=CreatGList(L,s);

°}

。elseif(x==')(){

q->tag=LIST;

Af(*s!=',')

。。q=NULL;

。x=*s;

。s++;

。if(x==z：){

°。。q=(GList)ma1loc(sizeof(structGLNode));

gq->ptr.tp=CreatGList(L,s)；

06|

。else(

gq->tag=ATOM;

。q->atom=x;

d|o

。}//if

◎elseq=NULL；

x=*s;

S++；

if(q!=NULL)

aif(x==,；)

。q->ptr.tp=CreatGList(L,s);

else

gq->ptr.tp=NULL；

oL=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;

e1se(

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)；

a

I

?returnT;

intGListLength(GListL)9//求廣義表長(zhǎng)度

(

inti=0;

dGListp;

p=L;

if(p->tag==LIST&&!p->ptr.hp)

?>return0;

elseif(p—>tag==ATOM)

?return1;

e1se(

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;

eIse

(

fbr(max=0,p=L->ptr,hp;p;p=p->ptr.tp)

(

?dep=GListDepth(p);

?if(dep>max)

fmax=dep；

)

)

retummax+1;

intGListEmpty(GListL>。。//判斷廣義表是否為空

if(!L||L->tag==LIST&&!L->ptr.hp)

3retum1；

return0;

)

GListGetHead(GListL)。。。。。。〃取廣義表表頭

(

GListp,h;

if(!L||L->tag==LIST&&!L->ptr.hp)

printf("\nEmptyGList-NoGListhead!\n")；

returnNULL：

I

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;

else

CopyGList(p—>ptr.hp,L->ptr.hp->ptr.hp);

returnp;

)

GListGetTail(GListL)。//取廣義表表尾

GListp：

?if(!L)

°{

printf("\nEmptyGList-NoGListtai1!\n");

。returnNULL;

}

p=(GList)mal1oc(sizeof(structGLNode));

p->tag=LIST;

p->ptr.tp二NULL;

0copyGList(p->ptr.hp,L—>ptr.hp—>ptr.tp);

?returnp;

)

intInsertFirst_GL(GListL,GListe)g〃插入一個(gè)元素作為廣義表的第一元素

{

0GListp;

ap=L->ptr.hp;

L->ptr.hp=e;

e->ptr.tp=p：

return1；

)

intDeleteFirst_GL(GList&L,GList&e)〃刪除廣義表的第一元素

oif(L){

e=L->ptr.hp;

?L->ptr.hp=e->ptr,tp；

oe—>ptr.tp=NULL;

。}

。eIse

?e=L；。

returnI;

)

voidTraverse_GL(GList&L,voidvisit(GListL))〃遍歷廣義表

{

if(L!=NULL){

-if(L->tag==LIST){

printf("(”)；

if(!L->ptr.hp)

。printf("")；

。。吃1se

。Traverse_GL(L->ptr.hp,visit)；

g}

?clse

ovisit(L);

<>if(L—>tag==L1ST)

。叩rintf("

if(L->ptr.tp!=NULL){

。print

wTraverse_GL(L->ptr.tp,visit);

°}

)

else

printfC^EmptyGList!\nH)；

}

4.測(cè)試

voidmain()

{GListL,T,d,f,head,tail;

inta;

chars[50],add[50],*p,*q;

叩二s;

q=add;

if(!InitGList(L)&&!InitGList(T)){

printf("FailtoinitGList!\n")；

return；

)

do{。?！ú僮鹘缑?/p>

printf("\n\n請(qǐng)選擇功能

\n”)；

printf("_____—_—_—__________—__—___—__—\n");

Printf("1創(chuàng)建廣義表

\n");

printf('*2銷毀廣義表

\n',)；

printf("3復(fù)制廣義表

\nH);

printf(n4求廣義表長(zhǎng)度

\n");

printf("5求廣義表深度

\nM);

printf(M6判斷廣義表是否為空\(chéng)n");

printf("7取廣義表表頭

\n");

printf("8取廣義表表尾

\nH);

printf("9插入一個(gè)元素

\n”)；

printf(*'10刪除一個(gè)元素

\n"）；

printf('*11遍歷廣義表

\n'*);

printf("12退出程序

\n");

printf(

\n"）；

printf(H請(qǐng)輸入你想進(jìn)行的操作項(xiàng)的序號(hào):\n");

?scanf(H%d",&a);

printfC'\n");

switch(a){

。case1:getchar();

。GetGList(s);

CrcatGList(L,p)；

。oobreak;

。case2:if(DestroyGList(L))

gprintf("Succeedtodestroy.\nn)；

。。break;

case3：CopyGList(T,L)；

。primf("\n原表是：");

。Traverse_GL(L>visit)；

。printf("\n復(fù)制所得的表是：")：

。Traverse_GL(T,visit)；

0。。break;

3case4:printf("表的長(zhǎng)度是%(1\心6藤山ength(D)；

。reak;

scase5:printf("表的深度是％d\n",GListDepth(L));

。。break;

case6:if(GListEmpty(L))

。。printf("EmptyGList!\nH);

eIse

ggprintf("NotEmptyGList!\nM);

。?break;

。case7:printf(*'表頭是：\nH);

head=GctHead(L);

gTraverse_GL(head,visit)；

。obreak;

。case8:printf("表尾是：\n");

tail=GetTail(L);

Traverse_GL(tai1,visit);

。oobreak;

case9:printf("輸入要插入的元素：");

getchar()；

。GetGList(add)；

。CreatGList(f,q);

gInsertFirst_GL(L,f);

?Traverse_GL(L,visit)；

。。break；

。case10:DeleteFirst_GL(L,d);

gprintf(”刪除后的廣義表是：\n")；

。?Traverse_GL(L,visit)；

^break;

case11:Traverse_GL(L,visit);

。。。break;

。case12:return;

。defau1t:

。printf(M\nlnputERROR!\n");

。。getchar();

}//switch

while(1);

請(qǐng)輸入你想進(jìn)行的操作項(xiàng)的序號(hào):

|1

InputGListtocreat：

<a,b,<c,d>>

請(qǐng)選擇功能

創(chuàng)

建廣

1義表

廣

22表

箱

義

廣

銷

3毒

廣

義

4義

深

廣

義

5取

表

表

廣

里

空

為

6否

賣

表

義

變

7取

廣

表

8義

入

表

一