数据结构课程试验报告15

1、课程实验报告课程名称：数据结构专业班级：信安 13021302学号：姓名：指导教师：报告日期：2021.5.2021.5.1212计算机科学与技术学院2 2 实验一基于顺序结构的线性表实现3 3 实验二基于链式结构的线性表实现4 4 实验三基于二叉链表的二叉树实现1课程实验概述这门课是为了让学生了解和熟练应用 C C 语言进行编程和对数据结构进一步深入了解的延续.首先,课程实验是培养为了我们学生的动手水平而开设的,我们都知道的是实验是最能检验一个学会还是没有学会知识的一种最为1 1 课程实验概述.错误!未定义书签.2.12.1 问题描述错误!未定义书签.2.22.2 系统设计错误!未定义书签.

2、2.32.3 系统实现错误!未定义书签.2.42.4 效率分析错误!未定义书签.3.13.1 问题描述错误!未定义书签.3.23.2 系统设计错误!未定义书签.3.33.3 系统实现错误!未定义书签.3.43.4 效率分析错误!未定义书签.4.14.1 问题描述错误!未定义书签.4.24.2 系统设计错误!未定义书签.4.34.3 系统实现错误!未定义书签.4.44.4 效率分析错误!未定义书签.5 5 实验总结与评价错误!未定义书签.有效地方式.关于本次实验的所需要的知识,就是所学的 C C 语言的知识,特别是 C C 语言的实际操作的水平.本次实验以数据链表的各种操作为基础,考察我们的综合

3、应用的水平,是对我们以前学习的一次很好的检测.还有就是根据数据结构这门课程的性质和它的教学的人物要求,让学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构储存结构及其相应的算法,并初步掌握算法的时间分析和空间分析.而与数据结构相配套的这三次的实验恰恰是为了让我们学生用实际的操作来验证树上所学到的数据结构的相应的方法.2实验一基于顺序结构的线性表实现2.12.1问题描述基于顺序存储结构,实现线性表的根本的、常见的运算,用线性和链性的方式对数据进行各种必要的操作.2.22.2系统设计,分别是：printf(MenuforLinearTableOnSequenceSt

4、ructuren);printf(n);printf(1.IntiaList7.LocateElemn);printf(2.DestroyList8.PriorElemn);printf(3.ClearList9.NextElemn);printf(4.ListEmpty10.ListInsertn);printf(5.ListLength11.ListDeleten);printf(6.GetElem12.ListTrabversen);printf(0.Exitn);printf(n);printf(请选择你的操作012:);,数据元素为包含一个整型变量的结构体：typedefstruct

5、intitem;Elemtype;,用于存储该表的根本信息和首结点地址：typedefstructElemtype*elem;intlength,status,Increment;intlistsize;SqList;intmain()SqListL;# defineTRUE1# defineFALSE0# defineOK1# defineERROR0# defineINFEASTABLE-1# defineOVERFLOW-2# defineLIST_INIT_SIZE100#defineLISTINCREMENT102.32.3系统实现2.3.1IntiaList 功能初始化线性表,传入

6、的是头结点地址.申请一个大小为LIST_INT_SIZE、类型为Elemtype的线性存储空间,并用头结点中的首结点指针指向该空间首地址2.3.2DestroyList功能销毁头结点中首结点址针指向的线性存储空间,传入的是头结点地址.2.3.3ClearList功能与Destroy类似但是又有不同,ClearList并不销毁物理空间,而是修改逻辑关系值：2.3.4ListEmpty功能判空功能,判断表是否为空表.传入的是头结点值,而非地址,由于不需要对头结点进行修改.2.3.5ListLength功能求表长的长度的功能,由于创立过程中已经把表长信息包含在头结点中,所以直接调用并显示即可：2.3

7、.6GetElem功能获取第i号元素,传入的是头结点值、元素编号i、以及出口表结点地址.2.3.7LocatElem功能获取指定元素编号,传入头结点值、存储了所需元素信息的一个临时表结点值compare函数地址.采用顺序比拟法从表头遍历并比拟,一旦找到,返回编号io时间复杂度为(1n)n/2/n,O(n).2.3.8PriorElem功能求指定元素的前一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址.主要思路是先调用LocatElem确定指定元素的位置,如果不是首结点那么可直接取到PriorElem的地址.时间复杂度为O(n).2.3.9NextEl

