广义表实验报告.docx
《广义表实验报告.docx》由会员分享，可在线阅读，更多相关《广义表实验报告.docx（17页珍藏版）》请在冰点文库上搜索。
广义表实验报告
数据结构实验报告
题目：
广义表抽象数据类型的实现
学院计算机学院
专业计算机科学与技术
年级班别2010级7班
学号
学生
指导教师
成绩____________________
2012年6月
1.题目
实现广义表抽象数据类型GList
ADTGList{
数据对象：
D＝{ei|i=1,2,...,n;n≥0;ei∈AtomSet或ei∈GList，AtomSet为某个数据对象}
数据关系：
R1＝{|ei-1,ei∈D,2<=i<=n}
基本操作：
InitGlist（&L）;
操作结果:
创建空的广义表L
CreateGList（&L,S）;
初始条件:
S是广义表的书写形式串
操作结果:
由S创建广义表L
DestroyGlist（&L）;
初始条件:
广义表L存在
操作结果:
销毁广义表L
CopyGlist（&T,L）;
初始条件:
广义表L存在
操作结果:
由广义表L复制得到广义表T
GListLength（L）;
初始条件:
广义表L存在
操作结果:
求广义表L的长度,即元素个数
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，用函数Visit处理每个元素
}ADTGList
2．存储结构定义
由于广义表中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个节点表示。
由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：
一种是表结点，用以表示列表；一种是原子结点，用以表示原子。
一个表结点可以由3个域组成：
标志域，指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：
标志域和值域。
其形式定义说明如下：
-------广义表的扩展线性链表存储表示------
typedefenum{ATOM,LIST}ElemTag;//ATOM==0:
原子,LIST==1:
子表
typedefstructGLNode{
ElemTagtag;//公共部分,用于区分原子结点和表结点
union{//原子结点和表结点的联合部分
AtomTypeatom;//atom是原子结点的值域AtomType由用户定义
struct{structGLNode*hp,*tp;}ptr;
//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
};
}*GList；//广义表类型
voidvisit（GListL）{//visit函数
printf（"%c",L->atom）;
}
voidGetGList（chars[]）
{//接收建表元素--书写形式串的函数
inti;
printf（"\nInputGListtocreat:
\n"）;
for（i=0;i<50;i++）
{
scanf（"%c",&s[i]）;
if（s[i]=='\n'）
break;
}
}
3.算法设计
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）//复制广义表
{
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;
else
CopyGList（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创建广义表\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"）;
printf（"11遍历广义表\n"）;
printf（"12退出程序\n"）;
printf（"------------------------------------\n"）;
printf（"请输入你想进行的操作项的序号：
\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复制所得的表是：
"）;
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．思考与小结
通过本次广义表的设计性实验，加深了我对广义表的存储结构和基本抽象数据类型的实现的理解。
由于广义表的操作涉与不少循环和递归的算法，所以本次实验后，我对递归算法的调用有了进一步的了解。
广义表的存储结构也是挺有意思的，很多情况下它的表头也是一个广义表，表尾也是一个广义表。
这就决定了用递归算法去实现它会是的算法更加的简洁。
同时，它的结构也和二叉树有很大的相似性，所以，广义表的抽象数据类型的实现会对数的结构的学习也有一定的帮助。
本次实验的难点主要是CreatGList函数。
由于广义表是由字符串创建的，所以，会涉与一些串的操作，本次实验尽量避开了串的操作，所以部分函数实现起来困难会增加。
难点就在于要判断什么时候该创建表头，什么时候该创建表尾，以与什么时候完毕。
由于设计时用了递归的技巧，所以程序的每一行都要非常注意，失之毫厘差之千里，在设计函数过程中一个个的错误让我体会到程序设计的严谨性。
升级会员 