广义表实验报告.docx

1、广义表实验报告数据结构实验报告题目：广义表抽象数据类型的实现学 院 计算机学院 专 业 计算机科学与技术 年级班别 2010级7班 学 号 学生 指导教师 成 绩 _2012年6月1. 题目实现广义表抽象数据类型GList ADT GList数据对象：D ei | i=1,2,.,n; n0;eiAtomSet或eiGList，AtomSet为某个数据对象数据关系：R1 |ei-1, eiD, 2=iatom);void GetGList(char s) /接收建表元素-书写形式串的函数int i;printf(nInput GList to creat:n);for(i=0;itag=LIS

2、T;L-ptr.hp=NULL;L-ptr.tp=NULL;return OK;GList CreatGList(GList &L,char *s) /由书写形式串建广义表 GList q; char x; x=*s; s+; if(x!=n) q=(GList)malloc(sizeof(struct GLNode); if(x=() q-tag=LIST; q-ptr.hp=CreatGList(L,s); else if(x=) q-tag=LIST; if(*s!=,) q=NULL; x=*s; s+; if(x=,) q=(GList)malloc(sizeof(struct GL

3、Node); q-ptr.tp=CreatGList(L,s); else q-tag=ATOM; q-atom=x; /if else q=NULL; x=*s; s+; if(q!=NULL) if(x=,) q-ptr.tp=CreatGList(L,s); else q-ptr.tp=NULL; L=q; return L;int DestroyGList(GList &L) /销毁广义表 GList ph,pt; if(L) if(L-tag) ph=L-ptr.hp; else ph=NULL; pt=L-ptr.tp; free(L); L=NULL; DestroyGList(

4、ph); DestroyGList(pt); return OK; GList CopyGList(GList &T,GList L) /复制广义表 if(!L) T=NULL; else T=(GList)malloc(sizeof(struct GLNode); 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); return T;int GListLength(GList L) /求广义表长度 int i=0; GList p

5、; p=L; if(p-tag=LIST&!p-ptr.hp) return 0; else if(p-tag=ATOM) return 1; elsep=L-ptr.hp;for(i=0;p;p=p-ptr.tp,i+);return i; -int GListDepth(GList L) /求广义表深度int max,dep;GList p;p=L;if(!L|p-tag=LIST&p-ptr.hp=NULL)return 1;else if(p-tag=ATOM)return 0;elsefor(max=0,p=L-ptr.hp;p;p=p-ptr.tp) dep=GListDepth(

6、p);if(depmax)max=dep; return max+1;int GListEmpty(GList L) /判断广义表是否为空if(!L|L-tag=LIST&!L-ptr.hp)return 1;return 0;GList GetHead(GList L) /取广义表表头GList p,h;if(!L|L-tag=LIST&!L-ptr.hp) printf(n Empty GList-No GList head!n); return NULL; p=(GList)malloc(sizeof(struct GLNode);h=L-ptr.hp;p-tag=h-tag;p-ptr

7、.tp=NULL;if(p-tag=ATOM)p-atom=L-ptr.hp-atom;elseCopyGList(p-ptr.hp,L-ptr.hp-ptr.hp);return p;GList GetTail(GList L) /取广义表表尾GList p; if(!L) printf(n Empty GList-No GList tail!n); return NULL; p=(GList)malloc(sizeof(struct GLNode); p-tag=LIST; p-ptr.tp=NULL; CopyGList(p-ptr.hp,L-ptr.hp-ptr.tp); return

8、 p;int InsertFirst_GL(GList L,GList e) /插入一个元素作为广义表的第一元素 GList p; p=L-ptr.hp; L-ptr.hp=e; e-ptr.tp=p; return 1;int DeleteFirst_GL(GList &L,GList &e) /删除广义表的第一元素 if(L)e=L-ptr.hp;L-ptr.hp=e-ptr.tp;e-ptr.tp=NULL; else e=L; return 1; void Traverse_GL(GList &L,void visit(GList L) /遍历广义表 if(L!=NULL) if(L-

9、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(nEmpty GList!n);4测试void main() GList L,T,d,f,head,tail;int a;char s50,add50,*p,*q;p=s;q=add;if(!InitGList(L)&!I

10、nitGList(T)printf(Fail to init GList!n); return;do /操作界面 printf(nn 请选择功能 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)

11、; printf( 11 遍历广义表 n); printf( 12 退出程序 n); printf( - n); printf( 请输入你想进行的操作项的序号： n);scanf(%d,&a);printf(n);switch(a) case 1: getchar(); GetGList(s); CreatGList(L,p); break; case 2: if(DestroyGList(L) printf(Succeed to destroy.n); break; case 3: CopyGList(T,L); printf(n原表是： ); Traverse_GL(L,visit); p

12、rintf(n复制所得的表是： ); Traverse_GL(T,visit); break; case 4: printf(表的长度是%dn,GListLength(L); break; case 5: printf(表的深度是%dn,GListDepth(L); break; case 6: if(GListEmpty(L) printf(Empty GList!n); else printf(Not Empty GList!n); break; case 7: printf(表头是：n); head=GetHead(L); Traverse_GL(head,visit); break;

13、case 8: printf(表尾是：n); tail=GetTail(L); Traverse_GL(tail,visit); break; case 9: printf(输入要插入的元素： ); getchar(); GetGList(add); CreatGList(f,q); InsertFirst_GL(L,f); Traverse_GL(L,visit); break; case 10: DeleteFirst_GL(L,d); printf(删除后的广义表是：n); Traverse_GL(L,visit); break; case 11: Traverse_GL(L,visit

14、); break; case 12: return; default: printf(nInput ERROR!n); getchar(); /switchwhile(1);6思考与小结通过本次广义表的设计性实验，加深了我对广义表的存储结构和基本抽象数据类型的实现的理解。由于广义表的操作涉与不少循环和递归的算法，所以本次实验后，我对递归算法的调用有了进一步的了解。广义表的存储结构也是挺有意思的，很多情况下它的表头也是一个广义表，表尾也是一个广义表。这就决定了用递归算法去实现它会是的算法更加的简洁。同时，它的结构也和二叉树有很大的相似性，所以，广义表的抽象数据类型的实现会对数的结构的学习也有一定的帮助。本次实验的难点主要是CreatGList函数。由于广义表是由字符串创建的，所以，会涉与一些串的操作，本次实验尽量避开了串的操作，所以部分函数实现起来困难会增加。难点就在于要判断什么时候该创建表头，什么时候该创建表尾，以与什么时候完毕。由于设计时用了递归的技巧，所以程序的每一行都要非常注意，失之毫厘差之千里，在设计函数过程中一个个的错误让我体会到程序设计的严谨性。