8、em功能与PriorElem功能类似,求指定元素的后一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址.主要思路是先调用LocatElem确定指定元素的位置,如果不是尾接点那么可直接取到NextElem的地址.时间复杂度为O(n).ListInsertt功能插入一个数据元素,传入头结点地址、插入位置i、临时表结点值.在调用插入函数前构造一个临时表结点,用于存储数据元素信息.进入插入子函数,插入前先判断插入位置是否合理,再判断是否“满载.如果满载那么重新申请更大的存储空间.接下来正式插入数据元素,“先空位置再插入.平均时间复杂度ListDelete功能删

9、除指定编号的数据元素,传入头结点地址、编号i、表结点类型结构体地址来返回被删除元素内容.执行前先判断传入的编号是否在可寻找范围内.执行删除操作之后,进行“移位运算.时间复杂度仍为O(n).ListTraverse功能顺序遍历顺序表元素,传入头结点值、visit函数地址.时间复杂度为O(n)compare与visit函数statuscompare(Elemtypec1,Elemtypec2)/*c1 等于 c2*/if(c1.item=c2.item)returnTRUE;elsereturnFALSE;statusvisit(Elemtypee)printf(%d,e);returnTRUE;

10、1.4效率分析在上面介绍各功能时已经提到时间复杂度的计算了,这里再简单分析一下.具有同数量级复杂度的功能在实现方法上一般近似.而LocatElem、PriorElem、NextElem是基于LocatElem,平均效率为O(n);由于在头结点结构体中已经包含了ListEmpty、ListLength所需信息,所以效率为O(1)；ListInsert、ListDelete都要对顺序表进行“移位运算,平均效率为O(n).3实验二基于链式结构的线性表实现2.1问题描述基于链式存储结构,实现线性表的根本的、常见的运算.2.2系统设计,数据元素包含一个整型变量以及自身类型的指针typedefstruct

11、LNodeElemTypedata;structLNode*next;为n(n1)/2/nO(n),n即listlength.LNode,*LinkList;# defineTRUE1# defineFALSE0# defineOK1# defineERROR0# defineINFEASTABLE-1# defineOVERFLOW-22.3系统实现2.3.1IntiaList由于链表的创立是动态的,因此初始化不需要创立一个巨大的存储空间,这样可以节约很多内存空间.2.3.2DestroyList需要遍历链表,同时释放掉每个元素.2.3.3ClearList由于链表不同于数序表,这里不仅要在

12、逻辑上清空,还要在物理结构上清空,实现上与Destroy类似,即在改变相应的对应的关系后还要销毁相应的元素.2.3.4ListEmpty判空操作,L.elem不为NULL即不空.2.3.5ListLength求表长,由于在插入元素的同时已经记录了表长信息,所以只要读取L.length即可.2.3.6GetElem取第i号元素并用一个数据元素类型结构体指针传出其信息.2.3.7LocatElem基于遍历链表实现定位.2.3.8PriorElem基于遍历找到指定元素的前一个元素.和线性链表中的直接前基类似.2.3.9NextElem与PriorElem思路同,基于遍历找到指定元素的后一个元素.Li

13、stInsert插入一个新元素,即根据要求在相应的位置插入按要求要插入的元素.ListDelete删除第i号元素,即根据要求在相应的位置删除按要求要删除的元素.ListTraverse顺序遍历链表.compare与visit函数statuscompare(ElemTypec1,ElemTypec2)/*c侍于c2*/if(c1=c2)returnTRUE;elsereturnFALSE;statusvisit(ElemTypee)printf(%d,e);returnTRUE;2.4效率分析同样地,分类分析各功能效率.很多功能都基于遍历：DestroyList、Clearlist、ListTr

