资源描述:
《广义表实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构实验报告题目:广义表抽象数据类型的实现学院计算机学院专业计算机科学与技术年级班别2010级7班学号学生姓名指导教师成绩____________________2012年6月1.题目实现广义表抽象数据类型GListADTGList{数据对象:D={ei
2、i=1,2,...,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}数据关系:R1={
3、ei-1,ei∈D,2<=i<=n}基本操作:InitGlist(&L);操作结果:创建空的广义表LCreateGList(&L,S);初始条件:S是广义表的书写形式串操作结果:
4、由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的尾InsertF
5、irst_GL(&L,e)初始条件:广义表L存在操作结果:插入元素e作为广义表L的第一元素DeleteFirst_GL(GList&L,&e)初始条件:广义表L存在操作结果:删除广义表L的第一元素,并用e返回其值Traverse_GL(GListL,void(*v)(AtomType))初始条件:广义表L存在操作结果:遍历广义表L,用函数Visit处理每个元素}ADTGList2.存储结构定义由于广义表中的数据元素可以具有不同的结构(或是原子,或是列表),因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个节点表示。由于列表中的数据元素可能为原子或列表,
6、由此需要两种结构的结点:一种是表结点,用以表示列表;一种是原子结点,用以表示原子。一个表结点可以由3个域组成:标志域,指示表头的指针域和指示表尾的指针域;而原子结点只需两个域:标志域和值域。其形式定义说明如下:-------广义表的扩展线性链表存储表示------typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分,用于区分原子结点和表结点union{//原子结点和表结点的联合部分AtomTypeatom;//atom是原子结点的值域AtomTy
7、pe由用户定义struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾};}*GList;//广义表类型voidvisit(GListL){//visit函数printf("%c",L->atom);}voidGetGList(chars[]){//接收建表元素--书写形式串的函数inti;printf("InputGListtocreat:");for(i=0;i<50;i++){scanf("%c",&s[i]);if(s[i]=='')break;}}3.算法设计intIni
8、tGList(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!=''){q=(GList)malloc(sizeof(structGLNode));if(x=='('){q->tag=LIST;q->ptr.hp=CreatGLis
9、t(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;}}//ifelseq=NULL;x=*s;s++;if(q!=NULL)if(x==',')q->ptr.tp=CreatGList(L,s);elseq->ptr.tp=NULL;L=q;retu