14、averse,效率为O(n);GetElem、LocatElem、PriorElem、NextElem、Listinsert、ListDelete,平均效率也为O(n).4实验三基于二叉链表的二叉树实现3.1问题描述二叉树的定义；二叉树的根本操作,如建立、前序遍历、中序遍历和后序遍历、结点个数的统计等;3.2系统设计,分别是：printf(Menun);printf(n);printf(1.InitBitree7.Rootn);printf(2.DestroyBitree8.Valuen);printf(3.CreateBitree9.Assignn);printf(4.ClearBitree

15、10.Parentn);printf(5.BitreeEmpty11.LeftChildn);printf(6.BitreeDepth12.RightChildn);printf(13.InsertChild14.DeleteChildn);printf(15.PreOrderTraverse16.InOrderTraversen);printf(17.PostOrderTraverse18.LevelOrderTraversen);printf(19.LeftSibling20.RightSiblingn);printf(0.Exitn);printf(n);printf(请选择你的操作,树

16、结点类型为结构体：typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;3.3系统实现3.3.1InitBitree构造空二叉树3.3.2 DestroyBitree初始条件：二叉树T已存在.结果：销毁二叉树T基于递归先序遍历创立二叉树,比方二叉树：初始条件：二叉树T存在.操作结果：假设T为空二叉树,那么返回TRUE,否那么返回FALSE.递归思想,“当前二叉树树高度=左子树高度与右子树高度最大值+13.3.7Root初始条件：二叉树T存在.操作结果：返回T的根.初始条件：二叉

17、树T存在,e是T中某个结点.操作结果：返回e的值.初始条件：二叉树T存在,e是T中某个结点.操作结果：结点e赋值为value.Parent初始条件：二叉树T存在,e是T中某个结点.操作结果：假设e是T的非根结点,那么返回它的双亲,否那么返回“空.LeftChild初始条件：二叉树T存在,e是T中某个结点.操作结果：返回e的左孩子.假设e无左孩子,那么返回空.初始条件：二叉树T存在,e是T中某个结点.操作结果：返回e的右孩子.假设e无右孩子,那么返回“空.InsertChild初始条件：二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空.操作结果：根据LR为0或1

18、,插入c为T中p所指结点的左或右子树.p所指结点的原有左或右子树那么成为c的右子树.DeleteChild初始条件：二叉树T存在,p指向T中某个结点,LR为0或1.操作结果：根据LR为0或1,删除T中p所指结点的左或右子树.PreOrderTraverse利用递归的特点,每次访问完根节点后,分别把其左儿子和右儿子设为根节点,递归调用,如果为空那么不访问.InOrderTraverse递归中序遍历思路与递归先序相同.非递归中序中序遍历二叉树T的非递归算法利用栈,对每个数据元素调用函数VisitEF#回车初始条件： 二叉树T存在操作结果：将二叉树T清为空树.PostOrderTraverse思路与

19、递归先序相同.LevelOrderTraverse层序递归遍历T利用队列,对每个结点调用函数Visit一次且仅一次LeftSibling初始条件：二叉树T存在,e是T中某个结点.操作结果：返回e的左兄弟.假设e是T的左孩子或无左兄弟,那么返回空.RightSibling初始条件：二叉树T存在,e是T中某个结点.操作结果：返回e的右兄弟.假设e是T的右孩子或无右兄弟,那么返回空.3.4效率分析建立二叉树由于是基于递归先序遍历建立二叉树,所以效率为O(n).Traverse对于递归实现的三种遍历、非递归实现的先序和中序遍历以及队列法实现的层遍历,由于每个元素被访问到且仅访问一次,且不要进行其他额外

20、大型运算,所以效率为O(n).求深度也是基于遍历,所以也是O(n).5实验总结与评价在完成三个实验的过程中,由于水平问题,存在很多BUG,特别是第三个“基于二叉链表的二叉树实现,再查阅了不少资料,请教了牛人之后,总算完成了实验.对于前两个线性表的实验,功能都实现了,根本要求都满足了在第三个实验中,虽然很多心思花在考虑如何实现非递归三种遍历和层遍历上,但大局部仍是用递归完成,不过,它们的效率好似都相近.在实现非递归算法时,由于各种困难,有时候都郁闷到想放弃的地步,不过后来在思考之后似乎又明白了什么,所以才继续走了下去,最后顺利实现了局部非递归后序遍历.虽然这些东西很小,价值不大,但是实现了它们却

21、总能带来一丝丝成就感,我想这也是收获之一吧.在整个实验中,最大的收获就是对C有了更熟练的掌握,尤其是指针.其次,就是对数据结构有了更系统的理解,对逻辑结构和物理结构的关系更有体会.虽然还有很多缺乏之处,但通过此次实验,我确实得到了进步,获益匪浅.附录：实验一代码：#include#include#include#include/*typedefintstatus;typedefstructintitem;Elemtype;# defineTRUE1*/# defineFALSE0# defineOK1# defineERROR0# defineINFEASTABLE-1# defineOVER

22、FLOW-2# defineLIST_INIT_SIZE100# defineLISTINCREMENT10typedefstructElemtype*elem;intlength,status,Increment;intlistsize;SqList;/*/statusIntiaList(SqList*L);statusDestroyList(SqList*L);statusClearList(SqListL);statusListEmpty(SqListL);intListLength(SqListL);statusGetElem(SqListL,inti,Elemtype*e);stat

23、usLocatElem(SqListL,Elemtypee,status(*compare)(Elemtype,Elemtype);statusPriorElem(SqListL,Elemtypecur_e,Elemtype&pre_e);statusNextElem(SqListL,Elemtypecur_e,Elemtype&next_e);statusListInsert(SqList&L,inti,Elemtypee);statusListDelete(SqList*L,inti,Elemtype*e);statusListTrabverse(SqListL,s

24、tatus(*visit)(Elemtypee);/*/statusvisit(Elemtypee);statuscompare(Elemtypec1,Elemtypec2);/*/voidmenu(void);/*intmain()SqListL;intop=0,i,Increment,el;L.elem=NULL;Elemtypee,pre_e,cur_e,next_e;do*/system(cls);menu();printf(Pleaseinputyouroption0-12:);scanf(%d,&op);switch(op)case0:break;case1:if(Inti

25、aList(&L)=OK)printf(线性表创立成功！n);elseprintf(线性表创立失败！n);getchar();getchar();break;case2:if(!L.elem)printf(n表不存在n);elseDestroyList(&L);printf(n销毁成功n);getchar();getchar();break;case 3: if(!L.elem)printf(n线性表不存在n);elseClearList(L);printf(n线性表已置空n);getchar();getchar();break;case 4: if(!L.elem)print

26、f(n线性表不存在n);elseel=ListEmpty(L);if(el)printf(表为空n);elseprintf(表不为空n);getchar();getchar();break;case 5: if(!L.elem)printf(n线性表不存在n);elseprintf(n元素个数为%dn,ListLength(L);getchar();getchar();break;case6:if(!L.elem)printf(n线性表不存在n);elseprintf(请输入数据位置n);scanf(%d,&i);el=GetElem(L,i,&e);if(el!=ERROR)

27、printf(n第%d个数据元素为%dn,i,e);elseprintf(查找失败n);getchar();getchar();break;case7:if(!L.elem)printf(n线性表不存在n);elseprintf(请输入要查找的数据n);scanf(%d,&e);el=LocatElem(L,e,compare);if(el)printf(n%d第一次出现的位置为%dn,e,el);elseprintf(n未找到n);getchar();getchar();break;case8:if(!L.elem)printf(n线性表不存在n);elseprintf(输入要查找前

28、驱的数据n);scanf(%d,&cur_e);el=PriorElem(L,cur_e,pre_e);if(el)printf(n该数据的前驱为%dn,el);elseprintf(该数据不存在前驱n);getchar();getchar();break;case 9: if(!L.elem)printf(n线性表不存在n);elseprintf(输入要查找后继的数据n);scanf(%d,&cur_e);el=NextElem(L,cur_e,next_e);if(el)printf(该数据的后继为%dn,el);elseprintf(n该数据不存在后继n);getchar

29、();getchar();break;case 10: if(!L.elem)printf(n线性表不存在n);elseprintf(n输入要插入的位置及数据n);scanf(%d%d,&i,&e);el=ListInsert(L,i,e);if(el=OK)printf(n插入成功n);elseif(el=ERROR)printf(n错误n);elseif(el=OVERFLOW)printf(n溢出n);getchar();getchar();break;case 11: if(!L.elem)printf(n线性表不存在n);elseprintf(n输入要删除的数据的位置

30、n);scanf(%d,&i);el=ListDelete(&L,i,&e);if(el=ERROR)printf(n错误n);elseprintf(删除的数据为%dn,e);getchar();getchar();break;case 12:if(!ListTrabverse(L,visit)printf(空表n);getchar();getchar();break;while(op);printf(nWelcomeagain!n);getchar();getchar();return0;statusIntiaList(SqList*L)L-elem=(Elemtyp

31、e*)malloc(LIST_INIT_SIZE*sizeof(Elemtype);if(!L-elem)exit(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;returnOK;statusDestroyList(SqList*L)if(L-elem)free(L-elem);L-elem=NULL;returnOK;statusClearList(SqListL)L.length=0;returnOK;statusListEmpty(SqListL)if(L.length=0)returnTRUE;elsereturnFALSE;intLis

32、tLength(SqListL)returnL.length;statusGetElem(SqListL,inti,Elemtype*e)if(iL.length|i1)returnERROR;*e=*(L.elem+i-1);returnOK;statusLocatElem(SqListL,Elemtypee,statuscompare)(Elemtype,Elemtype)inti=1;Elemtype*p=L.elem;while(iL.length&!compare(e,*p+)i+;if(i=L.length)returni;elsereturn0;statusPriorEl

33、em(SqListL,Elemtypecur_e,Elemtype&pre_e)/返回一个不是首元素的前驱inti=2;if(cur_e.item=(L.elem0).item)returnERROR;while(i=L.length&(L.elemi-1.item!=cur_e.item)i+;if(i=L.length+1)returnERROR;elsepre_e=L.elemi-2;returnOK;/PriorElemstatusNextElem(SqListL,Elemtypecur_e,Elemtype&next_e)/返回一个不是末元素的后继inti=1

34、;while(iL.length&(L.elemi-1.item!=cur_e.item)i+;if(i=L.length)returnERROR;elsenext_e=L.elemi;returnOK;(*printf(nallelementsoflieartablen);for(i=0;iL.length;i+)visit(L.elemi);return(1);/*/voidmenu(void)printf(nn);printf(printf(printf(printf(MenuforLinearTableOnSequenceStructuren);1.IntiaList2.Des

35、troyListn);7. LocatElemn);8. PriorElemn)/NextElemstatusListInsert(SqList&L,inti,Elemtypee)/在第i个元素前插入一个新的元素if(i+L.length)returnERROR;if(L.length=L.listsize)newbase=(Elemtype*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(Elemtype);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=LIST_I

36、NIT_SIZE+LISTINCREMENT;/勿忘for(intj=L.length;j=i;-j)/此处要注意L.elemj=L.elemj-1;L.elemi-1=e;returnOK;/ListInsertstatusListDelete(SqList*L,inti,Elemtype*e)Elemtype*p;Elemtype*q;if(i(*L).length+1)returnERROR;p=(*L).elem+i-1;q=(*L).elem+(*L).length-1;*e=*p;/*元素依次向前移*/while(pq)*p=*(p+1);p+;(*L).length-;retur

37、nOK;statusListTrabverse(SqListL,status(*visit)(Elemtypee)inti;if(!L.length)return(0);Elemtypeprintf(3.ClearList9.NextElemn);printf(4.ListEmpty10.ListInsertn);printf(5.ListLength11.ListDeleten);printf(6.GetElem12.ListTrabversen);printf(0.Exitn);printf(n);/*statuscompare(Elemtypec1,Elemtypec2)/*c1等于c2

38、*/if(c1.item=c2.item)returnTRUE;elsereturnFALSE;statusvisit(Elemtypee)printf(%d,e);returnTRUE;附录：实验二代码：#include#include#include#defineTRUE1#defineFALSE0# defineOK1# defineERROR0# defineINFEASTABLE-1# defineOVERFLOW-2typedefintstatus;typedefintElemType;/数据元素类型定义typedefstructLNodeElemTypedata;structLN

39、ode*next;LNode,*LinkList;statusIntiaList(LinkList&L);statusDestroyList(LinkList&L);statusClearList(LinkListL);statusListEmpty(LinkListL);intListLength(LinkListL);statusGetElem(LinkListL,inti,ElemType&e);statusLocateElem(LinkListL,ElemTypee,status(*compare)(ElemType,ElemType);statusPriorE

40、lem(LinkListL,ElemTypecur,ElemType&pre_e);statusNextElem(LinkListL,ElemTypecur,ElemType&next_e);statusListInsert(LinkListL,inti,ElemTypee);*/statusListDelete(LinkListL,inti,ElemType&e);statusListTrabverse(LinkListL,status(*visit)(ElemType);statuscompare(ElemTypec1,ElemTypec2);statusvisit

41、(ElemTypee);/*intmain()LinkListL;intop=1,i,e,el,cur_e,pre_e,next_e;L=NULL;while(op)system(cls);printf(nn);printf(MenuforLinearTableOnSequenceStructuren);printf(n);printf(1.IntiaList7.LocateElemn);printf(2.DestroyList8.PriorElemn);printf(3.ClearList9.NextElemn);printf(4.ListEmpty10.ListInsertn);print

42、f(5.ListLength11.ListDeleten);printf(6.GetElem12.ListTrabversen);printf(0.Exitn);printf(n);printf(请选择你的操作012:);scanf(%d,&op);switch(op)case 1:if(IntiaList(L)=OK)printf(线性表创立成功n);elseprintf(线性表创立失败n);getchar();getchar();break;case 2:if(L=NULL)printf(n表不存在,请初始化n);elseDestroyList(L);printf(n销毁成功n);

43、getchar();getchar();break;case 3:if(L=NULL)printf(n表不存在,请初始化n);elseClearList(L);printf(n去除成功n);getchar();getchar();break;*/case 4:if(L=NULL)printf(n表不存在,请初始化n);elseel=ListEmpty(L);if(el)printf(表为空n);elseprintf(表不为空n);getchar();getchar();break;case 5:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(n元素个数为%dn

44、,ListLength(L);getchar();getchar();break;case 6:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(请输入数据位置n);scanf(%d,&i);el=GetElem(L,i,e);if(el!=ERROR)printf(n第%d个数据元素为%dn,i,e);elseprintf(overflown);getchar();getchar();break;case 7:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(请输入要查找的数据n);scanf(%d,&e);el

45、=LocateElem(L,e,compare);if(el)printf(n%d首次出现的位置为%dn,e,el);elseprintf(n未找到n);getchar();getchar();break;case 8:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(请输入要查找前驱的数据n);scanf(%d,&cur_e);el=PriorElem(L,cur_e,pre_e);if(el)printf(n该数据的前驱为%dn,pre_e);elseprintf(该数据不存在前驱n);getchar();getchar();break;case 9

46、:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(请输入要查找后继的数据n);scanf(%d,&cur_e);el=NextElem(L,cur_e,next_e);if(el)printf(该数据的后继为%dn,next_e);elseprintf(n该数据不存在后继n);getchar();getchar();break;case 10:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(n请输入要插入的位置及数据n);scanf(%d%d,&i,&e);el=ListInsert(L,i,e);if

47、(el=OK)printf(n插入成功n);elseif(el=ERROR)printf(n错误n);elseif(el=OVERFLOW)printf(n溢出n);getchar();getchar();break;case 11:if(L=NULL)printf(n表不存在,请初始化n);elseprintf(n输入要删除的数据的位置n);scanf(%d,&i);el=ListDelete(L,i,e);if(el=ERROR)printf(n错误n);elseprintf(删除的数据为:%dn,e);getchar();getchar();break;case 12:if(L=NULL)printf(n表不存在,请初始化n);elseif(!ListT